Multinomial distribution on an integrated circuit

An integrated circuit device such as a neural network accelerator can be programmed to select a numerical value based on a multinomial distribution. In various examples, the integrated circuit device can include an execution engine that includes multiple separate execution units. The multiple execution units can operate in parallel on different streams of data. For example, to make a selection based on a multinomial distribution, the execution units can be configured to perform cumulative sums on sets of numerical values, where the numerical values represent probabilities. In this example, to then obtain cumulative sums across the sets of numerical values, the largest values from the sets can be accumulated, and then added, in parallel to the sets. The resulting cumulative sum across all the numerical values can then be used to randomly select a specific index, which can provide a particular numerical value as the selected value.

BACKGROUND

A multinomial distribution is the probability distribution of the outcomes from a multinomial experiment. A multinomial experiment is a statistical experiment in which there are a number of independent trials and each trial has a discrete number of possible outcomes. On any given trial, the probability that a particular outcome will occur is constant. An example of such an experiment is the tossing of two dice three times: the number of trials is three, each trial can result in a discrete number of outcomes (a sum between two and twelve, inclusive), and the probability of any outcome is constant, in that the outcome does not change from one toss to the next.

Multinomial distributions occur in computing systems when a computation performed by a computing device outputs a set of probabilities. In these situations, the computing device may be configured to randomly select one of the probabilities, where the value of each probability determines how frequently the probability will be picked. An example of a computation that outputs a set of probabilities is the softmax function. The softmax function takes as input a vector of K real numbers and normalizes the vector into a probability distribution including K probabilities. Softmax is often used in neural networks, for example to map the non-normalized output of a neural network to a probability distribution over predicted output classes.

A multinomial distribution selection process may be used in a computation to make the computation more resilient to errors. For example, a neural network can generate a set of probabilities when determining a next choice to make. In this example, when the neural network always chooses the highest-ranked choice, and this choice is wrong, then the neural network is consistently wrong. If the neural network instead makes a random choice, with the randomness being biased according to the rankings provided by the probabilities, then neural network may be able to self-correct as the computation progresses.

DETAILED DESCRIPTION

A neural network processor is a type of integrated circuit device that is purpose built to execute neural networks. Executing a neural network (referred to as performing an inference) can require large numbers of simple operations such as add and multiply, which can be performed in parallel and thus can be efficiently executed by hardware that supports large numbers of parallel computations. While a general purpose processor can execute a neural network, general purpose processors may be designed for greatest flexibility in the types of operations these processors can perform, rather than for large amounts of parallel computations. Graphics Processing Units (GPUs) can also be used to execute a neural network, but may be optimized for parallel computation on unrelated vectors of data, while neural networks tend to require tensor operations, such as multiplication of arrays and accumulation of array values. Additionally, graphics processing units may be expensive, in terms of monetary cost and operating cost, to add to a computing device, while neural network processors may be much more inexpensive. In some examples, neural network processors are also referred to as neural network accelerators.

Making a decision based on a multinomial distribution is an operation that can occur in the execution of a neural network. While the program instructions for performing such a selection can be performed by a general purpose processor, doing so can be disruptive to the execution of the neural network. For example, a neural network processor that is in the middle of performing an inference may have to stop and wait while a general purpose processor in the system performs the selection based on the multinomial distribution. In this example, the neural network processor will be idle until the general purpose processor has provided an answer. The inference can be performed more efficiently if the neural network processor can itself make the selection.

In various examples, an integrated circuit device such as a neural network accelerator can be programmed to select a numerical value based on a multinomial distribution. The multinomial distribution can be a set of probabilities output by a computation, such as a step in the execution of a neural network. Making a selection based on a multinomial distribution can include a sequential series of steps, however, the techniques discussed herein make use of the parallel computation capabilities of the integrated circuit device. By parallelizing the steps, the integrated circuit device can make the selection efficiently and with significant additional computational load on the device. The integrated circuit device can thus make the selection while performing a larger computation that uses the selection, so that the larger computation need not be stalled while steps to make the selection are performed elsewhere.

In various examples, the integrated circuit device can include an execution engine that includes multiple separate execution units. The multiple execution units can operate in parallel on different streams of data, and can perform various mathematical, logical, and/or comparative operations. For example, to make a selection based on a multinomial distribution, the execution units can be configured to perform cumulative sums on sets of numerical values, where the numerical values represent probabilities. In this example, to then obtain cumulative sums across the sets of numerical values, the largest values from the sets can be accumulated, and then added, in parallel to the sets. The resulting cumulative sum across all the numerical values can then be used to randomly select a specific index, which can provide a particular numerical value as the selected value.

FIG. 1illustrates an example of performing a selection based on a multinomial distribution. The multinomial distribution is illustrated here as a set of probabilities100having the values 0.1, 0.2, 0.3, and 0.4. The probabilities100can be generated, for example, by an operation such as the softmax function. In this example, the probabilities100are represented as a value between 0 and 1, and the sum of the probabilities100is 1. In other examples, the sum of the probabilities100can be less than 1 or greater than 1.

Making a selection based on a multinomial distribution means randomly selecting one of the probabilities100, where the likelihood of a particular probability being selected is determined by the value of the probability. For example, over a number of selections, the value 0.1 should be selected 10% of the time, the value 0.2 should be selected 20% of the time, the value 0.3 should be selected 30% of the time, and the value 0.4 should be selected 40% of the time.

An example technique for randomly selecting one of the probabilities100is shown by a selection space102illustrated inFIG. 1. The selection space102reflects all possible selections between 0 and the sum of the probabilities100, which here is 1. In the selection space102, each of the probabilities100is allocated an area that reflects the value of each probability. For example, the value 0.1 is allocated one tenth of the selection space, the value 0.2 is allocated two tenths of the selection space, the value 0.3 is allocated three tenths of the selection space, and the value 0.4 is allocated four tenths of the selection space. Though the probabilities100are shown in the selection space102sorted by smallest to largest, the probabilities100need not be arranged in any particular order, so long as the space assigned to each of the probabilities100reflects the numerical value of each probability.

To select one of the probabilities100using the selection space102, a random number104can be generated that falls somewhere within the selection space102. The random number104can be generated, for example, using random number generator that generates evenly distributed random numbers. To determine where in the selection space102the random number104falls, the selection process can compute a series of cumulative sums106of the probabilities100, and can compare the cumulative sums106against the random number104. For example, at the first index, the process can add the probability 0.1 to 0 to determine a cumulative sum of 0.1. The process can next determine whether the random number104is less than or equal to the cumulative sum of 0.1. Because the random number104is not less than or equal to the cumulative sum of 0.1, the process determines that the probability at the first index (0.1), is not the probability that has been selected. The process next adds the probability at the second index (0.2) to the cumulative sum, to obtain 0.3. The random number104is less than or equal to the new cumulative sum of 0.3. Thus, the process selects the probability at the second index (0.2). In this example, the process need not continue computing the remaining cumulative sums (0.6 and 1.0 for the third and fourth indexes, respectively).

FIG. 2illustrates integrated circuit components that can be used to select a value based on a multinomial distribution. The illustrated components include a memory subsystem204and an execution engine218. The components can be part of a larger integrated circuit, such as a neural network accelerator. Additionally, in some examples, components that are not illustrated here can interact with the illustrated components. For example, other execution engines may be able to read data from or write data to the memory subsystem204.

In various examples, the memory subsystem204provides storage space for data that is being operated on by the integrated circuit device, including being operated on by the execution engine218. The memory subsystem204can be organized into multiple independent memory banks214. The memory banks214can also be referred to as memory partitions. Independent, in this context, means that the memory banks214do not share an address space, and are each read and written independently. For example, to read a value from one memory bank, a read request is placed on the input ports to the one memory bank. In this example, the one memory bank cannot be read by, for example, placing a read request on the input ports of another memory bank, with the expectation that the read request will be passed on to the correct memory bank. This arrangement of independent memory banks214may be chosen for simplicity and efficiency. For example, by not requiring that any memory bank be readable, wiring across the memory subsystem204is eliminated and no arbitration logic for selecting among the memory banks214is needed. As another example, each memory bank can be assigned to a different client (e.g., a circuit component that uses the memory subsystem204), which then can use the assigned memory bank without contention with other clients.

In the example ofFIG. 2, execution units219of the execution engine218are assigned to different memory banks214of the memory subsystem204. The execution engine218of this example is an integrated circuit component that can be configured to perform various mathematical, logical, and/or comparative operations. The execution engine218uses the execution units219to perform these operations. The execution units219are each instances of a similar block of logic that can perform the operations. In various examples, the execution engine218has more than one execution unit so that the execution engine218can operated on different data simultaneously and in parallel. For example, the execution engine218can configure one or more of the execution units219to read two operands from the memory banks214assigned to each of the execution units219, execute an operation using the two operands, and to write a result back to a respective memory bank. In this example, the operation executed by the different execution units219can be the same or can be different.

