A unified approach to models of synchronous parallel machines

ABSTRACT

A number of different models of synchronous, unbounded parallel computers have appeared in recent literature. Without exception, running time on these models has been shown to be polynomially related to the classical space complexity measure. The general applicability of this relationship is called “the parallel computation thesis” and strong evidence of its truth is given in this paper by introducing the notion of “conglomerates” - a very large class of parallel machines, including all those which could feasibly be built. Basic parallel machine models are also investigated, in an attempt to pin down the notion of parallel time to within a constant factor. To this end, a universal conglomerate structure is developed with can simulate any other basic model within linear time. This approach also leads to fair estimates of instruction execution times for various parallel models.

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: A.K. Chandra, L.J. Stockmeyer, "Alternation", Proc. 17th FOCS, Oct. 1976 (98-108).
• 3: S.A. Cook, "Linear Time Simulation of Deternlinistic Two-Way Pushdown Automata", Proc. IFIP Congress, Aug. 1971 (75-80).
• 4: M. Flynn, "Very High-Speed Computing Systems", Proc. IEEE, vol.54, Dec. 1966 (1901-1909).
• 5: L.M. Goldschlager, "Synchronous Parallel Computation", Tech. Report No.114, Department of Computer Science, University of Toronto, Dec. 1977.
• 6: J. Hartmanis, J. Simon, "On the Power of Multiplication in Random Access Machines", Proc. 15th SWAT, Oct. 1974 (13-23).
• 7: D. Kozen, "On Parallelism in Turing Machines", Proc. 17th FOCS, Oct. 1976 (89-97).
• 8: V.R. Pratt, L.J. Stockmeyer, "A Characterization of the Power of Vector Machines", JCSS, vol.12, No.2, April 1976 (198-221).
• 9: W.J. Savitch, M.J. Stimson, "Time Bounded Random Access Machines with Parallel Processing", TR IW 67/76, Mathematisch Centrum, Amsterdam, Nov. 1976.

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

General Terms:
Theory