Parallel algorithms

Question 1

what is a the speedup factor

Answer 1

it is the measure in performance between a sequential program and a parallel one and defined such that :
S(n) = Ts/ Tp
Ts: is the execution time of the sequential version
Tp: is the execution time of the parallel version
considering that the maximum speedup factor that can be gained on n processors is simply n
if S(n) > n then the program can be simulated on a single processor

Question 2

what are the parallelizing costs

Answer 2

communication delay, instants when only a single process is being busy and the fact that parallel algorithm is harder to design

Question 3

explain the Amdhal law - Maximum Speed up-

Answer 3

f : fraction of the sequential part of the parallel program
in another word the speed up factor has an upper bound
limn→∞ S(n) = 1 /f
such that if we have fraction of 5% of sequential program then maximum of the speedup factor we can hop for is 20

Question 4

explain the Bitonic search

Answer 4

firstly we need to define a bitonic sequence :
a1 ≤ a2 ≤ ⋯ ≤ aj ≥ aj+1 ≥ aj+2 ≥ a2k
for sorting :
1-initiation of two bitonic sequences are produced
2- each bitonic sequence is started independently using Mrgek
3- the whole is concatenated

Merge-k is based on the process of compare and swap where it applies it on the pairs such till obtaining a single bitonic sequence, for example
we have a sequence of 2^3
MErge-k is such that
<5,10,9,4,11,2,6,12>
<5,10,9,4,2,11,12,6> — 2 bitonic seq. of length 4
<4,5,9,10,12,11,6,2> — 1 bitonic seq. of lenght 8