JP7837470B2 - Reducing memory bank contention in hardware accelerators - Google Patents

Description

This specification generally relates to the memory operation of hardware integrated circuits.
A neural network is a machine learning model that uses one or more layers of nodes to generate an output, such as a classification, for a received input. Some neural networks include one or more hidden layers in addition to the output layer. Some neural networks can be convolutional neural networks (CNNs) configured for image processing, or recurrent neural networks (RNNs) configured for speech and language processing. Various types of neural network architectures can be used to perform a variety of tasks related to classification or pattern recognition, prediction with data modeling, and information clustering.

A neural network layer can have a corresponding set of parameters or weights. The weights are used to process the input (e.g., a batch of inputs) through the neural network layer, generating the corresponding output of the layer for computing neural network inference. The batch of inputs and the set of kernels can be represented as a tensor of inputs and weights, i.e., a multidimensional array. A hardware accelerator is a dedicated integrated circuit for implementing a neural network. This circuit includes memory with locations corresponding to the elements of the tensor, which can be scanned or accessed using the circuit's control logic.

This document describes techniques for enabling simultaneous access to physical memory banks by reducing (or preventing) memory bank contention in the tile memory of hardware accelerators.

The compute tiles of the hardware accelerator receive requests used to access the accelerator's tile memory. For each request, i) a logical address represented by a sequence of bits is identified within the request, ii) a subset of the first bit is taken from the sequence, and iii) an identifier is generated based on a bank generation function using the subset of the first bit.

The identifier identifies a specific bank within the physical memory banks of tile memory. Each request is processed using the individual bank identifier ("bank ID") generated for that request. In response to processing the requests, multiple separate memory banks are accessed simultaneously within the same clock cycle (e.g., a single clock cycle).

One aspect of the subject matter described herein can be embodied in a method performed by a computer for simultaneously accessing memory banks of a hardware accelerator. The method comprises receiving a plurality of requests, each request used to access the tile memory of the hardware accelerator. For each of the plurality of requests, the method includes identifying an individual logical address represented by a sequence of bits within the request, obtaining a first subset of bits from the sequence of bits, and generating an individual bank identifier that identifies a specific bank from among a plurality of physical memory banks of the tile memory, based on a bank generation function using the first subset of bits. The method further includes i) processing each of the plurality of requests using the individual bank identifiers generated for the requests, and ii) simultaneously accessing a plurality of distinct physical memory banks of the tile memory during a clock cycle in response to processing each of the plurality of requests.

These and other embodiments may optionally include one or more of the following features. For example, in some embodiments, simultaneous access to multiple separate physical memory banks includes accessing multiple separate physical memory banks within a single clock cycle for a specific stride value. The specific stride value may be a memory access stride equal to the difference between specific rows in the same physical memory bank.

In some embodiments, simultaneous access to multiple separate physical memory banks includes accessing multiple separate physical memory banks without bank contention. In one embodiment, bank contention occurs when two or more requesters request access to the same physical memory bank of tile memory during the same clock cycle. Each physical memory bank may contain multiple rows, and the method includes, for each of the multiple requests, i) obtaining a subset of second bits from a sequence of bits; ii) providing the subset of second bits as input to a bank generation function; and iii) generating individual row identifiers that identify a specific row within a specific bank from among the multiple physical memory banks of tile memory, based on the application of the bank generation function to the subset of second bits.

In some embodiments, each row of multiple rows contains a width of 16 bytes, the partition of tile memory contains 32 physical memory banks, and the memory access stride is equal to row_width ^* num_banks. Obtaining a first subset of bits from a sequence of bits may include obtaining two or more bits that are in the least significant bit (LSB) of the sequence of bits.

This aspect and other embodiments of other aspects include corresponding systems, devices, and computer programs encoded on a computer storage device and configured to perform actions of the method. One or more computer systems can be configured in this way by software, firmware, hardware, or a combination thereof installed on the system that causes the system to perform actions when in operation. One or more computer programs can be configured in this way by having instructions that, when executed by a data processing device, cause the device to perform actions.

The subject matter described herein can be implemented in specific embodiments to achieve one or more of the following advantages: A bank generation function is disclosed that can be used to handle multiple requests for memory resources of tile memory without causing bank contention.

The bank generation function is configured to generate individual bank IDs for each request within a group of requests, so that no two requests request access to the same physical memory bank of tile memory. The bank generation function provides an access pattern that enables parallel processing of each request within the group within the same clock cycle (e.g., a single clock cycle). The access pattern provided by the bank generation function allows for the simultaneous processing of multiple requests regardless of the stride value used for memory access.

Details of one or more embodiments of the subject matter described herein are given in the accompanying drawings and the following description. Other potential features, aspects, and advantages of the subject matter will become apparent from the description, drawings, and claims.

This is a block diagram of an exemplary computing system for implementing a neural network machine learning model. This is a block diagram of an exemplary computing system for implementing a neural network machine learning model. This illustrates an exemplary processing pipeline for routing inputs and outputs between the memory and compute cells of a hardware integrated circuit. This shows an example of memory traversal for different banking generation functions. An exemplary bank generation function for reducing memory bank contention in hardware integrated circuits is shown. This is an exemplary process for reducing memory bank contention in hardware integrated circuits. Examples of input tensors, parameter tensors, and output tensors are shown.

Similar reference symbols and symbols in various drawings refer to the same elements.
Figure 1A is a block diagram of an exemplary computing system 100 for implementing a neural network model on a hardware integrated circuit, such as a machine learning hardware accelerator. The computing system 100 includes one or more compute tiles 101, a host 120, and a higher-level controller 125 ("controller 125"). As will be described in more detail below, the host 120 and the controller 125 work together to provide datasets and instructions to one or more compute tiles 101 of the system 100.

