Download downloading

Contents
1 Introduction
1.1 Static mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Sparse matrix ordering . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Contents of this document . . . . . . . . . . . . . . . . . . . . . . . .
5
5
6
6
2 The Scotch project
2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
7
7
3 Algorithms
3.1 Static mapping by Dual Recursive Bipartitioning . . . . . . . .
3.1.1 Static mapping . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Cost function and performance criteria . . . . . . . . . .
3.1.3 The Dual Recursive Bipartitioning algorithm . . . . . .
3.1.4 Partial cost function . . . . . . . . . . . . . . . . . . . .
3.1.5 Execution scheme . . . . . . . . . . . . . . . . . . . . .
3.1.6 Graph bipartitioning methods . . . . . . . . . . . . . . .
3.1.7 Mapping onto variable-sized architectures . . . . . . . .
3.2 Sparse matrix ordering by hybrid incomplete nested dissection
3.2.1 Minimum Degree . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Nested dissection . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Hybridization . . . . . . . . . . . . . . . . . . . . . . . .
3.2.4 Performance criteria . . . . . . . . . . . . . . . . . . . .
3.2.5 Ordering methods . . . . . . . . . . . . . . . . . . . . .
3.2.6 Graph separation methods . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
8
8
9
10
11
11
14
15
15
15
15
16
16
17
4 Updates
4.1 Changes from version 4.0 . . . . . . . . . . . . . . . . . . . . . . . .
18
18
5 Files and data structures
5.1 Graph files . . . . . . . . . . . . . . . . . . . .
5.2 Mesh files . . . . . . . . . . . . . . . . . . . . .
5.3 Geometry files . . . . . . . . . . . . . . . . . .
5.4 Target files . . . . . . . . . . . . . . . . . . . .
5.4.1 Decomposition-defined architecture files
5.4.2 Algorithmically-coded architecture files
5.4.3 Variable-sized architecture files . . . . .
5.5 Mapping files . . . . . . . . . . . . . . . . . . .
5.6 Ordering files . . . . . . . . . . . . . . . . . . .
5.7 Vertex list files . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
18
20
21
22
22
23
24
25
25
26
6 Programs
6.1 Invocation . . . .
6.2 Using compressed
6.3 Description . . .
6.3.1 acpl . . .
6.3.2 amk * . .
6.3.3 amk grf .
6.3.4 atst . . .
6.3.5 gcv . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
27
27
29
29
29
31
32
32
. . .
files
. . .
. . .
. . .
. . .
. . .
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.