Given below is the task dependency graph, from starting node S to ending node T. Each edge corresponds to a dependency. Each node (except nodes S and T) has its corresponding task id from t1 to t9 along with their computation unit times given inside nodes (circles). S and T have no additional cost. For instance, t4 needs 5 units computation time to complete its task. Delay from initial task S to t1, t2, and t3 are given as 0, 6, and 0 respectively. For instance, t2 starts its competition after 4 units time delay. Answer next 6 questions based on this graph.

1) What is critical path? Show it as a set of nodes in order such as S, t1, t5,

2) What is the best possible parallel computation time?

3) What is the parallel computation time for 2 processors?

4) What is maximum concurrency?

5) Indicate in which tasks we need a synchronization!

6) Assume that following sparse matrix and vector multiplication is given. What is the number of processor(s) needed for the finest granularity? In the figure dots refer to zeros in those elements.