Patent ID: 12236245

DETAILED DESCRIPTION

The described embodiments are embodied in methods, apparatuses and systems for a hardware architecture that supports SIMD (single input, multiple data) processing of an input tensor that includes a group load register, resulting in a output tensor.

FIG.1shows stages of graph streaming processing, according to an embodiment. The GSP architecture is designed for execution of acyclic data flow graphs in streaming manner, where, a graph is made of connected nodes, the arcs between the nodes of the graph indicate the dependency between them. Each node in the dataflow graph consists of a function that processes the data buffers produced by a previous node that is connected to it, and/or buffers stored in memory and produce data buffers for the following nodes to process. Each buffer is divided into blocks and processed in parallel by SIMD processor as a thread.FIG.1shows an acyclic graph with m levels, the nodes are numbered as Nxy where x is the level of the node in the graph and y is the number of the node in that level.

GSP consists of multiple processors arrays. A processor array can execute multiple threads in parallel on the SIMD processors available in it. The processor array also tracks the data availability of the instructions of the threads and dispatch the instructions to the SIMD processors for execution when the data is available. The processors array has interfaces to the memory subsystem to access the data and to the thread scheduler for receiving the threads.

In GSP, the thread scheduler is responsible for scheduling and management of all the threads running on the processor arrays. For an embodiment, the thread scheduler is organized as a pipeline of thread scheduling hardware units called stages. Each stage is responsible for scheduling threads for all the nodes at a certain depth in the acyclic graph. For the example shown in theFIG.1, stage-0 is responsible for dispatching threads of the nodes n-00, stage-1 schedules the threads for the node n-10 and node n-11 so on and so forth. The last stage of the pipeline is stage-N, where is N is fixed for a chip. The command buffer shown between two stages, is a buffer that consists of commands. Each command consists of thread index and pointer to an array of structures that holds pointers for the program kernel, and the input, output data buffers. Parent node can emit work as a multiple of child thread's work.

FIG.2shows multiple processor arrays of graph streaming processing, according to an embodiment. As shown, multiple processor arrays220,230,240,250each include a plurality of SIMD processors. For example, the processor array220includes SIMD processors222,224,226,228, the processor array230includes SIMD processors232,234,236,238, the processor array240includes SIMD processors242,244,246,248, and the processor array250includes SIMD processors252,254,256,258.

For an embodiment, a thread scheduler280of the Graph Steaming Processor is responsible for scheduling and management of all the threads running on the processor arrays220,230,240,250. For an embodiment, the scheduling and management include a group thread dispatch for the Graph Streaming Processor. For the group thread dispatch, for an embodiment, the thread scheduler280receives a group of threads of the Graph Streaming Processor, wherein the group of threads includes a plurality of threads which operate on a subset of inputs of an input tensor [I0-IN], wherein each of the plurality of threads operates on the subset of inputs of the input tensor and a weight tensor [W00-WNM] to generate an output tensor [O0-OM]. For an embodiment, the thread scheduler is configured to a calculate resource requirement for execution of the group of threads. Further, for an embodiment, the thread scheduler calculates a resource availability in a plurality of processors (for example, SIMD processors222,224,226,228) of each of a plurality of processor arrays220,230,240,250.

For an embodiment, the thread scheduler280is configured to dispatch the group of threads to a selected one of plurality of processors of processor arrays that has a resource availability that meets or exceeds the resource requirement for execution of the group of threads. For an embodiment, each thread of the group of threads is scheduled on a one processor of the selected plurality of processors and is processed independently on the one processor.

For an embodiment, the thread scheduler280is configured to schedule a group load instruction for all threads of the group of threads, comprising loading into a group load register a subset of inputs of the input tensor for processing of each thread of the group of threads, wherein the group load register provides the subset of the inputs of the input tensor to all of the plurality of processors of the selected processor array. For an embodiment, the processing of each thread of the group of threads comprises generating a subset of outputs of the output tensor for each thread of the plurality of threads based on a subset of weights of the weight tensor and the subset of inputs of the input tensor, which can be stored in a memory subsystem290.

Resource Requirements

For an embodiment, calculating resource requirement for execution of the group of threads comprises determining the number of threads in the group of threads and determining the number of registers required by each thread of the group of threads.

For an embodiment, calculating resource availability in a plurality of processors of each of a plurality of processor arrays includes determining the available thread slots and determining the number of available registers in each processor of the plurality of processors230of each of the plurality of processor arrays220.

FIG.3shows a thread scheduler305for an array of processor arrays340that includes counters310,312,314, according to an embodiment. For an embodiment, the thread scheduler305tracks the available thread slots and number of available registers in each processor of each processor array341,342,343of the array of processor arrays340. For an embodiment, when the scheduler305is to schedule a thread, the scheduler305identifies the processor(s) in each processor of each processor array341,342,343of the array of processor arrays340which have at least one available thread slot and available registers exceeding the number of registers needed by the thread (of the group of threads). For an embodiment, one of the identified processor(s) is selected (for example, using a round-robin selection process of the processors which satisfy the thread requirements). For an embodiment, when the thread is scheduled on the selected processor, an appropriate thread slot is marked as in use and the available registers in the processor are decremented by the number of registers used by the thread. As the thread completes, the appropriate thread slot is marked as available and the number of available registers in the processor is incremented by the number of registers used by the retiring thread. For an embodiment, the scheduler305includes counters310,312,314that maintain a count of available registers in each processor of corresponding processor arrays341,342,343. The number of available registers is decremented when starting a thread, and incremented when a thread is completed.

For an embodiment, when the scheduler305is scheduling a group of threads, the scheduler305identifies the processor array(s) (341,342,343) in the array of processor arrays340which have at least one available thread slot and available registers exceeding the number of registers needed by each thread of the group of threads in the processors of the processor array/s (341,342,343). One of identified processor array(s) (341,342,343) is picked (for example, using a round-robin selection process of the processor array(s) which satisfy the group of thread requirements). When the threads in the group of threads are scheduled on the processors of this processor array, the appropriate thread slots are marked as in use and the available registers in the processors of the processor array are decremented by the number of registers used by each thread of the group of threads. As the threads in the group of threads complete, the appropriate thread slots are marked as available and the available registers in the processors of the processor array are incremented by the number of registers used by each retiring thread of the group of threads. For an embodiment, the scheduler305includes counters310,312,314that maintain a count of available registers in each processor of corresponding processor arrays341,342,343. As previously stated, the number of available registers is decremented when starting a thread, and incremented when a thread is completed. For an embodiment, there is a counter (such as, counters310,312,314) for each processor of each processor array341,342,343. For an embodiment, determining the available thread slots and determining the number of available registers in each processor of the plurality of processors of each of the plurality of processor arrays includes decrementing, by a counter of the thread scheduler corresponding with the processor, the number of available registers when starting a thread, and incrementing, by the counter of the thread scheduler corresponding with the processor, the number of available when a thread is completed.

FIG.4is a flow chart of a method of executing a group load instruction, according to an embodiment. A step411includes starting a thread of a group of threads. A step412includes fetching instructions of the thread from memory. A step413includes reading the instructions for execution. A step414includes determining whether the instruction for execution is a group load instruction. If yes, all threads of the group of threads are synchronized when executing the group load instruction by step415which includes waiting for each thread of the group of threads to reach this instruction. A step416includes executing the instruction, wherein all threads of the group of threads are synchronized when executing the group load instruction. As described, for an embodiment, all threads of the group of threads are synchronized when executing the group load instruction due to the waiting for each thread of the group to reach group load instruction for execution.

If execution of step414includes determining that the instruction for execution is not a group load instruction, then the threads are processed independently on the processor. Accordingly, for an embodiment, threads of the group of threads are processed independently on the selected one of the plurality of processors when not executing the group load instruction. If an instruction is not a group instruction (414) then a determination (418) is made to determine whether the instruction includes is an end of program instruction. If no, then the instruction is executed416. If yes, then the thread ends419.

For an embodiment, each thread of the group of threads is scheduled on one processor of the selected one of the plurality of processors. After execution of an instruction416, it is determined417whether a next instruction is available.

As previously stated, for an embodiment, each thread of the group of threads is scheduled on a one processor of the selected plurality of processors and is processed independently on the one processor. For an embodiment, independently processing each thread of the group of threads on the one processor of the plurality of processors includes scheduling an instruction of one thread of the group of threads without relying on scheduling of an instruction of another thread of the group of threads.

For an embodiment, each thread includes an instance of a set of instructions running on a processor of the Graph Streaming Processor. For an embodiment, dispatching the group of threads to the plurality of processors of a one of the plurality of processor arrays comprising loading attributes of each thread of the group of threads to each of the available thread slots of a processor, wherein the attributes include a program pointer, pointer to the input tensor, pointer to the weight tensor, and pointer to the output tensor.

FIG.5shows SIMD (single input, multiple data) processing of an input tensor, resulting in an output tensor, according to an embodiment. The input510includes N−1 dimension of the N-dimensional input tensor Ijand the output530includes N−1 dimension of the N-dimensional output tensor Oi. For an embodiment, the 3D input tensor Ijis, for example, an array of 2D input images and the 3D output tensor Oiis, for example, an array of 2D output images. SIMD processing520performs operations on the input tensor Ijand generates the output tensor Oi.

