Dynamic-Width Reconfigurable Parallel Prefix Circuits

Parallel prefix circuits have drawn high interests because of its importance in many applications such as fast adders. Most proposed parallel prefix circuits assume fixed width. The input size could be of the same width as the circuit or different than the width of the circuit. In this paper, we propose a class of reconfigurable parallel prefix (RPP) circuits, Ř-circuits, that support different operational modes. The Ř-circuit can be reconfigured as one parallel prefix circuit of high width as well as several smaller width parallel prefix circuits that can operate on different parallel prefix problems in parallel. In particular, an Ř-circuit, Ř(k(m)), of width km with k building blocks (slices) each of width m, can be configured as a number of z prefix circuits z ≤ k, each of width b_j such that Σ_j=1^z b_j =km. For a circuit CR_b ϵ Ř(k(m)) of b slices and width bm, we show how such circuit can be constructed. We derive a bound for the depth of CR_b and show how CR_b can handle input size n ≥ bm. Then we show the performance of Ř(k(m)) and compare it with other fixed same width prefix circuits. Moreover, we show that the Ř-circuit can apply power-efficiency techniques if the width of the input n is smaller than circuit width.