0
$\begingroup$

i'm studying Parallel Processing ,

and i'm confused how can i calculate the max number of concurrency in a given dependency graph ?

i know that the maximum number of concurrency is the largest number of concurrent tasks at any point of the execution , but i can't calculate it from the graph

can someone explain how can i find the solution from the following graph ?

enter image description here

thank you ALL

$\endgroup$
1
$\begingroup$

Graph a:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is the sum of the weights of those four nodes: 10+10+10+10 = 40.

Phase 2: Task 6 and Task 5 can be executed parallelly (if you have more than 1 processor). So the degree of concurrency in this phase is: 9+6 = 15.

Phase 3: You can execute only Task 7, so the degree of concurrency here is 8.

The maximum number of concurrency is max(40, 15, 8) = 40. The average degree of concurrency is (40+15+8)/(10+9+8) = 63/27.

Graph b:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is: 10+10+10+10 = 40.

Phase 2: You can execute only Task 5, so the degree of concurrency here is 6.

Phase 3: You can execute only Task 6, so the degree of concurrency here is 11.

Phase 4: You can execute only Task 7, so the degree of concurrency here is 7.

The maximum number of concurrency is max(40, 6, 11, 7) = 40. The average degree of concurrency is (40+6+11+7)/(10+6+11+7) = 64/34.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.