Fault Tolerance and Computer Arithmetic
A Method for Graphically Analyzing High Speed Multiplier Arrays in Order to Reduce Reduction Errors and Minimize the Number of Half Adders
Ron S. Waters, Whitney J. Townsend, and Earl E. Swartzlander, Jr.
Austin Conference on Integrated Systems and Circuits
pp. 54-58, Austin, TX, May 13-15, 2007
Abstract
Wallace and Dadda tree multipliers use full adders and half adders in the tree reduction tiers. Half adders do not contribute to the array reduction, they only shift partial products. Therefore, minimizing the number of half adders used in a multiplier reduction is beneficial. Wallace tree multiplier analysis, especially for large data word sizes can be very cumbersome and difficult to reduce without error. There have been few innovations in topological manipulation of high speed multipliers that simplify analysis and reduce errors.
A method for high speed multiplier array reduction is presented using an array folding scheme for reduction simplification. This method defines an intermediate notation and ensures that the number of reductions is the same as when using classic Wallace or Dadda reduction techniques, hence the resulting multiplier performance is equivalent to Wallace and Dadda multipliers. For an n-bit by n-bit Wallace multiplier, the number of half adders is at least n. More often the number of half adders is significantly larger than n, resulting in Wallace multipliers that are more complex and larger than the equivalent Dadda multipliers. The reduction technique presented emphasizes the use of full adders and greatly reduces the number of half adders; allowing implementations with from 1/2 to 2/3 fewer half adders than standard Wallace multipliers.
Quadruple Time Redundancy: Efficient Error Correction for Datapaths *
Whitney J. Townsend and Jacob A. Abraham
Special Workshop in Honor of Prof. Edward J. McCluskey
in conjunction with the
22nd IEEE International Conference on Computer Design
pp. 19-20, San Jose, CA, October 10, 2004
Abstract
Quadruple Time Redundancy (QTR) presents a different paradigm of redundancy for the masking of datapath errors. It seeks to balance redundancy in hardware and time for error correction, reducing the overhead necessary for masking. Simulation results for adders of various sizes employing QTR are provided and contrasted with those for traditional masking techniques. Applications of QTR to both traditional silicon and emerging nanotechnologies are discussed.
Quadruple Time Redundancy Adders *
Whitney J. Townsend, Jacob A. Abraham, and Earl E. Swartzlander, Jr.
18th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems
pp. 250-256, Cambridge, MA, November 3-5, 2003
Abstract
This paper presents a concurrent error correcting adder design employing fault masking through a combination of time and hardware redundancy. This new method, Quadruple Time Redundancy, is compared with a non-redundant adder, a Triple Modular Redundancy adder, and a Time Shared Triple modular Redundancy adder with respect to the hardware complexity and the delay for adders of various sizes. In comparison with Time Shared Triple Modular Redundancy to which it is most closely related, Quadruple Time Redundancy results in a 40% - 55% reduction in hardware complexity while incurring a reasonable delay increase.
pdf
presentation pdf
A Comparison of Dadda and Wallace Multiplier Delays *
Whitney J. Townsend, Earl E. Swartzlander, Jr., and Jacob A. Abraham
SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII
pp. 552-560, San Diego, CA, August 6-8, 2003
Abstract
The two well-known fast multipliers are those presented by Wallace and Dadda. Both consist of three stages. In the first stage, the partial product matrix is formed. In the second stage, this partial product matrix is reduced to a height of two. In the final stage, these two rows are combined using a carry propagating adder. In the Wallace method, the partial products are reduced as soon as possible. In contrast, Dadda's method does the minimum reduction necessary at each level to perform the reduction in the same number of levels as required by a Wallace multiplier. It is generally assumed that, for a given size, the Wallace multiplier and the Dadda multiplier exhibit similar delay. This is because each uses the same number of pseudo adder levels to perform the partial product reduction. Although the Wallace multiplier uses a slightly smaller carry propagating adder, usually this provides no significant speed advantage. A closer examination of the delays within these two multipliers reveals this assumption to be incorrect. This paper presents a detailed analysis for several sizes of Wallace and Dadda multipliers. These results indicate that despite the presence of the larger carry propagating adder, Dadda's design yields a slightly faster multiplier.
pdf
presentation pdf
On-Line Error Detecting Constant Delay Adder *
Whitney J. Townsend, Jacob A. Abraham, and Parag K. Lala
9th IEEE Interational On-Line Testing Symposium
pp. 17-22, Kos Island, Greece, July 7-9, 2003
Abstract
Fault tolerance requires the inclusion of redundant information. In this paper an on-line error detecting adder is presented in which the redundant information serves a dual purpose. It provides fault tolerance during the arithmetic operations while also providing a method by which addition is constrained to become a constant delay operation regardless of the word size of the operands.
pdf
presentation pdf
On-Line Error Detection in a Carry-Free Adder
Whitney J. Townsend, Mitchell A. Thornton, and Parag K. Lala
11th IEEE/ACM International Workshop on Logic & Synthesis
pp. 251-254, New Orleans, LA, June 4-7, 2002
Abstract
This work presents an improved design for a carry-free adder featuring on-line error detection. The salient contribution of this work is an extremely quick and cost-effective method of conversion from either two's complement or signed magnitude format into the internal 1-out-of-3 code used within this adder.
pdf
poster presentation pdf
* This material is based upon work supported under a National Science Foundation Graduate Research Fellowship.