5.4.2
Algorithmically-coded architecture files
Almost all algorithmically-coded architectures are defined with unity edge and ver-
tex weights. They start with an abbreviation name of the architecture, followed by
parameters specific to the architecture. The available built-in architecture defini-
tions are listed below.
cmplt
size
Defines a complete graph with
size
vertices. The vertex labels are numbers
between 0 and
size
−
1.
cmpltw
size load
0
load
1
. . .
loadsize
−
1
Defines a weighted complete graph with
size
vertices. The vertex labels are
numbers between 0 and
size
−
1, and vertices are assigned integer weights in
the order in which these are provided.
hcub
dim
Defines a binary hypercube of dimension
dim
. Graph vertices are numbered
according to the value of the binary representation of their coordinates in the
hypercube.
tleaf
levlnbr sizeval
0
linkval
0
. . .
sizevallevlnbr
−
1
linkvallevlnbr
−
1
Defines a hierarchical, tree-shaped, architecture with
levlnbr
levels and
P
levlnbr
−
1
i
=0
sizeval
i
leaf vertices. This topology is used to model multi-stage,
NUMA ou NUIOA machines. The mapping is only computed with respect
to the leaf vertices, which represent processing elements, while the upper lev-
els of the tree model interconnection networks (intra-chip buses, inter-chip
interconnection networks, network routers, etc.), as shown in Figure 8. The
communication cost between two nodes is the cost of the highest common
ancestor level.
7
2
20
Figure 8: A “tree-leaf” graph of three levels. Processors are drawn in black and
routers in grey The description of this architecture is “
tleaf 3 3 20 2 7 2 2
”,
since it has 3 levels, the first level has 3 sons and a traversal cost of 20, the second
level has 2 sons and a traversal cost of 7, and the third level has also 2 sons and a
traversal cost of 2.
The two additional parameters
cluster
and
weight
serve to model hetero-
geneous architectures for which multiprocessor nodes having several highly
interconnected processors (typically by means of shared memory) are linked
by means of networks of lower bandwidth.
cluster
represents the number
of levels to traverse, starting from the root of the leaf, before reaching the
multiprocessors, each multiprocessor having 2
height
−
cluster
nodes.
weight
is
the relative cost of extra-cluster links, that is, links in the upper levels of the
tree-leaf graph. Links within clusters are assumed to have weight 1.
When there are no clusters at all, that is, in the case of purely homogeneous
architectures, set
cluster
to be equal to
height
, and
weight
to 1.
24
