Mixed-mode multiplier using hard and soft logic circuitry

Multiplier circuitry that efficiently utilizes the hard and soft logic regions of a programmable logic device (PLD) is provided. The multiplier circuitry includes a partial product generation block, a compression block (e.g., a carry-save adder), and an carry-propagate adder stage. The partial product generation and compression block are implemented in hard logic while the carry-propagate adder is implemented in soft logic. Local or global routing may be used to connect the hard and soft multiplier components. The multiplier may further include a selectable input register in hard logic and/or a selectable output register in soft logic. This mixed-mode design allows for a substantial savings in the amount of hard logic required to implement the multiplier without a significant decrease in multiplier performance.

BACKGROUND OF THE INVENTION

This invention relates generally to multiplier circuitry. In particular, this invention relates to a multiplier design that uses hard and soft logic in a programmable logic device in order to reduce the dedicated die area required for the multiplier. This design reduces the amount of dedicated die without using the soft logic inefficiently or producing a significant decrease in the performance of the multiplier.

Programmable logic devices (PLDs) include generalized logic circuitry such as look-up tables (LUTs) and sum-of-product based logic that are designed to allow a user to customize the circuitry to the user's particular needs. This configurable logic is typically divided into individual logic circuits that are referred to as logic elements (LEs). As an example, each LE in a PLD may be configured as a 4-input LUT. The LEs may be grouped together to form larger logic blocks referred to as logic array blocks (LABs) that may be configured to share the same resources (e.g., registers and memory). In addition to this configurable logic, PLDs also include programmable interconnect or routing circuitry that is used to connect the inputs and outputs of the LEs and LABs. The combination of this programmable logic and routing circuitry is referred to as soft logic.

Besides soft logic, PLDs may also include hard logic circuitry that implements specific predefined logic functions and thus cannot be configured by the user. One common type of functional circuitry that is implemented in hard logic in PLDs is a multiplier. Multipliers are intensively used in applications such as digital signal processing (DSP), for example. Currently, multipliers that are implemented using hard logic are implemented virtually exclusively in hard logic. Although soft logic may be used to combine several hard multipliers together to form a larger multiplier, none of the existing multiplier implementations divide the multiplier components (e.g., adder stages) that are responsible for performing the multiplication operation into portions that are implemented in hard logic and portions that are implemented in soft logic. The problem with providing multipliers and other types of hard logic circuitry on devices such as PLDs is that it increases the cost of the devices because of the of dedicated die area that is required to implement such circuitry. On the other hand, multipliers that are designed purely in soft logic often make inefficient use of the logic and routing resources and perform slower than equivalent hard logic multipliers. For example, the use of soft logic to perform partial product generation usually requires an excessive amount of LUTs and interconnect resources. For other common multiplier functions such as carry-save addition, the LUTs used for this function are not fully used and thus waste logic and routing. If an adder tree is used as an alternative to carry save addition, then fitting the design to the soft logic architecture can become an issue.

Thus, it would be desirable to create a multiplier design, in a device such as a PLD that uses includes hard and soft logic, that reduces the amount of dedicated die area required for the multiplier. It would be further desirable to design a multiplier using hard and soft logic that reduces the amount of required hard logic without inefficiently using the soft logic. It would be still further desirable to design a multiplier using hard and soft logic that reduces the amount of required hard logic without a significant decrease in the performance of the multiplier.

SUMMARY OF THE INVENTION

According to the present invention, a mixed-mode multiplier design that includes soft (i.e., configurable) logic and hard (i.e., non-configurable) logic regions is provided. The multiplier includes a partial product generation (PPG) block, a compression block (e.g., a carry-save adder (CSA)), and a final adder stage (e.g., a carry propagate adder (CPA)). The multiplier may also include a selectable input register and a selectable output register. The selectable input register, PPG, and compression block are implemented in hard logic, while the adder and selectable output register are implemented in soft logic. The output of the hard logic components of the multiplier may be connected to the soft logic components via local routing dedicated to the multiplier. Alternatively, the interface between the hard and soft multiplier components may be provided by global routing that is available for general use by the multiplier as well as other circuitry on the device. In addition, the adder and selectable output register may be implemented using the same LABs or equivalent soft logic structures. Since the final multiplier output stage is generated using soft logic, the output interface (e.g., multiplexer circuitry) that connects the multiplier output lines to global and/or local routing is also implemented in soft logic.

