Milestones:Dadda's Multiplier, 1965

Title

Dadda's Multiplier, 1965

Citation

Luigi Dadda published the first description of the optimized scheme, subsequently called a Dadda Tree, for a digital circuit to compute the multiplication of unsigned fixed-point numbers in binary arithmetic. This circuit allowed the arithmetic units of microprocessor-based computers to execute complex arithmetic operations with a performance/cost ratio unequaled at that time. His research and teaching pioneered computer engineering in Italy.

Street address(es) and GPS coordinates of the Milestone Plaque Sites

Politecnico di Milano, DEIB via Ponzio 34/5, 20133 Milano, Italy GPS: 45.478662, 9.232546,

Details of the physical location of the plaque

ground floor entrance hall.

How the plaque site is protected/secured

the plaque is inside the building in the main hall, monitored by the receptionist during opening hours and protected by alarm when the building is closed. the plaque will be located in a place freely accessible to the public during the opening hours of the building (typically 8am-8pm).

Historical significance of the work

In the middle of the 1960’s, research on the design of high-speed arithmetic circuits flourished, due to the need for faster computer arithmetic necessary for the quickly evolving processor architectures. In particular, the international research focused on the design of parallel digital multiplier circuits, which were far less optimized than the adder circuits. The work by Luigi Dadda [1], first published in 1965, provides one of the two most significant contributions to the design of optimized parallel digital multipliers for fixed-point binary numbers, the other one being that by C. S. Wallace [5]. Fixed-point multiplication is the most basic and frequent form of multiplication, used everywhere directly or as a component of floating point multiplication.

The key scientific idea of the work by L. Dadda is that of cleverly deferring and distributing the summation of the carry bits in the partial product matrix of the multiplication, in order to reduce the number of additions, and to arrange them so as to reduce the propagation delay. Such a parallel multiplier scheme significantly decreases the number of logic gates used by the circuit, with respect to previous solutions and in particular to the Wallace one, which shortly precedes it (1964). Not only, the principle on which the Dadda multiplier scheme is based, i.e., deferring and redistributing the carry propagation, is very original with respect to the methods that were current at that time, and it has been largely exploited in the subsequent developments of computer arithmetic. The Dadda scheme for parallel multipliers, ever since called “Dadda tree,” has become one of the two recognized structures for such a basic arithmetic circuit type, along with the Wallace one. Ever since, the so-called Dadda trees, as well as the Wallace trees, represent one of the two standard parallel multiplier schemes illustrated in every textbook on computer arithmetic, e.g., [2,3,4], and taught in the university courses on computer arithmetic.

The graphical notation invented by Luigi Dadda to demonstrate his methods, ever since called “dot diagram” or “dot notation,” has become a standard representation for the operations of binary arithmetic. There is evidence that the Dadda tree has often been considered to design efficient arithmetic-logic units (ALU) for successful processors, e.g., see [7,8] for a case of integration in the floating point unit of the IBM S/390 processor, thus significantly contributing to the development of computer arithmetic and the microprocessor revolution.

Features that set this work apart from similar achievements

The Dadda scheme for parallel fixed-point multipliers is a significant refinement of the Wallace scheme [5], which was invented shortly before (1964). The Dadda scheme considerably reduces the gate count with respect to the Wallace one, and it also slightly reduces the propagation delay. The result is a notably smaller and slightly faster multiplier circuit for unsigned fixed-point numbers, especially for large numbers of bits. Even today, it still represents an optimal solution for parallel multiplication.

Significant references

References:

[1] L. Dadda, “Some Schemes for Parallel Multipliers”, Alta Frequenza, vol. 34, pp. 349-356, 1965, http://bwrcs.eecs.berkeley.edu/Classes/icdesign/ee241_s01/PAPERS/archive/dadda65.pdf

[2] K. Hwang, Computer Arithmetic: Principles, Architecture and Design, John Wiley & Sons, Inc. New York, NY, USA, 1979, ISBN: 0471052000

[3] B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs, New York: Oxford University Press, 2000, ISBN: 978-0-19-532848-6

[4] I. Koren, Computer Arithmetic Algorithms, 2nd Edition, Published by A. K. Peters, Natick, MA, 2002, ISBN: 9781568811604

[5] C. S. Wallace, “A Suggestion for a Fast Multiplier”, IEEE Transactions on Electronic Computers, vol. EC-13, issue 1, pp. 14-17, 1964, http://dx.doi.org /10.1109/PGEC.1964.263830

[6] W. J. Townsend, E. E. Swartzlander, Jr., J. A. Abraham, “A Comparison of Dadda and Wallace Multiplier Delays”, in Proc. of SPIE, vol. 5205, Advanced Signal Processing Algorithms, Architectures, and Implementations XIII, 552, Dec., 2003, http://dx.doi.org/10.1117/12.507012

[7] E. M. Schwarz, B. Averill, L. Sigal, “A Radix-8 CMOS S/390 Multiplier," in Proc. of the 13-th Symposium On Computer Arithmetic, pp. 2-9, Asilomar, CA, Jul., 1997, http://dx.doi.org/10.1109/ARITH.1997.614873

[8] E. M. Schwarz, L. Sigal, T. J. McPherson, “CMOS Floating-Point Unit for the S/390 Parallel Enterprise Server G4”, IBM Journal of Research and Development – special issue: IBM S/390 G3 and G4 archive, vol. 41, issue 4-5, pp. 475-488, Jul./Sept. 1997, IBM Corp. Riverton, NJ, USA, http://dx.doi.org/10.1147/rd.414.0475

Comments on references:

Reference [1] is the original paper where the Dadda scheme is described and evaluated. This paper is systematically cited in the bibliography of all the subsequent research works on the same topic, as well as in that of the textbooks on computer arithmetic. The notation used in this paper, called “dot diagram” or “dot notation,” has become a standard way to represent and explain the functioning of the algorithms for binary arithmetic.

References [2,3,4] are well-known textbooks on computer arithmetic, published from the years ’60 until today, commonly adopted in the university courses on computer arithmetic. Those textbooks show the persistent importance and interest of the Dadda scheme, there always called “Dadda tree” or “Dadda multiplier,” for optimized parallel fixed-point multiplication.

Reference [5] is the original paper where the Wallace scheme is described and evaluated. It shortly precedes the Dadda scheme, which is a significant improvement thereof and is aimed in particular at reducing the gate count with respect to the Wallace scheme.

Reference [6] is a summary analysis paper on both the Wallace and Dadda parallel multiplier schemes, which proves again the superiority of the latter scheme in terms of circuit size as well as in terms of propagation delay, by using more recent microelectronic technologies at a larger integration scale. This paper gives evidence of the vitality of the Dadda scheme and of its fruitfulness even in technological scenarios greatly evolved since the time of its invention (middle 1960’s).

Reference [7] is a paper that describes the design of the arithmetic-logic unit of the IBM S/390 processor. It explicitly mentions the usage of a Dadda tree for optimizing at best the multiplication operation, thus giving evidence of the relevance of the Dadda scheme for designing successful processors. See the attached picture of a Dadda tree designed for the IBM S/390 processor.

Reference [8] is a paper that describes again the design of the arithmetic-logic unit of the IBM S/390 processor. The attached picture of such a unit apparently integrates a Dadda tree, as of [7].

Supporting materials

Department Chair's Letter accepting the installation of the plaque, if the Milestone will be approved by IEEE. Media:Polimi.pdf

Italy Section Chair's Letter accepting the charges and the duties for the plaque, if the Milestone will be approved by IEEE. Media:ItalySection.pdf