Asynchronous parallel prefix computation

The prefix problem is to compute all the products x₁⊗x₂⊗…⊗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 an asynchronous adder with O(log n) worst-case latency and O(log log n) average-case latency