Take the 2-minute tour ×

I am stuck with one of the algorithm homework problem. Can anyone give me some hint to solve it? Here is the question:

Consider a chain structured computation represented by a weighted graph G = (V;E) where V = {v1; v2; ... ; vn} and E = {(vi; vi+1) such that 1<= i <= n-1. We are also given a chain-structure m identical processors P = {P1; ... ; Pm} (i.e., there exists a communication link between Pk and Pk+1 for 1 <= k <= m - 1).

The set of vertices V represents computation modules, and the set of edges E represents communication between the two modules. Each node vi is assigned a weight wi denoting the execution time of the module on a single processor. Each edge (vi; vi+1) is assigned a weight ci denoting the amount of communication time between the two modules if they are assigned two different processors. If multiple modules are assigned to the same processor, the modules assigned to the same processor must be consecutive. Suppose modules va; va+1; .. ; vb are assigned to Processor Pk. Then, the time taken by Pk, denoted by Tk, is the time to compute assigned modules plus the time to communicate between neighboring processors. Hence, Tk = wa+...+ wb + ca-1 + cb. Note here that ca-1 = 0 if a = 1 and cb = 0 if b = n.

The objective of the problem is to find an assignment V to P such that max1<=k<=m Tk is minimized, where we assume that each processor must take at least one module. (This assumption can be relaxed by adding m dummy modules with zero weight on computational and communication time.) Develop a dynamic programming algorithm to solve this problem in polynomial time(i.e O(mn))

I tried to find the minimum execution time for each Pk and then find the max, but I doubt my solution is dynamic programming since there is no recursive formula. Please give me some hints! Thanks!

share|improve this question
Please format your text better that giant paragraph is almost unreadable in its current state. –  GWW Nov 14 '10 at 4:25
Could you explain in more detail what you have tried? I'm not grasping from your description. –  Winston Ewert Nov 14 '10 at 4:43
For each processor, I find all the possible execution times, then find the min. After find all the mins of all processor I take the max one –  user451587 Nov 14 '10 at 4:52
Hmmm six questions and only one accepted answer ... –  belisarius Nov 14 '10 at 5:38
@user451587, how do you make sure that you follow the requirement: If multiple modules are assigned to the same processor, the modules assigned to the same processor must be consecutive. –  Winston Ewert Nov 14 '10 at 14:08

2 Answers 2

up vote 0 down vote accepted

okay. this is easy. decompose your problem to be a function you need to minimise, say F(n,k). which results into the minimum assignment of the first n nodes to k first processors. Then derive your formula like this, collecting the number of nodes on the kth processor.

F(n,k) = min[i=0..n]( max(F(i,k-1), w[i]+...+w[n]+c[i-1]+c[n]) )
c[0] = 0
F(*,0) = inf
F(0,*) = inf
share|improve this answer
Thanks! it helps me a lot! –  user451587 Nov 14 '10 at 22:26
but one thing, I think u didn't consider the condition each processor must have at least 1 module –  user451587 Nov 14 '10 at 23:24
oh yes, then you need to say min[i=0..n-1], but the idea is the same. –  guruslan Nov 15 '10 at 8:13

I think you might be able to modify the Viterbi algorithm to solve this problem.

share|improve this answer
is it dynamic programming? I will check it out –  user451587 Nov 14 '10 at 5:25
Yes, it's a dynamic programming algorithm used in hidden Markov models to find the path with the greatest probability. –  Colin Nov 14 '10 at 5:29

Your Answer


