Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Session 1520

The Wallace Tree Simulator

John D. Carpinelli, Michael Dokachev New Jersey Institute of Technology

Abstract

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.

1. Introduction

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

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Dokachev, M., & Carpinelli, J. (2003, June), The Wallace Tree Simulator Paper presented at 2003 Annual Conference, Nashville, Tennessee. 10.18260/1-2--12429