For an embodiment, the SIMD processing520includes a SOMAC (Sum-Of-Multiply-Accumulate) instruction that performs, for example, a convolution of the subset of inputs of the input tensor Ijwith the subset of weights of a weight tensor Wji. The SOMAC operation is represented inFIG.1as Oi=ΣWji*Ij.

For an embodiment, the 3D output tensor Oi530generated by the SIMD processing also includes an array of 2D images.

FIG.6shows another representation of SIMD (single input, multiple data) processing of an input tensor, resulting in an output tensor, according to an embodiment. As shown, the SIMD processing includes generating an output O of the output tensor Oibased on all the inputs Ijof the input tensor I and corresponding weights of the weight tensor Wij.

FIG.7shows a hardware architecture of a processor array that provides SIMD (single input, multiple data) processing of an input tensor Ij, resulting in an output tensor Oi, according to an embodiment. The processor array ofFIG.7could be, for example, one of the processor arrays220,230,240,250of the multiple processor arrays of the GSP ofFIG.2.

As shown, data cache715(of the memory subsystem290) includes the input tensors Ij, and data cache716(of the memory subsystem290) includes the output tensor Oi. Further, the data cache (not shown) includes the weight tensor. While shown as separate cache715,716, for an embodiment, the cache715,716are the same or common cache of the memory subsystem290.

FIG.7shows only the first four inputs of the input tensor (I0, I1, I2, I3), but as described, there can be any number of Ijinputs. Further,FIG.7only shows four outputs of the output tensor (O0, O1, O2, O3), but as described, there can be any number of outputs Oi. Further, any number of weights of the weight tensor Wjimay be utilized.

As shown, the inputs (I0, I1, I2, I3) are each loaded input data registers720,721,722,723. Further, as shown, weights Wjiare loaded into weight registers730,731,732,733. Through the input data registers720,721,722,723and the weight registers730,731,732,733the inputs (I0, I1, I2, I3) and the weights Wjiare provided to a plurality (as shown, four) SIMD processors740,741,742,743which perform a SOMAC instruction on the inputs (I0, I1, I2, I3) and the weights Wjiyielding outputs (O0, O1, O2, O3) which are stored in output registers750,751,752,753.

As will be shown and described, for at least some embodiments, the SIMD processing of the SIMD processors740,741,742,743includes a dot-product-accumulate operation, or a convolve multiple and accumulate operation which can also be referred to as a Sum-Of-Multiply-Accumulate (SOMAC).

FIG.8shows a hardware architecture of a processor array810that provides SIMD (single input, multiple data) processing of an input tensor that includes a group load register820, resulting in an output tensor, according to an embodiment. The processor array810ofFIG.8could be, for example, one of the processor arrays220,230,240,250of the multiple processor array of the GSP ofFIG.2.

As can be observed inFIG.7, if the data registers720,721,722,723all have the same set of inputs (I0, I1, I2, I3) loaded into them, then as shown inFIG.8, a group load register820may be utilized, which reduces the number of registers used. Utilizing the group load register820over the data registers720,721,722,723enables improving the compute-to-bandwidth ratio and as a result reduces the amount of circuitry which reduces power consumption, space, and cost.

As shown inFIG.8, the hardware architecture provides a graph streaming processor that includes a data cache815,816. The data cache815is used for the inputs (I0, I1, I2, I3). The data cache816is used for outputs (O0, O1, O2, O3) generated by the graph streaming processing.

Further, the graph streaming processor includes a plurality of SIMD processors840,841,842,843.

For an embodiment, the group load register820operate to load a subset of inputs (I0, I1, I2, I3) of the input tensor Ij, wherein the group load register820provides the subset of inputs (I0, I1, I2, I3) of the input tensor to all of the plurality of processors840,841,842,843.

For an embodiment, a plurality of weight data registers830,831,832,833operate to load a subset of the weights of the weight tensor Wji, wherein each of the plurality of weight data registers830,831,832,833provides an input to a single of the plurality of processors840,841,842,843. For example, weights W00, W01, W02, W03may be loaded into weight register830which provides an input to the processor840. Weights W10, W11, W12, W13may be loaded into weight register831which provides an input to processor841. Weights W20, W21, W22, W23may be loaded into weight register832which provides an input to processor842. Finally, weights W30, W31, W32, W33may be loaded into weight register833which provides an input to processor843.

