Suppose you have a sequence of jobs, indexed from 1 to N, that you want to...

   

Transcribed Image Text:

Suppose you have a sequence of jobs, indexed from 1 to N, that you want to run on two processors. For each index i, running job i on processor 1 requires A[i] time, and running job i on processor 2 takes B[i] time. If two jobs i and j are assigned to different processors, there is an additional communication overhead of C[i, j]=Cj,i]. Thus, if we assign the jobs in some subset SC {1, 2,..., N} to processor 1, and we assign the remaining N-[S] jobs to processor 2, then the total execution time is iES A++ C[i, j]. jes iS,jes Describe an algorithm to assign jobs to processors so that this total execution time is as small as possible. The input to your algorithm consists of the arrays A[1... N], B[ldots N], and C[1... N, 1... N]. You should briefly justify the correctness of your design and state and analyse its runtime. Hint: Build a graph inspired by the matching example from class and using the inputs A, B, C;] as capacities (your graph does not need to be bipartite!). If the subset S of jobs is assigned to processor 1, what relevant object in your graph captures the execution time? Suppose you have a sequence of jobs, indexed from 1 to N, that you want to run on two processors. For each index i, running job i on processor 1 requires A[i] time, and running job i on processor 2 takes B[i] time. If two jobs i and j are assigned to different processors, there is an additional communication overhead of C[i, j]=Cj,i]. Thus, if we assign the jobs in some subset SC {1, 2,..., N} to processor 1, and we assign the remaining N-[S] jobs to processor 2, then the total execution time is iES A++ C[i, j]. jes iS,jes Describe an algorithm to assign jobs to processors so that this total execution time is as small as possible. The input to your algorithm consists of the arrays A[1... N], B[ldots N], and C[1... N, 1... N]. You should briefly justify the correctness of your design and state and analyse its runtime. Hint: Build a graph inspired by the matching example from class and using the inputs A, B, C;] as capacities (your graph does not need to be bipartite!). If the subset S of jobs is assigned to processor 1, what relevant object in your graph captures the execution time?