Asynchronous parallel prefix computation

The prefix problem is to compute all the products x 1 ⊗ x 2 ⊗ ⋯ ⊗ x k, 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: 1) a modification to the circuit that improves its average-case latency from O(log n) to O(log log n) time, and 2) 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(log log n) average-case latency. © 1998 IEEE.