Due to the independent arrangement of the memory banks214, the individual execution units219are not able to read or write data to a memory bank other than the memory bank assigned to each execution unit. To enable data operated one by one of the execution units219to be accessible to another execution unit, the memory subsystem204can include a set of registers230that have access to each of the memory banks214. The registers230can be used for temporary storage of data. In some examples, the registers230each store one data word (e.g., a 32-bit value, a 64-bit value, a 128-bit value, or a value of another size that is defined in the system as a “data word”) at a time. In various examples, the registers230can be used to read a value from any of the memory banks214(as shown by dotted lines inFIG. 2), which is then stored in the registers230. The data in the registers230can further be written to any of the registers230. As another example, a series of values can be read from one memory bank and into the registers230. The values in the registers230can also be serially read into one of the memory banks. Parallel reads from multiple memory banks into the registers230can be followed by serially writing the values into one memory bank, and serial reads from one memory bank into the registers230can be followed by a parallel write from the registers230into multiple memory banks214.

In the example ofFIG. 2, the registers230are illustrated as being part of the memory subsystem204. In some examples, the registers230can be located elsewhere, such as in the execution engine218.

FIGS. 3A-3Eillustrate an example of steps that can be performed to select a numerical value based on a multinomial distribution. The illustrated steps can be performed, for example, by the integrated circuit components illustrated inFIG. 2. The steps are illustrated inFIGS. 3A-3Eby showing numerical values, the operations performed on the numerical values, and the results of the operations. The numerical values and the results of the operations are shown as arranged in columns (a first column310, a second column,312, and a last column318; for the sake of clarity, the columns between the second and the last column318are not shown), where each column represents a set of numerical values that is stored in a different memory bank or memory partition. As in the example ofFIG. 2, each of the memory partitions ofFIG. 3can be read or written by a different execution unit that is capable of performing mathematical, logical, and/or comparative operations. Additionally, one execution unit is not able to read or write to another's memory partition. Data from the memory partitions can be, however, be read into a set of registers, which may each be able to store one data word at a time. The data can also be written from the registers into the memory partitions.

FIG. 3Aillustrate a set of numerical values302that represent the probabilities among which one value is to be chosen. The numerical values302are stored in 64 memory partitions, with each memory partitions storing a set of 16 values.FIG. 3Aalso illustrates the objective of the series of steps illustrated inFIGS. 3A-3F, which is cumulative sums304of the numerical values302. For the sake of the clarity in the following discussion, the numerical values302are all shown as being the same. In most cases, the numerical values302among which one value is to be chosen are going to vary. Additionally, the sum of the numerical values302of this example is greater than 1. In other examples, the sum of the numerical values302can be equal to 1.

In some examples, the numerical values302may have been generated in parallel, and thus are stored across different memory partitions as the numerical values302are output by an execution engine. In some examples, the numerical values302are evenly distributed across the memory partitions, such that, as best as possible, each partition has a same quantity of the numerical values302. In some examples, this may not be the case, for example because the numerical values302are not generated in sets of equal sizes, because the numerical values302are not evenly divisible by the number of available memory partitions, or for another reason. In various examples, the number of memory partitions used is equal to the number of execution units in the execution engine that is to perform the operations discussed below. For example, the execution engine may have 64 execution units. In some cases, not all the execution engines are available, or space in the memory partitions is not available, in which case fewer than all the execution engines (and corresponding memory partitions) can be used.

FIG. 3Billustrates a first step in generating the target cumulative sums304, and a first set of intermediate values306that is generated at this step. The intermediate values306inFIG. 3Bare cumulative sums on the set of numerical values in each memory partition. A cumulative sum is separately performed on each column, and can be performed in parallel by different execution units. As an example, in the first column310, the first value is added to zero, and the result (0.01) is stored in place of the first value. The second value is added to the previous sum (0.01+0.01) and stored in place of the second value. A third value would be added to this sum (0.01+0.02) and be stored in place of the third value, and so on to the sixteenth value in the set. The same steps are also performed in each of the second column312to the last column318. The execution engine can include an instruction called TensorCumulativeOp that can take as an argument a mathematical operation to perform in a cumulative fashion (e.g., addition, in the example ofFIG. 3B; other operations can include subtraction, multiplication, division, logical operators, and comparative operators).

In various examples, the cumulative sums can occur in parallel across the memory partitions. For example, 64 additions can occur at the same time (e.g., in the same clock cycle or set of clock cycles) with one addition being performed for each column. In this example, 16 iterations (e.g., 16 clock cycles or sets of clock cycles) occur in computing the intermediate values306.

In the example ofFIG. 3B, the intermediate values306replace the original numerical values302in the memory partitions (e.g., the numerical are overwritten with the intermediate values306). In other examples, the intermediate values306can be written to different locations in the memory partitions, or can be written to a separate set of memory partitions.

FIG. 3Cillustrates a second and third step in generating the cumulative sums304. In the second step, one cumulative sum330from each of the columns are copied to a separate memory partition. The cumulative sum330that is copied from each memory partition can be the one in the last index in each column (e.g., index16in the example ofFIG. 3C, with the indices starting at 0). The cumulative sum330in the last index is the sum of all the values in the column, and thus may be the largest sum in the column. To perform the copying, in some examples, the cumulative sums330from each of the columns can be copied to the set of memory registers. For example, an instructions for loading the registers in parallel with a value from each of the memory partitions can be used. The cumulative sums330can then be serially read from the registers, and written to the separate memory partition.

Once the cumulative sums330are copied to the separate memory partition, the third step is to perform another cumulative sum on these cumulative sums330to generate a second set of intermediate values332that includes the results. Similar to the first step, generating the second intermediate values332includes adding the first of the cumulative sums330to 0; adding the result of this sum to the second of the cumulative sums330; adding the result of this sum to the third of the cumulative sums330; and so on until the last of the cumulative sums330.

FIG. 3Dillustrates the fourth step in generating the cumulative sums304. In this step, the intermediate values332(e.g., the cumulative sums of the cumulative sums330from each column) are each copied to one of the memory partitions. Each of the intermediate values332is written to a partition that has an index that is one greater than the partition from which the value was originally obtained. For example, the first of the cumulative sums330that was used to compute the first of the intermediate values332was copied from the first column310, and thus this first intermediate value is written to the second column312. The last of the intermediate values332is not needed, and thus is discarded. Additionally, a value of 0 is written to the first column310, so that the next step can include identical operations on each of the columns.

To copy the intermediate values332to the memory partitions, the intermediate values332can first be copied to the set of registers, for example by serially reading each of the intermediate values332from the separate memory partition and into a different register of the set. Once the intermediate values332are loaded into the registers, the intermediate values332can then be written, in parallel, to the memory partitions. In various examples, this parallel writing can also include shifting the intermediate values332to the desired memory partitions.

FIG. 3Eillustrates a fifth step in generating the cumulative sums304. In this step, the intermediate values332generated inFIG. 3Dare added to each of the intermediate values306in the memory partitions. In this step, a cumulative sum is not performed; instead, individual sums are performed. For example, in the first column310, the value 0.0 is added to each of the set of numerical values in the first column310; in the second column312, the value 0.16 is added to each of the numerical values in the second column312; and so on until the last column318, where the value 10.08 is added to each of the numerical values in the last column318.

In various examples, the additions of this step can occur in parallel. For example, 64 additions can occur at the same time (e.g., in the same clock cycle or set of clock cycles), with one addition being performed per column. In this example, 16 iterations (e.g., 16 clock cycles or sets of clock cycles) occur, at the end of which the memory partitions are storing the cumulative sums304of the original numerical values302.

In the example ofFIG. 3E, the final cumulative sums304replace the intermediate values306in the memory partitions (e.g., the intermediate values306are overwritten by the cumulative sums304). In other examples, the cumulative sums304can be stored in different locations in the memory partitions, so that the intermediate values306are not overwritten. In some examples, the cumulative sums304can be written to entirely different memory partitions.

FIGS. 4A-4Cillustrate an example of steps that can be performed to select a numerical value based on a multinomial distribution. The illustrated steps can be performed, for example, by the integrated circuit components illustrated inFIG. 2. The steps illustrated inFIGS. 4A-4Cstart with a set of cumulative sums404computed from a set of numerical values, as illustrated inFIGS. 3A-3E. As in that example, the cumulative sums404ofFIGS. 4A-4Care arranged in columns (a first column410, a second column412, and a last column418, with a number of additional columns between the second column412and the last column418that are not illustrated), where each column represents a set of numerical values that is stored in a different memory bank or partition. Each memory bank or partition is independently accessible by an execution unit of an execution engine, and the execution units can perform various operations on the data stored in each partition. The execution engine or another component can include a set of registers for moving data between the memory partitions.

FIG. 4Aillustrates a first step in selecting a particular value. The particular value is selected using a random number440(0.175, in the illustrated example). The random number440can be generated, for example, by random number generation circuit that can generate uniformly distributed random numbers. In the step illustrated inFIG. 4A, the random number440is compared against each of the cumulative sums404to determine whether the random number440is greater than or equal to each of the cumulative sums404. In cases where the random number440is greater than or equal to a particular cumulative sum, the cumulative sum is replaced with a value of 1. In cases where the random number440is less than a particular cumulative sum, the cumulative sum is replaced with a value of 0.

