DATA PARALLEL ALGORITHMS

DATA PARALLEL ALGORITHMS

December 1986 | W. DANIEL HILLIS and GUY L. STEELE, JR.
Data parallel algorithms are suitable for fine-grained parallel computers with general communications. These algorithms use O(N) processors to solve problems of size N in O(log N) time. They are not new but demonstrate a programming style appropriate for machines with tens of thousands or millions of processors. The algorithms are designed for parallelism across large data sets rather than multiple threads of control. The Connection Machine system, with 16,384 or 65,536 processors, is an example of such a machine. It has a front-end computer and an array of processors, with the array acting as a memory. The processors can perform logical, integer, and floating-point operations, and data can be broadcast from the front end to all processors. The system supports virtual processors, allowing programs to run on different sizes of the machine. The model abstracts hardware details, enabling efficient programming. Examples of data-parallel algorithms include computing the sum of an array, all partial sums of an array, radix sort, parsing a regular language, and finding the end of a linked list. These algorithms demonstrate how data parallelism can be applied to problems that initially seem serial. The Connection Machine's general communication allows for efficient parallel processing, and the algorithms often use parallel-prefix computations. The model also supports pointer manipulation and combinator reduction, showing how data parallel algorithms can simulate control parallelism. Region labeling is another application, where linked-list operations are used to identify and label regions in a 2D image. Recursive data parallelism is used for matrix multiplication, and the algorithms can be applied to sparse matrices. The paper concludes that data parallel algorithms are applicable to a wide range of problems, especially when dealing with large data sets, and that the style of programming is distinct from hardware design issues like MIMD versus SIMD. The transition from serial to parallel thinking is ongoing, and some algorithms may appear outdated in the future.Data parallel algorithms are suitable for fine-grained parallel computers with general communications. These algorithms use O(N) processors to solve problems of size N in O(log N) time. They are not new but demonstrate a programming style appropriate for machines with tens of thousands or millions of processors. The algorithms are designed for parallelism across large data sets rather than multiple threads of control. The Connection Machine system, with 16,384 or 65,536 processors, is an example of such a machine. It has a front-end computer and an array of processors, with the array acting as a memory. The processors can perform logical, integer, and floating-point operations, and data can be broadcast from the front end to all processors. The system supports virtual processors, allowing programs to run on different sizes of the machine. The model abstracts hardware details, enabling efficient programming. Examples of data-parallel algorithms include computing the sum of an array, all partial sums of an array, radix sort, parsing a regular language, and finding the end of a linked list. These algorithms demonstrate how data parallelism can be applied to problems that initially seem serial. The Connection Machine's general communication allows for efficient parallel processing, and the algorithms often use parallel-prefix computations. The model also supports pointer manipulation and combinator reduction, showing how data parallel algorithms can simulate control parallelism. Region labeling is another application, where linked-list operations are used to identify and label regions in a 2D image. Recursive data parallelism is used for matrix multiplication, and the algorithms can be applied to sparse matrices. The paper concludes that data parallel algorithms are applicable to a wide range of problems, especially when dealing with large data sets, and that the style of programming is distinct from hardware design issues like MIMD versus SIMD. The transition from serial to parallel thinking is ongoing, and some algorithms may appear outdated in the future.
Reach us at info@study.space
Understanding Data parallel algorithms