Patent Description:
One application in which accumulators are particularly important is for large matrix multiplication or convolution operations. Matrix multiplications for certain applications, such as in the execution of an artificial neural network (ANN), require massive product-sum computations. As the data structures associated with standard ANNs can include millions or even billions of elements, a matrix multiplication conducted on such a data structure can likewise be associated with an immense number of computations. Computational circuits which are dedicate to the execution of large matrix multiplications can include accumulators which are configured to hold the output of a matrix multiplication where the accumulator includes multiple sectors individually associated with respective individual portions of the output of the matrix multiplication. The product-sums for calculating each portion of the output of the matrix multiplication can be calculated by passing the input data to a set of multiplication circuits and accumulating the outputs of those multiplication circuits in a sector of the accumulator. While this can lead to an efficient execution of a complex computation, the size of the accumulator can be cost prohibitive. Math circuits can be designed to conduct computations so fast that only register memory can keep pace with the circuits. However, register memory is relatively expensive compared with relatively slower memory such as static random-access memory or dynamic random-access memory. Also, the output of a large matrix multiplication, or other complex computation, can be an immense matrix. As such, if a sector of an accumulator using register memory needs to be dedicated for each portion of such a large matrix, the accumulator may be prohibitively expensive.

Methods and systems related to the field of computer processing architectures and circuitry are disclosed. The systems disclosed herein include computational circuits with hierarchical accumulators. The systems disclosed herein include hierarchical accumulators with hierarchies of two or more levels, with each level including an accumulator, and in which each level down the hierarchy includes an accumulator with increased size, decreased cost-per-bit, and decreased speed relative to the accumulator in the level above it in the hierarchy. These disclosed hierarchical accumulators result in fast low-cost accumulators with enhanced performance for complex computations.

In specific embodiments of the invention, at least the first level of a hierarchical accumulator is broken into different sectors with at least one sector remaining idle while another sector is being used to accumulate an output value, and the next level of the accumulator is configured to read from the idle sector while the first level is engaged in accumulating an output value in an active sector of the first level. In specific embodiments, at least the first level consists of two sectors with one sector being idle while the other is active and vice versa. In specific embodiments, each subsequent level of the accumulator can read all the values in an idle sector of the prior level before the idle sector of the prior level becomes active again.

In specific embodiments of the invention, the various levels of the accumulator are configured so that each level accumulates at a speed in data elements per second which is at least as fast as the prior level. In specific embodiments of the invention, the speed of an accumulator is set by the speed of the accumulate operations of that level of the accumulator expressed in writes per second divided by the number of accumulate operations required to compute a data element expressed in writes per data element. The speed of each level at producing final values in memory is therefore the speed of the accumulate operation divided by the number of accumulate operations required to compute a data element. Therefore, even though a higher-level accumulator may have a higher accumulation operation speed, if the ratio of the relative number of accumulate operations required to compute a data element between the higher level and the next level is set equal to the ratio of the relative accumulation operation speeds between that next level and that higher level, the hierarchical accumulator can continue to produce values at the fastest rate the computational circuitry can perform without creating any bottlenecks in the various levels of the hierarchy.

In specific embodiments of the invention, the hierarchical accumulators are used as part of the computational units in a network of computational nodes. In these embodiments, the use of a hierarchical accumulator can relieve pressure on the network by increasing data reuse of local data before additional data is required from the network while at the same time not requiring a massive and expensive fast accumulator. In specific embodiments of the invention, the computational circuits that include the disclosed hierarchical accumulators operate on operands which are retrieved from local memory (i.e., local data on the same substrate as a controller and computational circuit) and remote memory (i.e., remote data that is network accessible to the controller and/or computational circuit). The operands can be routed from memory, and through the network, in the form of blocks of a given size, and the hierarchical accumulator can be configured such that it includes a memory capable of storing a block of that given size. Advantageously, this block size can be large which increases the number of computations that can be conducted with a given block before another block must be delivered through the network. This benefit is more than a linear improvement as both the local data blocks and the remote data blocks are larger resulting in a major increase in the number of operations that can be conducted with a single remote data block.

In specific embodiments of the invention, a computational circuit is provided. The computational circuit includes a math circuit. The computational circuit also includes a first accumulator communicatively connected to the math circuit, having a first memory, and that accumulates values from the math circuit in the first memory. The computational circuit also includes a second accumulator communicatively connected to the first memory, having a second memory, and that accumulates values from the first memory in the second memory. The first memory is faster and smaller than the second memory.

In specific embodiments of the invention, a method is provided. The method includes accumulating, using a first accumulator with a first memory, values from a math circuit in the first memory. The method also includes accumulating, using a second accumulator with a second memory, values from the first memory in the second memory. The first memory is faster and smaller than the second memory.

In specific embodiments of the invention, a computational circuit is provided. The computational circuit includes a matrix multiplier array, a register memory, and a static random-access memory. The computational circuit also includes a first accumulator that accumulates values from the matrix multiplier array in the register memory. The computational circuit also includes a second accumulator that accumulates values from the register memory in the static random-access memory.

Methods and systems related to the field of computational circuits in accordance with the summary above are disclosed in detail herein. The methods and systems disclosed in this section are nonlimiting embodiments of the invention, are provided for explanatory purposes only, and should not be used to constrict the full scope of the invention. It is to be understood that the disclosed embodiments may or may not overlap with each other. Thus, part of one embodiment, or specific embodiments thereof, may or may not fall within the ambit of another, or specific embodiments thereof, and vice versa. Different embodiments from different aspects may be combined or practiced separately. Many different combinations and sub-combinations of the representative embodiments shown within the broad framework of this invention, that may be apparent to those skilled in the art but not explicitly shown or described, should not be construed as precluded.

<FIG> illustrates a block diagram of a computational circuit <NUM> with a hierarchical accumulator <NUM> and a flow chart <NUM> for a set of methods in accordance with specific embodiments of the invention disclosed herein. Computational circuit <NUM> includes a math circuit <NUM> and a hierarchical accumulator <NUM>. The math circuit could be a multiplication array able to take in many operands, multiple them in pairs, and output the product of the pairs. The math circuit could conduct an operation on its input operands and produce outputs in a single clock cycle or produce outputs in series over a set of clock cycles. The outputs could be a set of products required to compute all the elements of an output matrix. Computational circuit <NUM> also includes two input source registers in the form of source A register <NUM> and source B register <NUM>. Computational circuit <NUM> can accumulate the values for a composite computation in a pipeline fashion with multiple pairs of input values being provided to source A register <NUM> and source B register <NUM> to conduct multiple component computations of that composite computation using math circuit <NUM> and accumulating the outputs of those composite computations using hierarchical accumulator <NUM>.

Computational circuit <NUM> conducts a composite computation on multiple pairs of input values which are provided to source A register <NUM> and source B register <NUM>. While computational circuit <NUM> accepts a pair of inputs, alternative computational circuits in accordance with this disclosure can accept many more than two inputs. The inputs can be provided to the input source registers in a pipeline fashion by a control system orchestrating the execution of a composite computation. The values from the source registers are provided to math circuit <NUM> as the operands for the computations conducted by math circuit <NUM>. The input values stored in source A register <NUM> and source B register <NUM> could be scalar data elements of a data type compatible with math circuit <NUM> (e.g., <NUM>-bit integer, <NUM>-bit floating point, etc.). The input values stored in source A register <NUM> and source B register <NUM> could also be vectors or multidimensional tensors with a set of data elements of the same or various data types (e.g., each input could be a 16x16 tensor of individual data elements with each individual data element being a <NUM>-bit floating point data type). Accordingly, the math circuit <NUM> may include an array of discrete computational circuits <NUM> to conduct operations on the various data elements of the inputs to the math circuit in parallel. For example, computational circuit <NUM> could be a matrix multiplication circuit, and math circuit <NUM> could have an array of discrete multiplication circuits that each take in two values from the input data values (e.g., two <NUM>-bit floating point data element values from two 16x16 tensor input data values) and output the product of those values.

A control system responsible for feeding values to math circuit <NUM> could be designed to provide new values to source A register <NUM> and source B register <NUM> in synchronization with the speed of math circuit <NUM> to conduct a composite computation such as a large matrix multiplication while keeping math circuit <NUM> at full capacity. The math circuit <NUM> could conduct all the component computations required to be conducted on a set of inputs in a single clock cycle. For example, if math circuit <NUM> included <NUM> discrete multiplication circuits, each computing in a single clock cycle, math circuit <NUM> could conduct all the component multiplications needed for a composite computation in the form of a matrix multiplication of two 16x16 tensors in a single clock cycle. However, if the math circuit had not quite so many discrete multiplication circuits, or the discrete multiplication circuits did not compute at a speed of one clock cycle, more than one clock cycle would be required to conduct all the component multiplications.

Hierarchical accumulator <NUM> accumulates the output values from math circuit <NUM>. Hierarchical accumulator <NUM> includes a first accumulator <NUM> and a second accumulator <NUM>. The hierarchical accumulator <NUM> includes two levels which each consist of accumulators having memory for storing accumulated values, and logic circuits for: reading input values, adding the input values to accumulated values stored in memory, and storing the output of the addition in the memory. The logic circuits can comprise various logic gates, latches, flip-flops, and other digital logic or analog logic components. While hierarchical accumulator <NUM> includes two levels for ease of explanation, hierarchical accumulators in accordance with this disclosure can have more than two levels.

First accumulator <NUM> is communicatively connected to math circuit <NUM>, has a first memory <NUM>, and accumulates values from math circuit <NUM> in first memory <NUM>. The first accumulator <NUM> can accordingly read a value from memory <NUM>, obtain a value from math circuit <NUM>, conduct an addition operation on both values, and write the result of that addition operation back to memory <NUM>. This operation is shown as step <NUM> in flow chart <NUM> and includes accumulating, using a first accumulator <NUM> with a first memory <NUM>, values from a math circuit <NUM> in the first memory <NUM>. The speed at which those operations can be conducted can be referred to as the accumulation operation speed of accumulator <NUM> and can be expressed in units of data element writes per second. First memory <NUM> can include a first memory sector <NUM> and a second memory sector <NUM>. The memory sectors can each include many addresses at which data elements can be stored. The data elements can be various data types. However, the data type will generally match the format of the outputs from math circuit <NUM>. For example, first accumulator <NUM> may retrieve a value from memory sector <NUM>, obtain a value from math circuit <NUM>, conduct a summing operation on both values, and write the sum back into memory sector <NUM>. First memory <NUM> can be register memory, but it can also be any kind of memory including static random-access memory, dynamic random-access memory, cross bar memory, phase change memory, or any kind of readable and rewritable memory.

Second accumulator <NUM> is communicatively connected to first memory <NUM>, has a second memory <NUM>, and accumulates values from first memory <NUM> in second memory <NUM>. The second accumulator <NUM> can accordingly read a value from memory <NUM>, obtain a value from memory <NUM>, conduct an addition operation on both values, and write the result of that addition operation back to memory <NUM>. This operation is shown as step <NUM> in flow chart <NUM> and includes accumulating, using a second accumulator <NUM> with a second memory <NUM>, values from first memory <NUM> in second memory <NUM>. The speed at which those operations can be conducted can be referred to as the accumulation operation speed of accumulator <NUM> and can be expressed in units of data element writes per second. Second memory <NUM> can include a first memory sector <NUM> and a set of additional memory sectors <NUM>. The memory sectors can each include many addresses at which data elements can be stored. The data elements can be various data types. However, the data type will generally match the format of the data elements in memory <NUM>. Second memory <NUM> can be a static random-access memory. However, it can also be register memory, dynamic random-access memory, cross bar memory, phase change memory, or any kind of readable and rewritable memory.

In specific embodiments of the invention, each level of the hierarchical accumulator is slower but has more storage than the prior level of the hierarchy. For example, if computational circuit <NUM> were a matrix multiplier and math circuit <NUM> were a multiplier array, memory <NUM> could be as large as the output matrix generated by all of the products generated by math circuit <NUM> in response to a pair of operand inputs, and memory <NUM> could be as large as an output matrix generated from a set of operand inputs, such as set <NUM>, provided to the source registers. Furthermore, each level of the hierarchical accumulator could have a slower accumulation operation speed in data element writes per second than the prior level as attributable to either fewer logic circuits, slower logic circuits, slower memory, or both. For example, the math circuit <NUM> could output values at an output speed of <NUM> data elements per nanosecond and the first accumulator <NUM> could accumulate a value from the math circuit <NUM> in the first memory <NUM> at a first accumulation operation speed. The value could be a data element and the first accumulation operation speed could be a data element accumulation operation speed. Continuing with this example, the first accumulation operation speed could be at least as fast as the output speed of <NUM> data elements per nanosecond. The second accumulator <NUM> could accumulate a value from the first memory <NUM> in the second memory <NUM> at a second accumulation operation speed. The value could be a data element and the speed of the second accumulation operation speed could be a data element accumulation operation speed. In keeping with the above example, the second accumulation operation speed could be slower than the first accumulation operation speed of <NUM> data elements per nanosecond allowing a relatively slower memory to be used because the second accumulator does not need to accumulate values every nanosecond.

