Sorting data
When we think of sorting, the first image that comes to mind might be the orderly rearrangement of numbers into a sequence, from smallest to largest or vice versa. But in parallel programming, sorting turns out to be much more than simply lining things up. It is a problem that involves coordination, patience, and a hefty dose of synchronization. Sorting in parallel is not simply hard — it is a challenging puzzle, where each piece needs to know what the others are doing. In this exploration, we are going to dive into a parallel sorting method called odd-even sort and see what it tells us about the unique challenges of synchronization in parallel computation.
Odd-even sort gives us an elegant yet tricky solution to sorting with multiple processors. The basic idea is that rather than having each processor work on the entire array, we set processors up to work in pairs, comparing and swapping numbers in adjacent positions. In one round we compare the elements at...
