CROSS REFERENCE TO RELATED APPLICATION

[0001] This patent application claims priority to Provisional Patent Application Serial No. 62/333,214, entitled "Memory and Processing Architecture for Hardware Accelerated Machine Learning," filed May 7, 2016, which is hereby incorporated by reference herein in its entirety.

BACKGROUND

[0002] Machine learning and deep neural networks, including deep belief networks (collectively called neural networks), are rapidly becoming ubiquitous. Applications initially began with object recognition in computer images and with speech recognition now common in voice user interfaces such as Apple Siri™, Microsoft Cortana™, Amazon Alexa™, Google Assistant™ and the like. Neural networks are presently being applied to industrial controllers, medical diagnoses, leading to a burgeoning of neural networks.

[0003] However, neural network operations, at least as applied to machine learning and deep neural networks, typically make use of dense linear algebra operations, such as matrix operations, as well as more neural network specific operations such as convolutions, max pooling, and data noise generation. Such operations lend themselves to parallel operations, such as calculating matrix rows in parallel, which if performed on commonly available central processing units (CPU) which generally are not parallel, leads to suboptimal performance.

[0004] Accordingly, arrays of graphical processing units (GPU), which are optimized for matrix operations and parallel operations have been applied to neural networks, such as via NVidia' s CUD A™ architecture. However, while GPUs are optimized for matrix operations, they do not provide optimizations specific to neural networks, such as convolutions, max pooling and noise generation, thereby limiting their performance in neural network operations.

BRIEF DESCRIPTION OF THE DRAWINGS

[0005] The Detailed Description is set forth with reference to the accompanying figures. [0006] Figure 1 is a context diagram of a system environment for machine learning hardware acceleration.

[0007] Figure 2 is a block diagram for machine learning hardware acceleration.

[0008] Figure 3 is a block diagram for multicast network optimizations for machine learning hardware acceleration.

[0009] Figure 4 is a flow chart for multicast network optimizations for machine learning hardware acceleration.

[0010] Figure 5 is a context diagram for accessing strides of contiguous banked computer memory.

[0011] Figure 6 is a block diagram for a permutaton used in DRAM transfer optimizations for machine learning hardware acceleration.

[0012] Figure 7 is a block diagram for DRAM transfer optimizations for machine learning hardware acceleration.

[0013] Figure 8 is a flow chart for DRAM transfer optimizations for machine learning hardware acceleration.

DETAILED DESCRIPTION

Overview of Multicast Network and Memory Transfer Optimizations for Neural Network Hardware Acceleration

[0014] Neural network hardware acceleration occurs within the context of an environment to develop, compile (or programmatically transform), and execute applications that make use of neural networks. Such applications are often called machine learning applications, deep neural network applications, and/or deep belief network applications. While machine learning does not strictly demand the use of a neural network, many common present day frameworks and techniques make use of neural networks. Deep neural networks may be roughly considered to be a series or network of neural networks.

[0015] As stated above, present day hardware, either in the form of a central processing unit (CPU) or a graphical processing unit (GPU) array do not provide hardware optimizations for many operations common to neural networks. Disclosed herein are various techniques for neural network hardware acceleration, specifically in for multicast networks for data dispatched to data receivers such as execution units, and for memory transfer. [0016] The optimizations disclosed herein are designed to perform those operations in hardware in constant time (Big 0(C)) or linear time (Big O(n)) that CPUs and/or GPUs would otherwise use Big 0(n log(n)) or higher polynomial time. The optimizations may make use of information at design time and/or compile time, may make use of transformations to enable multidimensional operations common to matrix and tensor operations, and may recognize and exploit instruction pipeline opportunities in hardware.

[0017] Figure 1 provides a context diagram 100 in which neural network hardware acceleration may occur. Specifically, a user 102, accesses computing services from cloud 104. The user may be a developer or may be an end user.

[0018] Cloud 104 is comprised of several servers 106 capable of storing computer readable data and executing computer readable instructions. Those servers 106 may be disaggregated by a hypervisor 108 to serve virtual machines 110.