The comparisons can occur in parallel. For example, in the illustrated example, 64 comparison can occur at the same time, with one comparison being performed for every memory partition. In this example, 16 iterations of 64 comparisons occur. As a result of the comparisons, the first column410includes all 1 values, the second column412includes a 1 value in the first position and 0 values in all other partitions, and all other partitions until the last column418include only 0 values.

In the example ofFIG. 4A, the results of the comparisons replace the cumulative sums404in the memory partitions. In other examples, the results can be placed in a different location in each partition, or in entirely different partitions.

FIG. 4Billustrates a second step in selecting a particular value. In this step, a summation is computed over the comparison results in each memory partition, meaning that each of the comparison results in one column are added together. The summations for each column can occur in parallel, with (in this example) 64 additions happening at the same time. In this example, 16 iterations of 64 parallel additions occur in obtaining the final result, which is 64 sums.

The result of the summations in the step illustrated inFIG. 4Bis a counting occurrences of 1 values in each memory partition.FIG. 4Cillustrates use of these counts430to determine the index of the original numerical value (e.g., the numerical values illustrated inFIG. 3A), that is not greater than the random number440. The index can be determined by determining a count of occurrences of 1 values across each of the memory partitions, which can be determined by summing the counts430computed for each memory partition in the previous step. To sum these counts430, the counts430can first be copied from the individual partitions to one partition. For example, the counts430can be copied in parallel to temporary storage registers, then be serially written to the one memory partition. Once the counts430have been copied to the one memory partition, a sum432can be computed over all the counts430. The resulting sum, provides an index (17, in this example). The index can be used for further operations, and/or the index can be used to obtain one of the original numerical values.

In some examples, instead of the summation illustrated byFIG. 4B, a cumulative sum on each column can be performed, similar to the cumulative sum that is performed inFIG. 3B. In these examples, the cumulative sums would result in the last index of each column storing a sum of all of the values in the column. The last index of each column can then be copied to a separate partition, in a similar fashion as is illustrated inFIG. 4C. Once the sums from the individual columns are in one partition, the sums can then be added together, as in the step ofFIG. 4C, or a cumulative sum can be computed over the sums, with the last sum (e.g., the sum in the last index) determining the index.

FIG. 5includes a flowchart illustrating an example of a process500for determining cumulative sums for a numerical values that represent probabilities in a multinomial distribution. The process500can be executed, for example, by an integrated circuit device. For example, the steps of the process500can be implemented as program instructions for the integrated circuit device.

The process500takes as input X[m] [n]502, which is a two dimensional array of numerical values. The first index of X indicates a memory partition, and the second index of X indicates a particular value in each memory partition. As discussed previously, each memory partition can be read and written by an execution unit of an execution engine, and one execution unit is not able to access the memory partition of another execution unit. Data from any partition, however, can be written to temporary registers, which can store a limited amount of data (e.g., one data word per register). In the example ofFIG. 5, there are m memory partitions each storing n numerical values. In other examples, the memory partitions can be storing different numbers of values. In these examples, the process500is essentially the same.

At the start of the process500, the values X[m] [n]502have previously been stored in the memory partitions. For example, the values X[m][n] may have been generated by a computation performed by the integrated circuit device, where the computation includes parallel generation of the values and parallel storing of the values into the memory partitions. As another example, the values may have been read into the integrated circuit device's internal memory from an external memory, such as host or system memory.

At step504, process500includes performing cumulative sums in each partition. For example, given an index i that is incremented from 0 to m and an index j that is incremented from 0 to n, the values in X are modified as follows: X[i][j]=sum X[i][0] to X[i][j]. In this example, X[i][0] to X[i][j] means X[i][0]=0+X[i][0], X[i][1]=0+X[i][0]+X[i][1], X[i][2]=0+X[i][1]+X[i][2], and so on. Also in this example, the cumulative sums for each index i can be performed in parallel, since there is no dependency between the result of summing the values in one partition on summing the values in any other partition. Thus, the amount of time to perform step504is approximately equal to n times the amount of time to perform one sum. In this example, the values in X are overwritten. In other examples, the cumulative sums can be stored in another location, either in the same memory partitions or in different memory partitions.

At step506, the process500includes copying from each partition the cumulative sum at the last index X[i][n], and writing these values to a separate partition. For example, given an index i that is incremented from 0 to m, the value X[i][n] is copied to a Y2[i] in the separate partition. In this example, Y2 is a single dimension array having m indices, which is in one partition (e.g., the separate partition). In various examples, step506can be performed first by reading X[i] [n] from each partition in parallel into the temporary registers (a single-step operation), and then serially writing the registers from the temporary registers to the separate memory partition (an m step operation).

At step508, the process500includes performing a cumulative sum on the values in Y2. For example, given an index i that is incremented from 0 to m, the values of Y2 are modified as follows: Y2[i]=sum Y2[0] to Y2[i]. That is, Y2[0]=0+Y2[0], Y2[1]=0+Y2[0]+Y2[1], Y2[2]=0+Y2[0]+Y2[1]+Y2[2], and so on. These sums are computed on data in the same partition, and thus the amount of time for performing step508is m times the amount of time to perform one addition. The end result of step508is a horizontal sum across the partitions of the largest value in each of the partitions, computed in a separate partition in view to bypass the boundaries between the partitions.

At step510, the process500includes copying the cumulative sums computed in step508back to the original m partitions, shifted by 1 index. For example, given an index i that is incremented from 0 to m, Y2[i] is copied to Y3[i+1]. Y3 is a one dimensional array whose first index indicates a partition. In this example, Y3[i] indicates a same partition as is indicated by X[i]. The Y2 values are copied into the partitions shifted by one partition so that cumulative sums across the partitions can now be calculated.

At step512, the process500includes dropping the largest of the cumulative sums computed at step508, Y2[m]. This value is equal to the largest cumulative sum that will be computed, and thus is not needed for computing the cumulative sums across the partitions.

At step514, the process500includes setting Y3[0] equal to 0. This is done so that the next step can be performed in parallel on each of the partitions, without needing to treat partition zero differently.

At step516, the process500includes adding one of the cumulative sums computed at step510to each value in a partition. For example, given an index i that is incremented from 0 to m and an index j that is incremented from 0 to n, the values in X are modified as follows: X[i][j]=X[i][j]+Y3[i]. In this example, the additions in each partition can occur in parallel, such that m additions can be performed at the same time. The amount of time performing step516takes is thus n times the amount of time for performing one addition.

In this example, the values in X are replaced through the operation of step516. In other examples, the cumulative sums can be stored in different locations in the same memory partitions or in different memory partitions, so that the values in X before step516is completed are still available.

When step516is complete, X will be storing cumulative sums of the original X[m][n]502with which the process500started. The values in X can next be used to randomly select one of the original X[m][n]502values.

FIG. 6includes a flowchart illustrating an example of a process600for using a set of cumulative sums to determine an index, which can then be used to obtain a particular numerical value. The process600can be executed, for example, by an integrated circuit device. For example, the steps of the process600can be implemented as program instructions for the integrated circuit device.

The process600takes as input X[m] [n]602, which is a two dimensional array of cumulative sums computed according to the process illustrated inFIG. 5. The first index of X[m][n]602ofFIG. 6indicates a memory partition, and the second index indicates a particular cumulative sum in a memory partition. In various examples, the values in X[m][n]602were previously stored in the memory partitions when the process600begins.

The process600also takes as input a random value k604. The k604value can be a number that is between 0 and the largest cumulative sum (e.g., the value stored X[m][n]). The k604value can be generated using a random number generator configured to output evenly distributed random numbers. In some examples, k604can be scaled to the range of values covered by the original numerical values. For example, k604may be a 16-bit, 32-bit, 64-bit, or other size random value, and the original numerical values may be within a range of 0 to 100. In this example, k604can be scaled to be between 0 and 100.

The k604indicates the particular index to be selected. The steps of the process600is how the index is determined.

At step606, the process600includes comparing k604against each value in X. For example, given an index i that is incremented form 0 to m and an index j that is incremented from 0 to n, the values in X are modified as follows: X[i][j]=1 if k≥X[i][j]; else 0. In this example, when k604is greater than or equal to a value at X[i][j], then X[i][j] is set equal to 1, and when k604is less than the value at X[i][j], then X[i][j] is set equal to 0. The values in X are replaced by 1 or 0 in this example. In other examples, results of the comparisons can be stored in different locations in the memory partitions, or in different memory partitions.

The comparisons of values in different memory partitions can occur in parallel. For example, m comparisons can occur at the same time. Performing step606thus takes n times the amount of time required by one comparison.

