Asynchronous Parallel Prefix Computation

Rajit Manohar and José A. Tierno

The prefix problem is to compute all the products x1*x2*...*xk, for 1<= k<= n, where * is an associative binary operation. We start with an asynchronous circuit to solve this problem with O(log n) latency and O(n log n) circuit size, with O(n) *-operations in the circuit. Our contributions are:
  • A modification to the circuit that improves its average-case latency from O(log n) to O(loglog n) time; and
  • A further modification that allows the circuit to run at full-throughput i.e., with constant response time.
The construction can be used to obtain a asynchronous adder with O(log n) worst-case latency and O(loglog n) average-case latency.