Patent Description:
Accordingly, it may be understood that these statements are to be read in this light, and not as admissions of prior art.

Integrated circuit devices may be utilized for a variety of purposes or applications, such as digital signal processing, machine learning, and cryptocurrency or other blockchain-related applications. Programmable logic devices may be utilized to perform these functions, for example, using particular circuitry (e.g., processing blocks). In some cases, particular circuitry that is effective for performing multiplication operations (e.g., modular multiplication operations) may perform these operations with a latency that is undesirably high, the particular circuitry may occupy an undesirable amount of area on an integrated circuit device, or both.

The terms "including" and "having" are intended to be inclusive and mean that there may be additional elements other than the listed elements. Additionally, it should be understood that references to "some embodiments," "embodiments," "one embodiment," or "an embodiment" of the present disclosure are not intended to be interpreted as excluding the existence of additional embodiments that also incorporate the recited features. Furthermore, the phrase A "based on" B is intended to mean that A is at least partially based on B. Moreover, the term "or" is intended to be inclusive (e.g., logical OR) and not exclusive (e.g., logical XOR). In other words, the phrase A "or" B is intended to mean A, B, or both A and B.

As various applications such as machine leaning, artificial intelligence applications, cryptocurrency-related applications, and digital signal processing (DSP) applications have become ever more prevalent, there is an increasing desire to perform various operations associated with these applications in more efficient manners. For example, there may be a desire to alter (e.g., reduce) the amount of circuitry utilized to perform one or more of these operations in order to provide space for circuitry to perform one or more other operations. Similarly, there may be a desire to decrease the amount of time used to perform the operations associated with these applications. In other words, performing these operations in a lower latency manner may be desirable, for example, to enable the operations to be performed more quickly. Keeping this in mind, the presently described techniques relate to reducing latency associated with modular multiplication operations as well as reducing the amount of circuitry utilized to perform modular multiplication operations. For example, modular multiplication operations may be performed by an integrated circuit device, including programmable logic devices such as FPGAs, application-specific standard products (ASSPs), and application-specific integrated circuit (ASICs) when utilized for machine leaning, artificial intelligence applications, and cryptocurrency-related applications. As discussed below, circuitry included on an integrated circuit device (e.g., DSP circuitry, multiplication circuitry, addition circuitry) perform modular multiplication in a manner that reduces the latency associated with performing these operations while also reducing the amount of the area on the integrated circuit device utilized to perform these operations.

As a more specific example, integrated circuit devices may perform mathematical operations associated with variable delay functions (VDFs), which can be utilized as proofs of work utilized in cryptographic applications, such as cryptocurrency or blockchain applications. In general, a proof of work is a proof in which one party (e.g., a party in operating or associated with one or more integrated circuit devices being utilized for cryptocurrency application) proves to others (one or more parties of cryptocurrency transactions) that a certain amount of computational effort has been expended. As such, VDFs have a certain minimum latency. That is, a VDF cannot be accelerated or parallelized beyond best known implementation. Accordingly, it would be beneficial to determine the best (e.g., optimal or quickest) implementation for a VDF. In many cases, modular multiplication and other mathematical operations (e.g., addition) are performed by circuitry included in integrated circuit devices as part of determining such an implementation. Accordingly, by performing modular multiplication (and operations performed as part of performing modular multiplication) in a lower latency manner, integrated circuit devices may be able to determine better (e.g., optimal or quicker) solutions to VDFs, thereby enhancing the performance of the integrated circuit device when utilized for, among other things, cryptocurrency and blockchain applications.

With the foregoing in mind, <FIG> is a block diagram of a system <NUM> that may implement arithmetic operations, such as modular multiplication, using multiplier circuitry. A designer may desire to implement functionality, such as the large precision arithmetic operations of this disclosure, on an integrated circuit device <NUM> (such as a field-programmable gate array (FPGA) or an application-specific integrated circuit (ASIC)). In some cases, the designer may specify a high-level program to be implemented, such as an OpenCL program, which may enable the designer to more efficiently and easily provide programming instructions to configure a set of programmable logic cells for the integrated circuit device <NUM> without specific knowledge of low-level hardware description languages (e.g., Verilog or VHDL). For example, because OpenCL is quite similar to other high-level programming languages, such as C++, designers of programmable logic familiar with such programming languages may have a reduced learning curve than designers that are required to learn unfamiliar low-level hardware description languages to implement new functionalities in the integrated circuit device <NUM>.

Designers may implement their high-level designs using design software <NUM>, such as a version of Intel® Quartus® by INTEL CORPORATION. The design software <NUM> may use a compiler <NUM> to convert the high-level program into a lower-level description. The compiler <NUM> may provide machine-readable instructions representative of the high-level program to a host <NUM> and the integrated circuit device <NUM>. The host <NUM> may receive a host program <NUM> which may be implemented by the kernel programs <NUM>. To implement the host program <NUM>, the host <NUM> may communicate instructions from the host program <NUM> to the integrated circuit device <NUM> via a communications link <NUM>, which may be, for example, direct memory access (DMA) communications or peripheral component interconnect express (PCIe) communications. In some embodiments, the kernel programs <NUM> and the host <NUM> may enable configuration of multiplier circuitry <NUM> on the integrated circuit device <NUM>. The multiplier circuitry <NUM> may include circuitry that is utilized to perform several different operations. For example, the multiplier circuitry <NUM> may include one or more multipliers and adders that are respectively utilized to perform multiplication and addition operations. Accordingly, the multiplier circuitry <NUM> may include circuitry to implement, for example, operations to perform multiplication for AI or non-AI data processing (e.g., modular multiplication, matrix-matrix multiplication, matrix-vector multiplication, vector-vector multiplication). Additionally, in some embodiments, the multiplier circuitry <NUM> may include one or more DSP blocks, and the integrated circuit device <NUM> may include many (e.g., hundreds or thousands) DSP blocks. The DSP blocks may be communicatively coupled to another such that data outputted from one DSP block may be provided to other DSP blocks. Furthermore, adder circuitry may be included in the multiplier circuitry <NUM>, for example, to add subproducts that are determined when performing multiplication operations. Indeed, as discussed in examples below, the multiplier circuitry <NUM> may perform multiplication involving relatively large values (e.g., multipliers and/or multiplicands) by decomposing one or more of the values into several smaller values, generating subproducts, and adding the subproducts. When performing modular multiplication, modulus values of one or more sums associated with the subproducts (e.g., sums of columns of subproducts) may also be determined.

