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.

2 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. Thereare several colleagues with whom I had the good fortune to collaborate on severalpapers, and to whom I am very grateful, namely Dr.

3 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.

4 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 .. 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.

5 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 .

6 764 Iterative Multiplier Fixed-point Designs .. Multiplier Employing Decimal CSAs .. Multiplier Employing Signed-Digit Adders .. 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 .

7 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.

8 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).

9 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. Parallel) .. Multiplier Operand Digit Recoding Schemes [6] .. Area and Delay of DFXP Multipliers (Iterative vs.)

10 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.