Database Reference
In-Depth Information
1/3 of Array A
1/3 of Array A
1/3 of Array A
…
Dispatch array A evenly across
the three nodes
do i=0, 49
local_sum = local_sum +A[i];
end do
if (id == 0) {
recv_msg (Node2,
&local_sum2);
sum = local_sum + local_sum2;
recv_msg (Node3,
&local_sum3);
sum = local_sum + local_sum3;
Print sum;
}
else
send_msg (Node1, local_sum);
…
…
…
…
do i=0, 49
local_sum = local_sum +A[i];
end do
if (id == 0) {
recv_msg (Node2,
&local_sum2);
sum = local_sum + local_sum2;
recv_msg (Node3,
&local_sum3);
sum = local_sum + local_sum3;
Print sum;
}
else
send_msg (Node1, local_sum);
…
…
…
…
do i=0, 49
local_sum = local_sum +A[i];
end do
if (id == 0) {
recv_msg (Node2,
&local_sum2);
sum = local_sum + local_sum2;
recv_msg (Node3,
&local_sum3);
sum = local_sum + local_sum3;
Print sum;
}
else
send_msg (Node1, local_sum);
…
…
Node 1
(or
master)
Node 2
Node 3
FIGURE 1.10
An MPMD distributed program using the message-passing programming
model.
parallelism and graph parallelism. Graph parallelism is widely used in many domains
such as machine learning, data mining, physics, and electronic circuit designs, among
others. Many problems in these domains can be modeled as
graphs
in which
verti-
ces
represent computations and edges encode data dependencies or communications.
Recall that a graph
G
is a pair (
V
,
E
), where
V
is a finite set of vertices and
E
is a finite
set of pairwise relationships,
E
⊂
V
×
V
, called edges. Weights can be associated with
vertices and edges to indicate the amount of work per each vertex and the communica-
tion data per each edge. To exemplify, let us consider a classical problem from circuit
design. It is often the case in circuit design that pins of several components are to be
kept electronically equivalent by wiring them together. If we assume
n
pins, then an
arrangement of
n
−
1
wires, each connecting two pins, can be employed. Of all such
arrangements, the one that uses the minimum number of wires is normally the most
desirable. Obviously, this wiring problem can be modeled as a graph problem. In par-
ticular, each pin can be represented as a vertex, and each interconnection between a
pair of pins (
u
,
v
) can be represented as an edge. A weight
w
(
u
,
v
) can be set between
u
and
v
to encode the cost (i.e., the amount of wires needed) to connect
u
and
v
. The
problem becomes, how to find an acyclic subset,
S
, of edges,
E
, that connects all the
vertices,
V
, and whose total weight
uv
∈
∑
is the
minimum
. As
S
is acyclic
and fully connected, it must result in a tree known as the
minimum spanning tree
.
Consequently, solving the wiring problem morphs into simply solving the minimum
spanning tree problem. The minimum spanning tree problem is a classical problem
and can be solved using Kruskal's or Prim's algorithms, to mention a few [15].
wuv
(,)
(,)
Search WWH ::
Custom Search