Progress report on a system for general-purpose parallel symbolic algebraic computation

ABSTRACT

We discuss on-going work on large-grained parallel symbolic computation using a system based on Maple and Linda. The prototype runs on a Sequent Balance. The approach can be used with most existing algebra/symbol manipulation systems, and provides the potential to deliver of parallel symbolic computation on a variety of architectures (e.g. shared memory, hypercubes, networked workstations). Parallel speedup was achieved on a variety of algebraic problems, although many significant improvements in efficiency remain to be achieved.

REFERENCES

• ACG86: Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and friends, Computer, v.19 n.8, p.26-34, Aug. 1986 [doi>10.1109/MC.1986.1663305]
• Akr86: Alkiviadis G. Akritis, There is no “Uspensky's method.”, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.88-90, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32457]
• BCG89: Robert Bjornson, Nicholas Carriero, and David Gelernter. The implementation and performance of hypercube Linda. Technical Report YALEU/DCS/RR-690, Department of Computer Science, Yale University, March 1989.
• CFG+86: Bruce W. Char , Gregory J. Fee , Keith O. Geddes , Gaston H. Gonnet , Michael B. Monagan, A tutorial introduction to Maple, Journal of Symbolic Computation, v.2 n.2, p.179-200, June 1986 [doi>10.1006/jsco.1995.1045]
• CG88: Nicholas Carriero , David Gelernter, Applications experience with Linda, ACM SIGPLAN Notices, v.23 n.9, p.173-187, Sept. 1988
• 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]
• CL82: George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• FH89: Charles J. Fleckenstein , David Hemmendinger, Using a global name space for parallel execution of UNIX tools, Communications of the ACM, v.32 n.9, p.1085-1090, Sept. 1989 [doi>10.1145/66451.66456]
• Gel83: David Gelernter. Generative communication in Linda. Technical Report YALEU/ DCS/ RR-294, Department of Computer Science, YMe University, November 1983.
• Luc86: S. Lucco. A heuristic Linda kernel for hypercube multiprocessors. In Hypercube Processors 1986, pages 32-33. SIAM, September 1986.
• Sau89: B. D. Saunders , H. R. Lee , S. K. Abdali, A parallel implementation of the cylindrical algebraic decomposition algorithm, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.298-307, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74576]
• SLA89: B. D. Saunders , H. R. Lee , S. K. Abdali, A parallel implementation of the cylindrical algebraic decomposition algorithm, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.298-307, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74576]
• SSS89: Charles L. Seitz , Jakov Seizovic , Wen Su, The C Programmer''s Abbreviated Guide to Multicomputer Programming, California Institute of Technology, Pasadena, CA, 1988
• Wat86: Stephen Michael Watt, Bounded parallelism in computer algebra, University of Waterloo, Waterloo, Ont., Canada, 1986
• WL88: Robert A. Whiteside and Jerrotd S. Leichter. Using Linda for supercomputing on a local area network. Technical Report YALEU/DCS/TR-638, Department of Computer Science, Yale University, June 1988.
• Zip79: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Linda

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

          Nouns: Maple

General Terms:
Design, Languages, Performance