Name
Abstract | ||
|---|---|---|
The prefix problem is to compute all the products $x_1 \otimes x_2 \otimes \cdots \otimes x_k,$ for 1 驴k驴n, where $\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)\ \otimes\!\!-{\rm 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. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/12.736437 | Computers, IEEE Transactions |
Keywords | Field | DocType |
adders,asynchronous circuits,digital arithmetic,parallel algorithms,associative binary operation,asynchronous adder,asynchronous circuit,asynchronous parallel prefix computation,average-case latency,worst-case latency | Log-log plot,Binary logarithm,Asynchronous communication,Adder,Computer science,Latency (engineering),Parallel computing,Circuit design,Real-time computing,Time complexity,Asynchronous circuit | Journal |
Volume | Issue | ISSN |
47 | 11 | 0018-9340 |
Citations | PageRank | References |
14 | 0.94 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rajit Manohar | 1 | 1038 | 96.72 |
| Jose A. Tierno | 2 | 92 | 8.99 |