×

Parallel solution of recurrences on a tree machine. (English) Zbl 0569.68033

The recurrence: \(x_ 0=a_ 0\), \(x_ i=a_ i+b_ ix_{i-1}\), \(i=1,2,...,n-1\), requires O(n) operations on a sequential computer. Elegant parallel solutions exist, however, that reduce the complexity to O(log N) using \(N\geq n\) processors. This paper discusses one such solution, designed for a tree-structured network of processors. A tree structure is ideal for solving recurrences. It takes exactly one sweep up and down the tree to solve any of several classes of recurrences, thus guaranteeing a solution in O(log N) time for a tree with \(N\geq n\) leaf nodes. If n exceeds N, the algorithm efficiently pipelines the operation and solves the recurrence in \(O(n/N+\log N)\) time.

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. S. Stone, An efficient parallel algorithm for the solution of a tridiagonal linear system of equations.J. of the ACM 20(2):27?38 (1973). · Zbl 0269.65018 · doi:10.1145/321738.321741
[2] P. M. Kogge and H. S. Stone, A parallel algorithm for the efficient solution of a general class of recurrence equations.IEEE Trans. on Computers C-22(8):786?793 (1973). · Zbl 0262.68015 · doi:10.1109/TC.1973.5009159
[3] P. M. Kogge, Parallel solution of recurrence problems.IBM J. of Res. and Develop. 18(2):138?148 (1974). · Zbl 0307.65080 · doi:10.1147/rd.182.0138
[4] P. M. Kogge, Maximal rate pipelined solutions to recurrence problems. InProc. of the First Annual Symp. on Computer Arch., G. J. Lipovski and S. A. Szygenda, (eds.), Gainesville, Florida, 71?76 (1973).
[5] S. C. Chen, Time and parallel processor bounds for linear recurrence systems with constant coefficients. InProc. of the Inter. Conf., P. H. Enslow Jr. (ed.), 196?205.
[6] S. C. Chen and D. J. Kuck, Time and parallel processor bounds for linear recurrence systems.IEEE Trans. on Computers C-24(7):701?717 (1975). · Zbl 0307.68035 · doi:10.1109/T-C.1975.224291
[7] S. C. Chen and A. H. Sameh, On parallel triangular system solvers.Proc. of the Sagamore Computer Conf. on Parallel Proc., 237?238 (1975).
[8] S. C. Chen, D. J. Kuck, and A. H. Sameh, Practical parallel band triangular system solvers.ACM Trans. on Mathematical Software 4(3):270?277 (1978). · Zbl 0384.65013 · doi:10.1145/355791.355797
[9] D. D. Gajski, An algorithm for solving linear recurrence systems on parallel and pipelined machines.IEEE Trans. on Computers C-30(4):190?206 (1981). · Zbl 0454.68023 · doi:10.1109/TC.1981.1675755
[10] L. Hyafil and H. T. Kung, The complexity of parallel evaluation of linear recurrences.J. of the ACM 24(3):513?521 (1977). · Zbl 0358.68084 · doi:10.1145/322017.322030
[11] G. A. Magó, A network of microprocessors to execute reduction languages. Two parts.Inter. J. of Computer and Infor. Sci. 8(5):349?385 (1979);8(6):435-471 (1979). · Zbl 0427.68028 · doi:10.1007/BF00995174
[12] G. A. Magó, A cellular computer architecture for functional programming.Spring COMPCON. VLSI: New Architectural Horizons, 179?185 (1980).
[13] J. Backus, Can Programming be liberated from the von Neumann style? A functional style and its algebra of programs.Comm. of the ACM 21(8):613?641 (1978). · Zbl 0383.68013 · doi:10.1145/359576.359579
[14] D. M. Tolle, Coordination of computation in a binary tree of processors: an architectural proposal. Ph. D. dissertation, Department of Computer Science, University of North Carolina at Chapel Hill, (1981).
[15] E. H. Williams Jr., Analysis of FFP programs for parallel associative searching. Ph.D. dissertation, Department of Computer Science, University of North Carolina at Chapel Hill, (1981).
[16] G. A. Frank, Virtual memory systems for closed applicative language interpreters. Ph.D. dissertation, Department of Computer Science, University of North Carolina at Chapel Hill, (1979).
[17] A. Koster, Execution time and storage requirements of reduction language programs on a reduction machine. Ph.D. dissertation, Department of Computer Science, University of North Carolina at Chapel Hill, (1977).
[18] G. A. Magó, D. F. Stanat, and A. Koster, Program execution on a cellular computer: some matrix algorithms (In Preparation).
[19] S. A. Browning, Computations on a tree of processors.Proc. of the Caltech Conf. on VLSI, 453?478 (January 1979); also in Chap. 8 ofIntro. to VLSI Systems, by C. Mead and L. Conway, Addison-Wesley, Reading, Massachusetts, (1980).
[20] J. L. Bentley and H. T. Kung, A tree machine for searching problems. Proc. of theInter. Conf. on Parallel Processing, 257?266 (1979).
[21] C. E. Leiserson, Systolic priority queues.Proc. of the Caltech Conf. on VLSI, 199?214 (January 1979).
[22] C. A. R. Hoare, Communicating Sequential Processes.Comm. of the ACM 21(8):666?677 (1978). · Zbl 0383.68028 · doi:10.1145/359576.359585
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.