At step608, the process600includes summing the comparison results in each of the memory partitions. For example, given an index i that is incremented from 0 to m, the values in X can be modified as follows: X[i][n]=sum X[i][0] to X[i] [n]. In this example, the sum is stored in the last index X[i] [n]. In other examples, the sum can be stored elsewhere in the partition i, or in another partition, so that the value of X[i][n] is not modified. Once this operation is complete, each X[i] [n] will be storing a count of the number of one values in the partition i.

The count of ones produced at step608is per partition. The remaining steps are for determining the number of ones across partitions. At step610, the process600includes copying the sums from each partition into a separate partition. For example, given an index i that is incremented from 0 to m, the values X[i][n] can be copied to Y[i] in the separate partition. Y is a one dimensional array in the separate partition, having m indices.

Step612of the process600includes summing the values in the separate partition. For example, the values in Y can modified as follows: Y[m]=sum Y[0] to Y[m].

Once step612is completed, a count of all the ones determined at step606is obtained. At step614, this count can be determined by reading the value at Y[m]. This value indicates an index of a particular value from the original numerical values (X[m][n]502inFIG. 5) that is less than or equal k604and not greater than k604(which would be the case for the value at the index Y[m]+1). In various examples, the value at Y[m] can be used for additional computations, and/or to obtain a value from the original numerical values.

FIG. 7includes a flowchart illustrating an example of a process700for selecting a value based on a multinomial distribution. The example process700can be implemented by an integrated circuit device, such as a device that includes memory banks that can store the data operated on and/or generated by the steps of the process700and an execution engine that can perform the steps of the process700. In some examples, the steps of the process700can be implemented as program instructions for an integrated circuit device.

At step702, the process700includes computing first cumulative sums on numerical values stored in memory banks of the integrated circuit device. The sets of the numerical values are each stored in different memory banks, each memory bank having a bank identifier. Each first cumulative sum is computed in parallel on a respective set of the numerical values in a respective memory bank. In some examples, the numerical values each indicate a probability of being the particular numerical value determined at step714.

In some examples, the integrated circuit device is configured such that data cannot be read from one memory bank and be written directly to another memory bank. In some examples, can be read from one memory bank and written to another memory bank indirectly using a register of the integrated circuit device.

In some examples, the process700further includes performing a computation that produces the numerical values, such as softmax or another function that produces a range of probabilities.

At step704, the process700includes computing second cumulative sums on a set of the first cumulative sums, the set of the first cumulative sums including a first cumulative sum from each of the memory banks. In some examples, the first cumulative sum that is used for computing the second cumulative sums is a last of the cumulative sums in each of the memory banks, where the last of the cumulative sums can be determined from the indices of the cumulative sums in a memory bank. In some examples, the process700includes copying, before performing the second cumulative sum, the set of first cumulative sums from the memory banks to a separate memory bank. In these examples, the cumulative sum is performed on the data in the separate memory bank (e.g., the set of first cumulative sums).

At step706, the process700includes adding to each first cumulative sum a second cumulative sum from the second cumulative sums. The second cumulative sum that is added to each respective set of the first cumulative sums in a memory bank is from a memory bank with a bank identifier that is one less than a bank identifier for the memory bank storing the respective set of the first cumulative sums. That is, the second cumulative sums are shifted by one from the memory banks from which the values used to compute the second cumulative sums were copied. The shifting enables the cumulative sums to be carried across from one memory bank to the next. The adding can occur in parallel on the respective set of the first cumulative sums in the respective memory bank.

At step708, the process700includes comparing a random value generated by the integrated circuit device against each of the first cumulative sums. The comparing includes determining whether the random value is greater than or equal to each of the first cumulative sums. In some examples, the random value is generated using a random number generator that produces evenly distributed random numbers. In some examples, the numerical values from step702are within a range having a minimum value and a maximum value. In these examples, the random value is scaled to be greater than or equal to the minimum value and less than or equal to the maximum value.

At step710, the process700includes storing results of the comparing in the memory banks, wherein sets of the results are each stored in different memory banks. The results can be stored in a similar arrangement as the original numerical values, with each memory bank having one result for each numerical value stored in the memory bank.

At step712, the process700includes computing a first set of sums on the sets of the results. The first set of sums includes a sum for each of the sets of the results, meaning that a sum is computed over each set of results in each memory bank. Each of the first set of sums can be computed in parallel on a respective set of the results in a respective memory bank.

At step714, the process700includes computing a second sum on the first set of sums, meaning that each of the first set of sums is added together to produce the second sum. The second sum is an index of a particular numerical value of the numerical values in step702. In some examples, the process700includes copying, before computing the second sum, the first set of sums the memory banks to a separate, single memory bank. In these examples, the second sum is performed on data in the separate memory bank (e.g., the first set of sums).

At step716, the process700includes outputting the index.

In some examples, the process700further includes performing a computation using the index. In some examples, the process700further includes obtaining the numerical value that corresponds to the index, for example by using the index to determine the memory bank where the numerical value is located, and then the address where the numerical value can be found within the memory bank.

FIG. 8is a block diagram illustrating an example of an integrated circuit device that can be used to select a value based on a multinomial distribution. The example ofFIG. 8illustrates an accelerator engine802. In various examples, the accelerator engine802, for a set of input data (e.g., input data850), can execute computations using a processing engine array810, an activation engine816, and/or a pooling engine818. In some examples, the example accelerator engine802may be an integrated circuit component of a processor, such as a neural network processor. The processor may have other integrated circuit components, including additional accelerator engines.

In various implementations, the memory subsystem804can include multiple memory banks814. In these implementations, each memory bank814can be independently accessible, meaning that the read of one memory bank is not dependent on the read of another memory bank. Similarly, writing to one memory bank does not affect or limit writing to a different memory bank. In some cases, each memory bank can be read and written at the same time. Various techniques can be used to have independently accessible memory banks814. For example, each memory bank can be a physically separate memory component that has an address space that is separate and independent of the address spaces of each other memory bank. In this example, each memory bank may have at least one read channel and may have at least one separate write channel that can be used at the same time. In these examples, the memory subsystem804can permit simultaneous access to the read or write channels of multiple memory banks. As another example, the memory subsystem804can include arbitration logic such that arbitration between, for example, the outputs of multiple memory banks814can result in more than one memory bank's output being used. In these and other examples, though globally managed by the memory subsystem804, each memory bank can be operated independently of any other.

Having the memory banks814be independently accessible can increase the efficiency of the accelerator802. For example, values can be simultaneously read and provided to each row of the processing engine array810, so that the entire processing engine array810can be in use in one clock cycle. As another example, the memory banks814can be read at the same time that results computed by the processing engine array810are written to the memory subsystem804. In contrast, a single memory may be able to service only one read or write at a time. With a single memory, multiple clock cycles can be required, for example, to read input data for each row of the processing engine array810before the processing engine array810can be started.

In various implementations, the memory subsystem804can be configured to simultaneously service multiple clients, including the processing engine array810, the activation engine816, the pooling engine818, and any external clients that access the memory subsystem804over a communication fabric820. In some implementations, being able to service multiple clients can mean that the memory subsystem804has at least as many memory banks as there are clients. In some cases, each row of the processing engine array810can count as a separate client. In some cases, each column of the processing engine array810can output a result, such that each column can count as a separate write client. In some cases, output from the processing engine array810can be written into the memory banks814that can then subsequently provide input data for the processing engine array810. As another example, the activation engine816and the pooling engine818can include multiple execution channels, each of which can be separate memory clients. The memory banks814can be implemented, for example, using static random access memory (SRAM).

In various examples, the memory subsystem804can include a set of registers830for temporary storage of data. The memory subsystem804can include, for example, a register for each of the memory banks814or for a subset of the memory banks814. In some examples, there is a one-to-one correspondence between each register and a memory bank, such that data can be moved between one register and a corresponding memory bank, and cannot be moved between the register and a different memory bank. In these and other examples, the memory subsystem804may be able to read values from each of the registers830, independently of the registers' association with the memory banks814. For example, the registers830may be chained, such that a value can be read from one register and be written to a neighboring register. Alternatively or additionally, the memory subsystem804can include circuitry that can read from one or more of the registers830and can write to one or more of the registers830.

Using the registers830, the memory subsystem804can, for example, copy data from a set of memory banks814and store the data in the registers830. In this example, the memory subsystem804can later copy the data from the registers830back into the memory banks814. The registers830may support parallel and serial reads or writes. For example, in parallel mode, the memory subsystem804can read two or more of the memory banks814at the same time, and store the data that is read into respective registers. In this example, the memory subsystem804can also copy data from one or more of the registers into respective memory banks. As a further example, in serial mode, the memory subsystem804can read multiple values from one memory bank and store the values into the registers830, with each value being stored in a different register. In this example, the memory subsystem804can also copy values from each of two or more of the registers830, and write these values to one memory bank. As discussed further below, the memory subsystem804can use parallel and serial operations to move data between the memory banks814.

In various implementations, the memory subsystem804can include control logic. The control logic can, for example, keep track of the address spaces of each of the memory banks814, identify memory banks814to read from or write to, and/or move data between the memory banks814and a set of registers830. In some implementations, memory banks814can be hardwired to particular clients. For example, a set of memory banks814can be hardwired to provide values to the rows of the processing engine array810, with one memory bank servicing each row. As another example, a set of memory banks can be hired wired to receive values from columns of the processing engine array810, with one memory bank receiving data for each column.

