Milestone-Proposal:Dadda's Multiplier


To see comments, or add a comment to this discussion, click here.

Docket #:2014-15

This Proposal has been approved, and is now a Milestone


To the proposer’s knowledge, is this achievement subject to litigation?


Is the achievement you are proposing more than 25 years old? Yes

Is the achievement you are proposing within IEEE’s designated fields as defined by IEEE Bylaw I-104.11, namely: Engineering, Computer Sciences and Information Technology, Physical Sciences, Biological and Medical Sciences, Mathematics, Technical Communications, Education, Management, and Law and Policy. Yes

Did the achievement provide a meaningful benefit for humanity? Yes

Was it of at least regional importance? Yes

Has an IEEE Organizational Unit agreed to pay for the milestone plaque(s)? Yes

Has an IEEE Organizational Unit agreed to arrange the dedication ceremony? Yes

Has the IEEE Section in which the milestone is located agreed to take responsibility for the plaque after it is dedicated? Yes

Has the owner of the site agreed to have it designated as an IEEE Milestone? Yes


Year or range of years in which the achievement occurred:

1965

Title of the proposed milestone:

Dadda's Multiplier, 1965

Plaque citation summarizing the achievement and its significance:

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.

In what IEEE section(s) does it reside?

Italy

IEEE Organizational Unit(s) which have agreed to sponsor the Milestone:

IEEE Organizational Unit(s) paying for milestone plaque(s):

Unit: ITALY SECTION
Senior Officer Name: Senior officer name masked to public

IEEE Organizational Unit(s) arranging the dedication ceremony:

Unit: ITALY SECTION
Senior Officer Name: Senior officer name masked to public

Unit: ITALY SECTION COMPUTER SOCIETY CHAPTER
Senior Officer Name: Senior officer name masked to public

IEEE section(s) monitoring the plaque(s):

IEEE Section: ITALY SECTION
IEEE Section Chair name: Section chair name masked to public

Milestone proposer(s):

Proposer name: Proposer's name masked to public
Proposer email: Proposer's email masked to public

Please note: your email address and contact information will be masked on the website for privacy reasons. Only IEEE History Center Staff will be able to view the email address.

Street address(es) and GPS coordinates of the intended milestone plaque site(s):

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

Describe briefly the intended site(s) of the milestone plaque(s). The intended site(s) must have a direct connection with the achievement (e.g. where developed, invented, tested, demonstrated, installed, or operated, etc.). A museum where a device or example of the technology is displayed, or the university where the inventor studied, are not, in themselves, sufficient connection for a milestone plaque.

Please give the address(es) of the plaque site(s) (GPS coordinates if you have them). Also please give the details of the mounting, i.e. on the outside of the building, in the ground floor entrance hall, on a plinth on the grounds, etc. If visitors to the plaque site will need to go through security, or make an appointment, please give the contact information visitors will need. Department of Electronics, Information and Bioengineering of Politecnico di Milano. This is a university building, in which most of the research activity of the inventor (prof Luigi Dadda) has been carried out till his death in 2012. There are no other historical markers at this site.

Are the original buildings extant?

yes.

Details of the plaque mounting:

ground floor entrance hall.

How is the site protected/secured, and in what ways is it accessible to the public?

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

Who is the present owner of the site(s)?

Politecnico di Milano, one of the most renown universities for engineering in Italy.

What is the historical significance of the work (its technological, scientific, or social importance)?

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.

What obstacles (technical, political, geographic) needed to be overcome?

At the time of the invention of the Dadda scheme for parallel fixed-point multipliers (middle of the years ’60), the arithmetic-logic units for processors were realized using discrete logic components (i.e., transistors, resistors, capacitors, etc.), mounted on a board, and not as logical cells integrated on a single-chip full microprocessor. That technology was space-consuming and slow, due to the encumbrance of the many small circuit boards and to the long wires between them. Thus the need for both size reduction and speed-up was the driving force throughout the design of such units, and possibly even more pressing than today. The Dadda scheme was able to largely circumvent these difficulties, by providing a clever way to reduce the number of boards and to make the connections between chips as few and local (i.e., short) as possible. This was the outcome of an international research, involving different countries, in a time when there were fewer international journals and no online journal databases, as today. Notably, the first full description and evaluation of the Dadda multiplier scheme appeared (in English) in the journal Alta Frequenza published by the Italian editor AEI - Associazione Elettrotecnica ed Elettronica Italiana. Furthermore, the Dadda scheme is still used today, as it is apparent from its persistence in computer science and engineering teaching, as well as in industry practice.

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

Supporting texts and citations to establish the dates, location, and importance of the achievement: Minimum of five (5), but as many as needed to support the milestone, such as patents, contemporary newspaper articles, journal articles, or chapters in scholarly books. 'Scholarly' is defined as peer-reviewed, with references, and published. You must supply the texts or excerpts themselves, not just the references. At least one of the references must be from a scholarly book or journal article. All supporting materials must be in English, or accompanied by an English translation.

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.

Media:Some schemes for parallel multipliers (reprint).pdf

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.

Media:A suggestion for a fast multiplier.pdf

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

Media:A comparison of Dadda and Wallace multiplier delays.pdf

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.

Media:CMOS floating point unit for IBM S390.pdf

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

Media:DaddaMultiplierCircuit.pdf

Supporting materials (supported formats: GIF, JPEG, PNG, PDF, DOC): All supporting materials must be in English, or if not in English, accompanied by an English translation. You must supply the texts or excerpts themselves, not just the references. For documents that are copyright-encumbered, or which you do not have rights to post, email the documents themselves to ieee-history@ieee.org. Please see the Milestone Program Guidelines for more information.

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

Please email a jpeg or PDF a letter in English, or with English translation, from the site owner(s) giving permission to place IEEE milestone plaque on the property, and a letter (or forwarded email) from the appropriate Section Chair supporting the Milestone application to ieee-history@ieee.org with the subject line "Attention: Milestone Administrator." Note that there are multiple texts of the letter depending on whether an IEEE organizational unit other than the section will be paying for the plaque(s).