[0019] A compiled neural network application 112 may execute either directly on a server 106 or on a virtual machine 110. The server 106 and/or the virtual machine 110 may be provisioned by one or more neural network frameworks and/or runtimes 114. A neural network hardware acceleration unit 116 may be connected to a server 106 or may be standalone. As a resource of a server 106, a neural network hardware acceleration unit may be disaggregated as well by hypervisor 108 thereby making its resources available to a virtual machine 110.

[0020] The compiled neural network application 112 is a result of source code 118 for the neural network application as compiled by compiler 120. The neural network application 112 may also have been linked to libraries specific to the neural network frameworks or runtimes 114.

[0021] Turning back to the neural network hardware accelerator unit 116, it comprises a system control block 122 that among other operations may transfer instruction. It interfaces with a controlling CPU via a communications bus 124. The hardware accelerator unit will have an instruction interpreter 126 that interfaces with local memory 128, one or more multicast networks 130 and a plurality of data receivers 132. In some embodiments, the data receivers 132 may be execution units. The interface with offsite data may be via a data transfer unit 134 interfacing over a memory bus 136.

[0022] The neural network hardware accelerator unit 116 is described in further detail with respect to Figure 2 below. Note that the one or more multicast networks 130 and the data transfer units 134 have several optimizations. The multicast network optimizations are described in further detail with respect to Figures 3 and 4 below. The data transfer unit optimizations make use of features of group theory as described with respect to Figure 5 below. The data transfer unit optimizations themselves are described with respect to Figures 6, 7 and 8 below.

Exemplary Architecture of a Neural Network Hardware Acceleration Unit

[0023] A closer examination of a neural network hardware acceleration unit 116 is merited. Figure 2 provides a block diagram 200 of a neural network hardware acceleration unit expanding on the detail described with respect to Figure 1.

[0024] The neural network hardware accelerator unit 202, it may interface with a server or with some other controlling CPU via a system control block 204 via a parallel bus or serial bus 206. In some implementations the interface is a PCI bus or PCI-E bus. However, any standardized bus is sufficient. A serial bus may be used, but at a performance cost of the overhead of serialization.

[0025] Computer instructions and/or operation codes may be stored in local memory 208 and interpreted by an instruction interpreter 210. The computer instructions may arrive via the system control block 204. Local memory 208 may be static random access memory (SRAM). The SRAM may be subdivided into a location for computer instructions to interpret and execute, and one or more areas of working memory 208(a), 208(b) each of which may be in at least some portion subdivided into multiple banks of memory.

[0026] At least some of the areas of working memory 208(a), 208(b) may be each associated with a multicast network 212(a), 212(b) comprised of switch nodes, which dispatch data stored in the working memory areas 208(a), 208(b) to one or more data receivers 214.

[0027] As described in further detail with respect to Figures 3 and 4, the switch nodes comprising a multicast network 212(a), 212(b) are organized into a plurality of layers, the first layer being proximate to the memory 208(a), 208(b) and the last layer being proximate to the data receivers 214. The switch nodes comprising the last layer access the data receivers 214 in some permutation of connections. Note that the connection permutations of the last layers of the different multicast networks 212(a), 212(b) respectively need not be the same.

[0028] Data receivers 214 may be one of several embodiments, depending on the application. For neural network applications 112, the data receivers 214 may be a plurality of execution units 214, each capable of executing computer executable instructions.

[0029] Data may be transferred from local memory 208 to off board memory, may be performed by a data transfer unit 216 over a data bus 218. In the case where off board memory is in the form of dynamic random access memory (DRAM), the data transfer unit 216 is a DRAM transfer unit and the data bus 218 is a DRAM bus.

Multicast Network Optimizations for Neural Network Hardware Acceleration

[0030] The multicast networks 212(a), 212(b) are designed to reorder and duplicate data from the memory 208(a), 208(b) in order to feed portions and permutation of the data in the memory 208(a), 208(b) deterministically. To achieve this, multicast networks 212(a), 212(b) are configured as Benes networks, which are sets of switch nodes, organized into layers, where each switch node in a layer can duplicate and/or forward data to one or more switch nodes in subsequent layers. When input data have traversed all the layers, the data will have been rearranged into a desired permutation.

[0031] This feature of Benes networks is desirable for neural network operations which make use of multidimensional matrices known as tensors. Tensors may be stored in contiguous memory, meaning that each of the data elements comprising a tensor resides in a memory block with sequential and uninterrupted memory addresses. By being able to select and permute arbitrary data elements, a Benes network multicasting data elements to data receiver execution units 214 enable parallel operations on those multicast data elements.

[0032] For purposes of hardware acceleration, by making Benes network configuration data globally accessible to all switch nodes in a multicast network, and by pipelining execution instructions, configuration and operation may be reduced to constant time (Big 0(c)). Figure 3 is a block diagram 300 of two multicast networks 302(a), 302(b), permuting input data into data receivers 304.

[0033] Each multicast network 302(a), 302(b), receives input data, usually in the form of data elements of a tensor, from areas of working memory 306(a), 306(b) organized into banks. As will be seen with respect to Figure 5, organization of data elements of a tensor into banks lends itself to further optimization.

[0034] Each multicast network 302(a), 302(b) is comprised of switch nodes 308, organized into layers 310. The layers are ordered, where the first layer is proximate to the memory 306(a), 306(b) and the last layer is proximate to the data receivers 304. [0035] One purpose for implementing two multicast networks 302(a), 302(b), is that in tensor operations, it may be desirable to access different partitions of the tensor. For example, in a two dimensional tensor, a matrix, the first multicast network 302(a) may perform operations on rows, and the other multicast network 302(b) may perform operations on columns. For this reason, the permutation of switch nodes 308 interfacing the data receivers 304 from the one multicast network 302(a) (i.e. the last layer of switch nodes of the first multicast network 302(a)) need not be the same permutation of switch nodes 308 interfacing the data receivers 304 from the other multicast network 302(b) (i.e. the last layer of switch nodes for the second multicast network 302(b)). In one embodiment, the first multicast network 302(a) permutation is modulo, and the second multicast 302(b) permutation is grouped fanout.

[0036] An individual switch node 308, may contain a one or more data entries, either received from memory 306(a), 306(b), or from a switch node 308 from a prior level 310. A switch node may contain a configuration indicator 314 and a controller indicator. The configuration indicator 314 specifies whether to perform a broadcast mode whether input data is to be forwarded according to the configuration data, or a passthru mode wherein input data is to be forwarded regardless of the configuration data. The controller indicator 316 specifies whether to update at least one switch node entry.

[0037] There may be a separate global configuration data store 318, either in the form of registers, or in the form of memory. The global configuration data is accessible by all switch nodes 308, and holds the value of the configuration indicators 314 and the controller indicators 316 of the switch nodes 308 respectively. Since the configuration data store 318 is globally accessible, in some embodiments, the switch nodes 308 may potentially not have locally stored values of the configuration indicator 314 and the controller indicator 316, and may instead just access the global configuration data store 318.

[0038] Figure 4 is a flow chart 400 of a potential operation of the multicast networks 302(a), 302(b).

[0039] Block 402 starts configuration of a multicast network 302(a), 302(b) by retrieving configuration data retrieved from a known address from computer memory 306(a), 306(b). The retrieved configuration data is for configuring the switch nodes 308 comprising the multicast network 302(a), 302(b). In block 404, the retrieved configuration data is then stored in the global configuration data store 318. [0040] In block 406, the data elements in computer memory 306(a), 306(b) to be operated on may be stored in the data entry storage 312 of the switch nodes.

[0041] Since all the switch nodes 308 have access to the global configuration data store 318, in block 408, at least the first layer 310 of switch nodes 308 in the multicast network 302(a), 302(b) may have their respective configuration indicators 314 and controller indicators 316 populated with the control data in the global configuration data store 318.