In various examples, the registers830can, alternatively, be located in a different component of the accelerator, such as, for example, the pooling engine818. In this example, the pooling engine818can include control logic for moving data into or out of the registers830. Other examples of components of the accelerator where the registers can be located include the activation engine816, the results buffer812, or another component that is not illustrated here.

The processing engine array810is the computation matrix of the example accelerator802. The processing engine array810can, for example, execute parallel integration, convolution, correlation, and/or matrix multiplication, among other things. The processing engine array810includes multiple processing engines811, arranged in rows and columns, such that results output by one processing engine811can be input directly into another processing engine811. Processing engines811that are not on the outside edges of the processing engine array810thus can receive data to operate on from other processing engines811, rather than from the memory subsystem804.

In various examples, the processing engine array810uses systolic execution, in which data arrives at each processing engine811from different directions at regular intervals. In some examples, input data can flow into the processing engine array810from the left and weight values can be loaded at the top. In some examples weights and input data can flow from the left and partial sums can flow from top to bottom. In these and other examples, a multiply-and-accumulate operation moves through the processing engine array810as a diagonal wave front, with data moving to the right and down across the array. Control signals can be input at the left at the same time as weights, and can flow across and down along with the computation.

In various implementations, the number of columns in the processing engine array810determines the computational capacity of the processing engine array810, and the number of rows determines the required memory bandwidth for achieving maximum utilization of the processing engine array810. The processing engine array810can have, for example, 64 columns and 428 rows, or some other number of columns and rows.

An example of a processing engine811is illustrated inFIG. 8in an inset diagram. As illustrated by this example, a processing engine811can include a multiplier-accumulator circuit. Inputs from the left can include, for example, input data i and a weight value w, where the input data is a value taken from either a set of input data or a set of intermediate results, and the weight value is from a set of weight values that connect one layer of the neural network to the next. A set of input data can be, for example, an image being submitted for identification or object recognition, an audio clip being provided for speech recognition, a string of text for natural language processing or machine translation, or the current state of a game requiring analysis to determine a next move, among other things. In some examples, the input data and the weight value are output to the right, for input to the next processing engine811.

In the illustrated example, an input from above can include a partial sum, p_in, provided either from another processing engine811or from a previous round of computation by the processing engine array810. When starting a computation for a new set of input data, the top row of the processing engine array810can receive a fixed value for p_in, such as zero. As illustrated by this example, i and w are multiplied together and the result is summed with p_in to produce a new partial sum, p_out, which can be input into another processing engine811. Various other implementations of the processing engine811are possible.

Outputs from the last row in the processing engine array810can be temporarily stored in the results buffer812. The results can be intermediate results, which can be written to the memory banks814to be provided to the processing engine array810for additional computation. Alternatively, the results can be final results, which, once written to the memory banks814can be read from the memory subsystem804over the communication fabric820, to be output by the system.

In some implementations, the accelerator802includes an activation engine816. In these implementations, the activation engine816can combine the results from the processing engine array810into one or more output activations. For example, for a convolutional neural network, convolutions from multiple channels can be summed to produce an output activation for a single channel. In other examples, accumulating results from one or more columns in the processing engine array810may be needed to produce an output activation for a single node in the neural network. In some examples, activation engine816can be bypassed.

In various examples, the activation engine816can include multiple separate execution channels. In these examples, the execution channels can correspond to the columns of the processing engine array810, and can perform an operation on the outputs of a column, the result of which can be stored in the memory subsystem804. In these examples, the activation engine816may be able to perform between 1 and n parallel computations, where n is equal to the number of columns in the processing engine array810. In some cases, one or more of the computations can be performed simultaneously. Examples of computations that each execution channel can perform include exponentials, squares, square roots, identities, binary steps, bipolar steps, sigmoidals, and ramps, among other examples.

In some implementations, the accelerator802can include a pooling engine818. Pooling is the combining of outputs of the columns of the processing engine array810. Combining can include for example, computing a maximum value, a minimum value, an average value, a median value, a summation, a multiplication, or another logical or mathematical combination. In various examples, the pooling engine818can include multiple execution channels that can operating on values from corresponding columns of the processing engine array810. In these examples, the pooling engine818may be able to perform between 1 and n parallel computations, where n is equal to the number of columns in the processing engine array810. In various examples, execution channels of the pooling engine818can operate in parallel and/or simultaneously. In some examples, the pooling engine818can be bypassed.

Herein, the activation engine816and the pooling engine818may be referred to collectively as execution engines. The processing engine array810is another example of an execution engine. Another example of an execution engine is a Direct Memory Access (DMA) engine, which may be located outside the accelerator802.

Input data850can arrive over the communication fabric820. The communication fabric820can connect the accelerator802to other components of a processor, such as a DMA engine that can obtain input data850from an Input/Output (I/O) device, a storage drive, or a network interface. The input data850can be, for example one-dimensional data, such as a character string or numerical sequence, or two-dimensional data, such as an array of pixel values for an image or frequency and amplitude values over time for an audio signal. In some examples, the input data850can be three-dimensional, as may be the case with, for example, the situational information used by a self-driving car or virtual reality data. In some implementations, the memory subsystem804can include a separate buffer for the input data850. In some implementations, the input data850can be stored in the memory banks814when the accelerator802receives the input data850.

In some examples, the accelerator802can implement a neural network processing engine. In these examples, the accelerator802, for a set of input data850, can execute a neural network to perform a task for which the neural network was trained. Executing a neural network on a set of input data can be referred to as inference or performing inference.

The weights for the neural network can be stored in the memory subsystem804, along with input data850on which the neural network will operate. The neural network can also include instructions, which can program the processing engine array810to perform various computations on the weights and the input data. The instructions can also be stored in the memory subsystem804, in the memory banks814or in a separate instruction buffer. The processing engine array810can output intermediate results, which represent the outputs of individual layers of the neural network. In some cases, the activation engine816and/or pooling engine818may be enabled for computations called for by certain layers of the neural network. The accelerator802can store the intermediate results in the memory subsystem804for inputting into the processing engine array810to compute results for the next layer of the neural network. The processing engine array810can further output final results from a last layer of the neural network. The final results can be stored in the memory subsystem804and then be copied out to host processor memory or to another location.

FIG. 9includes a block diagram that illustrates an example of an acceleration engine900. The acceleration engine900is an example of an integrated circuit that can include one or more accelerators902a-902nthat may be similar to the accelerator illustrated inFIG. 8.

In the example ofFIG. 9, the acceleration engine900includes multiple accelerators902a-902n, each of which can perform a set of operations. In various examples, the accelerators902a-902nfor particular types of operations, so that the accelerators902a-902ncan perform the operations much faster than when similar operations are performed by a general purpose processor. In various examples, to perform a set of operations, input data on which the operations are to be performed must first be moved into the accelerators902a-902n. Additionally, in some cases, program code is also moved into the accelerators902a-902n, which programs the operations that the accelerators902a-902nwill perform on the data. In the illustrated example, the acceleration engine900includes n accelerators902a-902n. Examples of accelerators that can be included in the acceleration engine900include graphics accelerators, floating point accelerators, neural network accelerators, and others. In various examples, the accelerators902a-902ncan each be the same (e.g., each of the is a graphics accelerator) or can be different (e.g., the accelerators902a-902ninclude a graphics accelerator, a floating point accelerator, and neural network accelerator).

The example acceleration engine900further includes DRAM controllers942a-942kfor communicating with an external memory. The external memory is implemented, in this example, using DRAM930. In the illustrated example, the acceleration engine900includes k DRAM controllers942a-942k, each of which may be able to communicate with an independent set of banks of DRAM. In other examples, other types of RAM technology can be used for the external memory. The DRAM controllers942a-942kcan also be referred to as memory controllers.

In various examples, input data and/or program code for the accelerators902a-902ncan be stored in the DRAM930. Different programs can cause the accelerators902a-902nto perform different operations. For example, when one of the accelerators is a neural network accelerator, one program can configure the neural network accelerator to perform speech recognition while another program can configure the neural network accelerator to perform image recognition. In various examples, different accelerators902a-902ncan be programmed with different programs, so that each performs a different set of operations. In various examples, the processors948a-948scan manage moving of program code from the DRAM930to the accelerators902a-902n.

The example acceleration engine900further includes I/O controllers944a-944pfor communicating with I/O devices932in the system. The acceleration engine900can communicate with I/O devices over, for example, a processor bus. In some examples, the processor bus can be implemented using Peripheral Component Interconnect (PCI) and/or a variation of the PCI bus protocol. The processor bus can connect the acceleration engine900to I/O devices such as, for example, input and output devices, memory controllers, storage devices, and/or network interface cards, among other things. In some examples, the I/O controllers944-944pcan enable the acceleration engine900to act as an I/O device for a host processor. For example, the acceleration engine900can be the recipient of input data from the host processor, and a command indicating an operation to be performed on the input data (e.g., a particular computation or analysis). In the illustrated example, the acceleration engine900includes p I/O controllers944a-944p, each of which may include a separate root complex and may communicate with a separate set of I/O devices932. In other examples, other standardized bus protocols, such as Ultra Path Interconnect (UPI) can be used for the host bus. In other examples, a proprietary bus protocol can be used.

Movement of data in the acceleration engine900can be managed by one or more processors948a-948s, which can also be referred to as data management processors. In the example ofFIG. 9, the acceleration engine900includes s processors948a-948sincorporated into (e.g., on the same silicon die) the device. In other examples, the processors948a-948scan be external to the acceleration engine900(e.g., on a different die and/or in a different package). In some examples, the processors948a-948scan manage the movement of data from I/O devices932to the accelerators902a-902nor the DRAM930. For example, input data may be located at an I/O device932or in processor memory, and the processors948a-948scan move the input from the I/O device932or processor memory into an accelerator or into DRAM930. As another example, program code for the accelerators902a-902nmay be located on an I/O device932or in processor memory.

The example acceleration engine900further includes DMA engines946a-946dthat can move data between the accelerators902a-902n, DRAM controllers942a-942k, and I/O controllers944a-944p. In the illustrated example, the acceleration engine900includes d DMA engines946a-946d. In some implementations, the DMA engines946a-946dcan be assigned to specific tasks, such as moving data from the DRAM controllers942a-942dto the accelerators902a-902n, or moving data between the I/O controllers944a-944pand the accelerators902a-902n. These tasks can be assigned, for example, by enqueueing descriptors with the DMA engines946a-946d, where a descriptor identifies an address for a block of data and an operation (e.g., a read or a write) to perform. A descriptor, for example, can direct a DMA engine to instruct a DMA controller to read a block of data from DRAM930. A descriptor can, as a further example, instruct the DMA engine to write data, read by the DMA controller, to an accelerator. Further descriptors can be used to move data from an accelerator to DRAM930.

In various examples, each of the processors948a-948scan be responsible for managing the data movement for a different accelerator. In some examples, a processor may manage the data movement for more than one accelerator. Similarly, in various examples, each of the processors948a-948scan be assigned to one or more DMA engines946a-946d. In these and other examples, associations between processors948a-948s, accelerators902a-902n, and DMA engines946a-946dis determined by program code being executed by each respective processor.

In the example acceleration engine900, the various components can communicate over a chip interconnect920. The chip interconnect920primarily includes wiring for routing data between the components of the acceleration engine900. In some cases, the chip interconnect920can include a minimal amount of logic, such as multiplexors to control the direction of data, flip-flops for handling clock domain crossings, and timing logic.

FIG. 10includes a block diagram that illustrates an example of a host system1000in which an acceleration engine1060can be used. The acceleration engine1060ofFIG. 10is an example of a device that can include one or more accelerator engines such as is illustrated inFIG. 9. The example host system1000ofFIG. 10includes the acceleration engine1060, a host processor1072, DRAM1030or processor memory, I/O devices1032, and support systems1074. In various implementations, the host system1000can include other hardware that is not illustrated here.

The host processor1072is a general purpose integrated circuit that is capable of executing program instructions. In some examples, the host processor1072can include multiple processing cores. A multi-core processor may include multiple processing units within the same processor In some examples, the host system1000can include more than one host processor1072. In some examples, the host processor1072and the acceleration engine1060can be one chip, such as, one or more integrated circuits within the same package.

In various examples, the host processor1072can communicate with other components in the host system1000over one or more communication channels. For the example, the host system1000can include a host processor bus, which the host processor1072can use to communicate with the DRAM1030, for example. As another example, the host system1000can include an I/O bus, such as a PCI-based bus, over which the host processor1072can communicate with the acceleration engine1060and/or the I/O devices1032, for example. In various examples, the host system1000can, alternatively or additionally, include other communication channels or busses, such as serial busses, power management busses, storage device busses, and so on.

In some examples, software programs executing on the host processor1072can receive or generate input for processing by the acceleration engine1060. In some examples, the programs can select an appropriate neural network to execute for a given input. For example, a program may be for language translation, and can select one or more neural networks capable of speech recognition and/or machine translation. In these and other examples, the programs can configure the acceleration engine1060with the neural network to execute, and/or can select a neural network processing engine on the acceleration engine1060that has previously been configured to execute the desired neural network. In some examples, once the acceleration engine1060has started inference on input data, the host processor1072can manage the movement of data (such as weights, instructions, intermediate results, results of conditional layers, and/or final results) into or out of the acceleration engine1060.

In some examples, a software program that is using the acceleration engine1060to conduct inference can read the result from a conditional layer from the acceleration engine1060and/or from a storage location, such as in DRAM1030. In these examples, the program can determine what action the neural network should take next. For example, the program can determine to terminate the inference. As another example, the program can determine to change the direction of the inference, which can be translated by lower level code and/or the neural network processor to a next layer to execute. In these and other examples, the execution flow of the neural network can be coordinate by software.

The DRAM1030is memory that is used by the host processor1072for storage of program code that the host processor1072is in the process of executing, as well as values that are being operated on. In some examples, the data for a neural network (e.g., weight values, instructions, and other data) can be all or partially stored in the DRAM1030. DRAM is a common term for processor memory, and though DRAM is volatile memory, processor memory can be volatile and/or non-volatile. Though not illustrated here, the host system1000can include other volatile and non-volatile memories for other purposes. For example, the host system1000can include a Read-Only Memory (ROM) that stores boot code for booting the host system1000at power on, and/or Basic Input/Output System (BIOS) code.

Though not illustrated here, the DRAM1030can store instructions for various programs, which can be loaded into and be executed by the host processor1072. For example, the DRAM1030can be storing instructions for an operating system, one or more data stores, one or more application programs, one or more drivers, and/or services for implementing the features disclosed herein.

The operating system can manage and orchestrate the overall operation of the host system1000, such as scheduling tasks, executing applications, and/or controller peripheral devices, among other operations. In some examples, a host system1000may host one or more virtual machines. In these examples, each virtual machine may be configured to execute its own operating system. Examples of operating systems include Unix, Linux, Windows, Mac OS, iOS, Android, and the like. The operating system may, alternatively or additionally, be a proprietary operating system.

The data stores can include permanent or transitory data used and/or operated on by the operating system, application programs, or drivers. Examples of such data include web pages, video data, audio data, images, user data, and so on. The information in the data stores may, in some examples, be provided over the network(s) to user devices. In some cases, the data stores may additionally or alternatively include stored application programs and/or drivers. Alternatively or additionally, the data stores may store standard and/or proprietary software libraries, and/or standard and/or proprietary application user interface (API) libraries. Information stored in the data stores may be machine-readable object code, source code, interpreted code, or intermediate code.

The drivers can include programs that provide communication between components in the host system1000. For example, some drivers can provide communication between the operating system and peripheral devices or I/O devices1032. Alternatively or additionally, some drivers may provide communication between application programs and the operating system, and/or application programs and peripheral devices accessible to the host system1000. In many cases, the drivers can include drivers that provide well-understood functionality (e.g., printer drivers, display drivers, hard disk drivers, Solid State Device drivers, etc.). In other cases, the drivers may provide proprietary or specialized functionality.

The I/O devices1032can include hardware for connecting to user input and output devices, such as keyboards, mice, pens, tablets, voice input devices, touch input devices, displays or monitors, speakers, and printers, among other devices The I/O devices1032can also include storage drives and/or network interfaces for connecting to a network1080. For example, the host system1000can use a network interface to communicate with storage devices, user terminals, other computing devices or servers, and/or other networks, among various examples.

In various examples, one or more of the I/O devices1032can be storage devices. In these examples, the storage device include non-volatile memory and can store program instructions and/or data. Examples of storage devices include magnetic storage, optical disks, solid state disks, flash memory, and/or tape storage, among others. The storage device can be housed in the same chassis as the host system1000or may be in an external enclosure. A storage device can be fixed (e.g., attached by screws) or removable (e.g., having a physical release mechanism and possibly a hot-plug mechanism).

Storage devices, the DRAM1030, and any other memory component in the host system1000are examples of computer-readable storage media. Computer-readable storage media are physical mediums that are capable of storing data in a format that can be read by a device such as the host processor1072. Computer-readable storage media can be non-transitory. Non-transitory computer-readable media can retain the data stored thereon when no power is applied to the media. Examples of non-transitory computer-readable media include ROM devices, magnetic disks, magnetic tape, optical disks, flash devices, and solid state drives, among others. as used herein, computer-readable storage media does not include computer-readable communication media.

In various examples, the data stored on computer-readable storage media can include program instructions, data structures, program modules, libraries, other software program components, and/or other data that can be transmitted within a data signal, such as a carrier wave or other transmission. The computer-readable storage media can, additionally or alternatively, include documents, images, video, audio, and other data that can be operated on or manipulated through the use of a software program.

