Asynchronous Parallel Prefix ComputationRajit Manohar and José A. TiernoThe 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:
