Asee peer logo

The Wallace Tree Simulator

Download Paper |

Conference

2003 Annual Conference

Location

Nashville, Tennessee

Publication Date

June 22, 2003

Start Date

June 22, 2003

End Date

June 25, 2003

ISSN

2153-5965

Conference Session

Computers in Education Poster Session

Page Count

7

Page Numbers

8.1190.1 - 8.1190.7

Permanent URL

https://peer.asee.org/12429

Download Count

538

Request a correction

Paper Authors

author page

Michael Dokachev

author page

John Carpinelli

Download Paper |

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

Dokachev, M., & Carpinelli, J. (2003, June), The Wallace Tree Simulator Paper presented at 2003 Annual Conference, Nashville, Tennessee. https://peer.asee.org/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