For at least some embodiments, the plurality of processors840,841,842,843operate to perform a SOMAC (Sum-Of-Multiply-Accumulate) instruction, including each of the plurality of processors840,841,842,843simultaneously operating to determine an instruction size of the SOMAC instruction, wherein the instruction size indicates a number of iterations that the SOMAC instruction is to be executed and is equal to a number of outputs within a subset (O0, O1, O2, O3) of the output tensor Oi. As will be described further, for an embodiment, the instruction size is determined by a macro-instruction iterator of the graph streaming processor, and further it is determined whether the instruction is a Sum-Of-Multiply-Accumulate (SOMAC) instruction.

For at least some embodiments, each of the plurality of processors840,841,842,843further simultaneously operate to read a first source operand of a plurality of source operands of the SOMAC instruction from the group load register file820, wherein the first source operand is one of the subset of inputs (I0, I1, I2, I3) of the input tensor. That is, the first source operand of the SOMAC instruction is one of the subset of inputs I0, I1, I2, or I3of the input tensor.

For at least some embodiments, each of the plurality of processors840,841,842,843further simultaneously operates to read a second source operand of the plurality of source operands of the SOMAC instruction from the weight register file wherein the second source operand is one of the subset of weights of the weight tensor. That is, the second source operand of the SOMAC instruction is one of the subset of weights of the weight tensor Wji.

For at least some embodiments, each of the plurality of processors840,841,842,843further simultaneously operate to execute multiply and accumulate operations of the SOMAC operation for the number of iterations.

For at least some embodiments, each of the plurality of processors840,841,842,843further operate to read a destination operand of the plurality of operands of the SOMAC instruction from one of an output registers850,851,852,853wherein the destination operand is one of the subset of the output tensor. Further, each of the plurality of processors840,841,842,843further operate to add a sum-of-multiply result to the destination operand, and write a multiply-accumulate result back to the destination operand, wherein the destination operand is a register from the output register file that is an output of the instruction. After this operation, the sum-of-multiply result will be different. If the result would not have been different, then the operation would have been pruned.

For at least some embodiments, a size (number of registers) of the group load register820is dependent on a number of inputs within the subset of the input tensor.

For at least some embodiments, a size (number of registers) of the group load register820is dependent on a number of threads concurrently running on the plurality of processors.

For at least some embodiments, a size (number of registers) of the output registers850,851,852,853is dependent on a number of outputs within the subset of the output tensor.

For at least some embodiments, a size (number of registers) of the output registers850,851,852,853is dependent on a number of threads concurrently running on the plurality of processors.

For at least some embodiments, a size (number of registers) of the weight registers830,831,832,833is dependent on a number of inputs within the subset of the input tensor.

For at least some embodiments, a size (number of registers) of the weight registers830,831,832,833is dependent on a number of outputs within the subset of the output tensor.

For at least some embodiments, a size (number of registers) of the weight registers830,831,832,833is dependent on a number of threads concurrently running on the plurality of processors.

FIG.9is a flow chart that includes steps of a method of graph streaming processing that includes a group load register, according to an embodiment. A first step910includes receiving, by a thread scheduler of the graph streaming processor, a group of threads, wherein the group of threads comprises a plurality of threads which operate on an input tensor, wherein each of the plurality of threads operates on the inputs of the input tensor and a subset of a weight tensor to generate a subset of an output tensor. A second step920includes calculating by the thread scheduler, a resource requirement for execution of the group of threads. A third step930includes calculating, by the thread scheduler, resource availability in a plurality of processors of each of a plurality of processor arrays. A fourth step940includes dispatching the group of threads to a selected one of the plurality of processors of the plurality of processor arrays that has a resource availability that meets or exceeds the resource requirement for execution of the group of threads. A fifth step950includes scheduling a group load instruction for all threads of the group of threads, comprising loading into a group load register a subset of inputs of the input tensor for processing of each thread of the group of threads, wherein the group load register provides the subset of the inputs of the input tensor to the group of threads of the selected one of the plurality of processors, wherein all threads of the group of threads are synchronized when executing the group load instruction, wherein all threads of the group of threads are processed independently on the selected one of the plurality of processors when not executing the group load instruction, and wherein the processing of each thread of the group of threads comprises generating a subset of outputs of the output tensor for each thread of the plurality of threads based on the subset of weights of the weight tensor and the inputs of the input tensor.

For an embodiment, each thread of the group of threads is scheduled on one processor of the selected one of the plurality of processors.

