Information Technology Reference
In-Depth Information
The MultiBSP Model describes a model instance as a tree structure of nested
components, where the leaves are processors and each internal node is a BSP
computer with local memory or some storage capacity.
Formally, a MultiBSP machine is specified by a list of tuples (levels) where
each tuple has four parameters (
m
i
,p
i
,g
i
,L
i
)where:
-
p
i
is the number of
i
-1
th
level components inside an
i
th
component. For
i
=1,these1
st
level components consist of
p
1
raw processors, which can be
regarded as 0
th
level components. One computation step of such a processor
on a word in level 1 memory is taken as one basic unit of time.
-
g
i
is the communication cost parameter, it is defined as the ratio of the
number of operations that a processor can perform in a second and the
number of words that can be transmitted in a second between the memories
of a component at level
i
and its parent component at level
i
+1.A
word
here is the amount of data on which a processor operation is performed. We
assume that the level
1
memories can keep up with the processors, and hence
that the data rate (corresponding to the notation
g
0
) has the value one.
-
L
i
is the cost for the barrier synchronization for a level
i
superstep. The
definition requires barrier synchronization of the subcomponents of a com-
ponent, but no synchronization across above branches in the component
hierarchy.
-
m
i
is the number of words of memory inside an
i
th
level component that is
not inside any
i
1
th
level component.
−
Fig. 1.
Schematic view of the
i
th
component level of MultiBSP model
Fig. 1 shows a component of level
i
. A level
i
superstep is a construct running
at a level
i
component that allows each of its
p
i
level
i
−
1componentsto
execute independently (including supersteps of level
i
1). Once all
p
i
finish
their computation, they can all exchange information with the
m
i
memory of
the level
i
component with a communication cost determined by
g
i−
1
.Thecost
charged will be
mg
i−
1
,where
m
is the maximum number of words communicated
between the memory of the
i
th
level component and any one of its level
i
−
1
subcomponents. After a barrier between the
p
i
components, the next superstep
may begin.
−
