U of U CS 3710 - Expanding Dedicated Multipliers

Unformatted text preview:

Expanding Dedicated MultipliersMultiplication RevisionThe Weird Split!Splitting 2's Complement NumbersSplitting a Dedicated MultiplierCase Study 1Performance and Synthesis ToolsCase Study 2SummaryRevision HistoryNotice of DisclaimerWP277 (v1.0) May 22, 2008 www.xilinx.com 1© 2008 Xilinx, Inc. All rights reserved. XILINX, the Xilinx logo, and other designated brands included herein are trademarks of Xilinx, Inc. All other trademarks are the property of their respective owners. Those of you with DSP or computationally intensiveprojects in mind will be most interested in thededicated multipliers Xilinx® Spartan®-3 generationFPGA devices have to offer; the potential isenormous, with anything from 3 to 104 available perdevice.This white paper describes methods for expandingthe natural bit-width capability of dedicatedmultipliers in a way that will make best use of thecomplete FPGA resources. This information isapplicable to the Spartan-3 generation FPGAfamilies. The same dedicated multiplier is found inthe Virtex®-II FPGAs and Virtex-II Pro FPGAs, withup to 444 multipliers available.White Paper: Xilinx FPGAsWP277 (v1.0) May 22, 2008Expanding Dedicated MultipliersBy: Ken ChapmanR2 www.xilinx.com WP277 (v1.0) May 22, 2008Multiplication RevisionREach multiplier (Figure 1) supports up to 18-bit by 18-bit signed inputs, providing support for a huge range of applications. While many people exploit the configurable nature of Xilinx FPGA devices by reducing bit widths and therefore reducing product cost, I also see an exciting trend towards extending arithmetic precision (using more bits) to improve the quality of results and even make certain algorithms practical for the first time. This is particularly interesting in those cases where the processing performance made available by FPGAs exceeds that of ASIC implementations, while at the same time providing a standard product solution to applications where the volume simply could not entertain the ASIC development costs.In this white paper we will look at expanding the natural bit-width capability of dedicated multipliers in a way that will make best use of the complete FPGA resources. This information is applicable to the Spartan-3 generation FPGA families. The same dedicated multiplier is also found in the Virtex-II FPGAs and Virtex-II Pro FPGAs, with up to 444 multipliers available. Note: Newer Virtex families such as the Virtex-4 and Virtex-5 FPGAs, and the Spartan-3A DSP family, replace the multipliers with complete DSP blocks. For more information on using these dedicated DSP blocks, see the DSP User Guide for each family.Multiplication RevisionSince we are going to exceed the bit-widths supported by a single dedicated multiplier, we are going to need to decompose the multiplication process into smaller sub-processes. In fact, we do this every time the battery runs out in our favorite calculator (and it's too dark for the solar cell to work!). Then, we revert to good old pencil and paper and perform long hand multiplication (Figure 2).In each of the examples in Figure 2, we can see that a number can be split into separate digits. “87” has been split into an “8” (meaning 80) and “7”, and “49” has been split into a “4” (meaning 40) and “9”. Partial products are then formed by multiplying the X-Ref Target - Figure 1Figure 1: Dedicated MultiplierWP277_01_051508Multiplier18 x 18ABP183618X-Ref Target - Figure 2Figure 2: Long Hand Multiplication with Individual DigitsWP277_02_050708879637207839 7 639 8 7287496372042639 7 639 8 724 7 284 8 322803200Splitting 2's Complement NumbersWP277 (v1.0) May 22, 2008 www.xilinx.com 3Rindividual digits of the multiplicand with the individual digits of the multiplier. Once all combinations have been completed, the partial products are summed to form the final result. Care must be taken to ensure that the weighting of each partial result is applied. We achieve this in long hand multiplication by inserting the “0” to offset our partial product result (for example, when performing 87×49, the last partial product is 4×8=32, but this really means 40×80=3200).The Weird Split!As “normal people”, we learn to deal with numbers in powers of ten; during our long hand multiplication process, we naturally split the numbers into individual digits. However, the rules still work if we split numbers in weird ways, even if it doesn't make the mental task easier (Figure 3).We see in Figure 3 that the multiplicand has again been split into two parts; in this case, however, the left-hand part consists of 2 digits. Since we do not naturally know our “81” times-table, we find it hard to work out 9×81=729 (I bet you split it into separate digits or used a calculator!); but so long as the partial product is appropriately weighted during the summation, then the final result is good.Splitting 2's Complement NumbersA 2's complement number is an encoded binary representation of a signed value. We tend to learn about 2's complement as some form of “invert and add one” procedure that enables negative values to be represented; however, it is also possible to evaluate a negative value more directly by splitting the number (Figure 4).In Figure 4 the all-”11111111” pattern of an 8-bit number is used to represent the value “-1”. Rather than invert all bits and add one (00000000+1=00000001), we can see that the least significant bits can be considered to represent a positive value (+127), and the most significant bit, a large negative value (-128). The net effect of this is to form the X-Ref Target - Figure 3Figure 3: Long Hand Multiplication with 2 DigitsWP277_03_05140881749637290400339 7639 81 7294 7 284 81 32428032400X-Ref Target - Figure 4Figure 4: 2's Complement Split into 1 sign Bit and 7 value BitsWP277_04_05070864 32 16 8 421Bit Value12811111111128 64 32 16 8 421128 127 14 www.xilinx.com WP277 (v1.0) May 22, 2008Splitting a Dedicated MultiplierRvalue -1. The interesting thing is that we can split the binary representation at any point, provided that the negative weighting associated with the Most Significant Bit (MSB) is taken into consideration (Figure 5).Once again, we take the 8-bit pattern of “11111111”, but this time, we split it into 3 bits and 5 bits. It doesn't make it easier to work out the value from a human perspective, but the rules still apply. The least significant 5 bits are interpreted as a positive number since all of the original bit values were


View Full Document
Download Expanding Dedicated Multipliers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Expanding Dedicated Multipliers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Expanding Dedicated Multipliers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?