In some embodiments, the host 120 and the controller 125 are the same device. The host 120 and the controller 125 can perform separate functions, or they can be integrated into a single device package. For example, the host 120 and the controller 125 can form a central processing unit (CPU) that interacts with or collaborates with a hardware accelerator containing multiple compute tiles 101. In some embodiments, the host 120, the controller 125, and the multiple compute tiles 101 are contained on or formed on a single integrated circuit die. For example, the host 120, the controller 125, and the multiple compute tiles 101 can form a dedicated system-on-a-chip (SoC) optimized to run neural network models for processing machine learning workloads.

Each computational tile 101 generally includes a controller 103, which provides one or more control signals 105 to cause the input (or activation) of the input vector 102 to be stored in a memory location in a first memory 108 ("memory 108") or to be accessed from that memory location. Similarly, the controller 103 may also provide one or more control signals 105 to cause the weights (or parameters) of the weight matrix structure 104 to be stored in a memory location in a second memory 110 ("memory 110") or to be accessed from that memory location. In some embodiments, the input vector 102 is obtained from an input tensor, while the weight matrix structure is obtained from a parameter tensor. The input tensor and parameter tensor, respectively, may be multidimensional data structures such as multidimensional matrices or tensors. This will be described in more detail below with reference to Figure 6.

Each memory location in memories 108 and 110 can be identified by a corresponding memory address, such as a logical address having a corresponding mapping to a physical row in the physical memory bank of the memory. Referring to the example in Figure 1B, the compute tile 101 can derive a set of consecutive addresses (e.g., virtual/logical addresses) from a group of requests 130. For example, a set of consecutive addresses can be derived by referring to the logical memory corresponding to the physical memory 108 of the compute tile 101. This will be further described below with reference to embodiments in Figures 4 and 5.

The logical memory has multiple logical ports 135, each port potentially connected to or associated with a different requester seeking access to the physical resources of memory 108. To process a given access request, for each port, tile 101 (or its controller 103) determines the bank to which the request is routed, based on the address in the request. For each bank, the compute tile 101 may include an arbiter 140, which arbitrates access to that bank from multiple ports according to a bank generation function configured, for example, to mitigate some (or all) of the requests routed to the same physical memory bank. The logical memory, the ports of the logical memory, and the arbiter can be implemented in software, hardware, or both. In some embodiments, the logical memory and its ports, as well as the arbiter, are controlled based on control signals generated by the controller 103.

Each of the memories 108 and 110 may be implemented as a series of physical banks, units, or any other related storage medium or device. Each of the memories 108 and 110 may contain one or more registers, buffers, or both. In some embodiments, memory 108 is an input/activation memory, while memory 110 is a parameter memory. In some other embodiments, inputs or activations are stored in memory 108, memory 110, or both, and weights are stored in memory 110, memory 108, or both. For example, inputs and weights may be transferred between memory 108 and memory 110 to facilitate certain neural network computations. In some embodiments, each of the memories 108 and 110 is referred to as a tile memory.

Each computation tile 101 also includes an input activation bus 106, an output activation bus 107, and a computation unit 112, which has one or more hardware multiply-accumulate (MAC) circuits within each cell 114a/b/c. A controller 103 can generate control signals 105 to retrieve operands stored in the memory of the computation tile 101. For example, the controller 103 can generate control signals 105 to retrieve i) an exemplary input vector 102 stored in memory 108, and ii) weights 104 stored in memory 110. Each input retrieved from memory 108 is provided to the input activation bus 106 for routing (e.g., direct routing) to computation cells 114a/b/c in the computation unit 112. Similarly, each weight retrieved from memory 110 is routed to cells 114a/b/c in the computation unit 112.

As described below, each cell 114a/b/c performs a computation to obtain a partial sum or cumulative value to generate the output of a given neural network layer. An activation function can be applied to the set of outputs to generate a set of output activations for the neural network layer. In some embodiments, the outputs or output activations are routed for storage and/or transfer via the output activation bus 107. For example, a set of output activations can be transferred from a first computation tile 101 to a second different computation tile 101, where it can be processed as input activations for different layers of the neural network.

Generally, each computation tile 101 and system 100 may include additional hardware structures to perform computations associated with multidimensional data structures such as tensors, matrices, and/or data arrays. In some embodiments, the inputs of input vectors (or tensors) 102 and the weights 104 of a parameter tensor can be preloaded into the memories 108, 110 of the computation tile 101. The inputs and weights are received as a set of data values reaching a particular computation tile 101 from a host 120 (e.g., an external host) via a host interface, or from a higher-level control such as a controller 125.

Each of the compute tile 101 and controller 103 may include one or more processors, processing devices, and various types of memory. In some embodiments, the processors of the compute tile 101 and controller 103 include one or more devices such as a microprocessor or central processing unit (CPU), graphics processing unit (GPU), application-specific integrated circuit (ASIC), or a combination of different processors. Each of the compute tile 101 and controller 103 may also include other computing and storage resources such as buffers, registers, and control circuits. These resources cooperate to provide additional processing options for performing one or more of the decisions and calculations described herein.

In some embodiments, the processing units (or units) of the controller 103 execute programmed instructions stored in memory to cause the controller 103 and the compute tile 101 to perform one or more of the functions described herein. The memory of the controller 103 may include one or more non-temporary machine-readable storage media. These non-temporary machine-readable storage media may include solid-state memory, random-access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (e.g., EPROM, EEPROM, or flash memory), or any other tangible media capable of storing information or instructions.

System 100 receives instructions that define a specific computational operation performed by the computation tile 101. In some embodiments, the host can generate a set of parameters (i.e., weights) and corresponding inputs for processing in the neural network layer. For example, the host can generate a set of compressed parameters (CSPs) and corresponding mapping vectors, such as non-zero maps (NZMs), that map the neural network inputs to non-zero parameters in the set of CSPs for a given operation. The host 120 sends the parameters to the computation tile 101 via the host interface, enabling further processing on that tile. The controller 103 can execute programmed instructions to analyze the received weights and the data stream associated with the inputs, including the compressed parameters and corresponding mapping vectors.

The controller 103 causes the data stream inputs and weights to be stored in the computation tile 101. For example, the controller 103 can store mapping vectors and compressed sparse parameters in the local tile memory of the computation tile 101. This will be explained in more detail below. The controller 103 can also analyze the input data stream to detect operation codes ("opcodes"). The system 100 can support various types of opcodes, such as vector-matrix multiplication, element-wise vector operations, and opcode types that indicate whether a given operation uses compressed sparse parameters versus uncompressed parameters/weights.

Based on one or more opcodes, the controller 103 may activate or execute a bank generation function (described below) to mediate requests for access to the tile memory of the computing tile 101. For example, the controller 103 may utilize a bank generation function to mediate two or more requests such that each of the requests is processed for a different physical bank of the tile memory. The controller 103 may utilize a predetermined bank selection scheme programmed or encoded in the controller 103 before the inference decision is executed on the computing tile 101.

In some embodiments, a given computation operation involves multiple requesters/accessors, each requesting access to resources in memory 108. For example, a computation workload performed on computing tile 101 can trigger memory access requests through tensor traversal operations that request read and write access to individual address locations in memory 108. As described below, these address locations can correspond to elements of an input tensor processed as part of the workload.

In addition to tensor read/write operations, processing a workload may also include i) moving data (e.g., parameters) from memory 108 (narrow) to memory 110 (wide), and ii) processing read or write access requests to move data from memory 110 (wide) to memory 108 (narrow). In some cases, to process an exemplary workload, the first compute tile 101 may arbitrate and execute access requests (e.g., read/write requests) for memory 108, where the requests are based on external data communication originating from outside the first compute tile 101.

These different types of access requests correspond to one or more compute threads, all requesting access to the same physical memory 108. In some cases, multiple requests may correspond to a single compute thread (or clock cycle). The disclosed bank generation function can be used to handle multiple requests for memory resources in tile memory without causing bank contention. For example, the bank generation function is configured to generate individual bank IDs for each request within a group of requests, such that two requests do not request access to the same physical memory bank of tile memory.

In some embodiments, based on the bank identifier returned as the output of the bank generation function, the controller 103 can arbitrate requests by processing two or more requests for different physical memory banks of tile memory within the same clock cycle (e.g., a single clock cycle). The bank generation function allows the controller 103 to achieve these advantages even with respect to striding for specific issues, such as memory access where the stride is a function of the number of banks and the number of bytes in a row within a bank. This will be described in more detail below.

In addition, based on the opcode, the controller 103 can activate dedicated data path logic associated with one or more computation cells 114a/b/c to perform computations (e.g., sparse computations) using parameters and inputs/activations, as well as corresponding mapping vectors used to map inputs/activations to subsets of parameters. As used in this document, a sparse computation includes a neural network computation performed on a neural network layer using non-zero weight values in a set of compressed sparse parameters generated from the set of weights of the neural network layer.

In some embodiments, the opcode indicates details about the operation relating to the inputs and weights for a given layer, for example, the sparsity of one or more parameter tensors associated with that layer. The controller 103 i) detects an opcode containing any relevant tensor sparsity information, ii) retrieves parameters from tile memory (e.g., memory 108 or 110) using local read logic based on that opcode, and iii) wires or routes those parameters to cells 114a/b/c of the computed tile 101. The controller 103 can also analyze an exemplary data stream and, based on that analysis, generate a set of compressed sparse parameters and corresponding mapping vectors that map the discrete inputs of the input vectors to individual non-zero weight values within the compressed sparse parameters. To the extent that the operations and/or processes for generating the compressed sparse parameters and corresponding mapping vectors are described with reference to the controller 103, each of these operations and processes may also be performed by the host 120, the controller 125, or both.

In some embodiments, performing some (or all) of the following operations on the host 120—such as analyzing tensor indices, performing direct memory access (DMA) operations to read address spaces in system memory (e.g., SRAM, DRAM, etc.) to obtain input and weight values, generating compressed sparse parameters, and generating corresponding mapping vectors—reduces processing time at each computation tile 101 and improves data throughput at the system 100. For example, by using the controller 125 to perform these operations on the host 120, it is possible to send an already compressed set of parameters to a given tile computation 101, thereby reducing the size and amount of data routed at the system 100.

Figure 2 shows an exemplary processing pipeline 200 for routing inputs and outputs between the memory and compute cells of a hardware integrated circuit. Generally, the pipeline 200 uses an input bus 106 to route inputs obtained from memory locations in memory 108 to one or more compute cells 114, and uses an output bus 107 to route outputs generated from multiplications performed in one or more compute cells 114 to memory locations in memory 108.

The pipeline 200 leverages a hardware architecture in which the input bus 106 is coupled (e.g., directly coupled) to each of multiple groupings of hardware computing cells of a dedicated integrated circuit. The system 100 can provide a first operand from a location in memory 108 and a second operand from a location in memory 110. The operand 204 is used for a computation performed in cell 114, which generates an output corresponding to the result of that computation. In some embodiments, the computation is for machine learning operations, such as processing input through the neural network layer of an artificial neural network.

In this embodiment, the computation tile 101 can provide a subset of cells 114 with first operands corresponding to inputs or activations (e.g., a0, a1, a2, etc.) of the input feature map. For example, individual inputs of the input vector 102 are provided to each MAC in the subset via the input bus 106 of the computation tile 101. The system 100 can perform this broadcast operation across multiple computation tiles 101 to compute the product for a given neural network layer at each computation tile 101 using the individual groupings of inputs and their corresponding weights. At a given computation tile 101, the product is computed by multiplying each individual input (e.g., a1) by its corresponding weight (e.g., w1) at each MAC in the subset using the MAC's multiplication circuit.

System 100 can generate layer outputs based on the accumulation of multiple individual products calculated in each MAC of cells 114a/b/c within a subset of cells 114a/b/c of the computing unit 112. As described below with reference to Figure 6, the multiplication operations performed within the computing tile 101 may require i) a first operand (e.g., input or activation) stored in memory locations in memory 108 corresponding to individual elements of the input tensor, and ii) a second operand (e.g., weight) stored in memory locations in memory 110 corresponding to individual elements of the parameter tensor.

In the example in Figure 2, the shift register 202 can provide a shift function, in which the input of operand 204 is broadcast onto the input bus 106 and routed to one or more MACs 114 of cell 114. In some embodiments, the shift register 202 enables one or more input broadcast modes on the compute tile 101. For example, the shift register 202 can be used to broadcast inputs sequentially from memory 108, e.g., one by one (first broadcast mode), simultaneously from memory 108, e.g., in parallel (second broadcast mode), or using any combination of these broadcast modes. The shift register 202 can be an integrated function of memory 108 and can be implemented in hardware, software, or both.

In some embodiments, the weight (w3) of operand 206 may have a weight value of zero. When the controller 103 determines that the weight (w3) has a zero value, the multiplication between the input (a2) and the weight (w3) can be skipped to conserve processing resources. As a result, those operands are neither routed to nor consumed by cells 114a/b/c. The determination to skip this particular multiplication operation can be based on a mapping vector that maps the discrete inputs (an) of the input vector to individual weights (wn) of the parameter tensor, as described above.

Figure 3 shows a scan table 300 illustrating examples of memory/data scans for different functions 302 and 304 used to generate addresses for accessing the physical memory banks of memory 108. In particular, the first memory scan is shown for the first function 302, while the second different memory scan is shown for the second function 304. In some embodiments, memory 108 includes one or more memory partitions.

In the example in Figure 3, the partition of memory 108 includes 32 physical memory banks 312, shown as banks 0 through 31. Each bank can contain a certain number of rows, for example, 16, 24, etc. In some embodiments, each row is 16 bytes (16B) wide so that the compute tile 101 accesses data from memory 108 in 16B chunks (e.g., 128 bits). In some embodiments, memory 108 can contain more or fewer physical memory banks, and each row in a bank can have a width greater than 16B or less than 16B (e.g., 1B).

The scan table 300 includes a first address 306, a second address 308, and a third address 310. The memory scan distance between each of the first address 306, the second address 308, and the third address 310 can be based on a stride value. In the example in Figure 3, the stride value is 512. However, the stride value may differ in other examples. Therefore, other stride values are within the scope of this disclosure. Stride operation may be required when the computing system 100 performs computation for a given task or machine learning workload. Stride operation may be based on a stride parameter or stride value. A given stride value may be programmable by the system 100. For example, the system 100 can program a stride for a given inference based on a stride for a particular problem known by the system 100's compiler as specific to a particular inference operation.

In some embodiments, the stride value is determined based on the hardware configuration of memory 108, the type of machine learning operation being performed, or both. For example, a neural network (e.g., a convolutional neural network) can be implemented using the computational tile 101 of system 100, which is tuned or used for image and video content compression and/or recognition. The stride can be a component of the neural network. In this example, the machine learning operation involves processing an image through layers of the neural network according to a filter corresponding to a set of weights/parameters for that layer.

The image, or the pixel values associated with the image, can be stored across the physical rows and physical banks of memory 108, referencing the hardware configuration of the physical rows and physical banks of that memory. In this example, the stride is a component or parameter of the neural network's filter (or kernel). The stride is used to modify the amount the filter moves across the image or video. For example, if the stride is set to 1, the computation tile 101 moves the filter(s) one pixel (or input) at a time across the region. Similarly, if the stride is 2, the computation tile 101 moves the filter(s) two pixels at a time across the region.

Therefore, the filter may be shifted based on the stride value of the layer, and in some embodiments, the system 100 can repeat this process across multiple computational tiles 101 of different layers until the inputs of different regions of the image have the corresponding dot product. Moving the filter across the inputs of image regions based on the stride value may include searching for, retrieving, or otherwise accessing the inputs from various locations in memory 108 according to that stride value.

As described above, images, or pixel values associated with images, are stored across physical rows and physical banks in memory 108. An example in Figure 3 may be illustrated with reference to the stride values 512. In some examples, 512 represents a common stride associated with a particular image processing operation. Depending on the type of operation, the computation tiles 101 of system 100 can process requests to access memory 108 according to a range of stride values. For example, a first tile 101 may process a request based on a first stride value, while a second different tile 101 may process a request based on a second different stride value.

As shown in the scan table 300, when the bank generation function 302 is used to generate a bank ID for processing the request, 512 access strides are repeated in the same physical memory bank 314 (e.g., bank 0) of the tile memory. This indicates a bank contention. As used herein, a bank contention occurs when two or more requesters request access to the same physical memory bank of the tile memory during the same clock cycle.

As described below with reference to Figure 4, the bank generation function 304 is configured to consistently, or at least substantially, generate access to a distinct physical memory bank of memory 108 by processing requests for access to physical rows within the memory bank of memory 108. More specifically, for each request in a group of requests for access to memory 108, the bank generation function 304 uses bits from the address in the request to generate a bank ID that, for example, generates access to a different physical memory bank when the group of requests are processed in parallel during a single clock cycle.

For example, as shown in Figure 3, the bank generation function 304 enables the processing of two or more requests based on an access pattern that causes the compute tile 101 to access different physical memory banks of memory 108. The bank generation function 304 is configured to generate bank IDs and row IDs that enable this access pattern, regardless of the stride value used for memory access.

In some embodiments, based on the bank ID generated by the bank generation function 304, i) a first request causes the compute tile 101 to access 16B in row 1 of the first physical memory bank 316, for example, bank "0"; ii) a second request causes the compute tile 101 to access 16B in row 1 of a second different physical memory bank 318, for example, bank "4"; and iii) a third request causes the compute tile 101 to access 16B in row 1 of a third different physical memory bank 320, for example, bank "8".

