Finite-grain message passing concurrent computers

ABSTRACT

Fine-grain concurrent computers, by operating at a fine grain, increase the amount of concurrency that can be efficiently exploited in a given problem. Programming is simplified because programs may be partitioned into natural units of methods and objects and these objects are addressed uniformly whether they are local or remote. The construction of these machines poses challenging problems in reducing overhead, increasing communication bandwidth, and developing resource management techniques. This paper describes this class of machines, the challenges posed by their construction, and recent progress toward meeting these challenges.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Ametek Computer Research Division, Series 2010 Product Description, 1987.
• 3: Athas, W.C., and Seitz, C.L., Cantor Language Report, Technical Report 5232:TR:86, Dept. of Computer Science, California Institute of Technology, 1986.
• 4: BBN Advanced Computers, Inc., Butterfly Parallel Processor Overview, BBN Report No. 6148, March 1986.
• 5: William J. Dally, A VLSI Architecture for Concurrent Data Structures, Kluwer Academic Publishers, Norwell, MA, 1987
• 6: Dally, William J. and Seitz, Charles L., '~The Torus Routing Chip," J. Distributed Systems, Vol. 1, No. 3, 1986, pp. 187-196.
• 7: Daily, William J. "Wire Efficient VLSI MuItiprocessor Communication Networks," Proceedings Stanford Conference on Advanced Research in VLSI, Paul Losleben, Ed., MIT Press, Cambridge, MA, March 1987, pp. 391- 415.
• 8: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 9: W. J. Dally , L. Chao , A. Chien , S. Hassoun , W. Horwat , J. Kaplan , P. Song , B. Totty , S. Wills, Architecture of a message-driven processor, Proceedings of the 14th annual international symposium on Computer architecture, p.189-196, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30372]
• 10: Dally, William j., and Song, Paul., "Design of a Self-Timed VLSI Multicomputer Communication Controller," Proc. International Conference on Computer Design, ICCD-87, 1987, pp. 230-234.
• 11: Dally, William J., "Concurrent Data Structures," Chapter 7 in l~fessage-Passing Concurrent Computers: Their Architecture and Programming, C.L. Seitz et. al., Addison-Wesley, Reading, MA, publication expected 1988.
• 12: Dally, William J., "Concurrent Computer Architecture,'' Proceedings of Symposium on Parallel Computations and Their Impact on Mechanics, 1987.
• 13: Dennis, Jack B., "Data Flow Supercomputers," IEEE Computer, Vol. 13, No. 11, Nov. 1980, pp. 48-56.
• 14: Charles M. Flaig, VLSI Mesh Routing Systems, California Institute of Technology, Pasadena, CA, 1987
• 15: Robert H Halstead, Jr., Parallel symbolic computing, Computer, v.19 n.8, p.35-43, Aug. 1986 [doi>10.1109/MC.1986.1663306]
• 16: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 17: Inmos Limited, /MS T~24 Reference Manual, Order No. 72 TRN 006 00, Bristol, United Kingdom, November 1984.
• 18: Intel Scientific Computers, iP$C User's Guide, Order No. 175455-001, Santa Clara, CA, Aug. 1985.
• 19: Kermani, Parviz and Kleinrock, Leonard, "Virtual Cut-Through: A New Computer Communication Switching Technique," Computer Networks, Vol 3., 1979, pp. 267-286.
• 20: Knight, Tom, and Krymm~ Alex~ "Self Terminating Low-Voltage Swing CMOS Output Driver," Pvoc. Custom Integrated Circuits Conference, 1987.
• 21: Ligtenberg, Adriaan, Presentation at 1987 Princeton Workshop on Algorithm, Architecture, and Technology Issues in Models of Concurrent Computation, October 1987.
• 22: Lutz, C., et. ai., "Design of the Mosaic Element," Proc. MIT Conference on Advanced Research in VL$I, Artech Books, 1984, pp. 1-10.
• 23: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 24: Palmer, John F., "The NCUBE Family of ParMlel Supercomputers," Proc. iEEE International Conference on Computer Design, ICCD-86~ 1986, p. 107.
• 25: Pfister, G.F. et. al., "The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture'', Proc. International Conference on Parallel Processing, ICPP, 1985, pp. 764-771.
• 26: Seitz, Charles L., "System Timing" in Introduction to VLSI Systems, C. A. Mead and L. A. Conway, Addison-Wesley, 1980, Ch. 7.
• 27: Seitz, Charles L., et al., The Hypercube Communications Chip, Display File 5182:DF:85, Dept. of Computer Science, California Institute of Technology, March 1985.
• 28: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 29: Seitz, Charles L., Athas, William C., Dally, William J., Faucette, Reese, Martin, Alain J., Mattisson, Sven, Steele, Craig S., and Su, Wen-King, Message- Passing Concurrent Computers: Their Architecture and Programming, Addison-Wesley, publication expected 1988.
• 30: Su, Wen-King, Faucette, Reese, and Seitz, Charles L., C' Programmer's Guide to the Cosmic Cube, Technical Report 5203:TR:85, Dept. of Computer Science, California Institute of Technology, September 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

General Terms:
Design, Performance, Theory