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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.