Efficient communication in massively parallel computers
Robert Cypher, Lawrence Snyder · 1989
A fundamental operation in parallel computation is sorting. Sorting is important not only because it is required by many algorithms, but also because it can be used to implement irregular, pointer-based communication. We study two algorithms for sorting in massively parallel computers. First, we examine Shellsort. Shellsort is a sorting algorithm that is based on a sequence of parameters called increments. Shellsort can be used to create a parallel sorting device known as a sorting network. Researchers have suggested that if the correct increment sequence is used, an optimal size sorting network can be obtained. All published increment sequences have been monotonically decreasing. We show that no monotonically decreasing increment sequence will yield an optimal size sorting network. Second, we present a sorting algorithm called Cubesort. Cubesort is the fastest known sorting algorithm for a variety of parallel computers over a wide range of parameters. We also present a paradigm for developing parallel algorithms that have efficient communication. The paradigm, called the data reduction paradigm, consists of using a divide-and-conquer strategy. Both the division and combination phases of the divide-and-conquer algorithm may require irregular, pointer-based communication between processors. However, the problem is divided so as to limit the amount of data that must be communicated. As a result the communication can be performed efficiently. We present data reduction algorithms for the image component labeling problem, the closest pair problem and four versions of the parallel prefix problem.