While the techniques above discussion described to the application of a high-level program, in some embodiments, the designer may use the design software <NUM> to generate and/or to specify a low-level program, such as the low-level hardware description languages described above. Further, in some embodiments, the system <NUM> may be implemented without a separate host program <NUM>. Moreover, in some embodiments, the techniques described herein may be implemented in circuitry as a non-programmable circuit design. For example, the multiplier circuitry <NUM> may be formed at least partially in a non-programmable portion of a programmable logic device (e.g., an FPGA or ASIC). Furthermore, in other embodiments, the multiplier circuitry <NUM> may be partially implemented in portions of the integrated circuitry device <NUM> that are programmable by the end user (e.g., soft logic) and in parts of the integrated circuit device <NUM> that are not programmable by the end user (e.g., hard logic). For example, DSP blocks may be implemented in hard logic, while other circuitry included in the multiplier circuitry, including the circuitry utilized for routing data between portions of the multiplier circuitry, may be implemented in soft logic. Thus, embodiments described herein are intended to be illustrative and not limiting.

Turning now to a more detailed discussion of the integrated circuit device <NUM>, <FIG> illustrates an example of the integrated circuit device <NUM> as a programmable logic device, such as a field-programmable gate array (FPGA). Further, it should be understood that the integrated circuit device <NUM> may be any other suitable type of integrated circuit device (e.g., an application-specific integrated circuit and/or application-specific standard product). As shown, the integrated circuit device <NUM> may have input/output circuitry <NUM> for driving signals off device and for receiving signals from other devices via input/output pins <NUM>. Interconnection resources <NUM>, such as global and local vertical and horizontal conductive lines and buses, may be used to route signals on integrated circuit device <NUM>. Additionally, interconnection resources <NUM> may include fixed interconnects (conductive lines) and programmable interconnects (e.g., programmable connections between respective fixed interconnects). Programmable logic <NUM> may include combinational and sequential logic circuitry. For example, programmable logic <NUM> may include look-up tables, registers, and multiplexers. In various embodiments, the programmable logic <NUM> may be configured to perform a custom logic function. The programmable interconnects associated with interconnection resources may be considered to be a part of the programmable logic <NUM>.

Programmable logic devices, which the integrated circuit device <NUM> may represent, may contain programmable elements <NUM> within the programmable logic <NUM>. For example, as discussed above, a designer (e.g., a customer) may program (e.g., configure) the programmable logic <NUM> to perform one or more desired functions. By way of example, some programmable logic devices may be programmed by configuring their programmable elements <NUM> using mask programming arrangements, which is performed during semiconductor manufacturing. Other programmable logic devices are configured after semiconductor fabrication operations have been completed, such as by using electrical programming or laser programming to program their programmable elements <NUM>. In general, programmable elements <NUM> may be based on any suitable programmable technology, such as fuses, antifuses, electrically-programmable read-only-memory technology, random-access memory cells, mask-programmed elements, and so forth.

Many programmable logic devices are electrically programmed. With electrical programming arrangements, the programmable elements <NUM> may be formed from one or more memory cells. For example, during programming, configuration data is loaded into the memory cells using pins <NUM> and input/output circuitry <NUM>. In one embodiment, the memory cells may be implemented as random-access-memory (RAM) cells. The use of memory cells based on RAM technology is described herein is intended to be only one example. Further, because these RAM cells are loaded with configuration data during programming, they are sometimes referred to as configuration RAM cells (CRAM). These memory cells may each provide a corresponding static control output signal that controls the state of an associated logic component in programmable logic <NUM>. For instance, in some embodiments, the output signals may be applied to the gates of metal-oxide-semiconductor (MOS) transistors within the programmable logic <NUM>.

Keeping the foregoing in mind, the multiplier circuitry <NUM> discussed herein may be utilized for a variety of applications and to perform many different operations associated with the applications, such as multiplication and addition. For example, modular multiplication operations may be well suited for cryptocurrency applications. As discussed below, the multiplier circuitry <NUM> may reduce latency associated with modular multiplication operations due to the multiplier circuitry <NUM> itself as well as the manner in which the multiplier circuitry <NUM> performs modular multiplication. To help provide an overview for operations that the multiplier circuitry <NUM> may perform, <FIG> is provided. In particular, <FIG> is a flow diagram of a process <NUM> that the multiplier circuitry <NUM> may perform on data the multiplier circuitry <NUM> receives to determine a product of the inputted data. Additionally, it should be noted the operations described with respect to the process <NUM> are discussed in greater detail with respect to subsequent drawings. The process <NUM> generally includes receiving data (process block <NUM>), determining subproducts from the received data (process block <NUM>), and determining sums of the subproducts (process block <NUM>), which is done by determining a sum of each column of subproducts (sub-process block <NUM>) and adding the sums of the columns of subproducts (sub-process block <NUM>). The process <NUM> also includes reducing the columns of subproducts (process block <NUM>) and determining and outputting one or more sums (process block <NUM>).

At process block <NUM>, the multiplier circuitry <NUM> receives data. The data may include values that will be multiplied. The data may include fixed-point data types. In some cases, the values to be multiplied may be more precise that the precision of individual portions of the multiplier circuitry <NUM> utilized to perform multiplication operations. For example, the multiplier circuitry <NUM> may include <NUM>-bit wide DSP blocks that process values, but one or more of the values to be multiplied may include more than <NUM> bits (e.g., <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, or more than <NUM> bits). In such embodiments, the multiplier circuitry <NUM> or integrated circuit device <NUM> may subdivide one or more of the values to be multiplied into several smaller values. For example, continuing with the example in which the multiplier circuitry <NUM> includes DSP blocks that process <NUM>-bit values, two <NUM>-bit values to be multiplied may each be subdivided into five sub-terms.

