Richard E. Ladner
Michael J. Fischer
- 1 BOOTH, T.L. Sequential Machines and Automata Theory. Wdey, New York, 1967.Google Scholar
- 2 BRENT, R. On the addiuon ofbmary numbers. IEEE Trans. Comput. C-19, 8 (1970), 758-759Google Scholar
- 3 KNUTH, D.E. The Art of Computer Programming, Vol. 1. Addison-Wesley, Reading, Mass., 1968 Google Scholar
- 4 KNUTH, D.E. The Art of Computer Programming, Vol. 2. Addison-Wesley, Reading, Mass, 1969. Google Scholar
- 5 KRAPCHENKO, V.M. Asymptotic estimation of addition time of a parallel adder Syst. Theory Res. 19 (1970), 105-122 {Probl Kibern. 19, 107-122 (Russ.)}.Google Scholar
- 6 OFMAN, Yu. On the algorithmic complexity of discrete functions. Soy Phys Dokl 7 (1963), 589-591Google Scholar
- 7 PATERSON, M S An introduction to Boolean function complexity. Soodtd Math de France Astdnsque 38-39 1976, 183-201 Also Tech. Rep STAN-CS-76-557, Computer Science Department, Stanford Umv, Stanford, Cahf, August 1976Google Scholar
- 8 SAVAGE, J E.The Complexity of Computing. Wdey, New York, 1976 Google Scholar
- 9 SCHONHAGE, A A lower bound for the length of addition chains. Theor Comput. Sct 1 (1975), 1-12Google Scholar
- 10 TUNG, C Anthmettc In Computer Sctence, A F Cardenas, L. Presser, and M A Marm, Eds, Wdeylnterscience, New York, 1972Google Scholar
Index Terms
- Parallel Prefix Computation
Recommendations
New families of computation-efficient parallel prefix algorithms
New families of computation-efficient parallel prefix algorithms for message-passing multicomputers are presented. The first family improves the communication time of a previous family of parallel prefix algorithms; both use only half-duplex ...
Parallel prefix computation in the recursive dual-net
ICA3PP'10: Proceedings of the 10th international conference on Algorithms and Architectures for Parallel Processing - Volume Part IIn this paper, we propose an efficient algorithm for parallel prefix computation in recursive dual-net, a newly proposed network The recursive dual-net RDNk(B) for k>0 has ${(2n_0)^{2^k}/2}$ nodes and d0+k links per node, where n0 and d0 are the number ...
Parallel biological sequence comparison using prefix computations
We present practical parallel algorithms using prefix computations for various problems that arise in pairwise comparison of biological sequences. We consider both constant and affine gap penalty functions, full-sequence and subsequence matching, and ...
Comments