June 22, 2003
June 22, 2003
June 25, 2003
8.1190.1 - 8.1190.7
The Wallace Tree Simulator
John D. Carpinelli, Michael Dokachev New Jersey Institute of Technology
Wallace Trees are combinatorial logic circuits used to multiply binary integers. Constructed using carry-save adders, they are a fast, efficient method to implement multiplication. Since these adders do not propagate carry values between bits, they are faster than parallel adders and can produce multiplication products faster than other multiplication hardware.
This paper presents the Wallace Tree Simulator, an instructional aid for students studying computer architecture and CPU design, typically at the junior or senior level. It simulates 4-, 6-, and 8-bit Wallace Tree multipliers, as presented in the textbook Computer Systems Organization and Architecture. Students select the size of the Wallace Tree to be simulated and enter values for the operands to be multiplied. The simulator shows the partial products generated by the Wallace Tree, and the results generated by each carry-save adder in the tree, as well as the final product. Students can also examine the internal organization of the carry-save adders to see how they generate their results within the tree.
The Wallace Tree Simulator is coded as a platform-independent Java applet that can be executed within any Java-enabled web browser. The simulator and its source code are freely available under the terms of the GNU Public License.
In order to perform useful work, a CPU must be able to perform arithmetic and logical operations. Although copying data from one location to another is the most frequently performed operation within a processor, a CPU that cannot modify its data would not be useful for practical applications. All processors include circuitry to perform some arithmetic and logical operations, and this topic is typically covered in computer organization and architecture courses.
Integer multiplication can be performed using any of several methods. The traditional shift-add approach and ROM lookup tables are two methods used to implement multiplication, but each has its drawbacks. The time needed to calculate products using the shift-add method increases linearly as the number of bits in the operands increases, and the size of the lookup ROM increases exponentially with increases in the size of the operands. Wallace Trees1, which use
Proceedings of the 2003 American Society for Engineering Education Annual Conference & Exposition Copyright © 2003, American Society for Engineering Education
Dokachev, M., & Carpinelli, J. (2003, June), The Wallace Tree Simulator Paper presented at 2003 Annual Conference, Nashville, Tennessee. 10.18260/1-2--12429
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2003 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015