Patent Description:
One of the most common ways to boost speed of execution is to perform operations in parallel, such as in multiple processor cores. This principle is exploited on a much larger scale by configuring graphics processing units (GPUs) with many (e.g., many thousands) of processing pipelines that may each be configured to perform a mathematical function. In this manner, large amounts of data may be processed in parallel. Although originally used for graphics processing applications, GPUs are also often used for other applications, particularly artificial intelligence.

It would be an improvement in the art to improve the function of a GPU pipeline or of any processing device including many processing units.

In order that the advantages of the invention will be readily understood, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered limiting of its scope, the invention will be described and explained with additional specificity and detail through use of the accompanying drawings, in which:.

It will be readily understood that the components of the present invention, as generally described and illustrated in the Figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the invention, as represented in the Figures, is not intended to limit the scope of the invention, as claimed, but is merely representative of certain examples of presently contemplated embodiments in accordance with the invention. The presently described embodiments will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout.

Embodiments in accordance with the present invention may be embodied as an apparatus, method, or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, or an embodiment combining software and hardware aspects that may all generally be referred to herein as a "module" or "system. " Furthermore, the present invention may take the form of a computer program product embodied in any tangible medium of expression having computer-usable program code embodied in the medium.

Any combination of one or more computer-usable or computer-readable media may be utilized, including non-transitory media. For example, a computer-readable medium may include one or more of a portable computer diskette, a hard disk, a random access memory (RAM) device, a read-only memory (ROM) device, an erasable programmable read-only memory (EPROM or Flash memory) device, a portable compact disc read-only memory (CDROM), an optical storage device, and a magnetic storage device. In selected embodiments, a computer-readable medium may comprise any non-transitory medium that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

Computer program code for carrying out operations of the present invention may be written in any combination of one or more programming languages, including an object-oriented programming language such as Java, Smalltalk, C++, or the like and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The program code may execute entirely on a computer system as a stand-alone software package, on a stand-alone hardware unit, partly on a remote computer spaced some distance from the computer, or entirely on a remote computer or server. In the latter scenario, the remote computer may be connected to the computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

The present invention is described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions or code.

These computer program instructions may also be stored in a non-transitory computer-readable medium that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture including instruction means which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

<FIG> is a block diagram illustrating an example computing device <NUM>. Computing device <NUM> may be used to perform various procedures, such as those discussed herein. Computing device <NUM> can function as a server, a client, or any other computing entity. Computing device can perform various monitoring functions as discussed herein, and can execute one or more application programs, such as the application programs described herein. Computing device <NUM> can be any of a wide variety of computing devices, such as a desktop computer, a notebook computer, a server computer, a handheld computer, tablet computer and the like.

Computing device <NUM> includes one or more processor(s) <NUM>, one or more memory device(s) <NUM>, one or more interface(s) <NUM>, one or more mass storage device(s) <NUM>, one or more Input/Output (I/O) device(s) <NUM>, and a display device <NUM> all of which are coupled to a bus <NUM>. Processor(s) <NUM> include one or more processors or controllers that execute instructions stored in memory device(s) <NUM> and/or mass storage device(s) <NUM>. Processor(s) <NUM> may also include various types of computer-readable media, such as cache memory.

Memory device(s) <NUM> include various computer-readable media, such as volatile memory (e.g., random access memory (RAM) <NUM>) and/or nonvolatile memory (e.g., read-only memory (ROM) <NUM>). Memory device(s) <NUM> may also include rewritable ROM, such as Flash memory.

Mass storage device(s) <NUM> include various computer readable media, such as magnetic tapes, magnetic disks, optical disks, solid-state memory (e.g., Flash memory), and so forth. As shown in <FIG>, a particular mass storage device is a hard disk drive <NUM>. Various drives may also be included in mass storage device(s) <NUM> to enable reading from and/or writing to the various computer readable media. Mass storage device(s) <NUM> include removable media <NUM> and/or non-removable media.

I/O device(s) <NUM> include various devices that allow data and/or other information to be input to or retrieved from computing device <NUM>. Example I/O device(s) <NUM> include cursor control devices, keyboards, keypads, microphones, monitors or other display devices, speakers, printers, network interface cards, modems, lenses, CCDs or other image capture devices, and the like.

Display device <NUM> includes any type of device capable of displaying information to one or more users of computing device <NUM>. Examples of display device <NUM> include a monitor, display terminal, video projection device, and the like.

A graphics-processing unit (GPU) <NUM> may be coupled to the processor(s) <NUM> and/or to the display device <NUM>. The GPU may be operable to render computer generated images and perform other graphical processing. The GPU may include some or all of the functionality of a general-purpose processor, such as the processor(s) <NUM>. The GPU may also include additional functionality specific to graphics processing. The GPU may include hard-coded and/or hard-wired graphics function related to coordinate transformation, shading, texturing, rasterization, and other functions helpful in rendering a computer generated image.

Interface(s) <NUM> include various interfaces that allow computing device <NUM> to interact with other systems, devices, or computing environments. Example interface(s) <NUM> include any number of different network interfaces <NUM>, such as interfaces to local area networks (LANs), wide area networks (WANs), wireless networks, and the Internet. Other interface(s) include user interface <NUM> and peripheral device interface <NUM>. The interface(s) <NUM> may also include one or more user interface elements <NUM>. The interface(s) <NUM> may also include one or more peripheral interfaces such as interfaces for printers, pointing devices (mice, track pad, etc.), keyboards, and the like.

Bus <NUM> allows processor(s) <NUM>, memory device(s) <NUM>, interface(s) <NUM>, mass storage device(s) <NUM>, and I/O device(s) <NUM> to communicate with one another, as well as other devices or components coupled to bus <NUM>. Bus <NUM> represents one or more of several types of bus structures, such as a system bus, PCI bus, IEEE <NUM> bus, USB bus, and so forth.

In some embodiments, a processor <NUM> may include a cache <NUM>, such as one or both of a L1 cache and an L2 cache. A GPU <NUM> may likewise include a cache <NUM> that may likewise include one or both of a L1 cache and an L2 cache.

For purposes of illustration, programs and other executable program components are shown herein as discrete blocks, although it is understood that such programs and components may reside at various times in different storage components of computing device <NUM>, and are executed by processor(s) <NUM>. Alternatively, the systems and procedures described herein can be implemented in hardware, or a combination of hardware, software, and/or firmware. For example, one or more application specific integrated circuits (ASICs) can be programmed to carry out one or more of the systems and procedures described herein.

Referring to <FIG>, in some embodiments, a GPU <NUM>, processor <NUM>, or other computing device may include or access buffers <NUM>, <NUM>, such as defined in a cache <NUM>, <NUM>, RAM <NUM>, or some other hardware location. Values stored in the buffers <NUM>, <NUM> have a first width, such as <NUM> bits. As discussed in detail below, other parts of a computational pipeline of a GPU <NUM>, processor <NUM>, or other computing device, may have a smaller width, such as half of the first width, e.g., <NUM> bits where the first width is <NUM> bits. The values stored in the buffers <NUM>, <NUM> may be values used to implement and apply a convolution neural network (CNN) or other type of neural network. For example, buffer <NUM> may store coefficients of the CNN whereas buffer <NUM> stores the activation values for the CNN, e.g., the values being processed according to the CNN. The manner in which the CNN process is performed may be according to any method known in the art with some or all multiply/accumulate operations being performed according to the methods disclosed herein.

A sequencer <NUM> may read values from the buffers <NUM>, <NUM> in order to perform a multiply/accumulate operation using the values stored in the buffers <NUM>,<NUM>. In particular, the sequencer <NUM> may output a sequence of arguments <NUM>, <NUM> that have the second width and are portions of first values from the buffer <NUM> and second values from the buffer <NUM>. The manner in which the sequencer generates the arguments <NUM>, <NUM> is described in detail below with respect to <FIG>.

