Parallel prefix adder design

Adders are one of the critical elements in VLSI chips because of their variety of usages such as ALUs, floating point arithmetic units, memory addressing and program counting. For this reason, they have been studied for about half a century and a variety of adders have been invented. Among them, prefix adders are based on parallel prefix circuit theory which provides a solid theoretical basis for wide range of design trade-offs between delay, area and wiring complexity. This dissertation first presents an algorithm for prefix computation under the condition of non-uniform input signal arrival. To obtain the algorithm, the structure of prefix circuits is analyzed and a generalized circuit structure that is composed of two parts, a full-product generation tree and sub-product generation trees, is proposed. For the full-product generation tree, a delay optimized design algorithm is proposed and its optimality is shown. The proposed algorithm is easy of implement and fast in run-time due to its greedy strategy and it ensures the minimum depth prefix circuit design with the Ladner-Fischer strategy. This dissertation also presents a one-shot batch process that generates a wide range of designs for a group of parallel prefix adders. The prefix adders are represented by two two-dimensional matrixes and two vectors. This matrix representation makes it possible to compose two functions for gate sizing which calculate the delay and the total transistor width of the carry propagation graph of adders. After gate sizing, the critical path net list of the carry propagation graph is generated from the matrix representation for spice delay calculation. The process is illustrated by generating sets of delay and total transistor width pairs for 32-bit and 64-bit cases.