[0042] Note that at this point, the multicast network 302(a), 302(b) is configured. If blocks 402 and 404 are executed within one clock cycle, and block 408 is executed within one clock cycle, in effect (not counting insertion of no-operation instructions, also called no-ops), the multicast network 302(a), 302(b) is configured in two clock cycles, regardless of the amount of data. In effect the multicast network configuration is achieved in constant time (Big 0(c)).

[0043] In block 408, a Benes multicast operation at the first level of switch nodes commences the reordering and copying of the data elements stored in those switch node. A switch node 308 will determine whether to use configuration information, or to passthru data regardless of configuration based on the configuration indicator 314. The switch node 308 also considers the controller indicator 316 to determine which pattern to permute the data entries 312 to the next layer of switch nodes (or in the case of the last layer, to the data receivers 304).

[0044] The Benes multicast operations are performed sequentially through each layer 310 of switch nodes 308, in block 410, until the last layer in block 412 performs the last Benes multicast operation to permute the data elements into the data receivers 304.

[0045] Note that in the case of passthru, because operation proceeds regardless of the value of the configuration indicators 314 and controller indicators 316, operation may proceed within one clock cycle, skipping the operations to load and propagate control information.

Group Theory Backgrounder for Memory Transfer Optimizations

[0046] Before discussing memory transfer optimizations, a background in the group theory underpinnings of the disclosures herein is in order. Common operations in neural networks include tensor operations involve one partition of a tensor, is operated on another partition of that tensor or a different tensor. The partitions are comprised of data elements that are regularly spaced within their tensor. The data elements comprising the partitions may be called tiles.

[0047] Since the tiles comprising a partition may operate on their operands independently, this gives rise to an opportunity to perform the operation in parallel, thereby greatly saving processing time. Accordingly, it is useful to have the ability to retrieve and move tiles of a partition of a tensor in as small a number of operations as possible.

[0048] Group theory is the branch of mathematics that describes sets and their respective behavior over an operator. For example, the set of integers is a group with respect to the addition operation, since the addition of any two integers yields an integer. There are other aspects of a set that give rise to a group.

[0049] One group is a finite group of integers modulo D, where D is some positive integer. Such a group is also called a cyclic group D, denoted herein C _D . The memory techniques herein make use of a cyclic group C _D where D is the number of banks in a working group of memory. Figure 5 is a diagram 500 of such a working area 502. The banks 504 are indexed from 0 to D-1, and store a plurality of data elements 506. The data elements comprising a partition 508 are indicated in brackets.

[0050] The data elements are stored in contiguous memory. Note that contiguous means that the data elements are stored in consecutive, uninterrupted, memory addresses. The memory addresses need not be physical address, but can also relate to a virtual memory space. Since the partitions are spaced in regular intervals, and because we access data elements across the distance of those regular intervals, called "strides" (i.e. that is every Dth element plus some offset O), we can identify the bank that stores the desired data element according to the formula O + (M * i) % D, where O is the starting offset of a memory storing a tensor, D is the number of banks, and M is the stride of the tensor in memory. This ability lets us access tiles from a tensor in a constant number of operations, potentially within in a single processor instruction.

[0051] To avoid collisions, the number of banks D should be prime and the stride of the data elements M is not a strict multiple of D. Alternatively the number of banks D should be relatively prime to the stride of the data elements M, and the partition to be retrieved should be a vector with less than D data elements.

[0052] For example, say we want to access every fifth element. This would be to say that M = 5. Let us also presume that the starting offset address 0 is 2 and that the number of banks D is 7. Consequently we may read up to 7 elements, each of which will be read from a distinct bank of memory since 5 is relatively prime to 7. (Most certainly both 5 and 7 are prime numbers in their own right.) Accordingly:

(2 + 5*0) % 7 = 2 % 7 = 2

(2 + 5* 1) % 7 = 7 % 7 = 0

(2 + 5*2) % 7 = 12 % 7 = 5

(2 + 5*3) % 7 = 17 % 7 = 3

(2 + 5*4) % 7 = 22 % 7 = 1

(2 + 5*5) % 7 = 27 % 7 = 6

(2 + 5*6) % 7 = 32 % 7 = 4