Each of the first, second, and third requests may be a different request, may originate from a different requester, or both. Based on the bank IDs and/or access patterns enabled by the bank generation function 304, there are no cases, or virtually no cases, where two or more requesters request access to the same physical memory bank of tile memory within the same clock cycle. Therefore, each of the first, second, and third requests can be processed simultaneously within the same clock cycle (e.g., a single clock cycle) without causing bank contention in memory 108. Furthermore, each of the first, second, and third requests can be processed simultaneously within the same clock cycle (e.g., a single clock cycle) for a certain range of stride values (e.g., a stride of 512) without causing bank contention.

In some embodiments, the computation tile 101 can be configured to route and store the output so that the memory 108 (e.g., activation memory) does not encounter bank contention when the stored output value is acquired as an input activation to a second, different neural network layer. This applies to other data types/values that may be written to (or stored in) a physical location in memory 108, as described in the following paragraphs with reference to activation values.

The calculation tile 101 may include a nonlinear unit that applies an activation function to the cumulative values resulting from calculations performed by the calculation unit 112. In one example, the nonlinear unit may be hardware circuitry included within the multiplication and addition circuits of the calculation tile 101. In another example, the nonlinear unit is included in the calculation tile 101 but is outside the calculation unit 112.

The nonlinear unit applies its activation function to generate a set of activation values. These activation values can be the output of a machine learning workload. For example, the activation values may be the output of a first neural network layer, routed to and stored in memory bank 108. These activation values (e.g., the output of the first layer) can be retrieved from memory bank 108 and provided as input activations for processing through a second, different neural network layer.

The compute tile 101 can issue access requests (e.g., write accesses) to memory 108 to store outputs such as activation values in the physical rows and physical banks of memory 108. In some examples, these requests can be routed to a partition of memory 108 used as activation memory to store activations. In some embodiments, these write access requests can be handled using a bank generation function 304, so that the system 100 does not encounter bank contention in memory 108 when the output/activation values are stored in that compute tile 101.

The bank generation function 304 can also be used to reduce or prevent bank contention when access requests (e.g., read access) are processed and output values are retrieved or fetched. For example, output values can be fetched and provided as input activations to a second, different neural network layer.

Figure 4 shows an exemplary bank generation function 304 for reducing memory bank contention in a hardware integrated circuit. As described below, the bank generation function 304 is configured such that requests to access physical rows in the memory bank of memory 108 consistently, or at least substantially, result in access to a separate physical memory bank of memory 108.

For example, given a group of requests to access memory 108, the controller 103 of the compute tile 101 can derive a set of addresses from that group of requests. In some cases, the controller 103 may derive a set of consecutive addresses (e.g., virtual/logical addresses) from the group of requests. Given this set of consecutive addresses, the bank generation function 304 is configured to generate a corresponding set of bank identifiers ("bank IDs"). For example, the bank generation function 304 generates individual bank IDs for each request within the group of requests.

System 100, or compute tile 101, can process a group of requests using a set of bank IDs over one or more clock cycles, or over the same clock cycle, without bank contention occurring in memory 108. In other words, based on the set of bank IDs generated by the bank generation function 304, compute tile 101 can process each request in a group of requests simultaneously (e.g., in parallel), and two requests will not request access to the same physical memory bank of tile memory 108 during the same clock cycle.

In the example in Figure 4, the bank generation function 304 generates individual bank IDs for each request based on algorithm 402. Algorithm 402 generates bank IDs based on an exemplary sequence of address bits 404 contained in the corresponding request for accessing memory 108. For example, the computation tile 101 uses the sequence of address bits 404 to obtain individual values for one or more variables provided as input to algorithm 402. The input variables can correspond to different parts of the sequence of address bits 404.

The first variable A may be obtained from the first part of the bits, the second variable B from the second part of the bits, the third variable row_id from the third part of the bits, and the fourth variable byte_in_row from the fourth part of the bits. For example, the bit sequence 404 can be an input address divided into two parts: i) bytes_in_row (number of bytes in the memory row) and ii) row_address. Using the bank generation function 304, row_address can be divided into two parts: i) row_id (e.g., row_id in each bank) and ii) the conventional bank ID defined as variable A. The least significant bit (LSB) of row_id may be defined as variable B.

As shown in the example in Figure 4, for a given bit sequence 404, one or more bits in one part of the sequence may overlap with one or more bits in other parts of the sequence. In some embodiments, the input variable may correspond to the least significant bit (LSB) or the most significant bit (MSB) in the request.

In some embodiments, the bank generation function 304 is configured to perform at least a first set of operations 412, a second set of operations 414, and a third set of operations 416. The first and/or second set of operations can be used to establish specific input variables such as row_address, row_id, A, and B. In some cases, row_address is used to extract specific bits within sequence 404, such as bits 4-15, while row_id is used to extract other specific bits, such as bits 8-15. In some embodiments, these variables may be used to extract other ranges or combinations of bits.

A third operation (or set of operations) 416 can be used to rotate a bit vector based on a shift parameter or operation such as rotation_banking_shift. The bit vector can be derived from a sequence of address bits in a request to access memory 108, based on an operation performed using the bank generation function 304. The bit vector can be derived from the msb or lsb in the sequence of address bits. For example, the bit vector could be a combination of variables A and B, and the bank generation function 304 is configured to apply the rotation_banking_shift operation to this combination of variables.

The rotation_banking_shift operation can be applied by referencing the number of banks in the memory of the computation tile 101. For example, the rotation_banking_shift operation can be used to either i) shift the MSB bit vector by the amount specified by the shift value of the operation, or ii) shift the LSB bit vector by the amount specified by the shift value of the operation. System 100 performs the shift operation so that the bank ID of the new bank belongs to a specific group. Thus, the third operation 416 can be used to obtain the number of banks, as well as the rotated bank ID according to the attributes of any row, bank, and byte associated with variables A and/or B.

In some embodiments, system 100 determines the minimum number of bits required to define an MSB or LSB. For example, system 100 can determine the minimum number of bits based on the number of physical memory banks in a given partition of memory 108. For example, if there are 32 physical memory banks, system 100 can determine that a minimum of 5 bits is required to represent 32 digits or 32 row IDs.