At process block <NUM>, the multiplier circuitry <NUM> determines subproducts. In other words, the multiplier circuitry <NUM> may multiply the sub-terms associated with one value (e.g., a multiplicand) by sub-terms associated with another value (e.g., a multiplier) or, in the case that only one value is divided into sub-terms, the other value. In the example above in which two <NUM>-bit values are each subdivided into five sub-terms, twenty-five DSP blocks (e.g., a five-by-five arrangement of DSP blocks) may be utilized to multiply the sub-terms.

To help further expand on the multiplier circuitry <NUM> generating subproducts, <FIG> is provided. In particular, <FIG> is a diagram illustrating columns <NUM> (e.g., columns 90A-<NUM>) of subproducts <NUM> as well as a row <NUM> of sums <NUM> (e.g., sums 96A-<NUM>) of the columns <NUM>. More specifically, <FIG> includes seven columns <NUM> of subproducts <NUM>. While seven columns <NUM> of subproducts <NUM> are provided, it should be noted that the number of columns <NUM> and subproducts <NUM> may differ in other embodiments. Indeed, seven columns <NUM> may not correspond to any particular size multiplier or decomposition (e.g., of one or more values to be multiplied). Rather, the number of columns <NUM> and the depth of the columns <NUM> (i.e., the number of subproducts <NUM> per column <NUM>) may depend on the size of the values to the multiplied and how the values are subdivided (e.g., decomposed into smaller values that will be multiplied to generate the subproduct <NUM>). For instance, in the example of two <NUM>-bit values being decomposed into <NUM>-bit DSP blocks (e.g., a <NUM> x <NUM> arrangement of DSP blocks), there would be ten columns <NUM> with a column depth of up to nine terms (i.e., subproducts <NUM>). With that said, regardless of the number of columns <NUM>, the number of subproducts <NUM> in each column <NUM> generally increases from right to left until the middle (e.g., column 90D), and then decreases again from the middle to the left, as illustrated in <FIG>. Accordingly, while <FIG> includes seven columns <NUM> of subproducts <NUM> with a maximum depth of seven (e.g., the seven subproducts <NUM> of column 90D), the multiplication operation illustrated in <FIG> is merely one example. In other embodiments, fewer or more columns <NUM> compared to <FIG> may be included, and the maximum depth of the columns <NUM> may differ from <FIG>.

Keeping <FIG> in mind while returning to <FIG> and the discussion of the process <NUM>, at process block <NUM> the multiplier circuitry <NUM> determines sums of the subproducts. In other words, adder circuitry that may be included in the multiplier circuitry <NUM> adds the subproducts <NUM> together (e.g., as part of determining the product of the two initial values to be multiplied). To determine the sums of the subproducts, the multiplier circuitry <NUM>, at sub-block <NUM> determines a sum for each column <NUM> of the subproducts <NUM> (e.g., by adding together each subproduct <NUM> in a particular column <NUM>) and, at sub-block <NUM>, adds the sums of the columns <NUM>. In other words, the multiplier circuitry <NUM> adds each of the subproducts in a column <NUM> together for each of the columns <NUM> and adds the sums for the columns <NUM> together. For instance, in <FIG>, each of the sums <NUM> is a sum determined by adding the subproducts <NUM> of a particular column <NUM> (i.e., the column <NUM> in which the given sum <NUM> is located). More specifically, each sum <NUM> may be independently determined. That is, the sums <NUM> may be determined without accounting for values (e.g., subproducts, sums, wordgrowth) associated with other columns.

Generally, depending on the number of columns <NUM> of subproducts <NUM> and the depth of the columns <NUM>, wordgrowth may occur. In other words, as illustrated by bits <NUM> (e.g., bits 98A-98E) or any bits indicated by bars within the sums <NUM> (e.g., sums 96B-96F), a portion of the sums <NUM> may include one or more bits than a width processable by a DSP block included in the multiplier circuitry <NUM>. For instance, in <FIG>, the sums 96B, 96F include two bits of wordgrowth, while the sums 96C, 96D, 96E include three bits of wordgrowth. As another example, in the case of the <NUM>-bit wide DSP block discussed above, a sum <NUM> of a given column <NUM> of subproducts <NUM> may include one, two, three, or four bits more than <NUM> bits (i.e., one, two, three, or four bits of wordgrowth). Similar to the depth of the columns, the amount of wordgrowth generally increases from the right to the middle (e.g., column 90D) and decreases from the middle to the left.

The multiplier circuitry <NUM> performs further addition operations to add together the sums <NUM>. Specifically, at process block <NUM>, the multiplier circuitry <NUM> may reduce one or more of the sums <NUM> of the columns <NUM> by determining the modulus for each of the sums <NUM> that has a rank that is greater than the input argument size. In other words, each of the sums <NUM> that includes more bits than the subdivided values multiplied by the multiplier circuitry (which may be the same number of bits as the width of the DSP blocks utilized to determine the subproducts <NUM>) can be replaced by its modulus. Modular reduction may be performed based on the modulus identity provided below: <MAT> where A and B are values to be added (e.g., two of the sums <NUM>), "mod" is a modulo operation, and N is a value. In particular, the value of N may be an integer value determined on a case by case basis by the multiplier circuitry <NUM> or integrated circuit device <NUM>, for example, based on the values of the sums <NUM>. Accordingly, a modulus value for each of the sums <NUM> may be determined.

Returning to <FIG> and the discussion of the process <NUM>, at process block <NUM>, the multiplier circuitry <NUM> determines and outputs one or more sums. For example, adder circuitry in the multiplier circuitry <NUM> may add values generated from performing modular reductions discussed above.