The mixed-mode multiplier design efficiently uses soft logic while realizing a substantial savings in dedicated die area (e.g., for an 18×18-bit multiplier implementation, the mixed-mode design uses approximately 70% of the amount of dedicated die that is used in a pure hard logic multiplier) and little decrease in performance. Furthermore, the port densities of the hard and soft logic multiplier components are similar, thus providing a routing-efficient interface between the two types of multiplier logic.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1shows an illustrative embodiment of a multiplier100with a mixed-mode architecture and implemented in a programmable logic device. For purposes of illustration, multiplier100is shown to be configured to multiply two 18-bit input terms (i.e., perform 18×18-bit multiplication). Nevertheless, it will be understood that the multiplier can be scaled to support the multiplication of larger or smaller input terms.

Multiplier100includes input registers110, PPG block114, CSA118and CPA126. The inputs to multiplier100are provided by LABs102A-D. In this illustration, LABs102A-D each provide 9 bits of output to multiplier100. As a result, four LABs are required in order to feed the 36 bits of inputs to multiplier100to perform 18×18-bit multiplication. A fewer or greater number of LABs may in practice be used to provide the inputs to multiplier100, depending on the number of bits that each LAB is configured to provide and the size of multiplier100. Furthermore, the arrangement of the input LABs102A-D is merely illustrative, as they may be physically arranged in alternative configurations relative to each other and to multiplier100.

In general, the inputs to multiplier100may be routed from global or local routing on the PLD. As previously mentioned, global routing is not specific to the multiplier and can be used by other types of circuitry on the PLD including LABs, DSP circuitry, and I/O circuitry. On the other hand, local routing is dedicated to the multiplier, in that it provides routing that is designed for and used exclusively by the multiplier. InFIG. 1, the outputs of LABs102A-D are transmitted to global routing106via local interconnect lines104A-D. In particular, lines104A-D are muxed with global interconnect lines (not shown) in global routing106. Global routing106then routes the multiplier input signals to a region closer in proximity to multiplier100and demuxes the signals onto local interconnect lines108A and108B that are subsequently transmitted to input registers110.

Input registers110, which are implemented in hard logic, register the two inputs to multiplier100before passing the 18-bit inputs to PPG block114via lines112A and112B. It should also be mentioned that input registers110typically include associated bypass circuitry (e.g., input registers110may be followed by bypass multiplexers (not shown)) and are thus selectable (i.e., the registers may be selectively bypassed). For example, when the inputs are transmitted to the multiplier from other LABs (i.e., soft logic), it may be unnecessary to use the input registers since the inputs may be stored in the output registers of those LABs before being transmitted to the multiplier (without violating register timing constraints since the delay of the inputs through the local routing is negligible).

PPG block114, which is also implemented in hard logic, generates all the partial product terms for performing the multiplication of the two input terms, which consist of a multiplicand and a multiplier. Generally speaking, PPG block114performs bit-wise multiplication on each of the multiplier bits with each of the bits of the multiplicand. This may be achieved using any of a variety of common techniques that include a Booth or modified-Booth approach, or even simply the use of a plurality AND gates. The partial product terms generated by PPG block114are subsequently passed on to CSA118via lines116.

Like PPG block114, CSA118is also implemented in hard logic. CSA118compresses the partial product terms generated by PPG block114in order to reduce the number of terms that need to be added by CPA126. In the embodiment of the invention illustrated inFIG. 1, CSA118is configured as a Wallace tree (that may be constructed using multiple cascaded layers of 3-bit full adders) that efficiently reduces the plurality of partial product terms to two compressed vectors, a first 36-bit vector corresponding to the sum of only the bits in the partial product terms (i.e., a “summation term”), without generating carry bits, and a second 36-bit vector corresponding to the sum of the carry bits generated by the summation of the partial product terms (i.e., a “carry term”). Alternatively, CSA118may be substituted with other types of compression logic (e.g., other adder trees) implemented in hard logic that reduces the number of terms that need to be added. The outputs of CSA118are fed to CPA126via lines120A-H.

CPA126is implemented in soft logic. In the embodiment shown, lines120A-H connecting the hard logic CSA118to the soft logic CPA126represent local routing lines. Alternatively, global routing lines may be used to transmit the output of CSA118to CPA126(e.g., if the hard and soft logic portions of multiplier100are distant from each other). One advantage of transmitting the output of CSA118to CPA126via local rather than global routing is that it tends to consume less die area and may result in faster operation. However, configuring the LABs to receive input signals via local routing may complicate the general LAB design because they must be still configured to receive signals via global routing (i.e., from distant logic). On the other hand, if the inputs to CPA126were transmitted from CSA118via global routing, this design would make it possible to implement a simple LAB architecture in which all the inputs to the LABs were provided from global routing or at least from general-purpose routing.

