Probabilistic parallel prefix computation.

*(English)*Zbl 0772.94019Summary: Given inputs \(x_ 1,\dots,x_ n\), which are independent identically distributed random variables over a domain \(D\), and an associative operation \(\circ\), the probabilistic prefix computation problem is to compute the product \(x_ 1\circ x_ 2\circ\cdots\circ x_ n\) and its \(n-1\) prefixes. Instances of this problem are finite state transductions on random inputs, the addition or subtraction of two random \(n\)-bit binary numbers, and the multiplication or division of a random \(n\)-bit binary number by a constant.

The best known constant fan-in circuits for these arithmetic operations had logarithmic depth, linear size, and produce no errors. Furthermore, matching lower bounds for depth and size (up to constant factors between the upper and lower bounds) had previously been obtained for the case of constant fan-in circuits with no errors.

We give arithmetic circuits for probabilistic prefix computation, which for these random arithmetic operations have constant fan-in, linear size, \(O(\log\log n)\) depth, but error probability less than \(n^{-\alpha}\) for any given \(\alpha>0\). For any constant, fan-in circuits computing these random arithmetic operations with error probability \(n^{- \alpha}\), we prove the circuit depth must be bounded from below by \(\Omega(\log\log n)\). Hence, we conclude our circuits have asymptotically optimal depth among circuits with error probability \(n^{-\alpha}\).

We also give error-free circuits for these random arithmetic operations with constant fan-in at all nodes but one, linear size, and \(O(\log\log n)\) expected delay for their parallel evaluation.

The best known constant fan-in circuits for these arithmetic operations had logarithmic depth, linear size, and produce no errors. Furthermore, matching lower bounds for depth and size (up to constant factors between the upper and lower bounds) had previously been obtained for the case of constant fan-in circuits with no errors.

We give arithmetic circuits for probabilistic prefix computation, which for these random arithmetic operations have constant fan-in, linear size, \(O(\log\log n)\) depth, but error probability less than \(n^{-\alpha}\) for any given \(\alpha>0\). For any constant, fan-in circuits computing these random arithmetic operations with error probability \(n^{- \alpha}\), we prove the circuit depth must be bounded from below by \(\Omega(\log\log n)\). Hence, we conclude our circuits have asymptotically optimal depth among circuits with error probability \(n^{-\alpha}\).

We also give error-free circuits for these random arithmetic operations with constant fan-in at all nodes but one, linear size, and \(O(\log\log n)\) expected delay for their parallel evaluation.

##### MSC:

94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |

94B70 | Error probability in coding theory |

##### Keywords:

probabilistic prefix computation problem; fan-in circuits; error probability; error-free circuits; parallel evaluation
PDF
BibTeX
XML
Cite

\textit{J. H. Reif}, Comput. Math. Appl. 26, No. 1, 101--110 (1993; Zbl 0772.94019)

Full Text:
DOI

##### References:

[1] | Ladner, R.E.; Fischer, M.J., Parallel prefix computation, Journal of the assoc. for computing machinery, 27, 4, 831-838, (October 1980) |

[2] | Fich, F., New bounds for parallel prefix circuits, Proc. of the 15^{th} annual symp. on theory of computation, Boston, MA, (May 1983) |

[3] | Burks, A.W.; Goldstine, H.H.; von Neumann, J., Preliminary discussion of the logical design of an electronic computing instrument, 1, (1946), Inst. Advanced Study Princeton, NJ, Part 1 |

[4] | Reifwiesner, G.W., The determination of carry propagation length for binary addition, IRE transactions on electronic computers, 35-38, (March 1960) |

[5] | Gilchrist, B.; Pomerene, J.; Wong, S.Y., Fast carry logic for digital computers, IRE trans. electron. computers, 4, 133-136, (1955) |

[6] | Hendrickson, H.C., Fast high-accuracy binary parallel addition, IRE transactions on electronic computers, 465-469, (December 1960) |

[7] | Kilburn, T.; Edwards, D.B.G.; Aspinall, D., Parallel addition in digital computers, a new fast carry circuit, Proc. IEE, pt. B, 106, 464-466, (1959) |

[8] | Kilburn, T.; Edwards, D.B.G.; Aspinall, D., A parallel arithmetic unit using a saturated-transistor fast-carry circuit, Proc. IEE, pt. B, 107, 573-584, (1960) |

[9] | Tung, C., Arithmetic, () |

[10] | Krapchenko, V.M., Asymptotic estimation of addition time of a parallel adder., Syst. theory res., 19, 105-122, (1970), (Probl. Kibern. 19, 107-122 (Russ.)) |

[11] | Chandra, A.; Fortune, S.; Lipton, R., Unbounded Fan-in circuits and associative functions, Proc. of the 15^{th} annual symp. on theory of computation, Boston, MA, (May 1983) |

[12] | Winograd, S., On the time required to perform addition, J. of assoc. computing machinery, 12, 277-285, (1965) · Zbl 0194.48202 |

[13] | Booth, T.L., Sequential machines and automata theory, (1967), Wiley New York · Zbl 0165.02303 |

[14] | Brent, R., On the addition of binary numbers, IEEE trans. comput., C-19, 8, 758-759, (1970) · Zbl 0199.51702 |

[15] | Lehman, M.; Burla, N., Skip techniques for high-speed carry-propagation in binary arithmetic units, IRE trans. electron. computers, 10, 691-698, (1961) |

[16] | Lehman, M.; Burla, N., A note on the simultaneous carry generation system for high-speed adders., IRE trans. electron. computers, 9, 510, (1960) |

[17] | Metze, G.; Robertson, J.E., Elimination of carry propagation in digital computers, Proc. intern. conf. inform. processing, 10, 389-396, (Paris 1959), Paris 1959 UNESCO/NS/ICIP/G.2 |

[18] | Ofman, Y., On the algorithmic complexity of discrete functions, Sov. phys. dokl., 7, 589-591, (1963) · Zbl 0132.24803 |

[19] | Paterson, M.S., An introduction to Boolean function complexity, Societe math. de France asterisque (38/39), 183-201, (1976), (Also Tech. Rep. STAN-CS-76-557, Computer Science Department, Stanford University, Stanford, CA, August 1976) · Zbl 0348.94043 |

[20] | Savage, J.E., The complexity of computing, (1976), Wiley New York · Zbl 0363.68070 |

[21] | Schonhage, A., A lower bound for the length of addition chains, Theor. comput. sci., 1, 1-12, (1975) · Zbl 0307.68032 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.