The speed differential between different levels of the hierarchy could be caused by various factors. For example, the logic circuits of the accumulator of a level of the hierarchy could be slower at conducting the summing operations required for that level of the hierarchy than the accumulator of the prior level. In the alternative or in combination, each level of the hierarchical accumulator could utilize memory that has a slower read and/or write speed than the prior level. As there is, generally, an inverse relationship between the speed and size/cost of different types of memory, this configuration allows each layer of the hierarchy to be slower but larger/cheaper than the prior level. Applying this configuration to <FIG>, the first memory <NUM> would be faster and smaller than second memory <NUM>. For example, first memory <NUM> could be a small <NUM>,<NUM> bit register memory and second memory <NUM> could be a larger <NUM>,<NUM> bit static random-access memory.

<FIG> illustrates a block diagram <NUM> of the hierarchical accumulator <NUM> of <FIG> annotated to illustrate the interoperation of the levels of the hierarchical accumulator in accordance with specific embodiments of the invention disclosed herein. As illustrated, accumulator <NUM> includes a memory which is broken into memory sector <NUM> and memory sector <NUM>. Accumulator <NUM> receives upstream outputs <NUM> (which could be the outputs of math circuit <NUM>) and accumulates them in memory <NUM>. As illustrated, the outputs generated by the math circuit, such as output <NUM>, can have an output size and the sectors of the first memory, such as memory sector <NUM> and memory sector <NUM>, can be at least as large as the output size. Accordingly, each sector of memory can hold the entire output of the math circuit for a given input. In specific embodiments of the invention, such as the one illustrated in <FIG>, the first memory includes a first sector and a second sector which are both equal in size to the output size.

In specific embodiments of the invention, the memory of each level of the hierarchy is broken into at least two sectors which are in either an idle or active state with respect to one level while being in the alternative state with respect to an adjacent level. For example, in a hierarchical accumulator having two levels with the first level having a first accumulator with a first memory, and a second level having a second accumulator with a second memory, the first memory could be broken into a first sector and a second sector having this characteristic. The active state would be associated with an accumulator accumulating from/to that sector and the idle state would be associated with an accumulator not accumulating from/to that sector. In keeping with this example, the first accumulator could accumulate in the first sector of the first memory when the second accumulator accumulates from the second sector of the first memory, and the first accumulator could accumulate in the second sector of the first memory when the second accumulator accumulates from the first sector of the first memory.

As illustrated in <FIG>, hierarchical accumulator <NUM> could have accumulator <NUM> switch between utilizing memory sector <NUM> and memory sector <NUM> as additional upstream outputs, such as upstream output <NUM>, were received. The sector in which accumulator <NUM> was currently accumulating values, such as memory sector <NUM> in <FIG>, could be referred to as the active sector while any sector in which accumulator <NUM> was currently not accumulating values, such as memory sector <NUM> in <FIG>, could be referred to as an idle sector. The sector that is currently active could change with each upstream output received by the level of the hierarchy, or it could change less frequently. In the example of <FIG>, assuming that the inputs are matrices of equal sizes being multiplied, the sector that is active would change each time a new set of inputs was provided to the source registers.

In specific embodiments of the invention, a lower level of an accumulator is configured to read from an idle sector of a higher level of the accumulator while the higher level is engaged in accumulating an output value in an active sector of the higher level quickly enough that all the values are accumulated from the idle sector by the lower level before the sector becomes active again with respect to the higher level. For example, as illustrated, accumulator <NUM> can read and accumulate all the values from memory sector <NUM> of memory <NUM> into memory sector <NUM> of accumulator <NUM> before accumulator <NUM> beings writing in memory sector <NUM>. While accumulator <NUM> only has two memory sectors, more sectors could be utilized in the same manner with idle sectors being read and accumulated by accumulator <NUM> before being required to accumulate additional upstream outputs. Each level of the hierarchy could match this characteristic.

In specific embodiments of the invention, the various levels of a hierarchical accumulator are configured so that each level accumulates at a speed in bits per second which is at least as fast as the prior level regardless of whether lower levels of the accumulator have slower accumulation operation speeds than higher levels. As stated previously, each accumulator could have an accumulation operation speed which is slower than the prior level. However, the overall operation of the hierarchical accumulator can be such that while each level has a slower accumulation operation speed than the next higher level, each level can be as fast or faster than the next higher level in terms of bits per second accumulated. For example, a first accumulator could conduct a number of accumulation operations to store an output data value in the first memory in response to a set of operands being applied to the math circuit, and a second accumulator could conduct a number of accumulation operation to store the output data value in the second memory in response to the set of operands being applied to the match circuit, and the number of accumulation operations conducted by the first accumulator could be larger than the number of accumulation operations conducted by the second accumulator. For example, to store a single bit of an output in first memory <NUM>, it could take the provisioning of a set of operands <NUM> to math circuit <NUM>. This would require eight operations by math circuit <NUM> with eight different sets of operand inputs. For each set of operand inputs, accumulator <NUM> would need to conduct at least one accumulate operation. However, to store that single bit of the output in memory <NUM> could require only a single accumulation. Therefore, so long as the accumulation operation speed of accumulator <NUM> is less than eight times as fast as accumulator <NUM>, accumulator <NUM> will be able to keep its required pace in the pipeline.

In <FIG> the speed of accumulator <NUM> is set by the accumulation operation speed of accumulator <NUM> "X" expressed in writes per second divided by the number of accumulate operations required to compute a bit "A" expressed in writes per bit (i.e., bits per second accumulated = X/A). Continuing with this example, the speed of accumulator <NUM> is set by the speed of the accumulate operations of accumulator <NUM> (Y) expressed in writes per second divided by the number of accumulate operations required to compute a bit "B" expressed in writes per bit (i.e., bits per second accumulated = Y/B). In this example X can be larger than Y while the ratio Y/B can be larger than or equal to X/A. While the hierarchical accumulator of <FIG> provides a two-level hierarchy, many levels of hierarchy can be utilized so long as the ratio of writes per second and writes per second remain the same for multiple levels.

Referring again to <FIG>, but with specific numbers for the variables in the prior paragraph, each bit in accumulator <NUM> could require <NUM> upstream outputs <NUM> to be accumulated to compute the bit, while each bit in accumulator <NUM> could require a single bit from memory <NUM> in order to compute the bit. in the case of <FIG>, memory <NUM> could be register memory and the value for X could be <NUM> write per nanosecond. In this example the upstream outputs could be in the form of <NUM><NUM>-bit integers and all entries could be written in a single cycle of a <NUM> clock. Continuing with this example, the computational circuit could require <NUM> upstream outputs <NUM> to accumulate <NUM> portion of memory sector <NUM> where the portion of memory sector <NUM> had the same size as a single upstream output. As a result, the first level of the hierarchy would accumulate at a speed of <NUM> write / ns divided by <NUM> writes / value providing a speed of <NUM>/<NUM> values per ns. The second level accumulator could have a faster accumulation speed even if memory <NUM> were a slower memory such as static random-access memory such that the accumulator needed <NUM> nanoseconds to accumulate. If the computational circuit only required <NUM> value from memory <NUM>, the second level of the hierarchy would accumulate at a speed of <NUM>/<NUM> writes per nanosecond divided by <NUM> writes / value providing a speed of <NUM>/<NUM> values per ns. Accordingly, the two levels of the accumulator will keep pace with the pipeline providing upstream outputs and the capacity of both levels will be maximally utilized. In specific embodiments of the invention, instead of differences in memory speed, the accumulator operation speed in bits / second of different levels could also differ based on the number of logic circuits at each level where the logic circuits operate on a block of data in step wise fashion across a set of clock cycles (e.g., <NUM> logic circuits accumulating <NUM> values across two clock cycles).

<FIG> illustrates a block diagram of a matrix multiplication circuit <NUM> with a hierarchical accumulator <NUM> in accordance with specific embodiments of the invention disclosed herein. Hierarchical accumulator <NUM> includes a first accumulator <NUM> which can exhibit the features of first accumulator <NUM> described above. Hierarchical accumulator <NUM> also includes a second accumulator <NUM> which can exhibit the features of second accumulator <NUM> described above. First accumulator <NUM> includes a register memory <NUM>. Second accumulator <NUM> includes a static random-access memory <NUM>. Matrix multiplication circuit <NUM> is designed to multiply a first input matrix <NUM> with a second input matrix <NUM> to produce an output matrix. The output matrix can be stored in static random-access memory <NUM>. Matrix multiplier array <NUM> which includes an array of discrete multiplication computation units <NUM> which accept two operands, multiply them together, and output the product. The overall matrix multiplication of first input matrix <NUM> and second input matrix <NUM> can involve multiplier array <NUM> conducting all the product operations and first accumulator <NUM> and second accumulator <NUM> conducting all of the sum operations for the component product-sum calculations required for a a matrix multiplication.

In specific embodiments of the invention in accordance with <FIG>, the output matrix of the matrix multiplication circuit will comprise portions that correspond uniquely with sectors of a memory of the hierarchical accumulator. For example, the sectors of memory <NUM> are in a one-to-one correspondence with the portions of an output matrix that would result from the multiplication of first input matrix <NUM> and second input matrix <NUM>. The matrices of <FIG> are drawn as divided into individual portions such as portion <NUM>. These individual portions are applied to source A register <NUM> and source register B <NUM> in a pipelined fashion to conduct the matrix multiplication. The individual portions of the matrices could be scalar data elements of a data type compatible with matrix multiplier array circuit <NUM> (e.g., <NUM>-bit integer, <NUM>-bit floating point, etc.). The portions could also be vectors or multidimensional tensors with a set of data elements of the same or various data types (e.g., each input could be a 16x16 tensor of individual data elements each of a <NUM>-bit floating point data type). Accordingly, the multiplier array <NUM> may include an array of discrete computational circuits <NUM> to conduct operations on the various data elements of the inputs to the math circuit in parallel.

In the example of <FIG>, each portion of the input matrices is a <NUM> x <NUM> array of data elements. The sectors of static random-access memory <NUM> and register memory <NUM> (e.g., sector <NUM>) are therefore memories that can store <NUM> x <NUM> data elements. The multiplier array <NUM> can conduct a matrix multiplication of two input data values, in the form of two <NUM> x <NUM> arrays of data elements, in <NUM> clock cycles, with new values being output every clock cycle. Accordingly, accumulator <NUM> will need to have an accumulation operation time as fast as a single clock cycle. However, many writes will be required to compute an output portion of the output matrix in a memory sector of registers <NUM> (e. g, sector <NUM>). This is because every <NUM> x <NUM> matrix in column <NUM> of input matrix <NUM> must be matrix multiplied with every <NUM> x <NUM> matrix in row <NUM> of input matrix <NUM> to compute the portion of the output matrix that corresponds with sector <NUM> of static random-access memory <NUM>. The first accumulator <NUM> will accumulate these values, from all eight matrix multiplications done by matrix multiplier array <NUM> in register memory <NUM>. Accordingly, memory sector <NUM> will need to remain active for accumulator <NUM> to accumulate values for <NUM> × <NUM> clock cycles (<NUM> matrix multiplications times <NUM> clock cycles per matrix multiplication). This allows second accumulator <NUM><NUM> clock cycles to accumulate values from the register memory <NUM> in sector <NUM> to the static random-access memory <NUM> in sector <NUM>. Accumulator <NUM> can therefore have an accumulation operation speed of <NUM> clock cycles per <NUM> x <NUM> data elements in order to keep pace with the higher level of the accumulator. If a clock cycle is <NUM> ns, this <NUM> ns provides sufficient time to read from and write to a static random-access memory.

If matrix multiplication circuit <NUM> were designed only for matrix inputs with the size of first input matrix <NUM> and second input matrix <NUM>, the accumulator <NUM> could be replaced by a static random-access memory and a circuit that could read from register <NUM> and write to static random-access memory <NUM> alone (i.e., it would not need summing circuits). However, matrix multiplication circuit <NUM> can be used to conduct large matrix multiplication operations in which the <NUM> x <NUM> matrices shown in <FIG> are simply blocks of larger matrices. In specific embodiments, these larger matrices will have inner dimensions equal to the size of a memory of the hierarchical accumulator. In the example of <FIG>, this would be a matrix of <NUM> x <NUM> data elements so that the correspondence between portions of the output matrix and sectors of memory <NUM> can be preserved (i.e., memory <NUM> is large enough to store the entire output matrix). In these embodiments, the various blocks could be provided to matrix multiplication circuit <NUM> in the same way that individual portions of the illustrated matrices are provided to the source registers in a super cycle fashion. The accumulations that occur in accumulator <NUM> would therefore be used to compute the final values of the output matrix with a sector such as sector <NUM> being accumulated once per super cycle. In these embodiments, hierarchical accumulator could have another layer that was slower than accumulator <NUM> (e.g., the memory could be a dynamic random-access memory or EEPROM) while the size of memory <NUM> could be reduced in proportion to the speed allowed for writing to the next layer.

In specific embodiments of the invention, the blocks of a matrix are routed from main memory to a processing pipeline of a processor as a unit. In specific embodiments of the invention, the computational circuits disclosed herein are in a pipeline of a processor in a network of processing cores and the blocks are routed through the network as a unit. The blocks could be routed by a controller. The controller could also orchestrate the pipeline on the computational circuit. For example, if the computational circuit were a matrix multiplier circuit, the controller could be programmed to multiply a first matrix and a second matrix using the matrix multiplier circuit to generate an output matrix, provide the first matrix to the multiplier array in a first series of blocks, and provide the second matrix to the matrix multiplier circuit in a second series of blocks. In these embodiments, the second memory of the hierarchical accumulator, such as memory <NUM> could be as large as the output matrix.

Regardless of which type of embodiment is involved, routing large blocks of data through a processor or network of processing cores takes up valuable hardware and power resources. Accordingly, conducting matrix multiplications in a manner which maximizes data reuse and the time between when additional blocks of data are required from the slowest link in the pipeline can create significant benefits. Accordingly, the controller can be programmed to only retrieve blocks from the slowest link once (i.e., retrieve the block from the slowest link and conduct all the computations that block is involved in before retrieving another). In a matrix multiplication this will require alternative blocks (i.e., blocks taken from faster links) to be retrieved from memory multiple times.

<FIG> is a block diagram of a system <NUM> with a matrix multiplication circuit <NUM> having an accumulator <NUM> where the matrix multiplication circuit <NUM> receives one set of data values from a remote storage <NUM> via a network <NUM>, and another set of data values from a local storage <NUM>. The data values from remote storage <NUM> can be blocks of a first matrix. The data values from local storage <NUM> could be blocks of a second matrix. The inner dimensions of the first and second matrixes will set the dimensions of the output matrix <NUM>. The local storage <NUM> could be the main memory of a processor. The remote storage <NUM> could be the main memory of another processor where network <NUM> connects the two processors such that they can operate as multiple cores in a multicore processor. The accumulator could be a hierarchical accumulator such as hierarchical accumulator <NUM>. The accumulator includes a memory storing an output matrix <NUM>. The matrix multiplication circuit <NUM> operates on a first input matrix block <NUM> retrieved via network <NUM> from a set of first input matrix blocks <NUM>, and a second input matrix block <NUM> retrieved from local storage <NUM> from a set of second input matrix blocks <NUM>. The super cycle mentioned with reference to <FIG> is conducted each time a new block is retrieved from either remote storage <NUM> or local storage <NUM>. The super cycle could be orchestrated by a controller <NUM> which is programmed to multiply a first matrix (e.g., made of the set of first input matrix blocks <NUM>) and a second matrix (e.g., made of the set of second input matrix blocks <NUM>) using matrix multiplication circuit <NUM>, provide the first matrix to the matrix multiplication circuit <NUM> in a first series of blocks (e.g., a series formed by set of first input matrix blocks <NUM>), and provide the second matrix to the matrix multiplication circuit <NUM> in a second series of blocks (e.g., a series formed by set of second input matrix blocks <NUM>).

In specific embodiments of the invention, the hierarchical accumulator, and block sizes used by system <NUM> can be selected to minimize pressure placed on the network <NUM>. In <FIG>, the system can be designed to cycle through all the values from local storage <NUM> while conducting super cycles with a single input matrix block from set of first input matrix blocks <NUM>. Accordingly, in the illustrated case, and assuming the super cycles have the characteristics of the specific example provided with reference to <FIG> and each matrix is divided into four blocks, the network will have at least <NUM> x <NUM> x <NUM> x <NUM> clock cycles in which to deliver another block. The size of accumulator <NUM> therefore has a direct impact on decreasing the pressure placed on the network. If the accumulator were simply a single fast accumulator (e.g., required to have an accumulation operation speed of <NUM> clock cycle), the accumulator would be prohibitively expensive. Therefore, using the hierarchical accumulators disclosed herein provide significant benefits in these types of applications because the output matrix can be accumulated in a slightly cheaper memory that can be made large enough to support large block sizes. This benefit applies even more acutely if both input matrixes comprise blocks that are delivered from remote storage.

<FIG> illustrates a flow chart <NUM> for a set of methods for operating a hierarchical accumulator in accordance with specific embodiments of the invention disclosed herein. Flow chart <NUM> includes steps <NUM> and <NUM> from <FIG> nested within a step <NUM> of multiplying a first matrix and a second matrix to produce an output matrix. Flow chart <NUM> further includes a step <NUM> of providing the first matrix and the second matrix to a computational circuit as a set of blocks. The step is shown as part of a super cycle loop as the remaining steps can be conducted multiple times before another block is required. The blocks could be blocks such as blocks <NUM> and <NUM> from <FIG>. Flow chart <NUM> further includes a step <NUM> of accepting, using a computational circuit, the set of blocks as operands. The step is shown as part of a cycle loop because the remaining steps can be conducted multiple times as different portions of the blocks are fed to the computational circuit. The computational circuit could be computational circuit <NUM> from <FIG> or computational circuit <NUM> from <FIG>. The computational circuit could include a math circuit such as math circuit <NUM>. The second memory <NUM> could be at least as large as the output matrix. The math circuit could be a multiplier array such as multiplier array <NUM>. As such, the portions of the blocks that are provided to the computational circuit as operands could be the subblocks from a set of operand inputs, such as set <NUM>. The values from the math circuit which are utilized in step <NUM> could be generated using the set of blocks as operands and could comprise a set of products the first memory used in step <NUM> could be at least twice as large as the set of products. The related step is shown as step <NUM> of outputting values for the first accumulator using the math circuit. Step <NUM> could involve generating a set of products required to compute the output matrix.

