Asynchronous parallel prefix computation
Rajit Manohar, J. Tierno · IEEE Transactions on Computers · 1998
The prefix problem is to compute all the products x/sub 1//spl otimes/x/sub 2//spl otimes/.../spl otimes/x/sub k/, for 1/spl les/k/spl les/n, where /spl otimes/ 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) /spl otimes/-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.