Array-Sorting Application
The distributed array-sorting application uses the quicksort algorithm to sort an array of arbitrary length. The considered array-sorting application can have different degrees of parallelism by unfolding the sorting kernel. In fact, the actual process network is composed of a top-level process network and a structural description of the sorting process that might be replaced by another process network.
More detailed, process "src" ("dest") generates (displays) the input (output) array, and process "sort" sorts the elements in ascending order. As the quicksort algorithm recursively sorts the array, process "sort" can be replaced by a structural description. "div" first partitions the array into two groups: the first group contains the elements that are smaller than the median value and the second group contains the remaining elements. The divided arrays are individually sent to a different instance of the "sort" process. Finally, the individually sorted sub-arrays are merged into a single array. Thus, by recursively unfolding the "sort" process, the original topology can be transformed to have more tasks. As the length of the array that each "sort" process has to sort is halved in each recursion step, the execution time is reduced with each recursion step, as well.
