A comparison of sorting algorithms for the connection machine CM-2

摘要: Sorting is arguably the most studied problem in computer science, both because it used as a substep many applications and simple, combinatorial with interesting diverse solutions. also an important benchmark for parallel supercomputers. It requires significant communication bandwidth among processors, unlike other supercomputer benchmarks, efficient sorting algorithms communicate data irregular patterns. Parallel have been since at least 1960’s. An early advance came 1968 when Batcher discovered elegant U(lg2 n)-depth bitonic network [3]. For certain families of fixed interconnection networks, such hypercube shuffle-exchange, Batcher’s technique provides algorithm n numbers n) time processors. The question existence o(lg2 remained open until 1983, Ajtai, Komlos, Szemeredi [1] provided optimal U(lg network, but unfortunately, their construction leads to larger networks than those given by sort all “practical” values n. Leighton [15] has shown that any family can be bounded-degree domain. Not surprisingly, n)-time implied AKS are impractical. In Reif Valiant proposed more practical O(lg randomized [19], called flashsort. Many literature, including versions radix quicksort [5], variant hyperquicksort [23], smoothsort [18], column [15], Nassimi Sahni’s [17], merge [6]. This paper reports findings project undertaken Thinking Machines Corporation develop fast Connection Machine Supercomputer model CM-2. primary goals this were: