Edit Proposal: Milestone-Proposal:Dadda's Multiplier You do not have permission to edit this page, for the following reason: You are not currently logged in. The action you have requested is limited to users in the group: Users. Please log in or create an account. Docket ID: (admins only) Thank you for proposing a technical achievement for possible recognition as an IEEE Milestone in Electrical Engineering and Computing. Your efforts help preserve the heritage of technology. Detailed information on the Milestone application process may be found at: Milestone Guidelines and How to Propose a Milestone. At least one of the proposer(s) must be an IEEE Member (including Student Member) in good standing. To the proposer’s knowledge, is this achievement subject to litigation? If the answer is "yes", the proposal cannot proceed further. None Yes No You must be able to answer "yes" to all of the following questions. If the answer to any of the following questions is "no", the proposal cannot proceed further. Contact us at email@example.com if you are unable to answer "yes" to all of the following and would still like to proceed. Is the achievement you are proposing more than 25 years old? Yes No 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 No Did the achievement provide a meaningful benefit for humanity? Yes No Was it of at least regional importance? Yes No Has an IEEE Organizational Unit agreed to pay for the milestone plaque(s)? Yes No Has an IEEE Organizational Unit agreed to arrange the dedication ceremony? Yes No Has the IEEE Section in which the milestone is located agreed to take responsibility for the plaque after it is dedicated? Yes No Has the owner of the site given permission to place an IEEE plaque? Yes No Year or range of years in which the achievement occurred: Title of the proposed milestone. (Include date or date range in title. Example: “Alternating Current Electrification, 1886”) Please provide a plaque citation in English summarizing the achievement and its significance. Text absolutely limited by plaque dimensions to 70 words; 60 is preferable for aesthetic reasons. NOTE: The IEEE History Committee shall have final determination on the wording of the citation. Names of living persons are not normally used in citations. Exceptions to this are cases where the person's name is linked to the achievement itself (e.g. the Lempel-Ziv algorithm, Maxwell's Equations, etc.) or where the person's name is so widely recognizeable to the general public that it makes sense to use it. When used, the names should be the names of the engineers, scientists, or technologists who actually made the achievement, rather than managers or executives. For more information and suggestions about writing milestone citations, please visit Helpful Hints on Citations, Plaque Locations. 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) will the milestone plaque(s) reside? Please specify the IEEE Organizational Unit(s) which have agreed to sponsor the Milestone, and supply name and contact information for the senior officer from those OU(s). Sponsorship has three aspects: 1) Payment for the cost of the plaque(s), 2) Arranging the dedication ceremony, and 3) agreeing to monitor the plaque and to let IEEE History Center staff know in case the plaque needs to be moved, is no longer secure, etc. Number 3 must be done by the IEEE Section(s) in which the plaque(s) is located, but aspects 1 and 2 can be done by any IEEE Organizational Unit, and they need not be the same one. 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. IEEE Organizational Unit(s) paying for milestone plaque(s) Unit: Senior Officer Name: E-mail: Unit: Senior Officer Name: E-mail: IEEE Organizational Unit(s) arranging the dedication ceremony Unit: Senior Officer Name: E-mail: Unit: Senior Officer Name: E-mail: Unit: Senior Officer Name: E-mail: IEEE section(s) monitoring the plaque IEEE Section: IEEE Section Chair name: IEEE Section Chair e-mail: IEEE Section: IEEE Section Chair name: IEEE Section Chair e-mail: Milestone proposer(s) Proposer name: Proposer email: Proposer name: Proposer email: Street address(es) and GPS coordinates of the intended milestone plaque site(s). Please include coordinates in decimal format rather than degrees. What is the intended site(s) of the milestone plaque(s) relation to the achievement? 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. Also, please Describe briefly the intended site(s) of the milestone plaque(s). (e.g. Is it corporate buildings? Historic Site? Residential? Are there other historical markers already at the site?) Are the original buildings extant? Please provide 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. How is the intended plaque site protected/secured, and in what ways is it accessible to the public? If visitors to the plaque site will need to go through security, or make an appointment, please give details as well as the contact information visitors will need in order to arrange to visit the plaque. Who is the present owner of the site(s)? In the space below, please describe in detail: the historic significance of the achievement, its importance to the evolution of electrical and computer engineering and science, its importance to regional/national/international development, its benefits to humanity, the ways the achievement was a significant advance rather than an incremental improvement of existing technology. The material submitted here will constitute the main descriptive article on the ETHW website for readers to learn about the milestone. Space is unlimited, and detail is encouraged. Most milestones require 1000 to 1500 words of support, however there is no word limit. The article should be readable by a wide audience that includes practicing engineers, scholars of history, and the general public. Some examples of the text of good milestone articles are First Radio Astronomical Observations Using Very Long Baseline Interferometry] and G3_Facsimile International Standardization of G3 Facsimile (Do not worry about the formatting of the page, IEEE History Center Staff will do that afterwards.) 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 , 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 . 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 , 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. You must supply the texts or excerpts themselves, not just the references. 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. At least one of the references must be from a scholarly book or journal article. 'Scholarly' is defined as peer-reviewed, with references, and published. The full reference, in English, must be uploaded, not just the citation. See below section for details on uploading material to the website. All supporting materials must be in English, or accompanied by an English translation. References:  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  K. Hwang, Computer Arithmetic: Principles, Architecture and Design, John Wiley & Sons, Inc. New York, NY, USA, 1979, ISBN: 0471052000  B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs, New York: Oxford University Press, 2000, ISBN: 978-0-19-532848-6  I. Koren, Computer Arithmetic Algorithms, 2nd Edition, Published by A. K. Peters, Natick, MA, 2002, ISBN: 9781568811604  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  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  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  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  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  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  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  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  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 . [[Media:DaddaMultiplierCircuit.pdf]] Supporting materials (supported formats: GIF, JPEG, PNG, PDF, DOC) which can be made publicly available on the IEEE History Center’s website (i.e. unencumbered by copyright, or with the copyright holder’s permission). 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. Images and photographs are especially appreciated, however, it is necessary that you list the copyright owner for these and obtain the copyright owner’s permission to reuse. For documents that are copyright-encumbered, or which you do not have rights to post, email the documents themselves to firstname.lastname@example.org. Please see the Milestone Program Guidelines for more information. To add attachments, first upload the file and add by adding the text: [[Media:(filename)]] For example, if the file you uploaded was named "Milestone Reference.pdf", include the text: [[Media:Milestone Reference.pdf]] in the appropriate field. 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 email@example.com 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). Submit this proposal to the IEEE History Committee for review. Only check this when the proposal is finished Summary: This is a minor edit Watch this page Cancel Retrieved from "http://ieeemilestones.ethw.org/Milestone-Proposal:Dadda%27s_Multiplier"