To help expand on this discussion, <FIG> is provided. In particular, <FIG> illustrates one example of how the integrated circuit device <NUM> and multiplier circuitry <NUM> may perform the operations discussed above with respect to process blocks <NUM> and <NUM> of the process <NUM>. For example, multiplier blocks <NUM> (e.g., multiplier blocks 100A-100I) may be included in the multiplier circuitry <NUM> and determine the subproducts <NUM> as well as the sums <NUM>. Look-up tables (LUTs) <NUM> (e.g., LUTs 102A-102E) included in the multiplier circuitry <NUM> (or elsewhere in the integrated circuit device <NUM>) may be communicatively coupled to a corresponding multiplier block <NUM>, receive the output (e.g., a sum <NUM>) from the multiplier block <NUM>, perform a modulo operation on the value received from the multiplier block <NUM>, and output a modulus value. Accordingly, the LUTs <NUM> may be utilized to perform modular reduction. Similar to the discussion of the columns <NUM> and depth of the columns <NUM> above, the amount of multiplier blocks <NUM> and LUTs <NUM> utilized may vary depending on the number of bits being multiplied. Thus, in other embodiments, fewer or more multiplier blocks <NUM> and LUTs <NUM> than those illustrated in <FIG> may be utilized.

The outputs of the LUTs <NUM> are provided to adder circuitry <NUM>, which may be included in the multiplier circuitry <NUM> or otherwise included in the integrated circuit device <NUM>. In particular, a first portion (e.g., row) <NUM> of the adder circuitry <NUM> may receive values (e.g., portions of values generated by modulo operations) from two of the LUTs <NUM> (e.g., LUT 102D and LUT 102E), add the values, generate outputs (e.g., sums of the added values), and provide the outputs to a subsequent portion (e.g., a second portion <NUM>) of the adder circuitry <NUM>. The second portion <NUM>, as well as a third portion <NUM> and a fourth portion <NUM> of the adder circuitry <NUM> may receive a set of values from a preceding portion of the adder circuitry <NUM> as well as a set of values from one of the LUTs <NUM> and add the two sets of values together. While the adder circuitry <NUM> is illustrated as having four rows (e.g., portions <NUM>, <NUM>, <NUM>, <NUM>) that each include four adders, the adder circuitry <NUM> may include a different number of rows as well as a different number of adders per row in other embodiments, for example, based on the number of LUTs <NUM>, the size (e.g., number of bits) in the values to be multiplied, a width of DSP blocks, or a combination thereof.

Before continuing to discuss how the integrated circuit device <NUM> and multiplier circuitry <NUM> may perform portions of the process <NUM> more quickly (i.e., with less latency), it should be noted that the process <NUM> may include additional operations. For example, in other embodiments, the process <NUM> may include determining a product of two initial values and outputting such a product. More specifically, the product may be determined based on the sum(s) determined at process block <NUM> as well as a sum of the sums <NUM> of the columns <NUM> of subproducts <NUM> for which no reduction is done (e.g., at process block <NUM>). Accordingly, the multiplier circuitry <NUM> and integrated circuit device <NUM> may determine the product of two values by performing multiplication and addition (and modulo) operations using sub-values of the two values. Additionally, it should be noted that as an alternative to the discussion provided above, each of the illustrated multiplier blocks <NUM> may be thought of as a sum <NUM>, and the LUTs <NUM> may be thought of as modulus values output by look-up tables included in the integrated circuit device <NUM>.

Keeping the foregoing in mind, because adding circuitry may be used to perform addition on the partial products as well as values produced from performing modular reductions, circuitry utilized to perform the multiplication of the initial values (e.g., the multiplier circuitry <NUM>, LUTs <NUM>, and adder circuitry <NUM>) may utilize a larger than desired amount of area on the integrated circuit device <NUM>. Moreover, latency may be introduced when performing multiplication operations due to the splitting of initial values to be multiplied. For example, as discussed above, when initial values are converted into several smaller values, partial products can be determined, and the partial products will be summed to determine a product of the initial values. In other words, because the number of operations is increased, the amount of time used to calculate the product of the values may be higher than if the multiplication operation were performed using circuitry configured to perform multiplication on data having the same width (e.g., number of bits) as the initial values. Additionally, relatively higher amounts of latency may occur based on the amount of data (e.g., depth of the columns <NUM>), the order in which the columns <NUM> are summed, the sums <NUM> of the columns <NUM> of subproducts being determined independently of one another, or any combination thereof. Latency may also occur due to wordgrowth (e.g., due to performing reduction operations to reduce the wordgrowth).

For example, in <FIG>, because a fourth column 90D of subproducts includes more partial products than any of the other columns <NUM>, it may take more time for the multiplier circuitry <NUM> to determine the subproducts <NUM> of the column 90D, which means it may also take more time to determine the sum 96D of the fourth column 90D. Conversely, other columns (e.g., columns 90A, 90B, 90F, <NUM>) may include relatively fewer subproducts <NUM>, meaning the sums associated with the columns 90A, 90B, 90F, <NUM> (e.g., sums 96A, 96B, 96F, <NUM>, respectively) may be determined more quickly than sums <NUM> associated with columns <NUM> having a larger number of subproducts <NUM>.

Bearing this in mind, and turning to <FIG>, the multiplier blocks <NUM> may exhibit patterns generally similar to those of the columns <NUM> and sums <NUM> of <FIG>. For example, multiplier block 100I may be associated with a first number of subproducts <NUM>, multiplier block <NUM> may be associated with a higher number of subproducts <NUM> (e.g., a second number of subproducts <NUM>), multiplier block <NUM> may be associated with a higher number of subproducts <NUM> (e.g., a third number of subproducts <NUM>), multiplier block 100F may be associated with a higher number of subproducts <NUM> (e.g., a fourth number of subproducts <NUM>), multiplier block 100E may be associated with a higher number of subproducts <NUM> (e.g., a fifth number of subproducts <NUM>), multiplier block 100D may be associated with a lower number of subproducts <NUM> (e.g., the fourth number of subproducts <NUM>), multiplier block 100C may be associated with a lower number of subproducts <NUM> (e.g., the third number of subproducts <NUM>), multiplier block 100B may be associated with a lower number of subproducts <NUM> (e.g., the second number of subproducts <NUM>), and multiplier block 100A may be associated with a lower number of subproducts <NUM> (e.g., the first number of subproducts <NUM>). And, as noted above, columns <NUM> with fewer subproducts may be summed prior to columns <NUM> that have more subproducts <NUM>. Accordingly, the LUTs <NUM> associated with columns <NUM> that have more subproducts <NUM> may take more time to produce an output that can be provided to the adder circuitry <NUM> to be summed. Thus, in <FIG>, outputs from LUT 102E and LUT 102D would take relatively more time to determine and generate than outputs from LUTs 102C, 102B, 102A.

To reduce latency, addition involving reduced values (e.g., values produced in association with process block <NUM> of the process <NUM>) is performed in an order based on an amount of delay associated with each column <NUM> that, for example, may correspond to the depth of the columns <NUM>. That is, the order that addition operations are performed in may take into account the number of partial products <NUM> a column <NUM> has relative to one or more of the other columns <NUM>. <FIG> is a block diagram of the same circuitry as <FIG> that has been arranged to perform addition in an order based on column depth. More specifically, in <FIG> (relative to <FIG>), addition is performed by a first portion <NUM> of adder circuitry <NUM> using outputs from LUT 102A and LUT 102B, which would be in columns having the relatively lowest amounts of partial products <NUM> (e.g., compared to LUTs 102C, 102D, 102E). A second portion <NUM> of the adder circuitry <NUM> receives outputs from LUT 102C and LUT 102D and adds the inputs. The outputs from the first portion <NUM> and second portion <NUM> of the adder circuitry <NUM> are added by a third portion <NUM> of the adder circuitry <NUM>. Additionally, a fourth portion <NUM> of the adder circuitry <NUM> adds values received from the third portion <NUM> of the adder circuitry <NUM> and LUT 102E, which is the LUT <NUM> associated with the longest delay due to being associated with the column having the most partial products. In this manner, each portion of the moduli generated by the LUTs <NUM> is input into respective portions of the adder circuitry <NUM>, and each column is added independently (i.e., without any carries between columns). Accordingly, columns <NUM> are grouped by expected delay (e.g., based on the number of partial products <NUM> in each column <NUM>), and addition operations (e.g., addition involving modulus values) associated with the columns having larger delays (e.g., latency) occur further down in an adder tree (e.g., after addition associated with columns having lower expected delays). Indeed, a particular sum (e.g., values output by the first portion <NUM> of the adder circuitry <NUM>) may be determined before other LUTs (e.g., LUTs 102C, 102D) output modulus values.

Continuing with the drawings, <FIG> is a block diagram generally similar to <FIG> that also includes adder circuitry <NUM> (including adders <NUM>) that are used to reduce the sums <NUM> of the row <NUM> of sums <NUM>. In particular, the adders <NUM> may be adders that receive one of the sums <NUM> and a carry-out value from a preceding column (e.g., a column <NUM> directly to the right of the column <NUM> that a given adder <NUM> is in). In other words, each of the adders <NUM> may add carry-out bits (e.g., bits of wordgrowth such as bits <NUM>) from a sum <NUM> to bits of a next highest sum (in which case the case carry-out bits <NUM> may be of the same magnitude as the n least significant bits of the next highest sum, where n is the number of bit values in a given carry-out value). Accordingly, the additional carries (e.g., bits <NUM>) in each column are reduced by adding each column independently once more. As there are no carries across columns, carry-outs from the column reductions are added to the next higher rank column. Furthermore, while sums <NUM> (e.g., sums 124A-<NUM>) generated by some of the adders <NUM> may include an extra bit (e.g., bit <NUM>), the extra bits <NUM> are a single bits instead of the several carry bits that occur in row <NUM> of the sums <NUM>. These extra bits <NUM> may be removed by performing another round of addition. For example, any single bits <NUM> could be treated as carry-out values that are added to a sum from a column that is one order of magnitude larger (e.g., the column <NUM> directly the to the left).

However, while adding circuitry can be utilized to reduce wordgrowth and the number of carry-out bits, the adding circuitry may be relatively expensive in terms of the amount of space on the integrated circuit device <NUM> that the adding circuitry occupies as well as latency associated with several levels of addition to be performed. As an example, in the case where <NUM>-bit DSP blocks will be utilized to perform multiplication involving a <NUM>-bit multiplier, the <NUM>-bit multiplier may be expressed according to the following <NUM>-term polynomial expression: <MAT> where each a coefficient is <NUM>-bit value. In this case, there may be six columns <NUM> of partial products <NUM> to be reduced (e.g., eliminate or reduce the amount of wordgrowth), and the maximum depth of the columns <NUM> is nine, meaning there may be up to nine subproducts <NUM> in a given column <NUM>. In this example, up to four levels of <NUM>-input adders may be needed to calculate the sum <NUM> of each column <NUM>. Furthermore, the six columns will be reduced (e.g., by utilizing a modulus value for each column that is generated via a LUT <NUM>), and up to three levels of <NUM>-input adders will be needed to perform addition on the reduced values. Accordingly, seven total levels of adder circuitry may be needed in total. Ignoring the cost of DSP Blocks or modulo LUTs, adding the final carry-reducing adder circuitry may increase the amount of area utilized by adder circuitry by approximately fifteen percent.

Continuing with the drawings, <FIG> illustrates adding circuitry 140A that may be utilized to add subproducts <NUM> to determine the sums <NUM> of the columns <NUM>. The adding circuitry 140A may also be utilized to perform addition involving modulus values. In particular, the adding circuitry <NUM> includes a first adder tree 142A, a second adder tree 144A, and a third adder tree 146A that are independent of one another. Each of the adder trees 142A, 144A, 144C, includes adders <NUM>, which are two-input adders. For example, the first adder tree 142A includes two levels of adders <NUM> that may determine the sum of three inputs. The second adder tree 144A includes three levels of adders <NUM> that may determine a sum of five inputs. The third adder tree 146A includes four levels of adders <NUM> that may determine a sum of seven inputs. It should be noted that the adding circuitry 140A is not limited to including adder trees 142A, 144A, 146A. In other words, in other embodiments, the adding circuitry 140A may include other adder trees. For example, the adding circuitry 140A may include a nine-input adder tree that includes four levels of adders <NUM>. Accordingly, the adding circuitry 140A (and the adding circuitry 140B and adding circuitry 140C discussed below) may include any suitable number of adder trees, each of which may include any suitable number of adders (e.g., adders <NUM> or, as introduced below, ternary adders) arranged in any suitable number of levels.

