Scotch Brand 5.1.10 - Manual (Page 2)

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