# how can i find the Maximum Degree of Concurrency?

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 ?

thank you ALL

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.

• The maximum degree of concurrency wont be the sum of the weighted nodes but rather the number of leaf nodes itself Commented Aug 21, 2020 at 10:33