2.2 (20 points) Let D be the maximum degree of concurrency in a task dependency
ID: 669807 • Letter: 2
Question
2.2 (20 points) Let D be the maximum degree of concurrency in a task dependency graph with T tasks and a critical path length L. Prove that (T/L) <= D <= T- L + 1
2.3 (20 points) There are seven tasks, the running times of which are 1, 2, 3, 4, 5, 5, and 10 minutes. We assume that the time to assign work to a process is zero. Please compute the best-case speedup and the worst-case speedup for a centralized scheme for dynamic mapping with two processes.
2.4 (40 points) Let us consider a bucket-sort algorithm. The input of the bucket-sort algorithm is an array A of n random integers in the rang [1..r]. The output of the algorithm consist of r buckets, such that bucket I contains indices of all the elements in A that are equal to i. 2.4.1 (20 points) Describe a decomposition based on partitioning input data and an appropriate mapping onto p processes. Please describe how your parallel algorithm works. 2.4.2 (20 points) describe a decomposition based on partitioning output data and appropriate mapping onto p processes. Describe how your parallel algorithm works.
2.4.2 (20 points) describe a decomposition based on partitioning output data and appropriate mapping onto p processes. Describe how your parallel algorithm works.
Explanation / Answer
2.4.1
Divide the array A equally into p processors, such that each processor has n/p values.
Perform any sorting algorithm within each bucket on each processor.
2.4.2
To partitioning the output data, we can still divide the bucket equally into p processors With each one has r/p buckets.
The input data should be correspondingly (for each bucket) divided into each processor. Use All-to-one Reduction to get the final result.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.