As previously described, for an embodiment, calculating resource requirement for execution of the group of threads includes determining the number of threads in the group of threads and determining the number of registers required by each thread of the group of threads. For an embodiment, calculating resource availability in a plurality of processors of each of a plurality of processor arrays includes determining the available thread slots and determining the number of available registers in each processor of the plurality of processors of each of the plurality of processor arrays. For an embodiment, determining the available thread slots and determining the number of available registers in each processor of the plurality of processors of each of the plurality of processor arrays includes decrementing, by a counter of the thread scheduler corresponding with the processor, the number of available registers when starting a thread, and incrementing, by the counter of the thread scheduler corresponding with the processor, the number of available when a thread is completed.

As previously described, for an embodiment, when the scheduler305is scheduling a group of threads, the scheduler305identifies the processor array(s) (341,342,343) in the array of processor arrays340which have at least one available thread slot and available registers exceeding the number of registers needed by each thread of the group of threads in the processors of the processor array/s (341,342,343). One of identified processor array(s) (341,342,343) is picked (for example, using a round-robin selection process of the processor array(s) which satisfies the group of thread requirements). When the threads in the group of threads are scheduled on the processors of this processor array, the appropriate thread slots are marked as in use and the available registers in the processors of the processor array are decremented by the number of registers used by each thread of the group of threads. As the threads in the group of threads complete, the appropriate thread slots are marked as available and the available registers in the processors of the processor array are incremented by the number of registers used by each retiring thread of the group of threads.

As previously described, for an embodiment, determining the available thread slots and determining the number of available registers in each processor of the plurality of processors of each of the plurality of processor arrays includes decrementing, by a counter of the thread scheduler corresponding with the processor, the number of available registers when starting a thread, and incrementing, by the counter of the thread scheduler corresponding with the processor, the number of available when a thread is completed.

As previously described, for an embodiment, independently processing each thread of the group of threads on the one processor of the plurality of processors comprises scheduling an instruction of one thread of the group of threads without relying on scheduling of an instruction of another thread of the group of threads

As previously described, for an embodiment, each thread includes an instance of a set of instructions running on a processor of the graph streaming processor.

As previously described, for an embodiment, dispatching the group of threads to the plurality of processors of a one of the plurality of processor arrays comprising loading attributes of each thread of the group of threads to each of the available thread slots of a processor, wherein the attributes include a program pointer, pointer to the input tensor, pointer to the weight tensor, and pointer to the output tensor.

As previously described, at least some embodiments further include loading, by a plurality of weight data registers, a subset of weights of the weight tensor, wherein each of the weight data registers provide a weight to a single of the plurality of processors, and performing, by the plurality of processors, a SOMAC (Sum-Of-Multiply-Accumulate) instruction, including simultaneously determining, by each of the plurality of processors, an instruction size of the SOMAC instruction, wherein the instruction size indicates a number of iterations that the SOMAC instruction is to be executed and is equal to a number of outputs within a subset of the output tensor.

As previously described, at least some embodiments further include reading, by each of the plurality of processors, a first source operand of a plurality of source operands of the SOMAC instruction from the group load register file, wherein the first source operand is one of the subset of inputs of the input tensor. As previously described, at least some embodiments further include reading, by each of the plurality of processors, a second source operand of the plurality of source operands of the SOMAC instruction from the weight register file wherein the second source operand is one of the subset of the weights of the weight tensor. As previously described, at least some embodiments further include executing, by each of the plurality of processors, multiply and accumulate operations of the SOMAC operation for the number of iterations.

At least some embodiment further include reading, by each of the plurality of processors, a destination operand of the plurality of operands of the SOMAC instruction from the output register file, wherein the destination operand is one of the subset of outputs of the output tensor, adding, by each of the plurality of processors, a sum-of-multiply result to the destination operand, and writing, by each of the plurality of processors, the multiply-accumulate result back to the destination operand, wherein the destination operand is a register from the output register file that is an output of the instruction.

At least some embodiment further include loading, by a second group load register, a second subset of the inputs of the input tensor, wherein the second group load register provides the second subset of the inputs of the input tensor to all of a second plurality of processors, loading, by a second plurality of weight registers, a second subset of the weights of the weight tensor, wherein each of the second plurality of weight data registers provide a weight to a single of the second plurality of processors, and performing, by the second plurality of processors, the SOMAC (Sum-Of-Multiply-Accumulate) instruction, including each of the second plurality of processors simultaneously determining the instruction size of the SOMAC instruction, wherein the instruction size indicates a number of iterations that the SOMAC instruction is to be executed and is equal to a number of outputs within a second subset of the output tensor. For an embodiment, a size of the group register is dependent on a number of inputs within the subset of inputs of the input tensor.

Although specific embodiments have been described and illustrated, the described embodiments are not to be limited to the specific forms or arrangements of parts so described and illustrated. The embodiments are limited only by the appended claims.