W. Daniel Hillis
Guy L. Steele
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.
- 1 Backus. 1. Can programming be liberated from the van Neumann style? A functional style and its algebra of programs (1977 ACM Turing Award Lecture). Con~nruu. ACM 21, 8 (Aug. 1978), 613-641. Google Scholar
Digital Library
- 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.Google ScholarDigital Library
- 3 Batcher. K.E. Design of a massively parallel processor. IEEE Trans. Coqmf. C-29, 9 (Sept. 1980). 836-840.Google Scholar
- 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.Google Scholar
- 5 Bawden. A. Connection graphs. In Proceedings of fhe 1986 ACM Conftwrm ou Lisp arld Furrfioml Programming. ACM, (Cambridge, Mass., Aug. 4-6). New York. 1986. pp. 258-265. Google ScholarDigital Library
- 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.Google Scholar
- 7 Blelloch, G. Parallel prefix versus concurrent memory access. Tech. Rep. Thinking Machines Corp., Cambridge, Mass. 1986.Google Scholar
- 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.Google ScholarCross Ref
- 9 Christman. D.P. Programming the Connection Machine. Master's thesis. Dept. of Electrical Engineering and Computer Science, MIT, Cambridge. Mass., Jan. 1983.Google Scholar
- 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.)Google Scholar
- 11 Falkoff. A.D., and Orth. D.L. Development of an APL standard. In APL 79 Cmfemce Proceedings (Rochester. N.Y., June). ACM, New York. pp. 409-453. Published as APL Quote Quad 9.4 (June 1979). Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 14 Hillis, W.D. Tile Comertim Machine. MIT Press, Cambridge, Mass. 1985.Google Scholar
- 15 Iverson, K.E. A Progranmrit~g Language. Wiley. New York, 1962. Google ScholarDigital Library
- 16 Knuth. D.E. The Arf of Con~pufer Programmi?~g. Vol. 3. Sorfing and Searrhirig. Addison-Wesley, Reading, Mass. 1973.Google Scholar
- 17 Knuth, D. E. Tile Art of Compufer Progranmif~g. Vol. 2, Semitwnerical Algorifhm (Sccmd Edifim). Addison-Wesley, Reading, Mass. 1981. Google ScholarDigital Library
- 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.Google Scholar
- 19 Lim, W. Fast algorithms for labeling connected components in 2-D arrays. Tech. Rep. 86.22, Thinking Machines Corp., Cambridge, Mass., July 1986.Google Scholar
- 20 Minsky. M. and Papert. S. Percepfrorrs. 2nd ed. MIT Press, Cambridge, Mass. 1979.Google Scholar
- 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.Google ScholarDigital Library
- 22 Schwartz. J.T. Ultracomputers. ACM Trans. Progran~. Lang. Sysf. 2, 4 (Oct. 1980). 484-521. Google ScholarDigital Library
- 23 Shaw. D.E. Tire NON-VON Supercomputer. Tech. Rep., Dept. of Computer Science, Columbia Univ. New York. Aug. 1982.Google Scholar
- 24 Steele, G.L. Jr. and Hillis. W.D. Connection machine Lisp: Finegrained parallel symbolic processing. In Proceedings of fhe 1986 ACM Cmfmwe on Lisp and Fmcfimal Programming (Cambridge, Mass. Aug. 4-6). ACM, New York. 1986. pp. 279-297. Google ScholarDigital Library
- 25 Turner. D.A. A new implementation technique for applicative languages. Soffw. Pracf. &per. 9 (1979). 31-49.Google Scholar
Index Terms
- Data parallel algorithms
Recommendations
Communicating Data-Parallel Tasks: An MPI Library for HPF
HIPC '96: Proceedings of the Third International Conference on High-Performance Computing (HiPC '96)High Performance Fortran (HPF) has emerged as a standard dialect of Fortran for data-parallel computing. However, HPF does not support task parallelism or heterogeneous computing adequately. This paper presents a summary of our work on a library-based ...
Data-Parallel Programming on MIMD Computers
The implementation of two compilers for the data-parallel programming language Dataparallel C is described. One compiler generates code for Intel and nCUBE hypercube multicomputers; the other generates code for Sequent multiprocessors. A suite of ...
Pipelined Data Parallel Algorithms-I: Concept and Modeling
The basic concept of pipelined data-parallel algorithms is introduced by contrasting the algorithms with other styles of computation and by a simple example (a pipeline image distance transformation algorithm). Pipelined data-parallel algorithms are a ...
Reviews
Frans J. Peters
This expository paper presents a number of algorithms that have been implemented on the Connection Machine, a system consisting of tens of thousands of processors. The paper expresses the view that such fine-grained SIMD (Single Instruction stream, Multiple Data stream) systems are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. Programs are described in terms of virtual processors. The programming model allows each processor to communicate directly with any other processor, while other processors also communicate concurrently. To show the possibilities of data-parallel programming, several interesting algorithms are presented. The authors remark that most of the algorithms are not new. Beginning with some very simple examples to familiarize the reader with the model and the notation, the paper then proceeds to more elaborate and less obvious examples. The algorithms described all use O( N) processors to solve problems of size N, typically in O(log N) time. In some cases, the actual run-times measured on a 65,635 processor system are given. Algorithms presented include: sum of an array of numbers, all partial sums of an array (“sum-prefix” operation), counting and enumerating active processors, radix sort, parsing a regular language, parallel combinator reduction, finding the end of a linked list, all partial sums of a linked list, and region labeling. This lucidly written paper can be recommended to everyone with an interest in parallel programming and parallel algorithms.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments