3. (9 points) In computations over multiple processors, the load of a processor
ID: 3586832 • Letter: 3
Question
3. (9 points) In computations over multiple processors, the load of a processor is the sum of the times of all loads assigned to that processor. To balance the computation, the goal is to minimize the maximum load across the processors. For example, if the loads of three processors are 3, 10, 2 then the maximum load is 10. This assignment is less balanced (not as good) as one where the loads are 5,5,5 even though both assignments handle the same total load (15). For this question, assume that the processors are labelled P, P2, Ps. The input to the load balancing problem is a list of jobs, each labelled by the time it would take to complete that job. The output of the problem is an assignment of a processor to each job The greedy algorithm for load balancing goes through the list of jobs in the order given and assigns each job to the processor with smallest current load (if two processors have the same load, the algorithm chooses the one with smaller index; at the start of the algorithm, all processors have zero load) (a) If the list of jobs is J1 = 4,32 = 6,33 = 7= 8, Js = 5,36 = 2, what jobs are assigned to each processor by the greedy algorithm? P1: P2: (b) Is the greedy algorithm correct for this problem? Explain your answerExplanation / Answer
a. ) According to the given Greedy algorithm, final load that will be assigned to each processor is calculated as below:
Job
Time required
P1
P2
P3
J1
4
4
0
0
J2
6
4
6
0
J3
7
4
6
7
J4
8
4+8=12
6
7
J5
5
12
6+5=11
7
J6
2
12
11
7+2=9
Final
12
11
9
b.) Greedy algorithm is fine but not optimal for this problem because it doesn’t give optimal result.
Optimal case should be:
P1
P2
P3
11
11
10
This can be achieved by Greedy algorithm if we arrange the jobs in the decreasing order first and then apply the algorithm.
Job
Time required
P1
P2
P3
J4
8
8
0
0
J3
7
8
7
0
J2
6
8
7
6
J5
5
8
7
6+5=11
J1
4
8
7+4=11
11
J6
2
8+2=10
11
11
Final
10
11
11
Job
Time required
P1
P2
P3
J1
4
4
0
0
J2
6
4
6
0
J3
7
4
6
7
J4
8
4+8=12
6
7
J5
5
12
6+5=11
7
J6
2
12
11
7+2=9
Final
12
11
9
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.