The arguments <NUM>, <NUM> are input into a computational pipeline <NUM> that is configured to perform a multiply/accumulate operation. To that end, the pipeline <NUM> may include a multiplier <NUM> that multiplies the arguments <NUM>, <NUM> to produce a product and a summer <NUM> that adds the product to contents of an accumulation buffer <NUM> to obtain a sum and writes the sum to the accumulation buffer <NUM>.

As will be discussed in detail below, the contents of the accumulation buffer <NUM> may be added by an adder <NUM> to contents of a group accumulation buffer <NUM> and the result of this addition written to the group accumulation buffer <NUM>. The manner in which this is performed is also described in detail below. The group accumulation buffer <NUM> may be much wider than the accumulation buffer <NUM>. For example, where the first width is <NUM> bits, the second width is <NUM> bits, the group accumulation buffer may have a width of <NUM> bits whereas the accumulation buffer <NUM> has a width of <NUM> bits.

The contents of the group accumulation buffer <NUM>, following processing according to the methods of <FIG>, is a result of multiplying pairs of values from the buffers <NUM>, <NUM> and accumulating them. The contents of the group accumulation buffer <NUM> may then be used for any purpose desired, such as to implement a CNN or any other process that may benefit from a multiply/accumulate operation. In particular, the multiply/accumulate operation may be used to implement a dot product or matrix multiplication in any context in which these operations are performed.

Referring to <FIG>, the bit positions for each value stored in the buffers <NUM>, <NUM> may define a high portion and a low portion. The high portion has higher magnitude (e.g., higher significance) than the low portion and does not overlap the low portion. The number of bits in the high portion and the number of bits in the low portion is equal to the number of bits in each value stored in the buffers <NUM>, <NUM>. For example, where the buffers <NUM>, <NUM> store <NUM> bit values, bit positions <NUM> through <NUM> may be the high portion and bit positions <NUM> through <NUM> may be the low portion, where bit position <NUM> is defined as the least significant bit (LSB).

The illustrated method <NUM> illustrates one approach for implementing a multiply/accumulate operation. For purposes of the following discussion, let AHi represent the high portion at buffer position i of the buffer <NUM>. Let BHi represent the high portion at buffer position i of the buffer <NUM>. Let ALi represent the low portion at buffer position i of the buffer <NUM>. Let BLi represent the low portion at buffer position i of the buffer <NUM>.

The method <NUM> may include performing <NUM> a multiply/accumulate operation of AHi and BHi for all buffer positions i. Specifically, the sequencer <NUM> may, for each value i from <NUM> to N-<NUM>, where N is the number of values to be processed, output AHi and BHi as arguments <NUM>, <NUM> to be processed according to the pipeline <NUM>. Accordingly the result stored in the accumulation buffer <NUM> following step <NUM> will be <MAT>.

The method <NUM> may then include adding <NUM> the contents of the accumulation buffer <NUM> to contents of the group accumulation buffer <NUM> and writing the result of the addition to the group accumulation buffer <NUM>. Prior to execution of the method <NUM>, the group accumulation buffer <NUM> and accumulation buffer <NUM> may be initialized to zero such that step <NUM> includes simply writing the contents of the accumulation buffer <NUM> to the group accumulation buffer <NUM>. As described below with respect to <FIG>, writing may include shifting the contents of the accumulation buffer by the first width (e.g., <NUM> bits) prior to adding to account for the fact that the high portions AHi and BHi were processed.

The method <NUM> may include performing <NUM> a multiply/accumulate operation of AHi and BLi for all buffer positions i. Specifically, the sequencer <NUM> may, for each value i from <NUM> to N-<NUM>, where N is the number of values to be processed, output AHi and BLi as arguments <NUM>, <NUM> to be processed according to the pipeline <NUM>. Accordingly the result stored in the accumulation buffer <NUM> following step <NUM> will be <MAT>.

The method <NUM> may then include adding <NUM> the contents of the accumulation buffer <NUM> to contents of the group accumulation buffer <NUM> and writing the result of the addition to the group accumulation buffer <NUM>. Prior to execution of the method step <NUM>, the accumulation buffer <NUM> may be initialized to zero. As described below with respect to <FIG>, adding <NUM> may include shifting the contents of the accumulation buffer <NUM> by the second width (e.g., <NUM> bits) prior to adding to account for the fact that the high portions AHi were processed.

The method <NUM> may include performing <NUM> a multiply/accumulate operation of ALi and BLi for all buffer positions i. Specifically, the sequencer <NUM> may, for each value i from <NUM> to N-<NUM>, where N is the number of values to be processed, output ALi and BLi as arguments <NUM>, <NUM> to be processed according to the pipeline <NUM>. Accordingly the result stored in the accumulation buffer <NUM> following step <NUM> will be <MAT>.

The method <NUM> may then include adding <NUM> the contents of the accumulation buffer <NUM> to contents of the group accumulation buffer <NUM> and writing the result of the addition to the group accumulation buffer <NUM>. Prior to execution of the method step <NUM>, the accumulation buffer <NUM> may be initialized to zero. As described below with respect to <FIG>, adding <NUM> will not include shifting the contents of the accumulation buffer <NUM> since only the low precision portions ALi, BLi were processed.

The method <NUM> may include performing <NUM> a multiply/accumulate operation of ALi and BHi for all buffer positions i. Specifically, the sequencer <NUM> may, for each value i from <NUM> to N-<NUM>, where N is the number of values to be processed, output ALi and BHi as arguments <NUM>, <NUM> to be processed according to the pipeline <NUM>. Accordingly the result stored in the accumulation buffer <NUM> following step <NUM> will be <MAT>.

The method <NUM> may then include adding <NUM> the contents of the accumulation buffer <NUM> to contents of the group accumulation buffer <NUM> and writing the result of the addition to the group accumulation buffer <NUM>. Prior to execution of the method step <NUM>, the accumulation buffer <NUM> may be initialized to zero. As described below with respect to <FIG>, adding <NUM> may include shifting the contents of the accumulation buffer <NUM> by the second width (e.g., <NUM> bits) prior to adding to account for the fact that the high portions BHi were processed.

Following execution of the method <NUM>, the group accumulation buffer <NUM> will store the result of performing a multiply/accumulate operations for all the values in buffer positions <NUM> to N - <NUM> in the buffers <NUM>, <NUM>. Note that the ordering of steps <NUM>, <NUM>, <NUM>, and <NUM> is arbitrary and these may be rearranged and substituted with for one another. Note likewise, that buffer positons <NUM> to N - <NUM> are referred to but the starting address for this method and other methods described herein may be any position in memory defining the buffer.

<FIG> illustrates a more detailed method <NUM> for performing a multiply/accumulate operation for values having a first width using a computational pipeline <NUM> having a second width that is half of the first width.

The method <NUM> may include setting <NUM> the position of the first argument <NUM> to be low, i.e., the low portion of first values in the buffer <NUM>. The method <NUM> may further include setting <NUM> the position of the second argument <NUM> to be low, i.e. the low portion of second values in the buffer <NUM>. In this example, the low portions are processed first. This is exemplary only and starting with the high portions may also be performed.

The method <NUM> may include initializing <NUM> the current buffer position to zero and initializing the accumulator buffer <NUM> to zero.

The method <NUM> may then include performing <NUM> a multiply accumulate operation for the portions of the first values at the first argument position and the portions of the second values at the second argument positions. For example, step <NUM> may include using the computational pipeline <NUM> to perform the following operation: <MAT> where:.

The computation of step <NUM> may be performed iteratively, e.g., starting with i = <NUM>, (a) performing multiplication Ai[S(P1 + <NUM>) - <NUM>: S * P1] * Bi[S(P2 + <NUM>) - <NUM>: S * P2] to obtain a product, adding the product to the accumulation buffer <NUM> to obtain a sum, and writing the sum to the accumulation buffer <NUM> and (b) if i is not equal to N - <NUM>, incrementing i and repeating from (a).

The method <NUM> may then include adding <NUM> the contents of the accumulation buffer <NUM> to the contents of the group accumulation buffer <NUM> and writing the result of the addition to the group accumulation buffer <NUM>. The method <NUM> may be preceded with initializing the group accumulation buffer <NUM> to zero.

The method <NUM> may then include evaluating <NUM> whether the second argument position is high, if not, the second argument position <NUM> is set to high and processing continues at step <NUM>. If so, the method <NUM> may include evaluating <NUM> whether the first argument position is high, if not, the first argument position is set <NUM> to high, and processing continues at step <NUM>. If so, the method ends and the value stored in the group accumulation buffer <NUM> is the multiply/accumulation result for the values <NUM> to N - <NUM> in the buffers <NUM>, <NUM>. As noted above, <NUM> to N - <NUM> is exemplary only and any range of memory addresses may be processed according to the method <NUM>. Note further that the range of addresses of the buffer <NUM> may be the same as or different from the range of addresses in the buffer <NUM> that are processed according to the method <NUM>.

Referring to <FIG>, the illustrated method <NUM> may be used when adding the contents of the accumulation buffer <NUM> to the contents of the group accumulation buffer <NUM>. The method <NUM> may include evaluating <NUM> whether both the first and second argument positions are high. If so, the contents of the accumulation buffer <NUM> are left shifted <NUM> (assuming leftmost bit is most significant) by the first width, e.g., <NUM> bits, and the value as shifted at step <NUM> is then added <NUM> to the contents of the group accumulation buffer <NUM> and the result of the addition <NUM> is written to the group accumulation buffer <NUM>.

The method <NUM> may include evaluating <NUM> whether both only one of first and second argument positions are high. If so, the contents of the accumulation buffer <NUM> are left shifted <NUM> (assuming leftmost bit is most significant) by the second width, e.g., <NUM> bits, and the value as shifted at step <NUM> is then added <NUM> to the contents of the group accumulation buffer <NUM> and the result of the addition <NUM> is written to the group accumulation buffer <NUM>.

If neither of the argument positions is high, then no shift is performed and step <NUM> is performed on the un-shifted contents of the accumulation buffer <NUM>.

Claim 1:
A device (<NUM>) comprising:
a first input buffer (<NUM>) having a first width;
a second input buffer (<NUM>) having the first width;
a multiply/accumulate circuit configured to perform a multiply/accumulate operation on input arguments having a second width that is half the first width, the multiply/accumulate circuit having an accumulation buffer having a third width three times the second width;
a group accumulator (<NUM>) configured to accumulate an output the multiply/accumulate circuit, the group accumulator including a group accumulation buffer having a fourth width that is twice the third width;
a sequencer (<NUM>) configured to, read a first value from the first input buffer and read a second value from the second input buffer and processing the first value and the second value by:
performing a multiply/accumulate operation on a high portion of the first value and a high portion of the second value using a computational pipeline having a second width to obtain a first intermediate accumulation;
left shift the first intermediate accumulation by the first width and add the first intermediate accumulation to a group accumulation value stored in the group accumulation buffer;
performing a multiply/accumulate operation on the high portion of the first value and a low portion of the second value to obtain a second intermediate accumulation;
left shift the second intermediate accumulation by the second width and add the second intermediate accumulation to the group accumulation value stored in the group accumulation buffer;
performing a multiply/accumulate operation on a low portion of the first value and the low portion of the second value to obtain a third intermediate accumulation;
add the third intermediate accumulation to the group accumulation value stored in the group accumulation buffer;
performing a multiply/accumulate operation on the low portion of the first value and the high portion of the second value to obtain a fourth intermediate accumulation; and
left shift the fourth intermediate accumulation by the second width and add the fourth intermediate accumulation to the group accumulation value stored in the group accumulation buffer.