Fast problem-size-independent parallel prefix circuits

A family of parallel algorithms solving the prefix problem on the combinational circuit model is presented. These prefix circuits are waist-size optimal with waist 1 (WSO-1). They are not only building blocks for constructing fast depth-size optimal prefix circuits, but also themselves fast problem-size-independent prefix circuits. When the problem size is greater than the circuit width. the presented prefix circuits may very much faster than any other prefix circuits of the same width, especially when the problem size is greater than or equal to twice the circuit width. The new prefix circuits are compared analytically with other representative prefix circuits to show how fast they are. They have the minimum depth and are the fastest among all WSO-1 prefix circuits of the same width and fan-out. Thus, they are better building blocks than other WSO-1 circuits for constructing fast depth-size optimal prefix circuits with the same fan-out. (C) 2009 Elsevier Inc. All rights reserved.