In terms of operation, CPA126performs the addition of the terms output by CSA118to generate the final multiplier product term. InFIG. 1, CPA126includes four separate LABs122A-D that are arranged in two columns of LABs, each two LABs high. The advantage of this embodiment is that PPG block114and CSA118are each also two LABs high, and thus keeping CPA108two LABs high preferably maintains a rectangular layout for the overall multiplier. Each of LABs122A-D receives as input two 9-bit words and is accordingly configured as a 9-bit ripple-carry adder. Thus, four LABs are required in this example to add the two 36-bit summation and carry vectors from CSA118. Arrow124indicates the order of significance of the input terms from least to greatest. It will be understood that LABs122A-D shown here to form CPA126are merely illustrative, and that a greater or fewer number of LABs or equivalent soft-logic components may in actuality be used to form the final adder stage of the mixed-mode multiplier without departing from the scope of the invention. Factors that inevitably determine the number of LABs that are required to form CPA108include the number and size of the vectors generated by the carry-save adder as well as the specific parameters (e.g., number of LEs per LAB, size of each LE) of the LABs. The multiplier output product term that is generated by CPA126may be output to global or local routing depending on distance from the LAB to the intended destination and the LAB design. Alternatively, CPA126may be configured as another type of adder stage (e.g., a carry-lookahead or carry-select adder) or comparable accumulator structure that may be efficiently implemented in soft logic and used accordingly to perform addition of the output terms from CSA118. The output product term computed by CPA126may be muxed with either global or local routing lines for output. The product generated by LABs122A-D may be stored in a selectable output register of the LABs (e.g., a flip-flop) before being transmitted in order to pipeline the output.

FIG. 2shows an alternative multiplier200of the present invention. Multiplier200is similar to multiplier100ofFIG. 1, the only notable differences being that the inputs to multiplier200are provided directly by local LABs202A-D via local interconnect lines204A-D, and that the layout of multiplier200is four LAB units high rather than two. InFIG. 2, the input registers to multiplier200have been removed from the design (thereby further reducing the size of multiplier), as would be the case if, for example, the inputs were provided by LABs that registered the signals prior to transmitting them to multiplier200as previously explained. Alternatively, similar to multiplier100, multiplier200may also include input registers that may be selectively bypassed. Furthermore, since the layout of multiplier200is four LABs high, multiplier200may be easier to implement and as a result operate faster than multiplier100because the height of the multiplier matches the number of LABs with which it interfaces, thereby eliminating any routing inefficiencies. It is thus seen that the arrangement of the LABs (e.g., 2×2, as in the embodiment shown inFIG. 1; 4×1, as in the embodiment shown inFIG. 2; or 1×4)—and as a result the height of the multiplier—may be altered without departing from the scope of the present invention.

Since multiplier200operates substantially in the same manner as multiplier100, the operation of multiplier200will only be briefly described, with the understanding that the description of the operation and different embodiments of multiplier100are also applicable to multiplier200. Inputs to multiplier200are transmitted from local LABs202A-D via local interconnect lines204A-D to PPG block206, implemented in hard logic. PPG block generates the partial product terms (190 bits for 18×18-bit multiplication) and outputs the partial products to CSA210, which is also implemented in hard logic. CSA210reduces the partial products to two 36-bit vectors corresponding to a summation term and a carry term. These components are transmitted via local routing lines212A-H to soft logic CPA218, which includes LABs214A-D. CPA218adds together the vectors generated by CSA210to generate the final product term for output.

FIG. 3illustrates a PLD306that utilizes a multiplier in accordance with the present invention and that is part of an end-user data processing system300. Data processing system300may include one or more of the following components: a processor302; memory304; I/O circuitry308; and peripheral devices310. These components are coupled together by a system bus312and are populated on a circuit board314which is contained in system300.

System300can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable logic is desirable. PLD306can be used to perform a variety of different logic functions. For example, PLD306can be configured as a processor or controller that works in cooperation with processor302. In yet another example, PLD306can be configured as an interface between processor302and one of the other components in system300.

It will be understood, therefore, that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention, and that the present invention is limited only by the claims that follow.