Efficient compilation of high-level data parallel algorithms

ABSTRACT

We present a high-level parallel calculus for nested sequences, NSC , offered as a possible theoretical “core” of an entire class of collection-oriented parallel languages. NSC is based on while-loops as opposed to general recursion. A formal, machine independent definition of the parallel time complexity and the work complexity of programs in NSC is given. Our main results are: (1) We give a translation method for a particular form of recursion, called map-recursion, into NSC , that preserves the time complexity and adds an arbitrarily small overhead to the work complexity, and (2) We give a compilation method for NSC into a very simple vector parallel machine, which preserves the time complexity and again adds an arbitrarily small overhead to the work complexity.

REFERENCES

• AB88: Serge Abiteboul and Catriel Beeri. On the power of languages for the manipulation of complex objects. In Proceedings of International Workshop on Theory and Applications of Nested Relations and Complex Objects, Darmstadt, 1988. Also available as INRIA Technical Report 846.
• BBW92: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• Ble90: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• Ble93: Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
• BS90: Guy E. Blelloch , Gary W. Sabot, Compiling collection-oriented languages onto massively parallel computers, Journal of Parallel and Distributed Computing, v.8 n.2, p.119-134, February 1990 [doi>10.1016/0743-7315(90)90087-6]
• BTS91: Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain
• Cur88: P. L. Curien. The Ap-calculus: An abstract framework for environment machines. Technical Report URA 725, Laboratoire d'Informatique, Departement de Mathematiques et d'Informatique, Ecole Normale Superieure, 45 Rue d'Ulm, 75230 Paris Cedex 05, France, 1988.
• HS86: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• Jaj92: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• Kah87: G. Kahn, Natural semantics, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.22-39, February 1987, Passau, Germany
• KLGLS90: Kathleen Knobe , Joan D. Lukas , Guy L. Stelle, Jr., Data optimization: allocation of arrays to reduce communication on SIMD machines, Journal of Parallel and Distributed Computing, v.8 n.2, p.102-118, February 1990 [doi>10.1016/0743-7315(90)90086-5]
• Lei92: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• MH88: Zhijing Mou and Paul Hudak. An algebraic model for divide-and-conquer and its parallelism. Jounal o} Supercomputing, 2:257-278, 1988.
• MTH90: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• SBT94: Dan Suciu , Val Breazu-Tannen, A query language for NC, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.167-178, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182610]
• ST94: Dan Suciu and Val Tannen. Efficient compilation of high-level data parallel algorithms. Technical Report MS-CIS-94-17, University of Pennsylvania, Philadelphia, PA 19104, April 1994. Available by ftp from ftp. cis.upenn, odu.
• SV84: Larry Stockmeyer and Uzi Vishldn. Simulation of parallel random access machines by circuits. SIAM Journal o} Computing, 13:409-422, May 1984.
• Val75: L.G. Valiant. Parallelism in comparison problems. SIAM Journal of Computing, 4(3):348- 355, 1975.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

General Terms:
Algorithms, Theory, Verification