| |
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.
|
|
