COMPUTATION HARDWARE WITH HIGH-BANDWIDTH MEMORY INTERFACE

• US 20150067273A1
• Filed: 08/30/2013
• Published: 03/05/2015
• Est. Priority Date: 08/30/2013
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Strauss, Karin, Fowers, Jeremy
• Application Number:
  US14/015,872
• Publication Number:
  US 20150067273A1
• Time in Patent Office: Days
• US Class Current: 711/147
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Various embodiments relating to performing multiple computations are provided. In one embodiment, a computing system includes an off-chip storage device configured to store a plurality of stream elements and associated tags and a computation device. The computation device includes an on-chip storage device configured to store a plurality of independently addressable resident elements, and a plurality of parallel processing units. Each parallel processing unit may be configured to receive one or more stream elements and associated tags from the off-chip storage device and select one or more resident elements from a subset of resident elements driven in parallel from the on-chip storage device. A selected resident element may be indicated by an associated tag as matching a stream element. Each parallel processing unit may be configured to perform one or more computations using the one or more stream elements and the one or more selected resident elements.

Claims

1. A computing system comprising:

an off-chip storage device configured to store a plurality of stream elements and associated tags; and

a computation device in communication with the off-chip storage device, the computation device including;

an on-chip storage device configured to store a plurality of independently addressable resident elements; and

a plurality of parallel processing units, each parallel processing unit being configured to;

receive one or more stream elements and associated tags from the off-chip storage device;

select one or more resident elements from a subset of resident elements driven in parallel from the on-chip storage device, wherein a selected resident element is indicated by an associated tag as matching a stream element; and

perform one or more computations using the one or more stream elements and the one or more selected resident elements.

2. The computing system of claim 1, wherein multiple parallel processing units of the plurality of parallel processing units select a same resident element from the subset of resident elements in a same clock cycle.

3. The computing system of claim 1, wherein the computation device further includes a stream manager configured to receive a plurality of parallel data streams from the off-chip storage device, parse each of the plurality of parallel data streams into stream elements and associated tags, and send the stream elements and associated tags of each data stream to a different parallel processing unit, wherein all stream elements and associated tags of a data stream are processed by a single parallel processing unit.

4. The computing system of claim 1, wherein the computation device further includes a priority selector configured to receive requests from the plurality of parallel processing units, the requests including tags that indicate resident elements that match stream elements received by the plurality of parallel processing units, and drive the subset of resident elements that match the stream elements from the on-chip storage device to the plurality of parallel processing units.

5. The computing system of claim 1, wherein the on-chip storage device includes a resident element data buffer configured to store the plurality of resident elements in independently addressable banks.

6. The computing system of claim 1, wherein each parallel processing unit includes:

a stream element queue configured to store the one or more stream elements;

a stream tag queue configured to store the associated tags;

a resident element selector array including a plurality of resident element selector units, each resident element selector unit configured to compare addresses of the subset of resident elements selected by a priority selector to the address of a requested resident element indicated by an associated tag and if the requested resident element matches one of the resident elements of the subset, output an indication of the match;

a queue insertion controller configured to insert the one or more selected resident elements in a resident element queue based on receiving an indication of a match from the resident element selector array; and

a functional unit configured to receive a stream element from the stream element queue and a selected resident element from the resident element queue that matches the stream element, and perform a computation using the stream element and the selected resident element.

7. The computing system of claim 1, wherein the off-chip storage device includes dynamic random-access memory.

8. The computing system of claim 1, wherein the computation device is one of a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or a system-on-chip (SoC).

9. The computing system of claim 1, wherein the plurality of stream elements include values of a sparse matrix, wherein each parallel processing unit receives values of a different row of the sparse matrix, the plurality of resident elements includes values of a vector to be multiplied with each row of the sparse matrix, and wherein the computations are part of a sparse matrix-vector multiplication for a row of the sparse matrix.

10. A computing system comprising:

an off-chip storage device configured to store a plurality of stream elements and associated tags; and

