A class of almost-optimal size-independent parallel prefix circuits

摘要

Prefix computation is one of the fundamental problems that can be used in many applications such as fast adders. Most proposed parallel prefix circuits assume that the circuit is of the same width as the input size. In this paper, we present a class of parallel prefix circuits that perform well when the input size, n, is more than the width of the circuit, m. That is, the proposed circuit is almost optimal in speed when n > m. Specifically, we derive a lower bound for the depth of the circuit, and prove that the circuit requires one time step more than the optimal number of time steps needed to generate its first output. We also show that the size of the circuit is optimal within one. The input is divided into subsets, each of width m — 1, and presented to the circuit in subsequent time steps. The circuit is compared with functionally similar circuits of (Lin, 1999 [9]; Lin and Hung, 2009 [12]) to show its outperforming speed. When n > m, the circuit is shown to be faster than the family of waist-size optimal circuits with waist 1 (WSO-1) of the same width and fan-out.