Algorithms and Hardware Designs for Decimal …

1 Algorithms and Hardware Designs forDecimal MultiplicationbyMark A. ErlePresented to the Graduate and Research Committeeof Lehigh Universityin Candidacy for the Degree ofDoctor of PhilosophyinComputer EngineeringLehigh UniversityNovember 21, 2008 Approved and recommended for acceptance as a dissertation in partial fulfillment ofthe requirements for the degree of Doctor of DateDissertation Committee:Dr. Mark G. ArnoldChairDr. Meghanad D. WaghMemberDr. Brian D. DavisonMemberDr. Michael J. SchulteExternal MemberDr. Eric M. SchwarzExternal MemberDr. William M. PottengerExternal MemberiiiThis dissertation is dedicated to Michele, Laura, Kristin, and the path to completing this dissertation, I have traversed the birth of mythird daughter, the passing of my mother, and the passing of my father. Fortunately,I have not been alone, for I have been traveling with God, family, and am appreciative of the support I received from IBM all along the way.

2 Thereare several colleagues with whom I had the good fortune to collaborate on severalpapers, and to whom I am very grateful, namely Dr. Eric Schwarz, Mr. BrianHickmann, and Dr. Liang-Kai Wang. Additionally, I am thankful for the guidanceand assistance from my dissertation committee which includes Dr. Michael Schulte,Dr. Mark Arnold, Dr. Meghanad Wagh, Dr. Brian Davison, Dr. Eric Schwarz,and Dr. William Pottenger. In particular, I am indebted to Dr. Schulte for hismentorship, encouragement, and , finding myself at the end of this path, I see two roads of TablesixList of FiguresxiList of AcronymsxiiiAbstract11 Motivation for Decimal Computer Arithmetic .. Overview of Research .. Significance of Research .. Outline of Dissertation .. 132 Background of Decimal Computer History of Decimal Computer Arithmetic .. Decimal Numbers .. Binary Numbers .. Fixed-point Numbers .. Scaled Fixed-point Numbers.

3 Floating-point Numbers .. Early Computer Arithmetic Systems .. Software Support of Decimal Arithmetic .. Processor Support of Decimal Arithmetic .. IEEE 754-2008 Standard .. Differences Between BFP and DFP .. Decimal Formats .. Rounding .. Exceptions .. 383 Related Decimal Encodings .. Digit Encodings .. Significand Encoding .. Decimal Addition .. Bias, Binary Addition, and Correction .. Binary Addition and Correction .. Direct Decimal Addition .. Redundant Addition .. Subtraction via End-Around Carry Addition .. Decimal multiplication .. Digit-by-Digit multiplication .. Word-by-Digit multiplication .. Word-by-Word multiplication .. Decimal Floating-point multiplication .. 764 Iterative Multiplier Fixed-point Designs .. Multiplier Employing Decimal CSAs .. Multiplier Employing Signed-Digit Adders.

4 Summary of Iterative DFXP Designs .. Floating-Point design .. Algorithm .. Features .. Implementation and Analysis .. Summary .. 1345 Parallel Multiplier Fixed-point Designs .. Multiplier Employing Decimal Carry-Save Adders .. Multiplier Employing Binary Carry-Save Adders .. Summary of Parallel DFXP Designs .. Combined Binary/ Decimal , Fixed-point design .. Floating-point design .. Algorithm .. Features .. Implementation and Analysis .. Summary .. Analysis of Iterative and Parallel Designs .. 1686 Summary .. Future Research .. Closing .. 179A Glossary197viiB Notation209C Vita215viiiList of Successive Division of Nine by Ten [1] .. Time Line of Early Computer Systems and Notable Events [2] .. Software Support of Decimal Arithmetic .. Contemporary Processor Support of Decimal Arithmetic .. Preferred Exponent of Select Decimal Operations.

5 DFP Format Parameters .. DFP Format Ranges .. Combination Field for DFP Representations .. Rounding Mode Descriptions .. Select Binary-Coded Decimal Encodings .. Some Binary-Coded Decimal Values .. Some Signed-Digit Codes .. Encoding a Densely Packed Decimal Declet [3] .. Decoding a Densely Packed Decimal Declet [3] .. Generation of Primary Multiples from Different Multiples Sets .. Generation of Primary Multiples fromA, 2A, 4A, and 5A.. Area and Delay of Iterative DFXP Multiplier ( Decimal CSAs) .. Complexity of Digit-by-Digit Products for Ranges of Decimal Inputs . Restricted-Range, Signed-Magnitude Products .. Restricted-Range, Signed-Digit Sums [4] (All Digits Are Decimal ) .. Rounding Modes, Conditions, and Product Overrides for Overflow .. Area and Delay of Iterative Multipliers (DFXP vs. DFP) .. Multiplier Operand Digit Recoding Scheme [5] .. Area and Delay of DFXP Multipliers (Iterative vs.)

