Scribd
Upload
27 views4 pages

Maximum Degree of Concurrency Analysis

The document is an assignment by Muhammad Danyal for the subject Parallel and Distributed Computing, detailing solutions to a task dependency graph. It covers concepts such as maximal degree of concurrency, critical path and length, average degree of concurrency, shortest parallel execution time, number of processors needed for minimum time, and speedup. Each concept is explained with formulas and definitions relevant to binary trees and task execution.

Uploaded by

daniyal qadri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views4 pages

Maximum Degree of Concurrency Analysis

The document is an assignment by Muhammad Danyal for the subject Parallel and Distributed Computing, detailing solutions to a task dependency graph. It covers concepts such as maximal degree of concurrency, critical path and length, average degree of concurrency, shortest parallel execution time, number of processors needed for minimum time, and speedup. Each concept is explained with formulas and definitions relevant to binary trees and task execution.

Uploaded by

daniyal qadri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment No 2

Name: Muhammad Danyal

Class: BSCS-6A

Arid-No: 22-Arid-3106

Subject: Parallel and Distributed Comp

Submitted To: Mam Sadia Zar

Question 01: Given is the following task


dependency graph, Answer the following
questions:

Solution : -

1. Maximal Degree of Concurrency

This is the maximum number of tasks that can be executed


in parallel at any level.
In a binary tree:

● Level 0 has 1 node (root)

● Level 1 has 2 nodes

● Level 2 has 4 nodes

●…

● Level k has 2^k nodes

So, at the last level before the leaves, the number of tasks
is maximal: 2^(h-1) (where h is the tree height)

Let’s assume height = h, then maximal concurrency =


2^(h-1)

2. Critical Path and Critical Length

● Critical Path: Longest path from root (1) to any leaf


(n)

● Since this is a binary tree with height h, the longest


path is from root to any leaf → Critical Path Length
=h

Each level = 1 unit of time → So,


● Critical Length = h

3. Average Degree of Concurrency

Formula:

Average Degree of Concurrency=Total Work (Number of


Tasks)Critical Length (Parallel Time)\text{Average
Degree of Concurrency} = \frac{\text{Total Work
(Number of Tasks)}}{\text{Critical Length (Parallel
Time)}}Average Degree of Concurrency=Critical Length
(Parallel Time)Total Work (Number of Tasks)

● Total nodes in a binary tree = 2^h - 1

● Critical length = h

Avg Concurrency=2h−1h\text{Avg Concurrency} =


\frac{2^h - 1}{h}Avg Concurrency=h2h−1

4. Shortest Parallel Execution Time

This is the time if we run the graph with infinite


processors, constrained only by dependencies.

That equals the Critical Length = h


5. Number of Processors Needed for Minimum Time

Minimum time is h. To achieve that, we must be able to run


all tasks in parallel where possible.

So, the maximum number of concurrent tasks at any


level = max nodes at any level = 2^(h-1)

So, processors needed = 2^(h-1)

6. Speedup
Speedup=Serial Execution TimeParallel Execution

Time\text{Speedup} = \frac{\text{Serial Execution

Time}}{\text{Parallel Execution Time}}Speedup=Parallel


Execution TimeSerial Execution Time

● Serial Execution Time = total tasks = 2^h - 1

● Parallel Execution Time = h

Speedup=2h−1h\text{Speedup} = \frac{2^h -
1}{h}Speedup=h2h−1

You might also like