Patent Description:
According to aspects of the present invention there is provided a method and apparatus as defined in the accompanying claims.

According to a first example, a method is provided that includes providing a hard-wired integer multiplier circuit configured to multiply a first physical operand and a second physical operand, mapping a first logical operand to a first portion of the first physical operand, mapping a second logical operand to a second portion of the first physical operand, and mapping a third logical operand to the second physical operand. The method further includes multiplying the first physical operand and the second physical operand using the hard-wired integer multiplier circuit to provide a multiplication result that includes a first portion including a product of the first logical operand and the third logical operand, and a second portion including a product of the second logical operand and the third logical operand.

According to a second example, an apparatus is provided that includes a processor and a hard-wired integer multiplier circuit configured to multiply a first physical operand and a second physical operand. The processor is configured to map a first logical operand to a first portion of the first physical operand, map a second logical operand to a second portion of the first physical operand , and map a third logical operand to the second physical operand, and multiply the first physical operand and the second physical operand using the hard-wired integer multiplier circuit to provide a multiplication result that includes a first portion including a product of the first logical operand and the third logical operand, and a second portion including a product of the second logical operand and the third logical operand.

According to a third aspect, a method is provided that includes providing a hard-wired integer multiplier circuit configured to multiply a first physical operand and a second physical operand, converting a first logical operand, a second logical operand and a third logical operand from two's complement representation to sign magnitude representation, removing a first sign bit from the first logical operand, a second sign bit from the second logical operand, and third sign bit from the third logical operand, mapping the first logical operand to a first portion of the first physical operand, mapping the second logical operand to a second portion of the first physical operand , and mapping a third logical operand to the second physical operand, multiplying the first physical operand and the second physical operand using the hard-wired integer multiplier circuit to provide a multiplication result that includes a first portion including a product of the first logical operand and the third logical operand, and a second portion including a product of the second logical operand and the third logical operand, extracting the first portion of the multiplication result and the second portion of the multiplication result, creating a sign-extended first portion of the multiplication result by adding a sign bit to the extracted first portion of the multiplication result based on the first sign bit and the third sign bit, and creating a sign-extended second portion of the multiplication result by adding a sign bit to the extracted second portion of the multiplication result based on the second sign bit and the third sign bit, and converting the sign-extended first portion of the multiplication result to two's complement representation and converting the sign-extended second portion of the multiplication result to two's complement representation.

The above-summarized functionality can be manifested in various types of systems, devices, components, methods, computer readable storage media, data structures, graphical user interface presentations, articles of manufacture, and so on.

This Summary is provided to introduce a selection of concepts in a simplified form; these concepts are further described below in the Detailed Description.

The same numbers are used throughout the disclosure and figures to reference like components and features. Series <NUM> numbers refer to features originally found in <FIG>, series <NUM> numbers refer to features originally found in <FIG>, series <NUM> numbers refer to features originally found in <FIG>, and so on.

Machine learning algorithms, such as deep neural networks, perform numerous mathematical operations. Indeed, by some estimates, more than <NUM>% of the arithmetic operations performed when implementing a deep neural network consist of multiplies/accumulates for matrix-vector multiplication. Although such mathematical operations can be performed by a general-purpose CPU, the computation rate for machine learning algorithms often exceeds the capabilities of even the fastest general-purpose CPU.

For improved processing performance, a hardware acceleration component, such as a field programmable gate array (FPGA) or other reconfigurable logic device, can be used to perform multiplies/accumulates for matrix-vector multiplication. Indeed, contemporary FPGA devices typically include very large numbers of hard-wired integer multiplier circuits (sometimes referred to as "multiplier blocks" or "DSP blocks") that can be used to perform integer multiplies/accumulates for matrix-vector multiplication.

For example, an FPGA device may include <NUM> × <NUM> multiplier blocks that each have two inputs (referred to herein as a first physical operand and a second physical operand) and a single output. <FIG> is a simplified block diagram of an example <NUM> × <NUM> multiplier block <NUM> that includes a first physical operand X, a second physical operand Y, and an output Z. First physical operand X has an <NUM>-bit width and includes bits x<NUM>, x<NUM>,. , x<NUM>, second physical operand Y has an <NUM>-bit width and includes bits y<NUM>, y<NUM>,. , y<NUM>, and output Z has a <NUM>-bit width and includes bits z<NUM>, z<NUM>,.

The bit widths of first physical operand X, second physical operand Y, and output Z are referred to herein as native bit width. Some FPGA devices have multiplier blocks that can be configured to varying native bit widths. For example, some multiplier blocks can be configured to operate in a first mode (e.g., as an <NUM> × <NUM> multiplier), a second mode (e.g., as an <NUM> × <NUM> multiplier), and a third mode (e.g., as a <NUM> × <NUM> multiplier).

Although some FPGAs have variable prevision multiplier blocks, the native bit widths of multiplier blocks in FPGAs exceeds the required precision for some machine learning algorithms. Indeed, recent research has shown that deep neural networks can be implemented using low numerical precision (e.g., as low as two bits) at minimal or no losses to model accuracy.

