Design and Analysis of Algorithms

Assignment 5 CSCI 3110: Design and Analysis of Algorithms

Due June 16, 2014

Banner ID: Name:

Banner ID: Name:

Banner ID: Name:

Assignments are due on the due date before class and have to include this cover page. Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the authors named above declare that its content is their original work and that they did not use any sources for its preparation other than the class notes, the textbook, and ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported to the Faculty’s Academic Integrity Officer and possibly to the Senate Discipline Committee. The penalty for academic dishonesty may range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulations regarding academic integrity.

This assignment studies a problem with applications in parallel scheduling. You are given a set of jobs J1, J2, . . . , Jn you want to run on your super powerful parallel computer with k processors P1, P2, . . . , Pk. For each job Ji , you are given a prediction ti of the amount of time it takes to run this job on a single processor. A job cannot be split, that is, once assigned to a given processor it needs to be run to completion by this processor. Let S j be the set of jobs you choose to run on processor Pj . Then processor Pj finishes its work in Tj =

∑

Ji∈S j ti time. A schedule is a partition of the set

S = {J1, J2, . . . , Jn} into subsets S1, S2, . . . , Sk of jobs assigned to processors P1, P2, . . . , Pk (that is, ⋃k

j=1 S j = S and, for all j 6= j′, S j ∩ S j′ = ;). The makespan of this schedule is max{T1, T2, . . . , Tk}, that is, the time at which the last processor finishes its assigned work. In order to best utilize the computing power of your parallel computer, you try to find a schedule that minimizes the makespan. This problem turns out to be NP-hard to solve, even with only two processors. For such problems, we need to look for approximate solutions or for special types of inputs for which the problem can be solved exactly in polynomial time. This is the goal of this assignment.

Question 1 (10 marks) Describe a simple greedy algorithm that computes a 2-approximation of the optimal schedule. In other words, if T∗ is the smallest possible makespan achievable for the given set of jobs using k processors, then the schedule produced by your algorithm should have a makespan of at most 2T∗. Your algorithm should run in O(kn) time. Prove that the schedule produced by your algorithm has makespan at most 2T∗. To do so, you will probably want to use two properties the minimum makespan T∗ must obviously satisfy:

• T∗ ≥ 1 k

∑k i=1 ti . (The processor doing the most amount of work must do at least a 1/k fraction of the total amount

of work.)

• T∗ ≥ max{t1, t2, . . . , tn}. (The longest job needs to run on some processor Pj , so this processor finishes no earlier than the time it takes to complete this job.)

You should then prove that the schedule produced by your algorithm has makespan at most 1 k

∑k i=1 ti+max{t1, t2, . . . , tn}.

Question 2 (10 marks) Describe a modification of the above greedy algorithm that computes an optimal schedule, that is, one with the smallest possible makespan, provided the given set of jobs satisfies the following condition: Let t1, t2, . . . , tn once again be the predicted amounts of time it takes to run jobs J1, J2, . . . , Jn, and let t

∗ = min{t1, t2, . . . , tn}. You may assume that t∗ = 1. Then, for all 1 ≤ i ≤ n, ti is a power of 2. Your algorithm should run in O(n lg n + kn) time. Prove that it produces an optimal schedule.

1