An efficient general purpose parallel computer

ABSTRACT

In this paper we investigate the question of what is a good way to interconnect a large number of processors. Our main result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Dana Angluin , Leslie G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings, Proceedings of the ninth annual ACM symposium on Theory of computing, p.30-41, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803393]
• 3: K.E. Batcher, "Sorting networks and their applications," Proceedings AFIPS Spring Joint Computer Conference, April 1968, vol. 32, pp. 307-314.
• 4: A.K. Chandra, D.C. Kozen and L.T.Stockmeyer, "Alternation," IBM Research Report RC 7489, 1978.
• 5: S.N. Cole, "Real-time computation by iterative array of finite state machines," Doctoral Thesis, Harvard University, Cambridge, Mass., August 1964.
• 6: S.A. Cook, "Towards a complexity theory of synchronous parallel computation," presented at International Symposium über Logik und Algorithmik zu Ehren von Professor Ernst Specker, Zurich, Switzerland, February 1980.
• 7: P. Dymond and S.A. Cook, "Hardware complexity and parallel computation," Proceedings 21th Annual IEEE Symposium on Foundations of Computer Science, Syracuse, New-York, October 1980, pp. 360-372.
• 8: Z. Galil and W.J. Paul, "An efficient general-purpose parallel computer," manuscript, Tel-Aviv University, August 1980 (First version April 1980).
• 9: Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.89-94, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804336]
• 10: L.J. Guibas, H.T. Kung and C.D. Thompson, "Direct VLSI implementation of combinatorial algorithm," Research report, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pa., March 1979.
• 11: H.J. Hoover, "Some topics in circuit complexity," Technical Report 139/80, Department of Computer Science, University of Toronto, December 1979.
• 12: J. Ja'Ja' and J. Simon, "Parallel algorithms in graph theory: planarity testing," Extended abstract, Department of Computer Science, Penn State University, University Park, Pa., 1979.
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: V.M. Krapchenko, "Asymptotic estimation of addition time of a parallel adder," English trans. in Syst. Theory Res., vol. 19 (1970), pp. 105-122; orig. in Probl. Kibern. 19, pp. 107-122.
• 15: H.T. Kung and C.E. Leiserson, "Algorithms for VLSI processor arrays," Symposium on Sparse Matrix Computations, Knoxville, Tenn., Nov. 1978.
• 16: Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
• 17: G. Lev, N. Pippenger and L.G. Valiant, "A fast parallel algorithm for routing in permutation networks," manuscript, to appear in IEEE Trans. on Computers.
• 18: K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
• 19: D. Nassimi and S. Sahni, "Bitonic sort on a mesh-connected parallel computer," IEEE Transactions on Computers, vol. C-28, no. 1 (Jan. 1979), pp. 2-7.
• 20: David Nassimi , Sartaj Sahni, An optimal routing algorithm for mesh-connected Parallel computers, Journal of the ACM (JACM), v.27 n.1, p.6-29, Jan. 1980 [doi>10.1145/322169.322172]
• 21: D. Nassimi and S. Sahni, "Parallel algorithms to set-up the Benes permutation network," Technical report 79-19, Department of Computer Science, University of Minnesota, June 1979 (to appear in JACM).
• 22: Ju. P. Ofman, "A Universal automaton," Transactions of the Moscow Math. Soc., Vol. 14 (1965), pp. 186-199; English trans. AMS, Providence, R.I. (1967), pp. 200-215.
• 23: W.J. Paul and R. Reischuk, "On time versus space II," Proceedings of 20th Annual IEEE Symposium on Foundations of Computer Science, Puerto Rico, October 1979, pp. 298-306.
• 24: N. Pippenger, "On simultaneous resource bounds," Proceedings of 20th Annual IEEE Symposium on Foundations of Computer Science, Puerto Rico, October 1979, pp. 307-311.
• 25: F.P. preparata and J. Vuillemin, "The Cube-Connected-Cycles: a versatile network for parallel computation," Proceedings of 20th Annual IEEE Symposium on Foundations of Computer Science, Puerto Rico, October 1979, pp. 140-147.
• 26: C. Savage and J. Ja'Ja', "Fast, efficient parallel algorithms for some graph problems," manuscript, Department of Computer Science, Penn State University, University Park, Pa., 1979.
• 27: A. Schönhage, "Storage modification machines," Technical report, Tübingen University, West Germany, 1979.
• 28: A Schönhage and V. Strassen, "Schnelle Multiplikation grosser Zahlen," Computing, vol. 7 (1971), pp. 281-292.
• 29: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 30: C. Tung, "Arithmetic," in Computer Science, ed. by A.F. Cardenas, L. Presser and M.A. Marin, Wiley-Inter-science, New York, 1972.
• 31: Leslie G. Valiant, Universal circuits (Preliminary Report), Proceedings of the eighth annual ACM symposium on Theory of computing, p.196-203, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803649]
• 32: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]
• 33: C. S. Wallace, "A suggestion for a fast multiplier," IEEE Transactions on Electronic Circuits, vol. EC-13 (1964), pp. 14-17.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Theory