As described in more detail below, technology is described for using data packing techniques for hard-wired multiplier circuits in configurable logic devices, such as FPGAs. Without wanting to be bound by any particular theory, it is believed that such data packing techniques may increase a number of simultaneous multiplication operations that may be performed on each hard-wired multiplier circuit. In addition, without wanting to be bound by any particular theory, it is believed that such data packing techniques may improve processing speed and throughput of machine learning algorithms, such as deep neural networks using relatively low numerical precision.

As a preliminary matter, some of the figures describe concepts in the context of one or more structural components, variously referred to as functionality, modules, features, elements, etc. The various components shown in the figures can be implemented in any manner by any physical and tangible mechanisms, for instance, by software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof.

In one case, the illustrated separation of various components in the figures into distinct units may reflect the use of corresponding distinct physical and tangible components in an actual implementation. Alternatively, or in addition, any single component illustrated in the figures may be implemented by more than one actual physical component. Alternatively, or in addition, the depiction of any two or more separate components in the figures may reflect different functions performed by a single actual physical component.

Other figures describe concepts in flowchart form. In this form, certain operations are described as constituting distinct blocks performed in a certain order. Such implementations are illustrative and non-limiting. Certain blocks described herein can be grouped together and performed in a single operation, certain blocks can be broken apart into multiple component blocks, and certain blocks can be performed in an order that differs from that which is illustrated herein (including a parallel manner of performing the blocks). Blocks shown in the flowcharts can be implemented in any manner by any physical and tangible mechanisms, for instance, by software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof.

As to terminology, the phrase "configured to" encompasses any way that any kind of physical and tangible functionality can be constructed to perform an identified operation. The functionality can be configured to perform an operation using, for instance, software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof.

The term "logic" encompasses any physical and tangible functionality for performing a task. For instance, each operation illustrated in the flowcharts corresponds to a logic component for performing that operation. An operation can be performed using, for instance, software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof. When implemented by computing equipment, a logic component represents an electrical component that is a physical part of the computing system, however implemented.

The following explanation may identify one or more features as "optional. " This type of statement is not to be interpreted as an exhaustive indication of features that may be considered optional. That is, other features can be considered as optional, although not explicitly identified in the text. Further, any description of a single entity is not intended to preclude the use of more than one such entity. Similarly, a description of multiple entities is not intended to preclude the use of a single entity. Further, although the description may explain certain features as alternative ways of carrying out identified functions or implementing identified mechanisms, the features also can be combined together in any combination. Finally, the terms "exemplary" or "illustrative" refer to an implementation among potentially many implementations.

<FIG> illustrates an example environment <NUM> in which example packed multiplier circuits, such as for use with machine learning algorithms, as described herein can operate. In some examples, the various devices and/or components of environment <NUM> include a variety of computing devices <NUM>. By way of example and not limitation, computing devices <NUM> may include devices 202a-202e. Although illustrated as a diverse variety of device types, computing devices <NUM> can be other device types and are not limited to the illustrated device types. In some implementations any of a number of computing devices <NUM> may be interconnected via a network <NUM>.

Network <NUM> can include, but is not limited to, a cellular network (e.g., wireless phone), a point-to-point dial up connection, a satellite network, the Internet, a local area network, a wide area network, a WiFi network, an ad hoc network, an intranet, an extranet, or a combination thereof. Network <NUM> may include one or more connected networks (e.g., a multi-network environment). Network <NUM> may include one or more data centers that store and/or process information (e.g., data) received from and/or transmitted to computing devices <NUM>.

In an implementation, computing devices <NUM> can include any type of device with one or multiple processors <NUM> operably connected to an input/output interface <NUM>, a hardware accelerator <NUM>, and a memory <NUM>, e.g., via a bus <NUM>. Computing devices <NUM> can include personal computers such as, for example, desktop computers 202a, laptop computers 202b, tablet computers 202c, data center servers 202d (or servers is any other environment), smart phones 202e, electronic book readers, wearable computers, automotive computers, gaming devices, etc. In an implementation, computing devices <NUM> need not include processor <NUM>, and may be a hardware appliance.

Computing devices <NUM> also can include other computing devices such as, for example, server computers, thin clients, terminals, and/or work stations. In some examples, computing devices <NUM> can include, for example, components for integration in a computing device, appliances, or other sorts of devices.

In some examples, some or all of the functionality described as being performed by computing devices <NUM> may be implemented by one or more remote peer computing devices, a remote server or servers, or a cloud computing resource. In some examples, a computing device <NUM> may include an input port to receive an input data sequence. Computing device <NUM> may further include one or multiple processors <NUM> to perform machine learning processing, for example.

In some examples, as shown regarding device 202d, memory <NUM> can store instructions executable by the processor(s) <NUM> including an operating system <NUM>, and programs or applications <NUM> that are loadable and executable by processor(s) <NUM>. Applications <NUM> may include machine learning processor applications <NUM> that may be executed to operate hardware accelerator <NUM>, for example. The one or more processors <NUM> may include one or more central processing units (CPUs), graphics processing units (GPUs), video buffer processors, and so on.

