DATA PARALLEL ALGORITHMS

DATA PARALLEL ALGORITHMS

December 1986 Volume 29 Number 12 | W. DANIEL HILLIS and GUY L. STEELE, JR.
The article discusses data parallel algorithms for fine-grained parallel computers with general communications, focusing on the Connection Machine system. Data parallel algorithms are characterized by operations across large sets of data rather than multiple control threads. The authors present several algorithms that solve problems of size \( N \) using \( O(N) \) processors in \( O(\log N) \) time, including string parsing and linked list traversal. The Connection Machine system is described, emphasizing its unique features such as general-purpose communication and virtual processors. Key operations like summation, partial sums, counting, enumeration, and sorting are detailed, along with examples of parallel programming techniques. The article also explores applications like region labeling in images and recursive data parallelism, highlighting the broad applicability of data parallel algorithms. The authors conclude by reflecting on the transition from serial to parallel thinking and the potential for future research in this area.The article discusses data parallel algorithms for fine-grained parallel computers with general communications, focusing on the Connection Machine system. Data parallel algorithms are characterized by operations across large sets of data rather than multiple control threads. The authors present several algorithms that solve problems of size \( N \) using \( O(N) \) processors in \( O(\log N) \) time, including string parsing and linked list traversal. The Connection Machine system is described, emphasizing its unique features such as general-purpose communication and virtual processors. Key operations like summation, partial sums, counting, enumeration, and sorting are detailed, along with examples of parallel programming techniques. The article also explores applications like region labeling in images and recursive data parallelism, highlighting the broad applicability of data parallel algorithms. The authors conclude by reflecting on the transition from serial to parallel thinking and the potential for future research in this area.
Reach us at info@study.space