An adder tree (e.g., one of the adder trees 142A, 144A, 146A) may be utilized for summing the subproducts in a column <NUM>. Because each of the columns <NUM> may include a different number of subproducts, adder trees that are capable of adding different amounts of inputs may be utilized. For example, the first adder tree 142A may be utilized to add subproducts for a column <NUM> having three (or fewer than threes) subproducts. Because various adder trees 142A, 144A, 146A may have different amounts (e.g., vertical levels) of inputs (and adders <NUM>) certain adder trees may more quickly generate a column sum compared to other adder trees that process more inputs. Furthermore, as noted above, when the add trees are independent of one another, meaning each adder tree sums the subproducts <NUM> of a column <NUM> without passing any values to the adder tree for a different column <NUM>, more adding circuitry would be utilized to add the columns (e.g., to reduce wordgrowth).

To help account for the generally unbalanced nature of the adder trees (e.g., adder trees 142A, 144A, 146A) and reduce the latency associated with utilizing independent adder trees, <FIG> will now be discussed. In particular, <FIG> illustrates adding circuitry 140B that includes adder trees 142A, 144B, 146B, with adder trees 144B, 146B being different embodiments of the adding circuitry 144A, 146A, respectively. More particular, carry-out values (represented by diagonal lines <NUM>, <NUM>) from lower significance adders (e.g., adders farther to the right in <FIG>) are added to an input (e.g., on the subproducts of the column directly to the left of the column from which the carry-out value originates). While adders <NUM> have been added to the adding circuitry 140B compared to the adding circuitry 140A of <FIG>, it may be beneficial to do so because the delay of the multiplier circuitry <NUM> (in performing multiplication operations) is limited by the column with the longest delay.

Bearing this in mind, latency associated with the adding circuitry 140A of <FIG> may be reduced to a further extent by utilizing ternary adders, which are adders that can add three values. For example, in <FIG>, adding circuitry 140C is generally similar to the adding circuitry 140A of <FIG>, but adders <NUM> (e.g., adders 180A, 180B) are included in adder trees 144C, 146C are ternary adders. The adders <NUM> each receive three inputs and output a sum of the inputs (and, when applicable, a carry-out value). The inputs the adders <NUM> receive include two values (e.g., two subproducts <NUM>) associated with the same column <NUM> and a carry-in value that is a carry-out value (represented by diagonal lines <NUM>, <NUM>) generated by another adder (e.g., adder <NUM> in the case of adder 180A or adder 180A in the case of adder 180B). The carry-in values input into the adders <NUM> are generally lower precision values (e.g., <NUM>, <NUM>, <NUM>, or <NUM>-bit values) than the other two inputs. For instance, two of the inputs may be <NUM>-bit values, and the third input may be a carry-in value that includes one, two, three, or four bits. However, because the ternary addition involves one value that is generally much less precise (e.g., includes fewer bits) than the two other values being added, a "full-width" ternary adder that can sum three values having a larger precision (e.g., <NUM> bits) may be avoided. Indeed, as discussed below, ternary adders (e.g., adders <NUM>) may be implemented using a combination of circuitry that includes a relatively low precision ternary adder (or equivalent logic), <NUM>:<NUM> compressor circuitry, and adding circuitry. Accordingly, the circuitry discussed below may be implemented on programmable logic devices such as FPGAs regardless of whether the programmable logic device is configured to support ternary adders. For instance, to support ternary adders, programmable logic devices may utilize more wires (e.g., to route data) compared to when supporting binary (i.e., two-input) adders. And, in some cases, an FPGA or other programmable logic device may not include enough wires (or have a high enough density of wires) to support ternary adders that are configured to add three "full-width" values. As such, the circuitry discussed below (e.g., with respect to <FIG> and <FIG>) may be implemented on integrated circuit devices that do not support ternary adders.

Bearing this in mind, <FIG> illustrates adder circuitry <NUM>, which may be included in the adder <NUM> of <FIG>. In other words, the adder circuitry <NUM> may be utilized as a ternary adder within adder trees, such as adder trees utilized to add subproducts <NUM> or sums <NUM> of columns. The adder circuitry <NUM> includes a ternary adder <NUM>, compressor circuitry (e.g., <NUM>:<NUM> compressor circuitry) <NUM>, and adder circuitry <NUM>.

The ternary adder <NUM> may receive three n-bit inputs, where n is an integer value equal to the number of bits included in the carry-out from an adder (e.g., adder <NUM> of <FIG>). One of the inputs is such a carry-out value, while the other two inputs are the n least significant bits of two values (e.g., value A and value B) two to be summed. For example, the other two inputs may be subproducts <NUM> of a column <NUM>, and such column may include more subproducts than a column from which the carry-out value originates. In any case, such column will include subproducts that are more significant than the column from which the carry-out value is received. The ternary adder <NUM> may output a value that includes n bits, one bit of wordgrowth (indicated by "<NUM>"), and a carry-out value (indicated by "cout"). Accordingly, the ternary adder <NUM> may add a carry-out value having n bits to portions of other values (e.g., subproducts or values determined by adding together subproducts, or a combination thereof) that also include n bits.

The ternary adder <NUM> may be implemented in several different ways, typically depending on the value of n. For example, the ternary adder <NUM> may be implemented as a lookup table when n is a relatively smaller number of bits, such as one or two bits. The lookup table may be implemented in soft logic of the integrated circuit device <NUM>. As a more specific example, a LUT6 may be utilized when n is two. In other embodiments, including embodiments directed to inputs having other values of n bits, other circuitry of the integrated circuit device <NUM> may be utilized, such as logic implemented in soft logic of the integrated circuit device <NUM> when the integrated circuit device <NUM> is an FPGA. An example of such logic is illustrated in <FIG> and is discussed in more detail below.

Continuing with the discussion of the adder circuitry <NUM>, the compressor circuitry <NUM> includes several half-adders (e.g., half-adder <NUM>) that are utilized to logically shift one of the two inputs that are not carry-out values. More specifically, the compressor circuitry <NUM> may be <NUM>:<NUM> compressor circuitry that receives the bits of input A and input B (e.g., bits of subproducts of a column to be added together or bits of a sum generated by adding together two subproducts) other than those provided to the ternary adder <NUM> and produces two new outputs NA and NB, where NA has the alignment of A, and NB has the alignment of B left shifted by one position. For example, the compressor circuitry <NUM> may cause a "<NUM>" to be inserted into the least significant bit position of input B to generate output NB. Furthermore, as illustrated, each half-adder includes an XOR gate <NUM> and an AND gate <NUM>. In the case of the half-adder <NUM>, the AND gate <NUM> receives the bit of wordgrowth from the ternary adder (as indicated by "<NUM>").

Because the bits of the second output (e.g., output NB) have been left-shifted by one position relative to the second input (e.g., input B), the least significant bit of output NB may be thought of as being "free. " In other words, the output of compressor circuitry <NUM> that is provided to the adder circuitry <NUM> may be input NA (having the same alignment as the input A) and input NB (having the alignment of input B left-shifted by one position). Furthermore, the carry-out bit (as indicated by "cout") from the ternary adder <NUM> may be provided to the adder circuitry <NUM> and treated as though it were the least significant bit of an input to be added.

The adder circuitry <NUM> includes binary (i.e., two-input) adders <NUM> (e.g., adders 214A-214D) which add the bits received from the compressor circuitry <NUM>. In particular, each adder <NUM> may add two inputs (e.g., <NUM>-bit values) as well as a carry-in value (e.g., a carry-out value received as a carry-in value from a preceding adder or, in the case of adder 214D, a carry-out values from the ternary adder <NUM>). Accordingly, the adder circuitry <NUM> may be utilized to add the any bits of values that are in bit positions that are higher than n. For example, if n were equal to two, the adder circuitry <NUM> may be utilized to add the third least significant bit of inputs as well as any more significant bits of the inputs. As such, the adder circuitry <NUM> may be utilized to perform addition (e.g., binary addition) on bits of inputs that are not added by the ternary adder <NUM>.

Before continuing to discuss <FIG>, it should be noted that the adding circuitry <NUM> of <FIG> may only be a portion of the circuitry included in the ternary adder <NUM> of <FIG>. For example, in other embodiments, the compression circuitry <NUM> may include more half-adders <NUM> (e.g., tens, hundreds, or thousands of half-adders <NUM>) than those depicted in <FIG>, and the adding circuitry <NUM> may include more adders <NUM> than those depicted in <FIG>. For instance, there may be as many adders <NUM> as there are half-adders <NUM> in the compression circuitry <NUM>. As such, the adding circuitry <NUM> may be tailored to perform addition on values having a certain number of bits, which may further reduce latency associated with performing modular multiplication operations as well as reduce the amount of area of the integrated circuit device <NUM> occupied by adder circuitry (or other circuitry utilized when performing multiplication operations).

Continuing with the drawings, <FIG> is a block diagram of ternary adder circuitry <NUM>, which may be utilized as the ternary adder <NUM> in <FIG>. More specifically, the ternary adder circuitry <NUM> may be utilized to add three inputs having five bits each (i.e., three inputs for which n is equal to five). As illustrated, the ternary adder circuitry <NUM> includes various types of logic blocks, such as XOR logic blocks <NUM>, majority function blocks <NUM> (e.g., circuitry that outputs a "<NUM>" when more than half of the inputs are true (e.g., have values of "<NUM>")), and AND function blocks <NUM>. Additionally, the ternary adder circuitry <NUM> includes adders <NUM> that receive outputs of some of the logic blocks as inputs and add the inputs. As illustrated, the adders <NUM> may each receive two inputs as well as a carry-in value and generate a sum and a carry-out value.

Keeping the foregoing discussion in mind, an example of an implementation of the multiplier circuitry <NUM> will now be discussed. In this example, the integrated circuit device <NUM> may be a programmable logic device. More specifically, the programmable logic device may be an FPGA. The multiplier circuitry <NUM> may be implemented using a combination of hard and soft logic of the FPGA. In other words, multiplication operations (e.g., modular multiplication operations) may be performed using a combination of circuitry on the FPGA that is generally not alterable or programmable to an end user (e.g., hard logic) as well as circuitry on the FPGA that is alterable or programmable by the end user (e.g., soft logic). In this example, the multiplier circuitry <NUM> may include one or more DSP blocks that are implemented in hard logic that are utilized to multiply inputs to generate subproducts. For instance, as discussed above, the DSP blocks may multiply generally lower precision values that are derived from two relatively higher precision values to be multiplied, and the subproducts are the values generated by the DSP blocks when performing multiplication operations utilizing the generally lower precision values. As such, the DSP blocks may generate the columns of subproducts discussed above.

The multiplier circuitry may also include adder circuitry, such as adder trees discussed herein, that are utilized to sum the columns of subproducts. The adder trees may be implemented in hard logic or soft logic of the FPGA, but for the purposes of the example currently being discussed, the adder trees are implemented in soft logic. Moreover, routing circuitry from the DSP blocks to the adder trees and the circuitry (e.g., logic blocks) that make up the adder trees themselves may be implemented utilizing soft logic of the FPGA. More specifically, there may be one adder tree for each column of subproducts that includes more than one subproduct.

As discussed above, the adder trees may include various types of adders such as binary and ternary adders. Furthermore, the adder trees for the columns may be communicatively coupled to one another, as described above, such that carry-out values associated with columns may be provided to another column (e.g., a binary or ternary adder of a column of higher significance that the column from which the carry-out value originates). For instance, the adder trees may include a combination of binary and ternary adders, including the implementation of a ternary adder illustrated in <FIG> that includes ternary adder circuitry, compressor circuitry (e.g., <NUM>:<NUM> compressor circuitry), and binary adder circuitry. Furthermore, as shown in <FIG> and also discussed above, the ternary adders included in the adder trees may receive two values that are either subproducts, derived from subproducts (e.g., sums of subproducts determined while determining a sum for an entire column of subproducts, or a combination thereof. The ternary adders may also receive a carry-in value that is a carry-out value generated by adder circuitry within another adder tree. Furthermore, the adder trees may ultimately generate sums of columns that include a single bit of wordgrowth (e.g., as depicted in <FIG>).

The multiplier circuitry <NUM> may also include look-up tables that each receive a sum of a particular column. For example, look-up tables may receive values that include more bits than the values multiplied to generate the subproducts. In other words, the output (e.g., sum) of each column that has a rank higher than the input argument size may be provided to a look-up table that performs a modulo operation and outputs the modulus of the input.

The multiplier circuitry <NUM> may include additional adder circuitry, which may include adder trees, that are utilized to add the modulus values generated by the look-up tables. Furthermore, the additional adder circuitry may add the other values (e.g., sums from columns for which a modulus was not determined) with the modulus values. As discussed above (e.g., with respect to <FIG>), the additional adder circuitry may sum modulus values in an order that is related to the number of subproducts of a column from which a given modulus value is generated. For example, columns with relatively fewer subproducts may be summed more quickly, meaning a modulus value for such columns may be generated more quickly than modulus values for columns having relatively higher numbers of subproducts.

Bearing the foregoing in mind, the integrated circuit <NUM> may include the multiplier circuitry <NUM>, which may have interfaces to connect to other integrated circuit devices. In addition, the integrated circuit device <NUM> may be a data processing system or a component included in a data processing system. For example, the integrated circuit device <NUM> may be a component of a data processing system <NUM>, shown in <FIG>. The data processing system <NUM> may include a host processor <NUM> (e.g., a central-processing unit (CPU)), memory and/or storage circuitry <NUM>, and a network interface <NUM>. The data processing system <NUM> may include more or fewer components (e.g., electronic display, user interface structures, application specific integrated circuits (ASICs)). The host processor <NUM> may include any suitable processor, such as an INTEL® Xeon® processor or a reduced-instruction processor (e.g., a reduced instruction set computer (RISC), an Advanced RISC Machine (ARM) processor) that may manage a data processing request for the data processing system <NUM> (e.g., to perform encryption, decryption, machine learning, video processing, voice recognition, image recognition, data compression, database search ranking, bioinformatics, network security pattern identification, spatial navigation, cryptocurrency operations, or the like). The memory and/or storage circuitry <NUM> may include random access memory (RAM), read-only memory (ROM), one or more hard drives, flash memory, or the like. The memory and/or storage circuitry <NUM> may hold data to be processed by the data processing system <NUM>. In some cases, the memory and/or storage circuitry <NUM> may also store configuration programs (bitstreams) for programming the integrated circuit device <NUM>. The network interface <NUM> may allow the data processing system <NUM> to communicate with other electronic devices. The data processing system <NUM> may include several different packages or may be contained within a single package on a single package substrate. For example, components of the data processing system <NUM> may be located on several different packages at one location (e.g., a data center) or multiple locations. For instance, components of the data processing system <NUM> may be located in separate geographic locations or areas, such as cities, states, or countries.

In one example, the data processing system <NUM> may be part of a data center that processes a variety of different requests. For instance, the data processing system <NUM> may receive a data processing request via the network interface <NUM> to perform encryption, decryption, machine learning, video processing, voice recognition, image recognition, data compression, database search ranking, bioinformatics, network security pattern identification, spatial navigation, digital signal processing, or some other specialized task.

Furthermore, in some embodiments, the multiplier circuitry <NUM> and data processing system <NUM> may be virtualized. That is, one or more virtual machines may be utilized to implement a software-based representation of the multiplier circuitry <NUM> and data processing system <NUM> that emulates the functionalities of the multiplier circuitry <NUM> and data processing system <NUM> described herein. For example, a system (e.g., that includes one or more computing devices) may include a hypervisor that manages resources associated with one or more virtual machines and may allocate one or more virtual machines that emulate the multiplier circuitry <NUM> or data processing system <NUM> to perform multiplication operations and other operations described herein.

Accordingly, the techniques described herein enable multiplication (e.g., modular multiplication) to be performed more quickly (i.e., with a reduced latency), and the circuitry utilized to perform multiplication may occupy less physical space on an integrated circuit device compared to other circuitry that may also be utilized to perform multiplication. For example, Ternary addition, where available, can greatly reduce the latency of the overall structure of the circuitry utilized to perform (modular) multiplication operations. This may be half the latency of using two-input adders. For example, a reduction of nine elements would use four two-input levels of adders but only two levels when ternary adders are utilized in the manner described herein. Thus, even though utilized ternary adders can be routing intensive, the ternary structure described herein that is split into a combinatorial portion and a carry based portion may significantly reduce latency. Indeed, although the number of levels in the nine element reduction are the same as in the two-input case, the alternate levels being combinatorial may significantly ease placement, thus resulting in a lower latency. As such, technical effects of the present disclosure include modular multiplication being performed with reduced latency while using circuitry that utilized reduced amount of space on an integrated circuit device.

While the embodiments set forth in the present disclosure may be susceptible to various modifications and alternative forms, specific embodiments have been shown by way of example in the drawings and have been described in detail herein. However, it should be understood that the disclosure is not intended to be limited to the particular forms disclosed. The disclosure is to cover all modifications, equivalents, and alternatives falling within the scope of the disclosure as defined by the following appended claims.

Claim 1:
An integrated circuit device comprising:
multiplier circuitry configured to determine a plurality of columns of subproducts by multiplying a plurality of values, wherein each column of the plurality of columns comprises one or more subproducts of a plurality of subproducts;
adder circuitry configured to determine a plurality of sums, wherein each sum of the plurality of sums is a sum of one column of the plurality of columns, wherein a first portion of the adder circuitry associated with a first column of the plurality of columns is configured to receive a first value associated with the first column, a second value associated with the first column, and a third value associated with a second column of the plurality of columns that differs from the first column, wherein the third value is a carry-out value generated by a second portion of the adder circuitry associated with the second column;
one or more lookup-tables configured to generate a plurality of modulus values from a portion of the plurality of sums; and
second adder circuitry configured to determine a sum of the plurality of modulus values; characterized in that the plurality of columns is grouped based on the number of subproducts in each column, wherein the second adder circuitry is further configured to determine the plurality of sums of modulus values based on the number of subproducts in each column, wherein the sums of modulus values for columns with smaller numbers of subproducts are determined before sums of modulus values for columns with larger numbers of subproducts, and wherein each sum of the plurality of sums is replaced with the modulus of this sum.