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

ABSTRACT

Linda is a parallel programming language that differs from other parallel languages in its simplicity and in its support for distributed data structures. The S/Net is a multicomputer, designed and built at AT&T Bell Laboratories, that is based on a fast, word-parallel bus interconnect. We describe the Linda-supporting communication kernel we have implemented on the S/Net. The implementation suggests that Linda's unusual shared-memory-like communication primitives can be made to run well in the absence of physically shared memory; the simplicity of the language and of our implementation's logical structure suggest that similar Linda implementations might readily be constructed on related architectures. We outline the language, and programming methodologies based on distributed data structures; we then describe the implementation, and the performance both of the Linda primitives themselves and of a simple S/Net-Linda matrix-multiplication program designed to exercise them.

REFERENCES

• 1: S. AHUJA. S/Net: A high-speed interconnect for multiple computers. IEEE Selected Areas in Communication (Nov. 1983), 751-756.
• 2: Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983 [doi>10.1145/356901.356903]
• 3: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 4: Nicholas Carriero , David Gelernter , Jerrold Leichter, Distributed data structures in Linda, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-242, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512666]
• 5: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 6: David R. Cheriton , Willy Zwaenepoel, The distributed V kernel and its performance for diskless workstations, Proceedings of the ninth ACM symposium on Operating systems principles, p.129-140, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 7: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 8: DEPARTMENT OF DEFENSE. Reference Manual for the Ada Programming Language, U.S. Dept. of Defense, July 1982.
• 9: DEUTSCH, J. T. AND NEWTON, A.R. MSPL1CE: A multiprocessor-based circuit simulator. In Proceedings of the 1984 International Conference on Parallel Processing, (Aug. 1984), 207-214.
• 10: Richard P. Gabriel , John McCarthy, Queue-based multi-processing LISP, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.25-44, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802019]
• 11: David Gelernter , Arthur J. Bernstein, Distributed communication via global buffer, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.10-18, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806676]
• 12: GELERNTER, D. Dynamic global name spaces on network computers. In Proceedings International Conference Parallel Processing, (Aug. 1984).
• 13: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 14: GELERNTER, D., CARRIERO, N., CHANDRAN, S. AND CHANG, S. "Parallel programming in Linda," In Proceedings of the International Conference on Parallel Processing, (Aug. 1985), 255-263.
• 15: 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]
• 16: Inmos Corp, Occam Programming Manual, Prentice Hall Trade, 1984
• 17: SHAPIRO, E. Systolic programming: A paradigm of parallel processing. Tech. Rep. CS84-21, Weitzmann Institute of Science, Dept. of Applied Mathematics, Rehovot, Israel (Aug. 1984).
• 18: Alfred Z. Spector, Performing remote operations efficiently on a local computer network, Communications of the ACM, v.25 n.4, p.246-260, April 1982 [doi>10.1145/358468.358478]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications
      C.2.4 Distributed Systems
          Subjects: Network operating systems

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

General Terms:
Design, Languages