In various examples, one or more of the I/O devices1032can be PCI-based devices. In these examples, a PCI-based I/O device includes a PCI interface for communicating with the host system1000. The term “PCI” or “PCI-based” may be used to describe any protocol in the PCI family of bus protocols, including the original PCI standard, PCI-X, Accelerated Graphics Port (AGP), and PCI-Express (PCIe) or any other improvement or derived protocols that are based on the PCI protocols discussed herein. The PCI-based protocols are standard bus protocols for connecting devices, such as a local peripheral device, to a host device. A standard bus protocol is a data transfer protocol for which a specification has been defined and adopted by various manufacturers. Manufacturers ensure that compliant devices are compatible with computing systems implementing the bus protocol, and vice versa. As used herein, PCI-based devices also include devices that communicate using Non-Volatile Memory Express (NVMe). NVMe is a device interface specification for accessing non-volatile storage media attached to a computing system using PCIe.

A PCI-based device can include one or more functions. A “function” describes the hardware and/or software of an operation that may be provided by the PCI-based device. Examples of functions include mass storage controllers, network controllers, display controllers, memory controllers, serial bus controllers, wireless controllers, and encryption and decryption controllers, among others. In some cases, a PCI-based device may include more than one function. For example, a PCI-based device may provide a mass storage controller and a network adapter. As another example, a PCI-based device may provide two storage controllers, to control two different storage resources. In some implementations, a PCI-based device may have up to eight functions.

In some examples, the PCI-based device can include single-root I/O virtualization (SR-IOV). SR-IOV is an extended capability that may be included in a PCI-based device. SR-IOV allows a physical resource (e.g., a single network interface controller) to appear as multiple virtual resources (e.g., sixty-four network interface controllers). Thus, a PCI-based device providing a certain functionality (e.g., a network interface controller) may appear to a device making use of the PCI-based device to be multiple devices providing the same functionality. The functions of an SR-IOV-capable storage adapter device may be classified as physical functions (PFs) or virtual functions (VFs). Physical functions are fully featured functions of the device that can be discovered, managed, and manipulated. Physical functions have configuration resources that can be used to configure or control the storage adapter device. Physical functions include the same configuration address space and memory address space that a non-virtualized device would have. A physical function may have a number of virtual functions associated with it. Virtual functions are similar to physical functions, but are light-weight functions that may generally lack configuration resources, and are generally controlled by the configuration of their underlying physical functions. Each of the physical functions and/or virtual functions may be assigned to a respective thread of execution (such as for example, a virtual machine) running on a host device.

In various implementations, the support systems1074can include hardware for coordinating the operations of the acceleration engine1060. For example, the support systems1074can include a microprocessor that coordinates the activities of the acceleration engine1060, including moving data around on the acceleration engine1060. In this example, the microprocessor can be an integrated circuit that can execute microcode. Microcode is program code that can enable an integrated circuit to have some flexibility in the operations that the integrated circuit can execute, but because the program code uses a limited instruction set, the microprocessor may have much more limited capabilities than the host processor1072. In some examples, the program executed by the microprocessor is stored on the hardware of microprocessor, or on a non-volatile memory chip in the host system1000. In some examples, the microprocessor and the acceleration engine1060can be on chip, such as one integrated circuit on the same die and in the same package.

In some examples, the support systems1074can be responsible for taking instructions from the host processor1072when programs executing on the host processor1072request the execution of a neural network. For example, the host processor1072can provide the support systems1074with a set of input data and a task that is to be performed on the set of input data. In this example, the support systems1074can identify a neural network that can perform the task, and can program the acceleration engine1060to execute the neural network on the set of input data. In some examples, the support systems1074only needs to select an appropriate neural network processing engine of the neural network processor. In some examples, the support systems1074may need to load the data for the neural network onto the acceleration engine1060before the acceleration engine1060can start executing the neural network. In these and other examples, the support systems1074can further receive the output of executing the neural network, and provide the output back to the host processor1072.

In some examples, the operations of the support systems1074can be handled by the host processor1072. In these examples, the support systems1074may not be needed and can be omitted from the host system1000.

In various examples, the host system1000can include a combination of host systems, processor nodes, storage subsystems, and I/O chassis that represent user devices, service provider computers or third party computers.

User devices can include computing devices to access an application (e.g., a web browser or mobile device application). In some examples, the application may be hosted, managed, and/or provided by a computing resources service or service provider. The application may enable a user to interact with the service provider computer to, for example, access web content (e.g., web pages, music, video, etc.). The user device may be a computing device such as, for example a mobile phone, a smart phone, a personal digital assistant (PDA), a laptop computer, a netbook computer, a desktop computer, a thin-client device, a tablet computer, an electronic book (e-book) reader, a gaming console, etc. In some examples, the user device may be in communication with the service provider computer over one or more networks. Additionally, the user device may be part of the distributed system managed by, controlled by, or otherwise part of the service provider computer (e.g., a console device integrated with the service provider computers).

The host system1000can also represent one or more service provider computers. A service provider computer may provide a native application that is configured to run on user devices, which users may interact with. The service provider computer may, in some examples, provide computing resources such as, but not limited to, client entities, low latency data storage, durable data storage, data access, management, virtualization, cloud-based software solutions, electronic content performance management, and so on. The service provider computer may also be operable to provide web hosting, databasing, computer application development and/or implementation platforms, combinations of the foregoing or the like. In some examples, the service provider computer may be provided as one or more virtual machines implemented in a hosted computing environment. The hosted computing environment can include one or more rapidly provisioned and released computing resources. These computing resources can include computing, networking and/or storage devices. A hosted computing environment may also be referred to as a cloud computing environment. The service provider computer may include one or more servers, perhaps arranged in a cluster, as a server farm, or as individual servers not associated with one another, and may host application and/or cloud-based software services. These servers may be configured as part of an integrated, distributed computing environment. In some examples, the service provider computer may, additionally or alternatively, include computing devices such as for example a mobile phone, a smart phone, a personal digital assistant (PDA), a laptop computer, a desktop computer, a netbook computer, a server computer, a thin-client device, a tablet computer, a gaming console, etc. In some instances, the service provider computer may communicate with one or more third party computers.

FIG. 11includes a diagram of an example network1100, which can include one or more host systems, such as the host system illustrated inFIG. 10. For example, the example network1100ofFIG. 11includes multiple nodes1102a-1102h, one or more of which can be a host system such as is illustrated inFIG. 10. Others of the nodes1102a-1102hcan be other computing devices, each of which include at least a memory for storing program instructions, a processor for executing the instructions, and a network interface for connecting to the network1100.

In various examples, the network1100can be used to process data. For example, input data can be received at one of the nodes1102a-1102hor from other networks1108with which the network1100can communicate. In this example, the input data can be directed to a node in the network1100that includes an acceleration engine, for the acceleration engine to operate on and produce a result. The result can then be transferred to the node or other network from which the input data was received. In various examples, input data can be accumulated from various sources, including one or more of the nodes1102a-1102hand/or computing devices located in the other networks1108, and the accumulated input data can be directed to one or more host systems in the network1100. Results from the host systems can then be distributed back to the sources from which the input data was gathered.

In various examples, one or more of the nodes1102a-1102hcan be responsible for operations such as accumulating input data for host systems to operate on, keeping track of which host systems are busy and which can accept more work, determining whether the host systems are operating correctly and/or most efficiently, monitoring network security, and/or other management operations.

In the example ofFIG. 11, the nodes1102a-1102hare connected to one another using a switched architecture with point-to point links. The switched architecture includes multiple switches1104a-1104d, which can be arranged in a multi-layered network such as a Clos network. A network device that filters and forwards packets between local area network (LAN) segments may be referred to as a switch. Switches generally operate at the data link layer (layer 2) and sometimes the network layer (layer 3) of the Open System Interconnect (OSI) Reference Model and may support several packet protocols. The switches1104a-1104dofFIG. 11may be connected to the nodes1102a-1102hand provide multiple paths between any two nodes.

The network1100may also include one or more network devices for connection with other networks1108, such as a router1106. Routers use headers and forwarding tables to determine the best path for forwarding the packets, and use protocols such as internet control message protocol (ICMP) to communicate with each other and configure the best route between any two devices. The router1106ofFIG. 11can be used to connect to other networks1108such as subnets, LANs, wide area networks (WANs), and/or the Internet.

In some examples, network1100may include any one or a combination of many different types of networks, such as cable networks, the Internet, wireless networks, cellular networks and other private and/or public networks. The interconnected switches1104a-1104dand the router1106, if present, may be referred to as a switch fabric1110, a fabric, a network fabric, or simply a network. In the context of a computer network, terms “fabric” and “network” may be used interchangeably herein.

The nodes1102a-1102hmay be any combination of host systems, processor nodes, storage subsystems, and I/O chassis that represent user devices, service provider computers or third party computers.

