Concurrency
Question 1 
Below is the precedence graph for a set of tasks to be executed on a parallel processing system S.
What is the efficiency of this precedence graph on S if each of the tasks T1, T2, T3,….T8 takes the same time and the system S has five processors?
What is the efficiency of this precedence graph on S if each of the tasks T1, T2, T3,….T8 takes the same time and the system S has five processors?
25%  
40%  
50%
 
90%

Question 1 Explanation:
From the precedence graph, we say that the following tasks executed sequentially
I. T1 ,T2
II. T3 and T6
III. T4 and T7
IV. T5 and T8
(T3,T6),(T4,T7) and (T5,T8) will execute parallely.
So total number of processes that can be executed in 4 units time using 5 available processors = 5*4 = 20
Maximum number of tasks are 8
Efficiency = 8/20 * 100 = 40%
I. T1 ,T2
II. T3 and T6
III. T4 and T7
IV. T5 and T8
(T3,T6),(T4,T7) and (T5,T8) will execute parallely.
So total number of processes that can be executed in 4 units time using 5 available processors = 5*4 = 20
Maximum number of tasks are 8
Efficiency = 8/20 * 100 = 40%
Question 2 
A particular parallel program computation requires 100 seconds when executed on a single CPU. If 20% of this computation is strictly sequential, then theoretically the best possible elapsed times for this program running on 2 CPUs and 4 CPUs respectively are
55 and 45 seconds  
80 and 20 seconds  
75 and 25 seconds  
60 and 40 seconds 
Question 2 Explanation:
→From the given data, one CPU will require 100 seconds to complete given task.
→20% of computation is done by sequential which means 20% of 100 seconds (20 seconds)
→Remaining computation 80% of work(80 seconds) can be done by the parallel processing.
→2 Processors: 20 % of sequential work is done by processor p1 (20 sec) and remaining 80 % of work (80 seconds) can be distributed among p1 and p2 equally(each process will get 40 sec). so time required = 20 + 40 = 60 seconds
→4 Processors: 20 % of work is done by any of the processor sequentially(20 seconds) and remaining 80 % of work (80 seconds) can be divided among 4 processors(each process will get 20 sec), so maximum time required = 20 + 20 = 40 seconds
→20% of computation is done by sequential which means 20% of 100 seconds (20 seconds)
→Remaining computation 80% of work(80 seconds) can be done by the parallel processing.
→2 Processors: 20 % of sequential work is done by processor p1 (20 sec) and remaining 80 % of work (80 seconds) can be distributed among p1 and p2 equally(each process will get 40 sec). so time required = 20 + 40 = 60 seconds
→4 Processors: 20 % of work is done by any of the processor sequentially(20 seconds) and remaining 80 % of work (80 seconds) can be divided among 4 processors(each process will get 20 sec), so maximum time required = 20 + 20 = 40 seconds
There are 2 questions to complete.