(3M) Calculator User Manual

5.4.2 Algorithmi call y-coded architecture files
Almost all algorithmically-coded architectures are defined with unity edge and ver-
tex weig hts. 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 number s
between 0 and size − 1.
cmpltw size load
0
load
1
. . . load
size−1
Defines a weighted complete graph with size vertices. The vertex labels are
numbers between 0 and size − 1, and vertices are as signed integer weights in
the order in which these are provided.
hcub dim
Defines a binary hyperc ube of dimension dim. Graph vertices are numbered
according to the value of the binary representation of their coordinates in the
hype rcub e .
tleaf levlnbr sizeval
0
linkval
0
. . . sizeval
levlnbr−1
linkval
levlnbr−1
Defines a hierarchical, tree-shaped, architecture with levlnbr levels and
P
levlnbr−1
i=0
sizeval
i
leaf vertices. This topolo gy 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 c ost 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 traversa l 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
traver sal cost of 2.
The two additional parameters cluster and weight serve to model hetero-
geneous architectures for which multiproc e ssor nodes having several highly
interconnected proc e ssors (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, se t cluster to be equal to height, and weight to 1.
24