Produce parallel task schedules for dependency graphs G1 G2S

Produce parallel task schedules for dependency graphs G1, G2.

Solution

Basically here you need to find parallel schedule for both of the graphs. We can assign the task in parallel mode only if there is no dependency in between them. Suppose you are modifying the file A and also it is use by file B to read it then you can\'t run the parallel in it because there is no data integrity. Suppose A contains text \"My name is Alex\" and file B wants to read the content of A. But suddenly C come and modify A content to \"My name is Ashley\" and if you try to run it in parallel there is high chance that B has read A old content means \"My name is Alex\".

So make a direct edge here first for first graph -

b->a

b->e

c->b

c->d

e->d

To solve this kind of problem. Take the task as vertex of the graph and dependency as edge. So it is directed graph but it should not have cycle because if it has cycle then it can\'t be execute in parallel. Like A is dependent on B and B is dependent on A.

So basically we need to find the ordering of the task. Which task can be executed first so that it does not cause any problem for other task. This can be solved by famous algorithm topological sorting. Basically it do the dfs and find the depth. First it execute all the dependent task then it execute the main task. So for above graph if we do dfs on that

start with a , it has no dependency so its depth is 0

then b, b has dependency on a and e as a is executed so its depth will be max(1, e\'s depth) + 1.

Now e has dependency with d so e\'s depth is equal to d\'s depth + 1.

Now d has no dependency so its depth is 0. It means we can execute a and d parallely.

Now e has depth 1(i.e. d + 1=1)

so b\'s depth will be max(a, e) + 1= max(0, 1) + 1 = 2

Now c, it has dependency on b and d so its depth will be max(b, d) + 1 = max(2,1) + 1 = 3

Now f, it has 0 dependency so depth of f will be 0

So we have depth of task

a = d = f = 0

e = 1

b = 2

c = 3

so task a, d, f can be run in parallel.

Now try for other graph if you get doubt in understanding or solving it ask me.