To be considered for a 12, solve the following task:
In parallel implementations of MergeSort, we can consider the “span of comparisons”, for short “span”:
What is the longest chain of comparisons, that were executed serially by an implementation?
In effect, this means that when there are several parallel calls to functions, the span is the maximum of the spans.
The span of a function is then the sum of whatever happened serially in that function,
where some of the terms might be maxima of parallel calls.
Implement variants of the algorithms that compute the span
(by returning the span of comparisons instead of the total number of comparisons).
Design and perform an experiment that discusses if the span is a good predictor of the parallel running time of the different implementations.
To be considered for a 12, solve the following task:
In parallel implementations of MergeSort, we can consider the “span of comparisons”, for short “span”: What is the longest chain of comparisons, that were executed serially by an implementation? In effect, this means that when there are several parallel calls to functions, the span is the maximum of the spans. The span of a function is then the sum of whatever happened serially in that function, where some of the terms might be maxima of parallel calls.
Implement variants of the algorithms that compute the span (by returning the span of comparisons instead of the total number of comparisons). Design and perform an experiment that discusses if the span is a good predictor of the parallel running time of the different implementations.