In accordance with the approaches disclosed above, and the example of flow chart <NUM> step <NUM> and step <NUM> could include sub-steps in which different layers of the hierarchical accumulator utilize different sectors of the first memory and second memory. As illustrated, step <NUM> includes a sub-step <NUM> of accumulating, using the first accumulator with the first memory, values from the math circuit in a first sector of the first memory and a simultaneously conducted step <NUM> of accumulating using the second accumulator with the second memory, values from a second sector of the first memory in the second memory. As further illustrated, step <NUM> includes a sub-step <NUM> of accumulating, using the first accumulator with the first memory, values from the math circuit in the second sector of the first memory and a simultaneously conducted step <NUM> of accumulating, using the second accumulator with the second memory, values from the first sector of the first memory in the second memory.

The relative memory sizes and speeds at which steps are conducted in the implementations of flow chart <NUM> can match those described with reference to <FIG>. For example, in specific embodiments of the invention, the first sector of the first memory will be at least as large as the output size of the outputs generated by the math circuit in each cycle of step <NUM>. As another example, in specific embodiments of the invention, the first sector of the first memory used in step <NUM> is equal in size to the output size of the outputs generated in step <NUM>, and the second sector of the first memory used in step <NUM> is likewise equal in size to the output size of the outputs generated in step <NUM>. As another example, in specific embodiments of the invention, the step <NUM> of outputting values for the first accumulator using the math circuit is done at an output speed, step <NUM> is done at a first per value accumulation speed which is at least as fast as the output speed, and step <NUM> is done at a second per value accumulation speed which is slower than the first per value accumulation speed.

The hierarchical accumulators disclosed herein can be part of the processing pipeline of a processor. The processors can include one or more hierarchical accumulators. The processors can take on various forms. The processors can be processing cores in a multicore processor or standalone processors. The processors can be implemented as single chip systems, including wafer-scale single chip systems, multichip single package systems, or in a multichip multipackage system in which the chips are commonly attached to a common substrate such as a printed circuit board (PCB), interposer, or silicon mesh. The processor can be part of a network of processors. The network can be a network on chip (NoC). The processors in accordance with this disclosure can also be part of a network that includes chips on multiple substrates linked together by a higher-level common substrate such as in the case of multiple PCBs each with a set of chips where the multiple PCBs are fixed to a common backplane. Processors in accordance with this disclosure can also be implemented in chiplet based systems. For example, in specific embodiments of the invention, one or more processors could be housed or implemented by one or more networked chiplets, connected, for example, through an interposer.

A processor in accordance with this disclosure can included at least one non-transitory computer readable media. The at least one processor could comprise at least one computational node in a network of computational nodes. The media could include cache memories on the processor. The media can also include shared memories that are not associated with a unique computational node. The media could be a shared memory, could be a shared random-access memory, and could be, for example, a DDR DRAM. The shared memory can be accessed by multiple channels. The non-transitory computer readable media can store data required for the execution of any of the methods disclosed herein, the instruction data disclosed herein, and/or the operand data disclosed herein. The computer readable media can also store instructions which, when executed by the system, cause the system to execute the methods disclosed herein. The concept of executing instructions is used herein to describe the operation of a device conducting any logic or data movement operation, even if the "instructions" are specified entirely in hardware (e.g., an AND gate executes an "and" instruction). The term is not meant to impute the ability to be programmable to a device.

A processor in accordance with this disclosure can include at least one logic circuit as described above. The logic circuit can include both active and passive devices and operate with one or more logic levels. The logic circuit can operate using Boolean logic and can be a synchronous clocked circuit or an asynchronous circuit. The logic circuit can include logic gates, flip-flops, latches, registers, and other fundamental circuit components that are required to produce a digitized logical output in response to a digitized logical input. The logic circuit can be implemented directly in hardware such that a logic or operation is conducted by a physical collection of transistors that implement an OR gate and the storage of a data element involves the physical state of at least one flip flop, delay line, or other physical storage element.

Other aspects of the invention are defined in the following numbered statements:.

Claim 1:
A computational circuit comprising:
a math circuit;
a first accumulator communicatively connected to the math circuit, having a first memory, and that accumulates values from the math circuit in the first memory;
a second accumulator communicatively connected to the first memory, having a second memory, and that accumulates values from the first memory in the second memory; and
wherein the first memory is faster and smaller than the second memory.