Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate the ideal behavior of Schwartz's paracomputer model of computation and to implement efficiently the important fetch-and-add synchronization primitive. We outline the hardware that would be required to build a 4096 processor system using 1990's technology. We also discuss system software issues, and present analytic studies of the network performance. Finally, we include a sample of our effort to implement and simulate parallel variants of important scientific programs.

REFERENCES

• 1: A. Borodin and J. E. Hopcroft, "Merging on Parallel Models of Computation", Manuscript, 1981.
• 2: Burroughs Corp., Numerical Aerodynamic Simulation Facility Feasibility Study, NAS2-9897, March 1979.
• 3: Denelcor, Heterogeneous Element Processor Principles of Operation, 1981.
• 4: Narsingh Deo, C. Y. Pang, and R. E. Lord, "Two Parallel Algorithms for Shortest Path Problems"
• 5: Daniel Dias and J. Robert Jump, "Analysis and simulation of buffered delta networks", IEEE Trans.on Computers C-30, 1981, 273-282.
• 6: L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973 [doi>10.1145/800123.803967]
• 7: Allan Gottlieb, "PLUS-A PL/I Based Ultracomputer Simulator, I", Ultracomputer Note #10, Courant Institute, NYU 1980a.
• 8: Allan Gottlieb, "WASHCLOTH-The Logical Successor to Soapsuds", Ultracomputer Note #12, Courant Institute, NYU 1980b.
• 9: Allan Gottlieb, "PLUS - A PL/I Based Ultracomputer Simulator, II", Ultracomputer Note #14, Courant Institute, NYU 1980c.
• 10: Allan Gottlieb and Clyde P. Kruskal, "MULT-A Multitasking Ultracomputer Language with Timing, I&II", Ultracomputer Note #15, Courant Institute, NYU 1980.
• 11: Allan Gottlieb , Clyde P. Kruskal, Coordinating parallel processors: a partial unification, ACM SIGARCH Computer Architecture News, v.9 n.6, p.16-24, October 1981 [doi>10.1145/859515.859517]
• 12: Allan Gottlieb, Boris Lubachevsky, and Larry Rudolph, "Coordinating Large Numbers of Processors", Intl. Conf. on Parallel Processing, 1981.
• 13: Allan Gottlieb and Jack T. Schwartz, "Networks and Algorithms for Very Large Scale Parallel Computations", to appear in Computer, January 1982.
• 14: Leo J. Guibas and Frank M. Liang, "Systolic stacks, queues, and counters", Conference on Advanced Research in VLSI, Jan. 1982.
• 15: Robert G. Jacobsen and David P. Misunas, "Analysis of structures for packet communication", Int. Conf. on Parallel Processing, 1977.
• 16: Steven D. Johnson, "Connection Networks for Output-Driven List Multiprocessing", Tech. Rep. 114, Computer Science Dept., Indiana University, 1981.
• 17: Malvin Kalos, "Scientific Calculations on the Ultracomputer", Ultracomputer Note #30, Courant Institute, NYU, 1981.
• 18: Malvin Kalos, Gabi Leshem, and B. D. Lubachevsky, "Molecular Simulations of Equilibrium Properties", Ultracomputer Note #27, Courant Institute, NYU, 1981.
• 19: K. R. Kaplan and R. V. Winder, "Cache-Based Computer Systems", Computer 6, 1973, pp. 30-36.
• 20: David Korn, "Timing Analysis for Scientific Codes Run under WASHCLOTH Simulation", Ultracomputer Note #24, Courant Institute, NYU, 1981.
• 21: Clyde P. Kruskal, "Supersaturated Paracomputer Algorithms", Ultracomputer Note #26, Courant Institute, NYU, 1981.
• 22: Clyde P. Kruskal and Marc Snir, "Some results on Packet-Switching Networks for Multiprocessing", Princeton Conference on Information Sciences and Systems, 1982.
• 23: H. T. Kung, "The Structure of Parallel Algorithms", in Advances in Computers 19, M. C. Yovits (ed.), Academic Press, New York, 1980, 65-112.
• 24: Leslie Lamport, "How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs", IEEE Trans. C-28, 1979, pp. 690-691.
• 25: Duncan Lawrie, "Access and Alignment of Data in an Array Processor", IEEE Trans. C-24, 1975, pp. 1145-1155.
• 26: Gary Rodrigue, E. Dick Giroux, and Michael Pratt, "Perspectives on Large-Scale Scientific Computing", IEEE Computer v. 13 #10, Oct. 1980, pp. 65-80.
• 27: Norman Rushfield, "Atmospheric Computations on Highly Parallel MIMD Computers", Ultracomputer Note #22, Courant Institute, NYU, 1981.
• 28: J. T. Schwartz, "Preliminary Thoughts on Ultracomputer Programming Style", Ultracomputer Note #3, Courant Institute, NYU, 1979.
• 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: Howard J. Siegel and Robert J. McMillen, "Using the Augmented Data Manipulator Network in PASM", Computer, 14, 1981, pp. 25-34.
• 31: Burton J. Smith, "A Pipelined, Shared Resource MIMD Computer", Intl. Conf. on Parallel Processing, 1978, pp. 6-8.
• 32: Marc Snir, "'NETSIM' Network Simulator for the Ultracomputer", Ultracomputer Note #28, Courant Institute, NYU, 1981.
• 33: Marc Snir and Jon Solworth, "The Ultraswitch—A VLSI Network Node for Parallel Processing", Ultracomputer Note #39, Courant Institute, NYU, 1982.
• 34: Harold S. Stone, "Parallel Computers", in Introduction to Computer Architecture, Harold S. Stone (ed.), SRA, Chicago Ill., 1980, pp. 318-374.
• 35: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977 [doi>10.1145/800255.810659]
• 36: R. J. Swan, S. H. Fuller, and D. P. Siewiorek, "Cm* - A Modular, Multi-microprocessor", Proc. AFIPS Conf. 46, 1977, pp. 637-644.
• 37: D. S. Wise, "Compact Layout of Banyan/FFT Networks", CMU Conf. on VLSI systems and Computations, Kung, Sproull and Steele (eds.), Computer Science Press, Rockville Maryland, 1981, pp. 186-195.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design