[0053] For a given value of O and M, as long as M is relatively prime to D, we can always permute the logically ordered data elements, so that each access i goes to a unique bank. However, in a hardware implementation we must physically perform this permutation for arbitrary O and M. To remove the effect of O, it suffices to perform a rotation. Fast hardware implementation of rotation is an understood problem. To handle the effect of the stride, M, we rely on another property of prime fields. Specifically, multiplication modulo D, for a prime D, of the elements 1 to D-1 form a group as well. This group is in fact isomorphic to the cyclic group D-1. If M is not a strict multiple of D, this means that we can implement the effect of the multiplication by M by first applying a fixed permutation to map from the multiplication group of D to the cyclic group D-1, followed by a rotation in the group D-1, followed by another fixed permutation to back to the multiplication group of D. Hardware to implement fixed permutations can be done by wiring in metal layers, and the rotation as mentioned earlier is well understood.

[0054] Now we need to determine the fixed permutation use, as well as to compute the amount of rotation within the cyclic group D-1, which we shall call 'r'.

[0055] To define these permutations, we must choose a generator over the multiplication prime field in question. A generator for a group is an element that, by repeated applications, produces all the elements of the group. For example, for the prime field over D = 7, 3 is a multiplicative generator:

3 ¹ (mod 7) = 3

3 ² (mod 7) = 2

3 ³ (mod 7) = 6

3 ⁴ (mod 7) = 4

3 ⁵ (mod 7) = 5 3 ⁶ (mod 7) = 1

[0056] The chosen generator is denoted as g. Note that D and g are fixed at the time of design. A discrete log with respect to g, log _g (x), can be defined as the value y such that g ^y (mod D)= x. For example, for g = 3, D = 7, we compute log _g (6) = 3.

[0057] Since the rotation to handle the multiplicative part of the permutation happens in the cyclic space, it is required to compute the discrete log to determine the amount to rotate, which is complex to perform in hardware. In practical implementations, one may presume that M, and thus m, and log _g (m) are known in advance. This allows a compiler to perform the appropriate computations and provide a fixed constant for the rotation. Specifically, to determine the necessary rotation, we compute:

n = (log _g (m) + l)%(D - l)

[0058] Namely, to specify a transform, o and r are provided at the time of permutation. It is to be noted that the permutation network may be configured to one of two different variants. The first variant is called a forward modulo permutation network, which maps each i < D to a correspondingly appropriate bank position b = (O + M * i)%D given the correct o and n. This permutation is used to send address and data to the memory banks (i.e., for memory write operations). The second variant is called the reverse modulo permutation network, which simply performs the inverse mapping of the forward modulo permutation network, and is used to appropriately reorder the read data elements due to memory read operations.

[0059] Before forward and reverse modulo permutation networks can be described in greater detail, two simple wiring patterns are to be defined. The two wiring patterns are used to perform the mapping a logical group and a cyclic group. Specifically, a first wiring pattern, map to cylic is defined to take D - 1 elements and map each entry i of the D - 1 elements to entry log _g (i), for 1 <= i < D. A second wiring pattern, map from cylic is defined to do the opposite and map entry i to entry g ¹ (mod D). Since 0 is not a member of the multiplicative group, entry 0 of the elements is left unaltered by both the mapping and the rotations. This structure is described in greater detail with respect to Figure 6 below.

Permutatons

[0060] The hardware implementation of the memory transfer operations described above include the ability to permute data elements. A hardware device to do so is termed a permutaton. Figure 6 is a block diagram 600 of a permutaton 602. [0061] Consider receiving a parameter where o = O % D, where O is the offset start in memory, the memory storing data elements in contiguous memory and the memory organized into D banks in the memory. Further consider receiving a parameter r which represents the number of rotations to perform for a cyclic group less than D, wherein r is based at least on the discrete log of a generator g, log _g .

[0062] A permutaton comprises a number of inputs to permute 604. The inputs will generally correspond to D inputs, usually banks. Those inputs 604, are then mapped to a permutation via a first cyclic map 606 from inputs indexed 1 through D. In hardware this operation may be implemented via a right barrel shifter, which performs a right rotation of the data elements from 1 through D.