In some embodiments, the bank generation function 304 is configured or coded as shown in algorithm 402 in the example of Figure 4. In some other embodiments, a modified bank generation function can be configured or coded (using alternative commands) to generate a set of bank IDs that can be processed simultaneously on the computed tile 101 without causing bank contention in memory 108. For example, this modified bank generation function can be configured or coded for tile memory containing more or fewer physical memory banks and more or fewer rows compared to memory 108.

The bank generation function 304 can be an algorithm that receives one or more inputs and generates one or more outputs. For example, as described above, the inputs may be individual addresses for one or more rows ("row_address"), the number of rows in each bank ("rows_per_bank"), the least significant bit in the request (LSB), the minimum bit amount of the LSB, the most significant bit in the request (MSB), the minimum bit amount of the MSB, a bank rotation parameter, or a shift parameter ("MSB_shift_minus_1"). The outputs may be individual bank IDs of the physical memory banks of memory 108, and individual row IDs of the physical rows within the physical memory banks of memory 108. More or fewer inputs are within the scope of this disclosure and may be used in connection with the bank generation function 304.

Figure 5 shows an exemplary process 500 for reducing memory bank contention in the tile memory of a hardware accelerator or a dedicated hardware integrated circuit. In some embodiments, process 500 is performed during computations on a neural network machine learning model implemented on a hardware accelerator. For example, computations are performed using a dedicated neural network processor to process neural network inputs, such as images or speech utterances. Such a processor may be represented by the integrated circuit or system 100 described with reference to Figure 1A.

For example, a hardware integrated circuit can be configured to implement a CNN containing multiple neural network layers. In some cases, the neural network layers may include group convolutional layers. The input may be an exemplary image, such as those described above, including various other types of digital images or associated graphical data. In at least one example, the integrated circuit can implement an RNN for processing input derived from speech or other audio content. In some cases, process 500 is part of a technique that enables improvements in latency and throughput when accelerating neural network computations to generate image or audio processing output compared to other data processing techniques.

Process 500 can be implemented or executed using the system 100 described above. Therefore, the description of process 500 may refer to the aforementioned computing resources of system 100. In some examples, the steps or actions of process 500 are enabled by programmed firmware instructions, software instructions, or both. Each type of instruction may be stored in a non-temporary machine-readable storage device and is executable by one or more processors of the devices and resources described in this document.

In some embodiments, the steps of process 500 are performed by hardware circuitry to generate layer outputs for the neural network layer. These outputs can be part of a computation for a machine learning task or inference workload to generate image processing or image recognition outputs. As shown above, the integrated circuit can be a dedicated neural network processor or hardware machine learning accelerator configured to accelerate computations for generating various types of data processing outputs.

Referring again to process 500, system 100 receives multiple requests to access the system's memory resources (502). For example, each of the multiple requests can be used to access the first tile memory of an integrated circuit or hardware accelerator. In some embodiments, system 100 processes multiple requests across multiple tiles. For example, system 100 can process individual subsets of requests at each compute tile 101 of an integrated circuit.

For each request, system 100 can identify individual logical addresses represented by a sequence of bits within the request (504). As described above, memory 108 can be row-addressable, and as a result, a row in a memory bank can be identified or accessed based on the address in the corresponding request. Generally, each request specifies a logical address that can be mapped to a corresponding physical address. For example, the compiler of system 100 can determine the mapping of a set of logical addresses to a set of corresponding physical addresses, where the physical address specifies a physical location in memory, such as the location in a bank in the first memory 108, or the location in a row within a bank in the first memory 108.

For each request, system 100 can obtain a first subset of bits from a sequence of bits (506). For example, a logical address can be specified by a data structure containing a sequence of bits, e.g., 8 bits, 16 bits, etc. In some embodiments, the controller 103 of the computed tile 101 scans each data structure representing the logical address specified by the request. In response to scanning the bits that make up the data structure, the controller identifies or determines a subset of bits that can be used as input to the bank generation function. In some embodiments, the controller determines the subset of bits based on the configuration of the tile memory 108.

For each request, system 100 can generate individual bank identifiers ("bank IDs") based on a bank generation function 304 using a subset of the first bits (508). Each individual bank ID identifies a specific physical bank among the multiple physical memory banks of memory 108. As described above, each physical memory bank may contain multiple rows. For each request, computation tile 101 can i) obtain a subset of the second bits from a sequence of bits, ii) provide the subset of the second bits as input to the bank generation function, and iii) generate individual row IDs that identify a specific row within a specific bank among the physical memory banks of the tile memory, based on the bank generation function being applied to the subset of the second bits.

The system 100 is configured to process each request using individual bank IDs generated for each request (510). In some embodiments, the compute tile 101 processes multiple requests (e.g., simultaneously) and, in response to processing requests, accesses two or more physical memory banks in parallel without causing bank contention (512). For example, the controller 103 of the compute tile 101 generates a control signal to access a physical bank or row of memory 108 to retrieve an input vector 102 from an address location in the first memory 108.

In some embodiments, the computational tile 101 can simultaneously access multiple separate physical memory banks of the tile memory during a single clock cycle in response to processing each of the requests to retrieve one or more input vectors. The input vector 102 can correspond to an input feature map of an image and may be a matrix structure of neural network inputs, such as activations generated by previous neural network layers.

As described above, the bank generation function 304 enables the processing of two or more requests based on access patterns that cause the compute tile 101 to access different physical memory banks of memory 108. The bank generation function 304 is configured to generate bank IDs and row IDs that enable these access patterns, regardless of the stride value used for memory access.

In particular, the bank generation function can provide this access pattern even when the stride of a memory access is equal to the difference between specific rows in the same physical memory bank. For example, each row in a physical memory bank may have a width of 16 bytes, and a partition of tiled memory may have 32 physical memory banks. In this example, the bank generation function can also provide this access pattern even when the memory access stride is equal to row_width ^* num_banks (i.e., stride = 512).

