Data parallel algorithms

ABSTRACT

Parallel computers with tens of thousands of processors are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. The success of data parallel algorithms—even on problems that at first glance seem inherently serial—suggests that this style of programming has much wider applicability than was previously thought.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: Batcher. K.E. Sorting networks and their applications. In Proceedings of fhe 1968 Sprirlg Joirlf Compufer Corlferetxe (Reston, Va.. Apr.) AFIPS, Reston. Va.. 1968, pp. 307-314.
• 3: Batcher. K.E. Design of a massively parallel processor. IEEE Trans. Coqmf. C-29, 9 (Sept. 1980). 836-840.
• 4: Bawden. A. A programming language for massively parallel computers. Master's thesis. Dept. of Electrical Engineering and Computer Science. MIT, Cambridge. Mass.. Sept. 1984.
• 5: Alan Bawden, Connection graphs, Proceedings of the 1986 ACM conference on LISP and functional programming, p.258-265, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319868]
• 6: Blelloch. G. AFL-I: A programming language for massively concurrent computers. Master's thesis, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, Mass., June 1986.
• 7: Blelloch, G. Parallel prefix versus concurrent memory access. Tech. Rep.. Thinking Machines Corp., Cambridge, Mass.. 1986.
• 8: Bouknight, W.J., Denenberg, S.A., McIntyre. D.E.. Randall, 1.M.. Sameh, A.H.. and Slotnick, D.L. The ILLIAC IV system. Proc. IEEE 60.4 (Apr. 1972). 369-388.
• 9: Christman. D.P. Programming the Connection Machine. Master's thesis. Dept. of Electrical Engineering and Computer Science, MIT, Cambridge. Mass., Jan. 1983.
• 10: Christman, D.P. Programming the Connection Machine. Tech. Rep. ISL-84-3, Xerox Palo Alto Research Center, Palo Alto, Calif.. Apr. 1984. (Reprint of the author's master's thesis at MIT.)
• 11: A. D. Falkoff , D. L. Orth, Development of an APL standard, Proceedings of the international conference on APL: part 2, p.409-453, May 30-June 01, 1979, New York, New York, United States
• 12: Flanders, P.M., et al. Efficient high speed computing with the distributed array processor. In High Speed Computer and Algorithm Orgarlizafiorr. Koch, Lawrie. and Sameh. Eds. Academic Press, New York, 1977, pp. 113-127.
• 13: Haynes, L.S.. Lao. R.L.. Siewiorek. D.P., and Mizell. D.W. A survey of highly parallel computing. Compufer ()an. 1982). 9-24.
• 14: Hillis, W.D. Tile Comertim Machine. MIT Press, Cambridge, Mass.. 1985.
• 15: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 16: Knuth. D.E. The Arf of Con~pufer Programmi?~g. Vol. 3. Sorfing and Searrhirig. Addison-Wesley, Reading, Mass.. 1973.
• 17: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 18: Kong. H.T., and Lieserson. C.E. Algorithms for VLSI processor arrays. In Infroducfiorf fo VLSI Systems, L. Carver and L. Conway. Eds. Addison-Wesley, New York. 1980. pp. 271-292.
• 19: Lim, W. Fast algorithms for labeling connected components in 2-D arrays. Tech. Rep. 86.22, Thinking Machines Corp., Cambridge, Mass., July 1986.
• 20: Minsky. M.. and Papert. S. Percepfrorrs. 2nd ed. MIT Press, Cambridge, Mass.. 1979.
• 21: Pan, V., and Reif. J. Efficient parallel solution of linear systems. Tech. Rep. TR-02-85. Aiken Computation Laboratory, Harvard Univ.. Cambridge. Mass., 1985.
• 22: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 23: Shaw. D.E. Tire NON-VON Supercomputer. Tech. Rep., Dept. of Computer Science, Columbia Univ.. New York. Aug. 1982.
• 24: Guy L. Steele, Jr. , W. Daniel Hillis, Connection Machine Lisp: fine-grained parallel symbolic processing, Proceedings of the 1986 ACM conference on LISP and functional programming, p.279-297, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319870]
• 25: Turner. D.A. A new implementation technique for applicative languages. Soffw. Pracf. &per. 9 (1979). 31-49.

INDEX TERMS

Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Parallel

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

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

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms