Analysis of Algorithms : An Active Learning Approach

210 PARALLEL ALGORITHMS

nodev, and distance(vi,vj), which gives the shortest distance between
nodesvi and vj. Formally, this algorithm for the CREW PRAM model is
v 0 is labeled as the first tree node
Parallel Start
for j = 1 to p do
for each node in Vj do
set closest to v 0
end for each
end for j
Parallel End

for j = 1 to N-1 do
Parallel Start
for k = 1 to p do
Pk finds the smallest distance among its nodes
Pk reports distance(v, closest(v)), v, and closest(v)
(where v ∈ Vk)
end for k
Parallel End
Pcontrol finds the smallest reported distance and adds the
node vsand its edge to the MST
Pcontrol broadcasts the new MST node to P 1 through Pp
Parallel Start
for k = 1 to p do
if vs∈ Vk then
Pk marks it as now in the tree
end if
Pk updates closest and distance based on vs being in
the tree for each of its nodes that are not yet in the tree
end for k
Parallel End
end for j

Analysis

The first loop is the initialization loop, and it will execute in N / p time, because

each processor has to initialize the data for the number of nodes that are its

responsibility. The first parallel block in the main for loop will do N / p
 1

comparisons each time, because sequentially finding the minimum or maximum

was shown in Chapter 1 to take this many comparisons. The next step is to find

the minimum distance of those reported by the p processors, which will take

anotherp
 1 comparisons. The broadcast step in a CREW model was shown to