Figure 6 shows an example of a tensor or multidimensional matrix 600, including an input tensor 604, a variation of the parameter tensor 606, and an output tensor 608. In the example in Figure 6, each of the tensors 600 contains individual elements, where each element can correspond to an individual data value (or operand) for a computation performed in a given layer of the neural network.

For example, each input of the input tensor 604 can correspond to an individual element along a given dimension of the input tensor 604, each weight of the parameter tensor 606 can correspond to an individual element along a given dimension of the parameter tensor 606, and each output value or activation in the set of outputs can correspond to an individual element along a given dimension of the output tensor 608. In connection with this, each element can correspond to an individual memory location or address in the memory of the computation tile 101, which is allocated to operate on one or more dimensions of the given tensors 604, 606, and 608.

The computation performed on a given neural network layer may include multiplying the input/activation tensor 604 and the parameter/weight tensor 606 in one or more processor clock cycles to obtain a layer output that may include output activations. Multiplying the activation tensor 604 and the weight tensor 606 involves multiplying the activations from the elements of tensor 604 by the weights from the elements of tensor 606 to obtain one or more partial sums. The exemplary tensor 606 in Figure 6 can be an unmodified parameter tensor, a modified parameter tensor, or a combination thereof. In some embodiments, each parameter tensor 606 corresponds to a modified parameter tensor containing non-zero CSP values derived based on a specific sparsity exploitation technique.

The processor core of system 100 can operate on i) scalars corresponding to discrete elements in a multidimensional tensor 604, 606, ii) a vector of values containing multiple discrete elements 609 along the same or different dimensions of a multidimensional tensor 604, 606 (e.g., input vector 102), or iii) a combination of these. Each of the discrete elements 609, or multiple discrete elements 609, in a multidimensional tensor can be represented using X,Y coordinates (2D) or X,Y,Z coordinates (3D), depending on the dimensionality of the tensor.

System 100 can compute multiple partial sums corresponding to the product generated from the multiplication of batch inputs with their corresponding weight values. As described above, System 100 can perform the accumulation of products (e.g., partial sums) over many clock cycles. For example, the accumulation of products can be performed in random-access memory, shared memory, or scratchpad memory of one or more computation tiles based on the techniques described in this document. In some embodiments, the input weight multiplication can be written as a sum of products obtained by multiplying the discrete inputs of the input vector 102 by each weight element, such as a row or slice of the input tensor 604. This row or slice can represent a given dimension, such as a first dimension 610 of the input tensor 604, or a second different dimension 615 of the input tensor 604.

In some embodiments, the output of a convolutional neural network layer can be computed using an exemplary set of calculations. The computation of the CNN layer may include performing a 2D spatial convolution between a 3D input tensor 604 and at least one 3D filter (weight tensor 606). For example, a 2D spatial plane 620 or 625 can be obtained by convolving one 3D filter 606 onto the 3D input tensor 604. This computation may include calculating the sum of dot products over a specific dimension of the input volume containing the input vector 102.

For example, spatial plane 620 may contain the output value of the sum of products calculated from inputs along dimension 610, while spatial plane 625 may contain the output value of the sum of products calculated from inputs along dimension 615. The calculation to generate the sum of products of the output values in spatial planes 620 and 625 can be performed i) in calculation cells 114a/b/c, ii) directly in memory 110 using arithmetic units coupled to a shared bank of memory 110, iii) or both. In some embodiments, the reduction operation may be streamlined and performed directly in memory cells (or locations) of memory 110 using various techniques for reducing the cumulative value.

The subject matter and functional embodiments described herein can be implemented in digital electronic circuits, in tangibly embodied computer software or firmware, in computer hardware including the structures disclosed herein and their structural equivalents, or in one or more combinations thereof. Embodiments of the subject matter described herein can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible, non-temporary program carrier for execution by a data processing device or for controlling the operation of a data processing device.

Alternatively, or additionally, program instructions can be encoded into artificially generated propagating signals, such as mechanically generated electrical signals, optical signals, or electromagnetic signals, which are generated to encode information for transmission to a suitable receiving device for execution by a data processing device. Computer storage media can be machine-readable storage devices, machine-readable storage substrates, random or serial access memory devices, or a combination of one or more of these.

The term "computing system" encompasses all kinds of devices, machines, and equipment for processing data, including, for example, programmable processors, computers, or multiple processors or computers. A device may include dedicated logic circuits, such as FPGAs (Field-Programmable Gate Arrays) or ASICs (Application-Specific Integrated Circuits). In addition to hardware, a device may also include code that constitutes the execution environment for the target computer program, such as processor firmware, protocol stacks, database management systems, operating systems, or one or more of these.

Computer programs (sometimes called, or written as, programs, software, software applications, modules, software modules, scripts, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and can be deployed in any form, such as as standalone programs or as modules, components, subroutines, or other units suitable for use in a computing environment.

Computer programs may, but do not necessarily, correspond to files in a file system. A program can be stored in a single file dedicated to the program itself, or in multiple collaborative files, such as a file containing one or more scripts stored within a markup language document, or in a file containing one or more modules, subprograms, or parts of code, alongside other programs or data. Computer programs can be deployed to run on a single computer, or on multiple computers located in one location or distributed across multiple locations and interconnected by a communication network.

The processes and logic flows described herein can be executed by one or more programmable computers executing one or more computer programs to act on input data and generate outputs, thereby performing their functions. The processes and logic flows can also be executed by dedicated logic circuits, such as FPGAs (Field-Programmable Gate Arrays), ASICs (Application-Specific Integrated Circuits), or GPGPUs (General-Purpose Graphics Units), and the devices can also be implemented as these dedicated logic circuits.

A computer suitable for running computer programs includes, for example, a general-purpose or dedicated microprocessor, or both, or any other type of central processing unit, and can be based on them. Generally, the central processing unit receives instructions and data from read-only memory or random-access memory, or both. The elements of a computer include a central processing unit for executing or running instructions, and one or more memory devices for storing instructions and data. Generally, a computer also includes one or more mass storage devices for storing data, such as magnetic disks, magneto-optical disks, or optical disks, or is operablely coupled for receiving data from or transmitting data to them, or both. However, a computer is not required to have such devices. Furthermore, to give some examples, a computer can be incorporated into other devices, such as mobile phones, personal digital assistants (PDAs), portable audio or video players, game consoles, Global Positioning System (GPS) receivers, or portable storage devices, such as Universal Serial Bus (USB) flash drives.

Computer-readable media suitable for storing computer program instructions and data include, for example, all forms of non-volatile memory, media, and memory devices, such as semiconductor memory devices (e.g., EPROM, EEPROM, and flash memory devices), magnetic disks (e.g., internal hard disks or removable disks), magneto-optical disks, and CD-ROM and DVD-ROM disks. Processors and memory may be complemented by or integrated into dedicated logic circuits.

To provide user interaction, embodiments of the subject matter described herein can be implemented in a computer having a display device for displaying information to the user, such as an LCD (liquid crystal display) monitor, and a keyboard and pointing device, such as a mouse or trackball, that allows the user to provide input to the computer. Other types of devices can also be used to provide user interaction. For example, the feedback provided to the user can be any form of sensory feedback, such as visual feedback, auditory feedback, or tactile feedback, and input from the user can be received in any form, such as acoustic input, voice input, or tactile input. In addition, the computer can interact with the user by sending and receiving documents to and from devices used by the user, for example, by sending a web page to a web browser on the user's client device in response to a request received from a web browser.

Embodiments of the subject matter described herein can be implemented as a computing system including, for example, a backend component as a data server, or a computing system including a middleware component, for example, an application server, or a computing system including a frontend component, for example, a client computer having a graphical user interface or a web browser to enable a user to interact with the embodiment of the subject matter described herein, or in any combination of one or more such backend, middleware, or frontend components. The components of the system can be interconnected by any form or medium of digital data communication, for example, a communication network. Examples of communication networks include local area networks ("LANs") and wide area networks ("WANs"), for example, the Internet.

A computing system can include clients and servers. Clients and servers are generally geographically separated and typically interact via a communication network. The client-server relationship arises from computer programs running on individual computers that have a client-server relationship with one another.

This specification includes details of many specific embodiments, but these should not be interpreted as limitations on the scope of any invention or claim, but rather as descriptions of features that may be specific to a particular embodiment of a particular invention. Certain features described in this specification in the context of individual embodiments may also be implemented in combination in a single embodiment. Conversely, various features described in the context of a single embodiment may also be implemented in multiple embodiments, separately or in any preferred secondary combination. Furthermore, features may be described above as functioning in a particular combination, and may initially be claimed as such; however, one or more features from the claimed combination may, in some cases, be removed from the combination, and the claimed combination may cover secondary combinations or variations of secondary combinations.

Similarly, while operations are shown in a specific order in the drawings, this should not be understood as requiring that such operations be performed in a specific illustrated or sequential order, or that all illustrated operations be performed, in order to achieve the desired result. In certain situations, multitasking and parallel processing may be advantageous. Furthermore, the separation of various system modules and components in the embodiments described above should not be understood as requiring such separation in all embodiments, and the described program components and systems should generally be understood as being able to be integrated into a single software product or packaged into multiple software products.

Specific embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. For example, the desired results can still be achieved even if the actions described in the claims are performed in a different order. As an example, the process shown in the accompanying figures does not necessarily require the specific or sequential order shown to achieve the desired results. In certain embodiments, multitasking and parallel processing may be advantageous.

Claims (10)

A method performed by a computer for simultaneously accessing the memory banks of a hardware accelerator,
The system receives multiple requests, each used to access the tile memory of the aforementioned hardware accelerator.
For each of the aforementioned multiple requirements,
Within the aforementioned request, the individual logical addresses represented by a sequence of bits are identified,
Obtaining a subset of the first bit from the sequence of bits,
The method further includes generating individual bank identifiers that identify a particular bank from among a plurality of physical memory banks of the tile memory, based on a bank generation function that uses a subset of the first bits, and the method further includes
Processing each of the multiple requests using the individual bank identifiers generated for the aforementioned requests,
A method comprising simultaneously accessing a plurality of separate physical memory banks of the tile memory during a clock cycle in response to processing each of the plurality of requests. Simultaneous access to the aforementioned multiple separate physical memory banks is
The method according to claim 1, comprising accessing the plurality of separate physical memory banks during a single clock cycle for a specific stride value. The method according to claim 2, wherein the specific stride value is a memory access stride equal to the difference between specific rows in the same physical memory bank of the plurality of separate physical memory banks. Simultaneous access to the aforementioned multiple separate physical memory banks is
The method according to claim 3, comprising accessing the plurality of separate physical memory banks without bank contention. The method according to claim 4, wherein bank contention occurs when two or more requesters request access to the same physical memory bank of the tile memory during the same clock cycle. Each physical memory bank includes multiple rows, and the method further includes,
For each of the aforementioned multiple requirements,
Obtaining a subset of the second bit from the sequence of bits,
The above-mentioned subset of the second bits is provided as input to the bank generation function,
The method according to claim 5, comprising generating individual row identifiers that identify a specific row in a specific bank from among the plurality of physical memory banks of the tile memory, based on the bank generation function being applied to a subset of the second bits. Each of the aforementioned rows has a width of 16 bytes,
The partition of the tile memory includes 32 physical memory banks,
The method according to claim 6, wherein the memory access stride is equal to row_width * num_banks. Obtaining a subset of the first bits from the sequence of bits is:
The method according to claim 1, comprising obtaining two or more bits in the least significant bit (LSB) of the sequence of bits. It is a system,
Hardware accelerators and
Processing device and
A system comprising a non-temporary machine-readable storage medium for storing instructions, wherein the instructions are executable to cause the processing device to perform the method described in any one of claims 1 to 8 . A program that causes a hardware accelerator processing device to perform the method described in any one of claims 1 to 8 .