a computation device in communication with the off-chip storage device, the computation device including;

an on-chip storage device configured to store a plurality of independently addressable resident elements;

a stream manager configured to;

receive a plurality of parallel data streams from the off-chip storage device;

parse each of the plurality of parallel data streams into stream elements and associated tags; and

send the stream elements and associated tags of each data stream to a different parallel processing unit of a plurality of parallel processing units, wherein all stream elements of a data stream are processed by a single parallel processing unit; and

each parallel processing unit of the plurality of parallel processing units being configured to;

receive stream elements and associated tags of a data stream from the stream manager;

send requests to a priority selector for selected resident elements indicated by the associated tags, wherein the priority selector is configured to aggregate requests received from the plurality of parallel processing units to form a subset of resident elements and drive the subset of resident elements from the on-chip storage device to each of the plurality of parallel processing units;

select the resident elements from the subset of resident elements driven from the on-chip storage device; and

perform computations using the stream elements and the selected resident elements.

11. The computing system of claim 10, wherein multiple parallel processing units of the plurality of parallel processing units select a same resident element from the subset of resident elements in a same clock cycle.

12. The computing system of claim 10, wherein the on-chip storage device includes a resident element data buffer configured to store the plurality of resident elements in independently addressable banks.

13. The computing system of claim 10, wherein each parallel processing unit includes:

a stream element queue configured to store the one or more stream elements;

a stream tag queue configured to store the associated tags;

a resident element selector array including a plurality of resident element selector units, each resident element selector unit configured to compare addresses of the subset of resident elements selected by a priority selector to the address of a requested resident element indicated by an associated tag and if the requested resident element matches one of the resident elements of the subset, output an indication of the match;

a queue insertion controller configured to insert the one or more selected resident elements in a resident element queue based on receiving indications of matches from the resident element selector array; and

a functional unit configured to receive a stream element from the stream element queue and a selected resident element from the resident element queue that matches the stream element, and perform a computation using the stream element and the selected resident element.

14. The computing system of claim 10, wherein the off-chip storage device includes dynamic random-access memory.

15. The computing system of claim 10, wherein the computation device is one of a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or a system-on-chip (SoC).

16. The computing system of claim 10, wherein the plurality of stream elements include values of a sparse matrix, wherein each parallel processing unit receives values of a different row of the sparse matrix and processes all row values for that row, the plurality of resident elements includes values of a vector to be multiplied with each row of the sparse matrix, and wherein the computations are part of a sparse matrix-vector multiplication for a row of the sparse matrix.

17. A method for performing computations with a plurality of parallel processing units of a computation device, the method comprising:

at each parallel processing unit, receiving one or more stream elements and associated tags from an off-chip storage device;

selecting one or more resident elements from a subset of independently addressable resident elements driven in parallel from an on-chip storage device, wherein a selected resident element is indicated by an associated tag as matching a stream element; and

performing one or more computations using the one or more stream elements and the one or more selected resident elements.

18. The method of claim 17, further comprising:

receiving, at the computation device, a plurality of parallel data streams from the off-chip storage device;

parsing each of the plurality of parallel data streams into stream elements and associated tags; and

sending the stream elements and associated tags of each data stream to a different parallel processing unit, wherein all stream elements and associated tags of a data stream are processed by a single parallel processing unit.

19. The method of claim 17, further comprising:

receiving requests from the plurality of parallel processing units, wherein the requests include tags that indicate resident elements that match stream elements received by the plurality of parallel processing units; and

driving the subset of resident elements that match the stream elements from the on-chip storage device to the plurality of parallel processing units in parallel.

20. The method of claim 17, wherein the computation is a sparse matrix-vector multiplication, wherein the stream element includes a row value of a sparse matrix, wherein each parallel processing unit receives values of a different row of the sparse matrix, and wherein the selected resident element includes a value of a vector to be multiplied with the row value as part of the sparse matrix-vector multiplication.