Illustrate the parallel algorithm for sorting numbers in ascending order with an example and analyze the performance of this algorithm in terms of parallel run time and communication cost.

Welcome back.

and 3 others joined a min ago.

1.6kviews

written 6.0 years ago by

teamques10 ★ 69k

• modified 5.7 years ago

Mumbai University > Computer Engineering > Sem 8 > Parallel & Distributed System

distributed systems

ADD COMMENT EDIT

1 Answer

12views

written 5.7 years ago by

teamques10 ★ 69k

modified 5.7 years ago by

ankitpandey • 100

The Even - Odd bubble sort can perform sorting of n numbers with n/2 processing elements.

In 1st parts if swaps all odd numbers with mat and 2nd parts it swaps all even numbers with next.

Example :

enter image description here

This way n numbers can be saved in n passes.

without parallelism, bubble sort takes $0 (n^2)$

with even-odd parallelism, bubble sort takes time $0(n)$ but with n/2 processing elements.

Serial Run : $0(n^2)$

Parallel Run : $0(n)$

communication cost in parallel run is 1 element communicated by end processing element in each pass ad hence I/O communication cost is O(n)

ADD COMMENT EDIT

Community

Content

Company