6 Parallel) .. Multiplier Operand Digit Recoding Schemes [6] .. Area and Delay of DFXP Multipliers (Iterative vs. Parallel) .. Binary Multiplier Operand BoothRadix-4 Recoding Scheme .. Area and Delay of Various Parallel DFXP Multipliers [7] .. Area and Delay of Parallel Multipliers (DFXP vs. DFP) .. Area and Delay vs. Pipeline Depth of Parallel DFP Multiplier .. Area and Delay of Multipliers (Iterative vs. Parallel, DFXP vs. DFP) Notation and Nomenclature of DFP Entity Components and Fields . Notation of Operands and Data .. Unary Arithmetic Operations and Symbols .. Binary Arithmetic Operations, Symbols, and Operand Names .. Logic Operations and Symbols .. Truth Tables of Logic Operations .. Operator Precedence .. 214xList of Fixed-point Example .. Scaled Fixed-point Example .. Floating-point Example .. Generalized Flow of DFXP Addition .. Successive Correction Example.

7 Bias and Correction Example .. Carry-save Addition Example .. Signed-digit Addition Example .. Generalized Flow of DFXP multiplication .. Generalized design of DFXP Digit-by-digit multiplication .. Generalized design of DFXP Word-by-digit multiplication .. Generalized design of DFXP Word-by-word multiplication .. Preliminary Iterative DFXP Multiplier design .. Flowchart of Iterative DFXP Multiplier Using Decimal CSAs .. Iterative DFXP Multiplier design Using Decimal CSAs .. Flowchart of Iterative DFXP Multiplier Using Signed-Digit Adders . Example of Recoding into Signed Decimal Digits .. Example for Iterative DFXP Multiplier Using Signed-Digit Adders .. Recoder Block: (a) Single Digit, (b) n-Digit Operand .. Digit Multiplier Block: (a) Single Digit, (b) n-Digit .. Iterative DFXP Multiplier Using Signed-Digits Adders .. Flowchart of Iterative DFP Multiplier Using Decimal CSAs.

8 Top Portion of Iterative DFP Multiplier design .. Rounding Scheme .. Bottom Portion of Iterative DFP Multiplier design .. Flowchart of Parallel DFXP Multiplier Using Decimal CSAs [5] .. Partial Product Reduction Tree Employing Decimal CSAs [5] .. Flowchart of Parallel DFXP Multiplier Using Binary CSAs [6] .. Partial Product Reduction Tree:Radix-10 Recoding, Binary CSAs [6] Flowchart of Parallel BFXP/DFXP Multiplier Using Binary CSAs [7] Binary/ Decimal Multiplier Operand Recoding Example [7] .. Combined Bin/Dec Partial Product Reduction Tree (33 Products) [7] Split Bin/Dec Partial Product Reduction Tree (33 Products) [7] .. Flowchart of Parallel DFP Multiplier Using Binary CSAs [8] .. Parallel DFP Multiplier design [8] .. DFP Storage Fields .. 210xiiList of AcronymsASIC - Application-specific Integrated CircuitBCD - Binary Coded DecimalBID - Binary Integer DecimalBFXP - Binary Fixed-PointBFP - Binary Floating-PointCLB - Combinatorial Logic BlockCMOS - Complimentary Metal-Oxide SemiconductorCSA - Carry-Save AdderDFXP - Decimal Fixed-PointDFP - Decimal Floating-PointDPD - Densely Packed DecimalHDL - Hardware Description LanguageIC- Integrated CircuitLSB - Least Significant BitLSD - Least Significant DigitLUT - Look-Up TableMSB - Most Significant BitMSD - Most Significant DigitNaN - Not-a-NumberNFET - Negative-channel Field-Effect TransistorFET - Field-Effect TransistorPFET - Positive-channel Field-Effect TransistorQNaN - Quiet Not-a-NumberSNaN - Signaling Not-a-NumberXS3 - Excess-3 binary coded decimalxiiiAbstractAlthough a preponderance of business data is in Decimal form.

9 Virtually all floating-point arithmetic units on today s general-purpose microprocessors are based on thebinary number system. Higher performance, less circuitry, and better overall errorcharacteristics are the main reasons why binary floating-point Hardware (BFP) ischosen over Decimal floating-point (DFP) Hardware . However, the binary numbersystem cannot precisely represent many common Decimal values. Further, althoughBFP arithmetic is well-suited for the scientific community, it is quite different frommanual calculation norms and does not meet many legal to the shortcomings of BFP arithmetic, many applications involving fractionaldecimal data are forced to perform their arithmetic either entirely in software or with acombination of software and Decimal fixed-point Hardware . Providing DFP hardwarehas the potential to dramatically improve the performance of such applications. Onlyrecently has a large microprocessor manufacturer begun providing systems with DFPhardware.

10 With available die area continually increasing, dedicated DFP hardwareimplementations are likely to be offered by other microprocessor dissertation discusses the motivation for Decimal computer arithmetic, a briefhistory of this arithmetic, and relevant software and processor support for a varietyof Decimal arithmetic functions. As the context of the research is the IEEE Standardfor Floating-point Arithmetic (IEEE 754-2008) and two-state transistor technology,1descriptions of the standard and various Decimal digit encodings are research presented investigates Algorithms and Hardware support for decimalmultiplication, with particular emphasis on DFP multiplication . Both iterative andparallel implementations are presented and discussed. Novel ideas are advanced suchas the use of Decimal counters and compressors and the support of IEEE 754-2008floating-point, including early estimation of the shift amount, in-line exception han-dling, on-the-fly sticky bit generation, and efficient Decimal rounding.