[0063] The permutaton then permutes the data elements via a second cyclic map 608 that rotates of all the data elements from 0 through D-l to the right. This may be performed via a right barrel shifter, which performs a right rotation of the data elements from 0 through D-l and thereto forward the permuted data elements to outputs 610.

[0064] Note that a reverse permutaton, which restores the data elements to their original positions, may be implemented via a left barrel shifter which performs a left rotation of the data elements 0 through D-l, followed by a left barrel shifter which performs a left rotation of the data elements 1 through D. In this way, a reverse permutaton is the hardware inverse of a permutaton.

[0065] Between the permutaton and the reverse permutaton, hardware support for permutation operations for the memory transfer techniques disclosed herein are supported.

Memory Transfer Optimizations for Neural Network Hardware Acceleration

[0066] Permutatons may be applied to create a memory transfer unit optimized for neural network hardware acceleration. Figure 7 is a block diagram 700 of an exemplary memory transfer unit 702. Figure 8 is a flow chart 800 of an exemplary operation of the memory transfer unit 700.

[0067] A modulo address generator 704 is a forward or standard permutaton. It receives inputs from data banks, permutes the data elements per input parameters o and r as described with respect to Figures 5 and 6 above. Specifically, per block 802 in the flow chart 800, the modulo address generator receives a memory address and a length, and in block 804 of the flow chart 800, the modulo address generator 704 generates a set of memory addresses corresponding to data elements stored in a computer readable memory separated by strides. [0068] The enqueuing controller 706, is responsible for controlling the forwarding of the received data elements into D address queues 708. Specifically, the address queues 708 store memory addresses of the data elements in hardware rather than the values of the data elements themselves. In block 806 of the flow chart 800, the enqueuing controller 706 receives the set of memory addresses generated by the modulo address generator 704, and in block 808 of the flow chart 800, forwards the memory addresses into the corresponding address queues 708, while concurrently adding control information into a control queue 710. The control information is used to synchronize reception on a receiving dequeuing controller 712.

[0069] The address queues 708 feed into a plurality of address decoders 714 respectively which in turn feed into a plurality of data queues 716 respectively. Specifically, in block 810 of flow chart 800, the address decoders 714 decode the memory addresses of the data elements in the address queues 708, into their respective data elements, and queue the decoded data elements into the data queues 716 respectively.

[0070] In block 812 of the flow chart 800 the dequeuing controller 710 receives the queued data elements from the data queues 714, and receives the control information from the control queue 708, and forwards to a reverse permutaton 716, based at least on the received control information.

[0071] In block 814 of the flow chart 800, the reverse permutaton 718 performs the inverse operation of the modulo address generator's 704 forward permutaton, to restore the data received from the dequeuing controller 712. Upon doing so, in block 816 of the flow chart 800, the restored data is forwarded to data out 720.

Exemplary Use Cases

[0072] As described with respect to Figure 1, the multicast network and memory transfer optimizations disclosed herein may be applied to neural network operations. One or more multicast networks may be used to forward permutations of data elements stored in memory banks to a plurality of execution units. If multiple multicast units are used, then those units may use different permutations to feed into execution units. In one embodiment, different multicast units may relate to different partitions of a tensor.

[0073] In this way, the multicast network and the memory transfer units may be thought of discretely and separately from the context of a neural network hardware accelerator, each with applications potentially unrelated to neural network hardware acceleration. [0074] By way of example, the multicast network and memory transfer optimizations may be used in other hardware acceleration contexts, such as graphical processing including the calculation of linear algebra operations, tensor operations specific to graphics and quaternion operations.

[0075] In the case of memory transfer optimizations, the application need not be specific to particular operations, but may be used simply in a memory controller. For example, where partitions and/or vectors of a data elements stored in contiguous memory are to be transferred, the memory transfer optimizations may be applied. Furthermore, because the multicast network optimizations may copy and permute data elements arbitrarily, used in conjunction with the memory transfer operations may provide the basis for a full memory controller.

Conclusion

[0076] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.