In some implementations, machine learning processor applications <NUM> include executable code stored in memory <NUM> and executable by processor(s) <NUM> to receive and implement machine learning algorithms that include data sequences (e.g., streaming data or data files), locally or remotely by computing device <NUM>, via input/output interface <NUM>. In some examples, the data sequences may be associated with one or more applications <NUM>. Machine learning processor applications <NUM> may operate in combination with hardware accelerator <NUM> to apply any of a number of processes, such as packed multiplier operators, used to process data stored in memory <NUM> or received via input/output interface <NUM>.

Although certain blocks have been described as performing various operations, the modules are merely examples and the same or similar functionality may be performed by a greater or lesser number of modules. Moreover, the functions performed by the modules depicted need not necessarily be performed locally by a single device. Rather, some operations could be performed by a remote device (e.g., peer, server, cloud, etc.).

Alternatively, or in addition, some or all of the functionality described herein can be performed, at least in part, by one or more hardware logic circuits. For example, and without limitation, illustrative types of hardware logic circuits that can be used include an FPGA device, an application-specific integrated circuit (ASIC) device, a GPU, a massively parallel processor array (MPPA) device, an application-specific standard product (ASSP) device, a system-on-a-chip device (SOC) device, a complex programmable logic device (CPLD), a custom integrated circuit, etc..

For example, all or a portion of hardware accelerator <NUM> may be implemented on one or more FPGAs, ASICs, GPUs, MPPAs, ASSPs, SOCs, CPLDs, and/or custom integrated circuits. The term "hardware" accelerator broadly encompasses different ways of leveraging a hardware device to perform a function, including, for instance, at least: a) a case in which at least some tasks are implemented in hard ASIC logic or the like; b) a case in which at least some tasks are implemented in soft (configurable) FPGA logic or the like; c) a case in which at least some tasks run as software on FPGA software processor overlays or the like; d) a case in which at least some tasks run on MPPAs of soft processors or the like; e) a case in which at least some tasks run as software on hard ASIC processors or the like, and so on, or any combination thereof.

The following explanation will present a primary example in which hardware accelerators, such as hardware accelerator <NUM>, correspond to one or more FPGA devices, although, as noted, hardware accelerators may be constructed using other types of hardware logic circuits.

Computer readable media may include computer storage media and/or communication media. Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, phase change memory (PRAM), static random-access memory (SRAM), dynamic random-access memory (DRAM), other types of random-access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disk read-only memory (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device.

In contrast, communication media embodies computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer storage media does not include communication media. In various examples, memory <NUM> is an example of computer storage media storing computer-executable instructions.

In various examples, an input device of input/output interface <NUM> can be a direct-touch input device (e.g., a touch screen), an indirect-touch device (e.g., a touch pad), an indirect input device (e.g., a mouse, keyboard, a camera or camera array, etc.), or another type of non-tactile device, such as an audio input device.

Computing device(s) <NUM> also may include one or more input/output interfaces <NUM> to allow computing device <NUM> to communicate with other devices. Input/output interface <NUM> can include one or more network interfaces to enable communications between computing device <NUM> and other networked devices such as other device(s) <NUM>. Input/output interface <NUM> can allow a computing device <NUM> to communicate with other devices such as user input peripheral devices (e.g., a keyboard, a mouse, a pen, a game controller, a voice input device, a touch input device, gestural input device, and the like) and/or output peripheral devices (e.g., a display, a printer, audio speakers, a haptic output, and the like).

<FIG> is a block diagram depicting an example system <NUM> that includes any number of servers <NUM> and computing devices <NUM> in communication with a network <NUM>. At least a portion of servers <NUM> and/or computing devices <NUM> are located in one or more data centers <NUM>, as indicated by the dashed arrows. Such communication, for example, may involve transmitting and/or receiving data among servers <NUM>, computing devices <NUM>, and data center <NUM> via network <NUM> at relatively fast network rates. For example, data received in data center <NUM> may include network data traffic via the Internet (e.g., network <NUM>), for example. Such data may be received by the data center at network speeds that exceed <NUM> Gb/sec, for example.

Individual servers <NUM> and computing devices <NUM>, for example, may be the same as or similar to computing device <NUM> described above and illustrated in <FIG>. Network <NUM> may the same as or similar to network <NUM>, for example, described in <FIG>. In some examples, data center <NUM> is a facility used to house computer systems and associated components, such as telecommunications and storage systems. Such a data center may include, among other things, redundant or backup power supplies, redundant data communications connections, environmental controls (e.g., air conditioning, fire suppression), and various security devices. Data centers may involve industrial-scale operations and relatively large amount of electrical power for supporting operations.

<FIG> is a block diagram depicting an example system <NUM> that includes any number of processors <NUM> and FPGAs <NUM>. System <NUM>, which may be incorporated in a data center (e.g., data center <NUM> of <FIG>) for example, may be similar to or the same as computing device <NUM> described above and illustrated in <FIG>. System <NUM> may be configured to implement machine learning algorithms that are received into the data center or transmitted from the data center. In some implementations, such data may be transmitted through FPGAs <NUM>, for example. FPGAs <NUM> may directly communicate with memory <NUM>, which may store data during machine learning processing performed with FPGAs <NUM>.

In some examples, FPGAs <NUM> may be the same as or similar to hardware accelerator <NUM> described above and illustrated in <FIG>. In various implementations, system <NUM> may include any number of ASICs, GPUs, MPPAs, ASSPs, SOCs, CPLDs, custom integrated circuits, or a combination thereof, in addition to or in place of FPGAs <NUM>. In other words, for example, machine learning processor applications that perform packed multiplier operations described herein may be implemented using any of a number of hardware configurations, such as those listed above.

As described above, machine learning algorithms typically perform numerous matrix-vector multiplication operations. An example of a simple matrix-vector multiplication operation A × v = o is shown below: <MAT>.

In this example, a 3x3 matrix A is multiplied by a <NUM>-dimensional vector v, and the result is a <NUM>-dimensional output vector o having elements o1, o2 and o3. Elements o1, o2 and o3 can be written as: <MAT> <MAT> <MAT>.

Thus, this example matrix-vector multiplication includes nine multiplications: (a × k), (b × k), (c × k), (d × <NUM>), (e × l), (f × l), (g × m), (h × m) and (i × m). In a conventional FPGA implementation, three separate multiplier blocks (e.g., three separate <NUM> × <NUM> multiplier blocks) may be used to perform these nine multiplications.

For example, <FIG> are block diagrams depicting an implementation of three separate <NUM> × <NUM> multiplier blocks <NUM>(<NUM>)-<NUM>(<NUM>) (e.g., each identical to multiplier block <NUM> of <FIG>) coupled to corresponding accumulators <NUM>(<NUM>)-<NUM>(<NUM>), respectively, used to implement the matrix vector multiplication of Equations (<NUM>)-(<NUM>), above.

In an implementation, multiplier block <NUM>(<NUM>) has a first physical operand X1, a second physical operand Y1, and provides a multiplication result Z <NUM> that is coupled to an input of an accumulator <NUM>(<NUM>). Multiplier block <NUM>(<NUM>) has a first physical operand X2, a second physical operand Y2, and provides a multiplication result Z2 that is coupled to an input of an accumulator <NUM>(<NUM>). Multiplier block <NUM>(<NUM>) has a first physical operand X3, a second physical operand Y3, and provides a multiplication result Z3 that is coupled to an input of an accumulator <NUM>(<NUM>).

<FIG> depict the operation of multiplier blocks <NUM>(<NUM>)-<NUM>(<NUM>) and corresponding accumulators <NUM>(<NUM>)-<NUM>(<NUM>), respectively, at three separate time instants to implement the matrix vector multiplication of Equations (<NUM>)-(<NUM>), above. In <FIG>, at a first time instant,.

At the completion of the multiply-accumulate operation of <FIG>, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have values (a × k), (b × k), and (c × k), respectively.

In <FIG>, at a second time instant after the first time instant,.

At the completion of the multiply-accumulate operation of <FIG>, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have values (a × k) + (d × <NUM>), (b × k) + (e × <NUM>), and (c × k) + (f × <NUM>), respectively.

In <FIG>, at a third time instant after the second time instant,.

At the completion of the multiply-accumulate operation of <FIG>, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have values (a × k) + (d × <NUM>) + (g × m), (b × k) + (e × <NUM>) + (h × m), and (c × k) + (f × <NUM>) + (i × m), respectively. Thus, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have the values o1, o2 and o3, respectively, of Equations (<NUM>)-(<NUM>), above.

If the elements a, b,. , i of matrix A and the elements k, l, m of vector v each have a bit width less than the native bit width of the multiplier block, data packing multiplication techniques may be used to reduce the number of separate multiplier blocks needed to perform the various multiplications described above. <FIG> depict various implementations of data packing multiplication techniques.

For example, <FIG> is a diagram illustrating an implementation of a data packing multiplication operation using an <NUM> × <NUM> multiplier block <NUM> (e.g., identical to multiplier block <NUM> of <FIG>) that includes a first physical operand X6, a second physical operand Y6, and an output Z6. First physical operand X6 has an <NUM>-bit width, second physical operand Y6 has an <NUM>-bit width, and output Z6 has a <NUM>-bit width.

In an implementation, multiplier block <NUM> may be used to perform the multiplications (a × k) and (b × k), with elements a, b and k each having six bit precision, as follows:.

Steps (i) - (v) may be performed by a processor, such as a processor implemented in hardware accelerator <NUM> of <FIG>, or other processor.

Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. A first portion of result Z6 represents the product (b × k), and a second portion of result Z6 represents the product (a × k). In particular, an (R + U) = <NUM> least significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (b × k), and an (S + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (a × k).

Thus, by mapping R = S = <NUM>-bit logical operands a and b to first physical operand X6, with T = <NUM> zero padding bits inserted between the two mapped operands, and mapping U = <NUM>-bit logical operand k to second physical operand Y6, a single multiplier block may be used to simultaneously perform two separate multiplication operations. To prevent carries from the first product (b × k) from interfering with the result of the second product (a × k), the number T of zero padding bits inserted between the mapped logical operands a and b in the first physical operand X6 is equal to the maximum bit width of logical operands a, b and k (e.g., T = max (R, S, U) = <NUM> bits).

In the implementation depicted in <FIG>, each logical operand (a, b, k) has a bit width exactly one-third of the width of first physical operand X6 and second physical operand Y6. In other implementations, logical operands (a, b, k) may each have a bit width less than one-third of the width of first physical operand X6 and second physical operand Y6. For example, <FIG> illustrates an implementation of a data packing multiplication operation in which multiplier block <NUM> is used to perform the multiplications (a × k) and (b × k), with elements a, b and k each having five bit precision, as follows:.

Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. A first portion of result Z6 represents the product (b × k), and a second portion of result Z6 represents the product (a × k). In particular, an (R + U) = <NUM> least significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (b × k), and an (S + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (a × k). As in the previous implementation, to prevent carries from the first product (b × k) from interfering with the result of the second product (a × k), the number T zero padding bits inserted between the mapped logical operands a and b in the first physical operand X6 is equal to the maximum bit width of logical operands a, b and k (e.g., T = max (R, S, U) = <NUM> bits).

In the implementations depicted in <FIG>, each logical operand (a, b, k) has the same width (i.e., R = S = U). In other implementations, logical operands (a, b, k) may have different widths. For example, <FIG> illustrates an implementation of a data packing multiplication operation in which multiplier block <NUM> is used to perform the multiplications (a × k) and (b × k), with elements a, b and k having different bit widths, as follows:.

Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. A first portion of result Z6 represents the product (b × k), and a second portion of result Z6 represents the product (a × k). In particular, an (R + U) = <NUM> least significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (b × k), and an (S + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (a × k). To prevent carries from the first product (b × k) from interfering with the result of the second product (a × k), the number T of zero padding bits inserted between the mapped logical operands a and b in the first physical operand X6 is equal to the maximum bit width of logical operands a, b and k (e.g., T = max (R, S, U) = <NUM> bits).

In the implementations depicted in <FIG>, two logical operands (a, b) are mapped to first physical operand X6. In other implementations, more than two logical operands may be mapped to first physical operand X6. For example, <FIG> illustrates an implementation of a data packing multiplication operation in which multiplier block <NUM> is used to perform the multiplications (a × k), (b × k) and (c × k), with elements a, b, c and k each having three bit precision, as follows:.

Steps (i) - (vi) may be performed by a processor, such as a processor implemented in hardware accelerator <NUM> of <FIG>, or other processor.

Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. A first portion of result Z6 represents the product (c × k), a second portion of result Z6 represents the product (b × k), and a third portion of result Z6 represents the product (a × k). In particular, an (R + U) = <NUM> least significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (c × k), an (S + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (b × k), and a (W + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (a × k).

Thus, by mapping R = S = W = <NUM>-bit logical operands a, b and c to a single physical operand X6 of multiplier block <NUM>, with T = <NUM> zero padding bits between each of the three mapped operands, and mapping U = <NUM>-bit logical operand k to second physical operand Y6, a single multiplier block may be used to simultaneously perform three separate multiplication operations. To prevent carries from the first product (c × k) from interfering with the result of the second product (b × k), and to prevent carries from the second product (b × k) from interfering with the result of the second product (a × k), the number T of zero padding bits inserted between the mapped logical operands a and b and c and b in the first physical operand X6 is equal to the maximum bit width of logical operands a, b, c and k (e.g., T = max (R, S, W, U) = <NUM> bits).

In the implementations depicted in <FIG>, the number T of zero-padding bits inserted between the mapped logical operands in the first physical operand X6 is equal to the maximum bit width of logical operands a, b, c and k (e.g., T = max (R, S, W, U)). In another implementation, the T number of zero-padding bits inserted between the mapped logical operands in the first physical operand X6 is less than the maximum bit width of logical operands a, b, c and k. For example, <FIG> illustrates an implementation of a data packing multiplication operation in which multiplier block <NUM> is used to perform the multiplications (a × k), (b × k) and (c × k), with elements a, b, c and k each having four bit precision, as follows:.

Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. A first portion of result Z6 represents the product (c × k)*, a second portion of result Z6 represents the product (b × k)*, and a third portion of result Z6 represents the product (a × k)*. In particular, an (R + U) = <NUM> least significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (c × k)*, an (S + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (b × k)*, and a (W + U) = <NUM> next most significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (a × k)*.

Because the number T = <NUM> zero padding bits inserted between the mapped logical operands a and b and c and b in the first physical operand X6 is less than the maximum bit width of logical operands a, b, c and k (e.g., four bits), carries from the first product (c × k)* may interfere with the result of the second product (b × k)*, and carries from the second product (b × k)* may interfere with the result of the second product. As a result, the products (c × k)*, (b × k)*, and (a × k)* of the implementation of <FIG> may not equal the products (c × k), (b × k), and (a × k), respectively, of the implementation of <FIG>.

However, because neural networks are inherently tolerant to noise, in some implementations the zero padding between operands may be reduced (such as in the implementation of <FIG>), potentially allowing carries between partial products to interfere, without significantly impacting accuracy. Thus, the number of multiplication results obtained from a single multiplier block may be increased by reducing zero padding between operands, in exchange for some sacrifice of neural network accuracy.

In an implementation, additional logic circuits (e.g., soft logic on an FPGA) may be used to process the output of data-packed multiplier blocks. For example, FIGS. 6FA-<FIG> depict an implementations of a data packing multiplication operation of multiplier block <NUM> (e.g., identical to multiplier block <NUM> of <FIG>) and accumulators <NUM>(<NUM>)-<NUM>(<NUM>) at three separate time instants to implement the matrix vector multiplication of Equations (<NUM>)-(<NUM>), above, using three-bit matrix elements a-i and three bit vector elements k-m. Result Z6 of multiplier block <NUM> is coupled to accumulators <NUM>(<NUM>)-<NUM>(<NUM>) as follows: bits z12-z17 of result Z6 are coupled to an input of accumulator <NUM>(<NUM>), bits z6-z11 of result Z6 are coupled to an input of accumulator <NUM>(<NUM>), and bits z0-z5 of result Z6 are coupled to an input of accumulator <NUM>(<NUM>).

In <FIG>, at a first time instant, first logical operand (a), second logical operand (b) and third logical operand (c) are mapped to first physical operand X6, and fourth logical operand k is mapped to second physical operand Y6, such as described above in connection with <FIG>. Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. Bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (a × k) and are coupled to the input of accumulator <NUM>(<NUM>), bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (b × k) and are coupled to the input of accumulator <NUM>(<NUM>), and bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (c × k) and are input to accumulator <NUM>(<NUM>). At the completion of the multiply-accumulate operation of <FIG>, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have values (a × k), (b × k), and (c × k), respectively.

In <FIG>, at a second time instant after the first time instant, first logical operand d, second logical operand e and third logical operand f are mapped to first physical operand X6, and fourth logical operand <NUM> is mapped to second physical operand Y6, such as described above in connection with <FIG>. Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. Bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (d × <NUM>) and are coupled to the input of accumulator <NUM>(<NUM>), bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (e × <NUM>) and are coupled to the input of accumulator <NUM>(<NUM>), and bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (f × <NUM>) and are input to accumulator <NUM>(<NUM>). At the completion of the multiply-accumulate operation of <FIG>, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have values (a × k) + (d × <NUM>), (b × k) + (e × <NUM>), and (c × k) + (f × <NUM>), respectively.

In <FIG>, at a third time instant after the second time instant, first logical operand g, second logical operand h and third logical operand i are mapped to first physical operand X6, and fourth logical operand m is mapped to second physical operand Y6, such as described above in connection with <FIG>. Multiplier block <NUM> is then used to multiply the first physical operand by the second physical operand, and produce a result Z6. Bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (g × m) and are coupled to the input of accumulator <NUM>(<NUM>), bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (h × m) and are coupled to the input of accumulator <NUM>(<NUM>), and bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 are the product (i× m) and are input to accumulator <NUM>(<NUM>). At the completion of the multiply-accumulate operation of <FIG>, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have values (a × k) + (d × <NUM>) + (g × m), (b × k) + (e × <NUM>) + (h × m), and (c × k) + (f × <NUM>) + (i × m), respectively. Thus, accumulators <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(<NUM>) have the values o1, o2 and o3, respectively, of Equations (<NUM>)-(<NUM>), above.

In the implementations of data packing multiplication operations described above and depicted in <FIG>, multiplier block <NUM> is an <NUM> × <NUM> multiplier block including a first physical operand having an <NUM>-bit width, a second physical operand having an <NUM>-bit width, and an output having a <NUM>-bit width. In other implementations, multiplier blocks may be used that have other native bit widths, such as <NUM> × <NUM> multiplier blocks, <NUM> × <NUM> multiplier blocks, etc. In addition, other implementations, multiplier blocks may be used in which the first physical operand has a first bit width, and the second physical operand has a second bit width different from the first bit width (e.g., <NUM> × <NUM> multiplier blocks, etc.).

In the implementations of data packing multiplication operations described above, the matrix elements a-i and vector elements k-m have been assumed to be positive integers. The techniques described above can be used to multiply positive and negative numbers, but the sign bit for each element are handled separately from the multiplication operation.

<FIG> is a flowchart of an implementation of a process <NUM> for multiplying signed numbers using the data packing multiplication operations described above. In an implementation, circuitry on hardware accelerator <NUM> of <FIG> implements process <NUM>, although in other implementations, some other circuit or combination of circuits may implement process <NUM>. In the description below of an implementation of process <NUM>, elements to be multiplied, such as matrix elements a-i and vector elements k-m described above, are assumed to be in two's complement representation. In the following description, except as otherwise noted, logical operands are assumed to be in two's complement representation prior to the multiplication operation.

At step <NUM>, the logical operands to be multiplied are converted from two's complement representation to sign magnitude representation, in which the most significant bit represents the sign (e.g., <NUM> = positive, <NUM> = negative) of the number. For example, in the example described above and depicted in <FIG>, each of logical operands (a), (b) and (k) are converted from two's complement representation to sign magnitude representation. In embodiments in which logical operands are already in sign magnitude representation, step <NUM> may be omitted.

Referring again to <FIG>, at step <NUM> the sign bit of each logical operand is stripped off and reserved (e.g., in a data register). For example, in the example described above and depicted in <FIG>, the sign bit of each of logical operands (a), (b) and (k) is stripped off and saved in memory, such as in a data register in hardware accelerator <NUM> of <FIG>.

Referring again to <FIG>, at step <NUM> the multiplication operation is performed. For example, the data packing multiplication operations described above in and depicted in <FIG> may be performed to produce two multiplication results: a first portion of result Z6 represents the product (b × k), and a second portion of result Z6 represents the product (a × k).

Referring again to <FIG>, at step <NUM> the multiple multiplication results are extracted. For example, as described above in connection with <FIG>, the twelve least significant bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 may be extracted as the product (b × k), and the next twelve bits z<NUM>, z<NUM>,. , z<NUM> of result Z6 may be extracted as the product (a × k).

Referring again to <FIG>, at step <NUM> the sign of each multiplication result is determined. In an implementation, an exclusive-OR of the sign bits stripped off at step <NUM> provide the sign bit for each multiplication result. For example, an exclusive-OR of the sign bits of elements (b) and (k) provides the sign bit of the product (b × k), and an exclusive-OR of the sign bits of elements (a) and (k) provides the sign bit of the product (a × k).

Referring again to <FIG>, at step <NUM> the sign bits determined at step <NUM> are added as the most significant bit of each multiplication result extracted at step <NUM> to create sign-extend versions of each multiplication result.

At step <NUM>, each sign-extended multiplication result is converted from sign magnitude representation to two's complement representation. In other embodiments, step <NUM> may be omitted if it is desired to keep the multiplication results in sign magnitude representation.

Unless otherwise noted, all of the methods and processes described above may be embodied in whole or in part by software code modules executed by one or more general purpose computers or processors. The code modules may be stored in any type of computer-readable storage medium or other computer storage device. Some or all of the methods may alternatively be implemented in whole or in part by specialized computer hardware, such as FPGAs, ASICs, etc..

Conditional language such as, among others, "can," "could," "might" or "may," unless specifically stated otherwise, are used to indicate that certain examples include, while other examples do not include, the noted features, elements and/or steps. Thus, unless otherwise stated, such conditional language is not intended to imply that features, elements and/or steps are in any way required for one or more examples or that one or more examples necessarily include logic for deciding, with or without user input or prompting, whether these features, elements and/or steps are included or are to be performed in any particular example.

Conjunctive language such as the phrase "at least one of X, Y or Z," unless specifically stated otherwise, is to be understood to present that an item, term, etc., may be either X, or Y, or Z, or a combination thereof.

Many variations and modifications may be made to the above-described examples, the elements of which are to be understood as being among other acceptable examples. All such modifications and variations are intended to be included herein within the scope of this disclosure.

The following summary provides a non-exhaustive list of illustrative aspects of the technology set forth herein.

According to a first aspect, a method is provided that includes providing a hard-wired integer multiplier circuit configured to multiply a first physical operand and a second physical operand, mapping a first logical operand to a first portion of the first physical operand, mapping a second logical operand to a second portion of the first physical operand , and mapping a third logical operand to the second physical operand. The method further includes multiplying the first physical operand and the second physical operand using the hard-wired integer multiplier circuit to provide a multiplication result that includes a first portion including a product of the first logical operand and the third logical operand, and a second portion including a product of the second logical operand and the third logical operand.

According to a second aspect, the method further includes inserting zero padding bits between the first portion of the first physical operand and the second portion of the first physical operand.

According to a third aspect, a number of zero padding bits includes a maximum word length of the first logical operand, the second logical operand, and the third logical operand.

According to a fourth aspect, a number of zero padding bits includes less than a maximum word length of the first logical operand, the second logical operand, and the third logical operand.

According to a fifth aspect, the method further includes coupling the first portion of the multiplication result to a first accumulator, and coupling the second portion of the multiplication result to a second accumulator.

According to a sixth aspect, the method further includes converting the first logical operand to a sign magnitude representation before mapping the first logical operand to the first portion of the first physical operand, converting the second logical operand to a sign magnitude representation before mapping the second logical operand to the second portion of the first physical operand , and converting the third logical operand to a sign magnitude representation before mapping the third logical operand to the second physical operand.

According to a seventh aspect, the method further includes extracting the first portion of the multiplication result, extracting the second portion of the multiplication result, converting the extracted first portion of the multiplication result to two's complement representation , and converting the extracted second portion of the multiplication result to two's complement representation.

According to an eighth aspect, the method further includes mapping a fourth logical operand to a third portion of the first physical operand, wherein multiplying further provides a multiplication result that includes a third portion including a product of the fourth logical operand and the third logical operand.

According to a ninth aspect, the first logical operand includes a bit width R, the second logical operand includes a bit width S, the third logical operand includes a bit width U, an (R + U) least significant bits of the multiplication result includes the product of the first logical operand and the third logical operand, and an (S + U) next most significant bits of the multiplication result includes the product of the second logical operand and the third logical operand.

According to a tenth aspect, the hard-wired integer multiplier can be configured to varying native bit widths.

According to an eleventh aspect, the hard-wired integer multiplier includes a field programmable gate array.

According to a twelfth aspect, a machine learning algorithm includes a matrix including a first element including the first logical operand and a second element including the second logical operand, and a vector including an element including the third logical operand, and the multiplication result includes a first element of a matrix-vector multiplication and a second element of the matrix-vector multiplication.

According to a thirteenth aspect, an apparatus is provided that includes a processor and a hard-wired integer multiplier circuit configured to multiply a first physical operand and a second physical operand. The processor is configured to map a first logical operand to a first portion of the first physical operand, map a second logical operand to a second portion of the first physical operand, and map a third logical operand to the second physical operand, and multiply the first physical operand and the second physical operand using the hard-wired integer multiplier circuit to provide a multiplication result that includes a first portion including a product of the first logical operand and the third logical operand, and a second portion including a product of the second logical operand and the third logical operand.

According to a fourteenth aspect, the processor is further configured to insert zero padding bits between the first portion of the first physical operand and the second portion of the first physical operand.

According to a fifteenth aspect, a number of zero padding bits includes a maximum word length of the first logical operand, the second logical operand, and the third logical operand.

According to a sixteenth aspect, a number of zero padding bits includes less than a maximum word length of the first logical operand, the second logical operand, and the third logical operand.

According to a seventeenth aspect, the apparatus further includes a first accumulator coupled to the first portion of the multiplication result, and a second accumulator coupled to the second portion of the multiplication result.

According to an eighteenth aspect, the apparatus further includes a field programmable gate array.

According to a nineteenth aspect, a method is provided that includes providing a hard-wired integer multiplier circuit configured to multiply a first physical operand and a second physical operand, converting a first logical operand, a second logical operand and a third logical operand from two's complement representation to sign magnitude representation, removing a first sign bit from the first logical operand, a second sign bit from the second logical operand, and third sign bit from the third logical operand, mapping the first logical operand to a first portion of the first physical operand, mapping the second logical operand to a second portion of the first physical operand , and mapping a third logical operand to the second physical operand, multiplying the first physical operand and the second physical operand using the hard-wired integer multiplier circuit to provide a multiplication result that includes a first portion including a product of the first logical operand and the third logical operand, and a second portion including a product of the second logical operand and the third logical operand, extracting the first portion of the multiplication result and the second portion of the multiplication result, creating a sign-extended first portion of the multiplication result by adding a sign bit to the extracted first portion of the multiplication result based on the first sign bit and the third sign bit, and creating a sign-extended second portion of the multiplication result by adding a sign bit to the extracted second portion of the multiplication result based on the second sign bit and the third sign bit, and converting the sign-extended first portion of the multiplication result to two's complement representation and converting the sign-extended second portion of the multiplication result to two's complement representation.

According to a twentieth aspect, the hard-wired integer multiplier includes a field programmable gate array.

Claim 1:
A method comprising:
providing a hard-wired integer multiplier circuit (<NUM>) configured to multiply a first physical operand and a second physical operand;
mapping a first logical operand to a first portion of the first physical operand;
mapping a second logical operand to a second portion of the first physical operand;
mapping a third logical operand to the second physical operand;
mapping a fourth logical operand to a third portion of the first physical operand;
multiplying the first physical operand and the second physical operand using the hard-wired integer multiplier circuit (<NUM>) to provide a multiplication result that includes a first portion comprising a product of the first logical operand and the third logical operand, a second portion comprising a product of the second logical operand and the third logical operand and a third portion comprising a product of the third logical operand and the fourth logical operand;
wherein the mapping to the first physical operand comprises:
inserting a number of zero padding bits between the first portion of the first physical operand and the second portion of the first physical operand,
where the number of zero padding bits is less than a maximum word length of the first logical operand, the second logical operand, and the third logical operand; and
wherein the mapping to the first physical operand further comprises: inserting a second number of zero paddings bits between the second portion of the first physical operand and the third portion of the first physical operand,
where the second number of zero padding bits is less than a maximum word length of the first logical operand, the second logical operand, the third logical operand and the fourth logical operand.