Extending the two-partner shared variable protocol to n partners

ABSTRACT

APL as a language has always provided a high level of abstraction to its users. Only in the field of communication have APL channels --- called shared variables --- been restricted to at most two partners. As most distributed applications demand more than two interacting programs, APL users had to apply their own techniques, like client-server, to develop applications that share information among more than two partners. This paper presents a proposal to move the administration of shared memory from application to language level: An extension to the well known shared variable protocol to share memory among more than two partners. Two applications of this distributed shared memory system are presented: A combinatorial optimization problem that is distributed among the machines of a workstation network and an application for students that learn APL in a working group are based upon a prototype implementation of the proposed protocol.

REFERENCES

• And91: Gregory R. Andrews, Paradigms for process interaction in distributed programs, ACM Computing Surveys (CSUR), v.23 n.1, p.49-90, March 1991 [doi>10.1145/103162.103164]
• AS88: Gregory R. Andrews and Fred B. Schneider. Concepts and Notations for Concurrent Programming. In Narain Gehani and Andrew D. McGettrick, editors, Concurrent Prograrnmiug, pages 3-69. Addison-Wesley Publishing Company, United States of America, 1988.
• AU72: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• BK92: James A. Brown , Erik Kane, APL2 implementation of cross-system shared variables, ACM SIGAPL APL Quote Quad, v.23 n.1, p.34-39, July 1992
• CG89a: Nicholas Carriero , David Gelernter, How to write parallel programs: a guide to the perplexed, ACM Computing Surveys (CSUR), v.21 n.3, p.323-357, Sep. 1989 [doi>10.1145/72551.72553]
• CG89b: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• Din89: Anne Dinning, A Survey of Synchronization Methods for Parallel Computers, Computer, v.22 n.7, p.66-77, July 1989 [doi>10.1109/2.30733]
• Dya85: Dyadic Systems Limited, Hampshire, Englartd. Lynwood Dyalog APL User Guide, 1985.
• FI81: Adin D. Falkoffand Kenneth E. iverson. The Design of APL. In A Source Book in APL, pages 49-59. APL Press, Palo Alto, United States of America, 1981. Reprint of Article in the IBM Journal of Research and Development, Voi. 17, Nr. 4, 1973.
• GK92: Anath Y. Grama and Vipin Km~lar. Parallel Processing of Discrete ()ptinfization Problems: A Survey. Technical report, Department of Computer Science, University of Minnesota, United States of America, November 1992. This report is available from the attthor via ftp or E-mail.
• GSK92: Andreas Geyer-Schulz , Thomas Kolarik, Distributed computing with APL, ACM SIGAPL APL Quote Quad, v.23 n.1, p.60-69, July 1992
• IBM92: IBM Corporation. APL2 Programming (APL2 Version 2 Rel. 1): System Services Reference, first edition, March 1992.
• ISO86: Draft International Standard (DIS 8485): Programming Language APL, Fel)ruary 1986.
• LLKS85: E. L. Lawler, .J.K. Lenstra, A. H, G. Rinnoy Kan, and D. B. Shrnoys. The Travelling Salesmart Problem. Wiley-Interscience. John Wiley and Sons, Inc., New York, 1985.
• NL91: Bill Nitzberg , Virginia Lo, Distributed Shared Memory: A Survey of Issues and Algorithms, Computer, v.24 n.8, p.52-60, August 1991 [doi>10.1109/2.84877]
• Ous90: John K. Ousterhout. Tel: An Embeddable Command Language. in Proceedings of the 1990 USENIX Winter Conference, .}anuary 1990.
• Sha92: Shg~rp. Sharp APL product information: NSVP 1.2, Septeml)er 1992.
• Ste92: W. Richard Stevens, UNIX network programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• SZ90: Michael Stumm , Songnian Zhou, Algorithms Implementing Distributed Shared Memory, Computer, v.23 n.5, p.54-64, May 1990 [doi>10.1109/2.53355]
• TN91: Alfred Taudes and Thomas Netousek. Implementing Branch-and-Bound Algorithms on A Cluster of Workstations- A Survey, Some New Results and ()pen Problems. In Parallel Computing and Mathematical Optimization. Springer, 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Languages