Unit 2.
2 :- BSR (Broadcasting
with Selective Reduction)
Class 8
Unit 2.2 Parallel and Distributed Computing 1
BSR
• Broadcast instruction consists of three phases
1. Broadcast Phase
2. Selection Phase
3. Reduction Phase
• Broadcast Phase
– Allows all of the N processors to write
concurrently to all of the M memory locations
– Each processor Pi, 1iN, produced a record
containing two fields, a tag ti and a datum di, to be
stored
Unit 2.2 Parallel and Distributed Computing 2
BSR…………………………………………….
• Selection Phase
– After the data are received at each memory
locations Uj, 1jM, a switch Sj will select the
receiving data di by comparing tag value ti by
using a selection rule, [<, , =, >, , ]
• Reduction Phase
– Selected data are reduces to a single value using
𝑚𝑎𝑥 𝑚𝑖𝑛
reduction rule, R {, , , , , , }
∩ ∪
Unit 2.2 Parallel and Distributed Computing 3
BSR…………………………………………….
Unit 2.2 Parallel and Distributed Computing 4
BSR…………………………………………….
• A generalized BSR model
– Mathematically, it can be expressed as
𝑈𝑗 ← 𝑅𝑑𝑖 | t(i, h) h l(j, h)
1jM 1iN 1hk 1jM
– Where
• N no. of processors
• di datum broadcast by the processor Pi
• h selection operation, 1hk, where k is the number of criteria
• t(i, h) tag broadcast by processor i for criteria h
• l(i, h) limit value j for criteria h
• R reduction operation, R {, , , , , , }
• Ui memory location to be stored for the single reduced value
Unit 2.2 Parallel and Distributed Computing 5
BSR…………………………………………….
• Types
1. One criterion BSR algorithm
2. Two criterion BSR algorithm
3. Three criterion BSR algorithm
4. Multiple criterion BSR algorithm
Unit 2.2 Parallel and Distributed Computing 6
One Criterion BSR
• Each broadcast datum has to pass a single test
being allowed to participate in the reduction
process
• Example
– Sorting
– Parenthesis Matching
– Optimal Sum Subsegment
Unit 2.2 Parallel and Distributed Computing 7
One Criterion BSR……………………….
• Sorting
– Number of processors needed = N (number of
elements in array is N)
– Rank of element xj can be expressed as
rj = 1 | xi xj
– When all the elements in the array are distinct,
every datum xj in its position rj are in the sorted
array
Unit 2.2 Parallel and Distributed Computing 8
One Criterion BSR……………………….
• Sorting
– Illustration
A = {3, 2, 6, 5}
P1 P2 P3 P4
for 3 3 3, 2 3, rank = 2
for 2 2 2, rank =1
for 6 3 6, 2 6, 6 6, 5 6, rank = 4
for 5 3 5, 2 5, 5 5, rank = 3
Hence the sorted array is {2, 3, 5, 6}
Unit 2.2 Parallel and Distributed Computing 9
One Criterion BSR……………………….
• Sorting
– What happens if some of the elements are
duplicate
– A = {3, 4, 3}
Unit 2.2 Parallel and Distributed Computing 10
One Criterion BSR……………………….
• Sorting (in case of duplicate)
1 1
– Sj = 1 | ti lj where 𝑡𝑖 = 𝑟𝑖 − ,𝑙 = 𝑟𝑗 −
𝑖 𝑗 𝑗
– Illustration A = {3, 4, 3}
– Case of A[1] = 3
1 1
𝑡1 = 3− ≤ 𝑙1 = 3− → 𝑇𝑟𝑢𝑒
1 1
1 1 Rank =1
𝑡2 = 4− ≤ 𝑙1 = 3− → 𝐹𝑎𝑙𝑠𝑒
2 1
1 1
𝑡3 = 3− ≤ 𝑙1 = 3− → 𝐹𝑎𝑙𝑠𝑒
3 1
Unit 2.2 Parallel and Distributed Computing 11
One Criterion BSR……………………….
• Case of A[2] = 4
1 1
𝑡1 = 3 − ≤ 𝑙2 = 4 − → 𝑇𝑟𝑢𝑒
1 2
1 1
𝑡2 = 4 − ≤ 𝑙2 = 4 − → 𝑇𝑟𝑢𝑒 Rank = 3
2 2
1 1
𝑡3 = 3 − ≤ 𝑙2 = 4 − → 𝑇𝑟𝑢𝑒
3 2
• Case of A[3] = 3
1 1
𝑡1 = 3 − ≤ 𝑙3 = 3 − → 𝑇𝑟𝑢𝑒
1 3
1 1 Rank = 2
𝑡2 = 4 − ≤ 𝑙3 = 3 − → 𝐹𝑎𝑙𝑠𝑒
2 3
1 1
𝑡3 = 3 − ≤ 𝑙3 = 3 − → 𝑇𝑟𝑢𝑒
3 3
Unit 2.2 Parallel and Distributed Computing 12
Parenthesis Matching
• One criterion BSR algorithm
• The problem is to find the pairs of matching parenthesis in a given
legal sequences l1, l2, ……., ln of parenthesis
• By legal means that every parenthesis has its matching parenthesis
in a sequence
• Example
Output for the input sequence,
( ) ( ( ( ) ) ) ( ( ) ) is,
( ) ( ( ( ) ) ) ( ( ) )
1 2 3 4 5 6 7 8 9 10 11 12
• Can
2 be
1 8 7 6 5 4 3 12 11 10 9
• Can be solved by N processors
Unit 2.2 Parallel and Distributed Computing 13
Parenthesis Matching………………….
• Algorithm
– For each processor j do in parallel
– If lj == ‘(‘ then bj = 1 else bj = -1
– Pj = bj | i j
– If bj == -1 then Pj = Pj + 1
1
– 𝑃′𝑗 = 𝑃𝑗 −
𝑗
– qj = -1, tj = 0, rj = 0
– 𝑞𝑗 =∩ 𝑃′ 𝑖 |𝑃′ 𝑖 < 𝑃′𝑗
– 𝑡𝑗 =∩ 𝑖 | 𝑃′ 𝑖 = 𝑞𝑗
– 𝑟𝑗 =∪ 𝑖|𝑡𝑖 = 𝑗
– If lj = ‘)’ then mj = tj else mj = rj
Unit 2.2 Parallel and Distributed Computing 14
End of Session
Unit 2.2 Parallel and Distributed Computing 15