User devices may include computing devices to access an application1132(e.g., a web browser or mobile device application). In some aspects, the application1132may be hosted, managed, and/or provided by a computing resources service or service provider. The application1132may allow the user(s) to interact with the service provider computer(s) to, for example, access web content (e.g., web pages, music, video, etc.). The user device(s) may be a computing device such as for example a mobile phone, a smart phone, a personal digital assistant (PDA), a laptop computer, a netbook computer, a desktop computer, a thin-client device, a tablet computer, an electronic book (e-book) reader, a gaming console, etc. In some examples, the user device(s) may be in communication with the service provider computer(s) via the other network(s)1108. Additionally, the user device(s) may be part of the distributed system managed by, controlled by, or otherwise part of the service provider computer(s) (e.g., a console device integrated with the service provider computers).

The node(s) ofFIG. 11may also represent one or more service provider computers. One or more service provider computers may provide a native application that is configured to run on the user devices, which user(s) may interact with. The service provider computer(s) may, in some examples, provide computing resources such as, but not limited to, client entities, low latency data storage, durable data storage, data access, management, virtualization, cloud-based software solutions, electronic content performance management, and so on. The service provider computer(s) may also be operable to provide web hosting, databasing, computer application development and/or implementation platforms, combinations of the foregoing or the like to the user(s). In some examples, the service provider computer(s) may be provided as one or more virtual machines implemented in a hosted computing environment. The hosted computing environment may include one or more rapidly provisioned and released computing resources. These computing resources may include computing, networking and/or storage devices. A hosted computing environment may also be referred to as a cloud computing environment. The service provider computer(s) may include one or more servers, perhaps arranged in a cluster, as a server farm, or as individual servers not associated with one another and may host the application1132and/or cloud-based software services. These servers may be configured as part of an integrated, distributed computing environment. In some aspects, the service provider computer(s) may, additionally or alternatively, include computing devices such as for example a mobile phone, a smart phone, a personal digital assistant (PDA), a laptop computer, a desktop computer, a netbook computer, a server computer, a thin-client device, a tablet computer, a gaming console, etc. In some instances, the service provider computer(s), may communicate with one or more third party computers.

In one example configuration, the node(s)1102a-1102hmay include at least one memory1118and one or more processing units (or processor(s)1120). The processor(s)1120may be implemented in hardware, computer-executable instructions, firmware, or combinations thereof. Computer-executable instruction or firmware implementations of the processor(s)1120may include computer-executable or machine-executable instructions written in any suitable programming language to perform the various functions described.

In some instances, the hardware processor(s)1120may be a single core processor or a multi-core processor. A multi-core processor may include multiple processing units within the same processor. In some examples, the multi-core processors may share certain resources, such as buses and second or third level caches. In some instances, each core in a single or multi-core processor may also include multiple executing logical processors (or executing threads). In such a core (e.g., those with multiple logical processors), several stages of the execution pipeline and also lower level caches may also be shared.

The memory1118may store program instructions that are loadable and executable on the processor(s)1120, as well as data generated during the execution of these programs. Depending on the configuration and type of the node(s)1102a-1102h, the memory1118may be volatile (such as RAM) and/or non-volatile (such as ROM, flash memory, etc.). The memory1118may include an operating system1128, one or more data stores1130, one or more application programs1132, one or more drivers1134, and/or services for implementing the features disclosed herein.

The operating system1128may support nodes1102a-1102hbasic functions, such as scheduling tasks, executing applications, and/or controller peripheral devices. In some implementations, a service provider computer may host one or more virtual machines. In these implementations, each virtual machine may be configured to execute its own operating system. Examples of operating systems include Unix, Linux, Windows, Mac OS, iOS, Android, and the like. The operating system1128may also be a proprietary operating system.

The data stores1130may include permanent or transitory data used and/or operated on by the operating system1128, application programs1132, or drivers1134. Examples of such data include web pages, video data, audio data, images, user data, and so on. The information in the data stores1130may, in some implementations, be provided over the network(s)1108to user devices. In some cases, the data stores1130may additionally or alternatively include stored application programs and/or drivers. Alternatively or additionally, the data stores1130may store standard and/or proprietary software libraries, and/or standard and/or proprietary application user interface (API) libraries. Information stored in the data stores1130may be machine-readable object code, source code, interpreted code, or intermediate code.

The drivers1134include programs that may provide communication between components in a node. For example, some drivers1134may provide communication between the operating system1128and additional storage1122, network device1124, and/or I/O device1126. Alternatively or additionally, some drivers1134may provide communication between application programs1132and the operating system1128, and/or application programs1132and peripheral devices accessible to the service provider computer. In many cases, the drivers1134may include drivers that provide well-understood functionality (e.g., printer drivers, display drivers, hard disk drivers, Solid State Device drivers). In other cases, the drivers1134may provide proprietary or specialized functionality.

The service provider computer(s) or servers may also include additional storage1122, which may include removable storage and/or non-removable storage. The additional storage1122may include magnetic storage, optical disks, solid state disks, flash memory, and/or tape storage. The additional storage1122may be housed in the same chassis as the node(s)1102a-1102hor may be in an external enclosure. The memory1118and/or additional storage1122and their associated computer-readable media may provide non-volatile storage of computer-readable instructions, data structures, program modules, and other data for the computing devices. In some implementations, the memory1118may include multiple different types of memory, such as SRAM, DRAM, or ROM.

The memory1118and the additional storage1122, both removable and non-removable, are examples of computer-readable storage media. For example, computer-readable storage media may include volatile or non-volatile, removable or non-removable media implemented in a method or technology for storage of information, the information including, for example, computer-readable instructions, data structures, program modules, or other data. The memory1118and the additional storage1122are examples of computer storage media. Additional types of computer storage media that may be present in the node(s)1102a-1102hmay include, but are not limited to, PRAM, SRAM, DRAM, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, DVD or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, solid state drives, or some other medium which can be used to store the desired information and which can be accessed by the node(s)1102a-1102h. Computer-readable media also includes combinations of any of the above media types, including multiple units of one media type.

The node(s)1102a-1102hmay also include I/O device(s)1126, such as a keyboard, a mouse, a pen, a voice input device, a touch input device, a display, speakers, a printer, and the like. The node(s)1102a-1102hmay also include one or more communication channels1136. A communication channel1136may provide a medium over which the various components of the node(s)1102a-1102hcan communicate. The communication channel or channels1136may take the form of a bus, a ring, a switching fabric, or a network.

The node(s)1102a-1102hmay also contain network device(s)1124that allow the node(s)1102a-1102hto communicate with a stored database, another computing device or server, user terminals and/or other devices on the network(s)1100.

In some implementations, the network device1124is a peripheral device, such as a PCI-based device. In these implementations, the network device1124includes a PCI interface for communicating with a host device. The term “PCI” or “PCI-based” may be used to describe any protocol in the PCI family of bus protocols, including the original PCI standard, PCI-X, Accelerated Graphics Port (AGP), and PCI-Express (PCIe) or any other improvement or derived protocols that are based on the PCI protocols discussed herein. The PCI-based protocols are standard bus protocols for connecting devices, such as a local peripheral device to a host device. A standard bus protocol is a data transfer protocol for which a specification has been defined and adopted by various manufacturers. Manufacturers ensure that compliant devices are compatible with computing systems implementing the bus protocol, and vice versa. As used herein, PCI-based devices also include devices that communicate using Non-Volatile Memory Express (NVMe). NVMe is a device interface specification for accessing non-volatile storage media attached to a computing system using PCIe. For example, the bus interface module may implement NVMe, and the network device1124may be connected to a computing system using a PCIe interface.

A PCI-based device may include one or more functions. A “function” describes operations that may be provided by the network device1124. Examples of functions include mass storage controllers, network controllers, display controllers, memory controllers, serial bus controllers, wireless controllers, and encryption and decryption controllers, among others. In some cases, a PCI-based device may include more than one function. For example, a PCI-based device may provide a mass storage controller and a network adapter. As another example, a PCI-based device may provide two storage controllers, to control two different storage resources. In some implementations, a PCI-based device may have up to eight functions.

In some implementations, the network device1124may include single-root I/O virtualization (SR-IOV). SR-IOV is an extended capability that may be included in a PCI-based device. SR-IOV allows a physical resource (e.g., a single network interface controller) to appear as multiple resources (e.g., sixty-four network interface controllers). Thus, a PCI-based device providing a certain functionality (e.g., a network interface controller) may appear to a device making use of the PCI-based device to be multiple devices providing the same functionality. The functions of an SR-IOV-capable storage adapter device may be classified as physical functions (PFs) or virtual functions (VFs). Physical functions are fully featured functions of the device that can be discovered, managed, and manipulated. Physical functions have configuration resources that can be used to configure or control the storage adapter device. Physical functions include the same configuration address space and memory address space that a non-virtualized device would have. A physical function may have a number of virtual functions associated with it. Virtual functions are similar to physical functions, but are light-weight functions that may generally lack configuration resources, and are generally controlled by the configuration of their underlying physical functions. Each of the physical functions and/or virtual functions may be assigned to a respective thread of execution (such as for example, a virtual machine) running on a host device.