Scotch Brand 5.1.10 - Manual (Page 24)

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
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 2height
− 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