Homework answers / question archive / Chalmers GOTEBORGS UNIVERSITET Concurrent Programming TDA384/DIT391 Material permitted during the exam (hjalpmedel): As the exam is run remotely we cannot realy restrict your usage of material

Chalmers GOTEBORGS UNIVERSITET Concurrent Programming TDA384/DIT391 Material permitted during the exam (hjalpmedel): As the exam is run remotely we cannot realy restrict your usage of material

Computer Science

Share With

---

Chalmers GOTEBORGS UNIVERSITET

Concurrent Programming TDA384/DIT391

Material permitted during the exam (hjalpmedel):

As the exam is run remotely we cannot realy restrict your usage of material.

Grading: You can score a maximum of 70 points. Exam grades are:

Points in exam	Grade Chalmers	Grade GU
28-41	3	G
42-55	4	G
56-70	5	VG

 

Passing the course requires passing the exam and passing the labs. The overall grade for the course is determined as follows:

Points in exam + labs	Grade Chalmers	Grade GU
40-59	3	G
60-79	4	G
80-100	5	VG

 

The exam results will be available in Ladok within 15 working days after the exam’s date.

Instructions and rules:

• You should be monitored on the dedicated zoom channel while taking the exam!
• Submit the exam solution as a PDF file on Canvas. The solution should be typeset using your favourite software. No scanned hand-written notes or diagrams are allowed.
• Please write your answers clearly and legibly: unnecessarily complicated solutions will lose points, and answers that cannot be read will not receive any points!
• Justify your answers, and clearly state any assumptions that your solutions may depend on for correctness.
• Answer each question on a new page. Glance through the whole paper first; five questions, numbered Q1 through Q5. Do not spend more time on any question or part than justified by the points it carries.
• Be precise. In your answers, try to use the programming notation and syntax used in the questions. You can also use pseudo-code, provided the meaning is precise and clear. If need be, explain your notation.
• A Word template and a Latex template are available on Canvas so you can use them to deliver your answer.

Q2) We have seen the following parallel implementation of merge sort (lecture 09, combination of slides 21, 22, and 25):

1 public class PMergeSort extends RecursiveAction {

2 private Integer[] data;

3 private int low, high;

4

5 @override

6 protected void compute() {

7 if (high - low <= 1) {

8 sort(data,low,high); // sort sequentially small chunks of 1024

9 return; // or less

10 }

11 int mid = low + (high - low)/2; // mid point

12 // left and right halves

13 PMergeSort left = new PMergeSort (data, lLow,mid) ;

14 PMergeSort right = new PMergeSort(data,mid,high) ;

15 left.fork(); // fork thread working on left

16 right.fork(); // fork thread working on the right

17 left.join(); // wait for sorted left half

18 right.join(); // wait for sorted right half

19 merge(mid); // merge halves

20 =}

21 }

The following appears somewhere in the main:

1 RecursiveAction sorter = new PMergeSort(numbers,0,numbers. length) ;

2 ForkJoinPool. commonPool().invoke(sorter) ;

Based on the dependency graph (or otherwise) for a run of invoke(sorter) when the array numbers has 8 elements, answer the following.

(Part a). How many threads participate in the computation? (4p)

(Part b). What is the maximum number of tasks that can be executed in parallel in this implementation on the same data (excluding parent tasks waiting for a child task to finish)? (4p)

You apply the second optimization in slide 25. That is, you change line 16 to right.compute(); and comment out line 18.

(Part c). How many threads participate now in the computation? (4p)

(Part d). What is the maximum number of tasks that can be executed in parallel? (3p)

(Part e).

You now get an array with 9000 elements. Change the program according to the first advice in slide 25 so that the number of threads that participate in the computation does not change to all the previous answers. (4p)