Scotch Brand 5.1.10 Manuale Utente

Scotch and libScotch 5.1 User’s Guide(version 5.1.10)Fran¸cois PellegriniBacchus team, INRIA Bordeaux Sud-OuestENSEIRB & LaBRI, UMR CNRS 5800Unive

calls a graph bipartitioning algorithm to split the subset of processes associated withthe domain across the two subdomains, as sketched in the follow

This routine is useful to get the size of a mesh read by means of the SCOTCHmeshLoad r outine, in order to allocate auxilia ry arrays of proper sizes.

the reference to the adjacency end index array, and is equal to verttab + 1if the adjacency a rray is compact. velotab and vnlotab ar e pointers toloc

scotchfmeshstat (doubleprecision (*) meshdat,integer*num vnlomin,integer*num vnlomax,integer*num vnlosum,doubleprecision vnloavg,doubleprecision vnlod

In o rder to save memory space as well as computation time, in the currentimplementation of SCOTCH meshGraph, some mesh arrays are shared with thegrap

On return, permtab holds the direct permutation of the unknowns, that is,node vertex i of the original mesh has index permtab[i] in the reorderedmesh,

The SCOTCH meshOrderInit routine fills the ordering structure pointed to byordeptr with all of the data that are passed to it. Thus, all subsequent cal

DescriptionThe SCOTCHmeshOrderSave routine saves the contents of the SCOTCHOrdering structure pointed to by ordeptr to stream stream, in the Scotchord

DescriptionThe SCOTCHmeshOrderSaveTree routine saves the tree hierarchy informationassociated with the SCOTCH Ordering structure pointed to by ordeptr

DescriptionThe SCOTCHmeshOrderCompute routine computes a block ordering of themesh structure pointed to by grafptr, us ing the mapping strategy pointe

7.10.3 SCOTCH stratSaveSynopsisint SCOTCHstratSave (const SCOTCH Strat * straptr,FILE * stream)scotchfstratsave (doubleprecision (*) stradat,integer f

3.1.4 Partial cost functionThe production of efficient complete mappings requires that all graph bipar tition-ings favor the criteria that we have chose

7.10.5 SCOTCH stratGraphMapSynopsisint SCOTCH stratGraphMap (SCOTCH Strat * straptr,const char * string)scotchfstratgraphmap (doubleprecision (*) stra

7.10.7 SCOTCH stratGraphOrderSynopsisint SCOTCH stratGraphOrder (SCOTCH Strat * straptr,const char * string)scotchfstratgraphorder (doubleprecision (*

7.10.9 SCOTCH stratMeshOrderSynopsisint SCOTCH stratMeshOrder (SCOTCH Strat * straptr,const char * string)scotchfstratmeshorder (doubleprecision (*) s

7.11 Geometry handling routinesSince the Scotch project is based on algorithms that rely on topology data only,geometry data do not play an important

The SCOTCH geomExit function frees the contents o f a SCOTCH Geom structurepreviously initialized by SCOTCH geomInit. All subsequent calls to SCOTCH*G

7.11.4 SCOTCH graphGeomLoadChacSynopsisint SCOTCH graphGeomLoadChac (SCOTCH Graph * grafptr,SCOTCHGeom * geomptr,FILE * grafstream,FILE * geomstream,c

The SCOTCH graphGeomSaveChac routine saves the contents of the SCOTCHGraph str uctur e pointed to by grafptr to stream grafstream, in the Chacograph f

int SCOTCH graphGeomLoadScot (SCOTCH Graph * grafptr,SCOTCH Geom * geomptr,FILE * grafstream,FILE * geomstream,const char * string)scotchfgraphgeomloa

Fortra n users must use the PXFFILENO or FNUM functions to obtain the numbersof the Unix file descriptors graffildes and geomfildes associated with the

scotchfmeshgeomloadscot (doubleprecision (*) meshdat,doubleprecision (*) geomdat,integer meshfildes,integer geomfildes,character (*) string)Descriptio

neighbor proces ses, whether they are handled by the job itself or not, since it canestimate in f′Cthe dilation of the corresponding edges. This resul

7.12 Error handling routinesThe handling of errors that occur within library routines is often difficult, becauselibrary routines should be able to issu

The SCOTCH errorProg function is designed to be ca lled at the beginning of aprogram or of a portio n of code to identify the place where subsequent e

metis edgend (integer n,integer (*) xadj,integer (*) adjncy,integer numflag,integer (*) options,integer (*) perm,integer (*) iperm)DescriptionThe METI

While Scotch has also both node and edge separation capabilities, a ll ofthe three MeTiS stubs METIS EdgeND, METIS NodeND and METIS NodeWND callthe sa

void METIS PartGraphKway (const int * const n,const int * const xadj,const int * const adjncy,const int * const vwgt,const int * const adjwgt,const in

metis partgraphrecursive (integer n,integer (*) xadj,integer (*) adjncy,integer (*) vwgt,integer (*) adjwgt,integer wgtflag,integer numflag,integer np

DescriptionThe METISPartGraphVKway function p e rforms a mapping onto the completegraph of the graph re presented by arrays xadj, adjncy, vwgt and vsi

COMMON FILE COMPRESS LZMA for lzma decompression. Note that the correspond-ing development libraries must be installed on your system before compile t

This can also be done in a single piped command:% echo cmplt 7 | gmap brol.grf - /tmp/brol.mapIf compressed data handling is enabled, read the graph a

To speed up tar get architecture loading in the future, the decomposition-defined target architecture is compiled by means of acpl.• Build an architect

space that derives from the one which was g lobally defined a t the coarsestlevel, thus preventing local optimization refinement algorithms to be trappe

simple mesh, in the form of a bipartite graph, the definition of which is given infile mesh.h, respectively. From this structure are derived enriched gr

1. Write the code of the method itself. First, choose a free two-letter code todescribe your method, say “xy”. In the libscotch sourc e directory, cre

• STRATPARAMSTRAT: strategy. For instance, the gr aph ordering methodby nested dissection takes a vertex partitioning strategy as one of itsparameters

• Alex Pothen kindly gave me a version of his Multiple Minimum Degree algo-rithm, which was embedded into Scotch from version 3.2 to version 3.4;• Luc

[13] M. R. Garey and D. S. Johnson. Computers and Intractablility: A Guide tothe Theory of NP-completeness. W. H. Freeman, San Francisco, 1979.[14] G.

[29] P. H´enon, F. Pellegrini, P. Ramet, J. Roman, and Y. Saad. High performancecomplete and incomplete factorizations for very large sparse systems b

[44] F. Pellegrini and J. Roma n. Exp e rimental analysis of the dual recursive bipar-titioning algorithm for static mapping. Research Report, LaBRI,

tree rooted at a randomly chosen vertex, and this process is iterated by se-lecting a new root vertex within the last layer as long as the number of l

for it to account fo r topological structures of the graph that would else be ofa too high level for it to encompass in its local optimization process

vertex separa tors are computed by using direct heuristics [28, 37], or from edgeseparators [48, and included references] by minimum cover techniques

measure its quality, several parameters can be defined: hmin, hmax, and havgdenotethe minimum, maximum, and average heights of the tree1, r e spec tive

3.2.6 Graph separation methodsThe co re of o ur incomplete nested dissection alg orithm uses gra ph separationmethods as black boxes. It a llows the o

Scotch can now handle compressed streams on the fly, in several widely usedformats such as gzip, bzip2 or lzma. Please refer to Section 6.2 for more in

Contents1 Introduction 61.1 Static mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Sparse matrix ordering . . . . . . . . . .

The numeric flag, similar to the one used by the Chaco graph format [24], ismade of three decimal digits. A non-zero value in the units indicates that

The third line holds three figures: the base index of the first element vertex inmemory (velmbas), the base index of the first node vertex in memory (vno

425163101178 913 8 241 4 0004 2 (= 5) 8 (= 11) 4 (= 7) 3 (= 6)4 7 (= 10) 2 (= 5) 8 (= 11) 1 (= 4)4 5 (= 8) 6 (= 9) 3 (= 6) 4 (= 7)1 22 2 12 1 32 1 31

allowed to do so because, in our approach, the recursive bipartitioning of the targetgraph is fully independent with res pect to that o f the source g

5.4.2 Algorithmi call y-coded architecture filesAlmost all algorithmically-coded architectures are defined with unity edge and ver-tex weig hts. They st

mesh2D dimX dimYDefines a bidimensiona l array of dimX columns by dimY rows. The vertexwith coordinates (posX, posY) has label posY × dimX + posX.mesh3

of the target graph vertex onto which it is mapped. Mapping pairs can be storedin any order in the file; however, labels of source graph vertices must

80 61 32 23 74 15 56 47 0Figure 10: Ordering file obtained when reordering the hypercub e graph of Figure 4.Vertex lists are coded as lists of integer

ProgramFileSourcegraph file.grfmtst.tgtTarget filegtst atst.mshSourcemesh filemordExternalgraph filegcvExternalmesh filemmk_* gmk_*mcv.xyzGeometryfile

A brief on-line help is provided with all the programs . To get this help, use the“-h” option after the pro gram name. The case of option letters is n

6.3.5 gcv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.3.6 gmap / gpart . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

However, compiled architecture files are read much more efficiently, as they aredirectly loaded into memory without further processing. Since the compila

Program amk hy outputs the target architecture file of a hypercube graphof dimension dim. Vertices are labeled a c c ording to the decimal value ofthei

6.3.3 amk grfSynopsisamk grf [input graph file [output target file]] optionsDescriptionThe program amkgrf turns a source graph file into a decomposition-

6.3.4 atstSynopsisatst [input target file [output data file]] optionsDescriptionThe program atst is the architecture tester . It gives some statistics o

c Chaco v1.0/MeTiS format.m The Matrix Market for mat.s Scotch source graph format.-V Print the program version and copyright.Default option set is “-

-bratSet the maximum load imbalance ratio to rat, which should be a valuecomprised between 0 and 1. This option can be used in co njunction withoption

DescriptionThe gmk* programs make source graphs. Each of them is devoted to asp e c ific topo logy, for which it builds target graphs of any dimension.

-h Display the program synopsis.-V Print the program version and copyright.6.3.9 gmtstSynopsisgmtst [inputgraph file [input target file [input mapping fi

DescriptionThe gord prog ram is the block sparse matrix graph o rderer. It uses an or-dering strategy to compute block orderings of sparse matrices re

When the geometry of the graph is available, this mapping file may beprocessed by program gout to display the vertex separators and s uper -variable am

7.5.3 SCOTCH graphFree . . . . . . . . . . . . . . . . . . . . . . . . 777.5.4 SCOTCH graphLoad . . . . . . . . . . . . . . . . . . . . . . . . 787.5.

6.3.12 goutSynopsisgout [input graph file [input geometry file [input mapping file [outputvisualization file]]]] optionsDescriptionThe gout program is the

a. A subgraph of M2(4, 4) tobe mapped onto K(2).b. Mapping re sult displayedon the full M2(4, 4) graph.c. Mapping result dis-played on another s ubgra

Figure 15: Snapshot of an Open Inventor display of a sphere partitioned into 7almost equal pieces by mapping onto the complete graph with 7 vertices.

-V Print the program version and copyright.Default option set is “-Oi{v} ”.6.3.13 gtstSynopsisgtst [inputgraph file [output data file]] optionsDescripti

s Scotch source mesh format.-oformatSpecify the output graph format. The available output formats are listedbelow.s Scotch source graph format.-V Prin

Since its main purpose is to provide order ings that exhibit high concurrencyfor parallel block factorization, it comprises a nested dissection method

a root of the separator tree (there can be several roots, if the mesh isdisconnected).Combined to the column block mapping data produced by option -m,

• error handling routines, which allow the user either to provide his own errorservicing routines, or to use the default routines pr ovided in the lib

exists a SCOTCHFTYPEACTION () Fortran counterpart, in which the separatingunderscore character is replaced by an “F”. In most cases, the Fortran routi

“-lscotch -lscotcherr -lm”. If you want to handle errors by yourself, youshould not link with library file libscotcherr.a, but rather provide a SCOTCHe

7.10.2 SCOTCH stratExit . . . . . . . . . . . . . . . . . . . . . . . . 1087.10.3 SCOTCH stratSave . . . . . . . . . . . . . . . . . . . . . . . . 109

and “Data”, allow callers to retrieve informa tion from opaque structures.In all of the following, whenever arrays are defined, passed, and accessed, i

basevalvertnbredgenbrvlbltabverttabedgetabedlotabvelotabvendtab244 10 13 16 19 22 2544444122211333111241 234561712 6 3 4 1 7 6 5 1 2 4 2 7 3 7 2 6 2 1

Dynamic graphs can b e handled elegantly by using the vendtab array. In orderto dynamically manag e graphs, one just has to allocate verttab, vendtab

edgenbrvlbltabverttabvelotabvendtabvnodnbrvelmbasvnodbasvelmnbredgetab2411 10 115 9 2513 14 16 18 20 21 22 2311 4251635 7 6 5 4 6 78 9 2 2 1 31 1 3 3

edgenbrvlbltabvelotabvnodnbrvelmbasvnodbasvelmnbrverttabedgetabvendtab241112 13 16 1912 13 16 19 22 252211 11 12 13 11 12 14 13 13 14 12 141 2 5 8 92

edgenbrvlbltabvelotabvnodnbrvelmbasvnodbasvelmnbrverttabedgetabvendtab12 13 16 1913 16 19 22 252213 14 14 11252713 1413362731313512 11 12 1012353811 1

dimnnbr ≤ 2, a nd its “z” coordinate is loca ted at geomtab[(i - vnodbas) *dimnnbr + baseval + 2] if dimnnbr = 3.7.2.5 Block ordering formatBlock orde

peritabcblknbrrangtabtreetabpermtab1310 11 121011 1210−11 2 4 85 672 3 4 8 7 161 2 453 3 7 6 765 912 398 76541526948373 6789123456710111210 11 12Figur

such as floating point exceptions, which could not be properly handled by thecalling software.7.3.2 Mapping strategy stringsAt the time being, mapping

u Untie jo b pools. Subjobs are stored in the next job pool to be pro-cessed.map=tieThe tie flag defines how results of bipartitioning jobs are propagat

1 Introduction1.1 Static mappingThe efficient e xecution of a parallel program on a parallel machine requires thatthe communicating processes of the pro

cond1 |cond2Logical or operator. The result of the condition is true if cond1 or cond2are true, or both.cond1 &cond2Logical and operator. The resu

application of the bnd bipartitioning method to the band graph leads toa situation where both anchor vertices are placed in the same pa rt.width=valSe

pass=nbrSet the maximum number of optimization passes performed by the algo-rithm. The Fiduccia-Mattheyses algor ithm stops as soon as a pass hasnot y

7.3.4 Ordering strategy stringsOrdering strategies are available both for graphs and for meshes. An orderingstrategy is made of one or several orderin

of large diagonal blocks are likely to be filled at facto ring time. However, inthe context of incomplete solving methods such as ILU(k) [29], it can l

frat=ratFill-in ratio over which some column block will not amalgamate one ofits descendents in the elimination tree. Typical values range from 0.05to

ordering strategy is then a pplied to the derived graph, and this ordering isprojected back to the nodes of the mesh. This method is here for evaluati

levlThe level of the s ubgraph in the separators tree, starting from zeroat the r oot of the tree. Integer.procThe number of processors on which the c

bal=valSet the load imbalance tolerance to val, which is a floating-point ratioexpressed with re spect to the ideal load of the partitions.strat=stratS

computed for coa rser graphs or meshes. This strategy is not applied tothe coar sest graph or mesh, for which only the low strategy is us e d.low=st r

1.3 Contents of this documentThis document describes the capabilities and o perations of Scotch, a softwarepackage devoted to static mapping, graph an

7.4 Target architecture handling routines7.4.1 SCOTCHarchInitSynopsisint SCOTCHarchInit (SCOTCH Arch * archptr)scotchfarchinit (doubleprecision (*) ar

The SCOTCH archLoad routine fills the SCOTCH Arch structure pointed to byarchptr with the source graph description available from stream stream inthe S

string pointers, the scotchfarchname routine takes as second and third pa-rameters a character() array to be filled with the name of the architecture,a

When listptr is not NULL and listnbr is greater than zero, thedecomposition-defined a rchitecture is restricted to the listnbr vertices whoseindices ar

DescriptionThe SCOTCHarchCmpltw routine fills the SCOTCH Arch structure pointed toby archptr with the description of a weighted complete graph architec

Return val uesSCOTCHarchMesh2D returns 0 if the 2D mesh target architecture has beensuccessfully built, and 1 else.7.4.12 SCOTCH archMesh3DSynopsisint

(i + 1) of each node at level i, and linktab[i] is the cost o f communicationbetween pr ocessors the first common ancestor of which belongs to this lev

Return val uesSCOTCHarchTorus3D returns 0 if the 3D torus target architecture has beensuccessfully built, and 1 else.7.5 Graph handling routines7.5.1

DescriptionThe SCOTCHgraphFree function frees the graph data of a SCOTCH Graph struc-ture previously initialized by SCOTCH graphInit, but preserves it

7.5.5 SCOTCH graphSaveSynopsisint SCOTCH graphSave (const SCOTCH Graph * grafptr,FILE * stream)scotchfgraphsave (doubleprecision (*) grafdat,integer f

The free/libre software license under which Scotch 5.1 is distributed isthe CeCILL-C license [6], which has bas ic ally the same features a s the GNUL

DescriptionThe SCOTCHgraphBuild routine fills the source graph structure pointed toby grafptr with all of the data that are passed to it.baseval is the

DescriptionThe SCOTCHgraphBase routine sets the base of all graph indices according tothe given ba se value, and returns the old base va lue. This rou

Any of these pointers can be set to NULL on input if the corresponding infor-mation is not nee ded. Else, the reference to a dummy area can be provide

hold the number of arcs (that is, twice the number o f edges). edgetab is thepointer to a location that will hold the reference to the adjacency array

scotchfgraphstat (doubleprecision (*) grafdat,integer*num velomin,integer*num velomax,integer*num velosum,doubleprecision veloavg,doubleprecision velo

The SCOTCH graphPart routine computes a partition into partnbr parts of thesource graph structure pointed to by grafptr, using the graph partitionings

7.6.3 SCOTCH graphMapInitSynopsisint SCOTCH graphMapInit (const SCOTCH Graph * grafptr,SCOTCHMapping * mappptr,const SCOTCH Arch * archptr,SCOTCH Num

7.6.5 SCOTCH graphMapLoadSynopsisint SCOTCHgraphMapLoad (const SCOTCH Graph * grafptr,SCOTCHMapping * mappptr,FILE * stream)scotchfgraphmapload (doubl

7.6.7 SCOTCH graphMapComputeSynopsisint SCOTCH graphMapCompute (const SCOTCH Graph * grafptr,SCOTCHMapping * mappptr,const SCOTCH Strat * straptr)scot

Return val uesSCOTCHmapView returns 0 if the data has been successfully written to stream,and 1 else.7.7 Graph ordering r out inesThe first routine pro

This function, which has already been considered by several authors for hyper-cube target topologies [11, 21, 25], has several interesting properties:

vertnbr − 1 if the graph base is 0, and from 1 to vertnbr if the graph baseis 1.The three other result fields, *cblkptr, rangtab and treetab, contain d

vertnbr + 1, and treetab is the array holding the structure of the separatorstree, of size vertnbr. See the above manual page of SCOTCH graphOrder, as

Return val uesSCOTCHgraphOrderLoad returns 0 if the ordering structure has been success-fully loaded from stream, and 1 else.7.7.5 SCOTCHgraphOrderSav

resulting mapping file can be used by the gout program (see Section 6.3.12)to produce pictures showing the different separators and blocks.Fortra n user

DescriptionThe SCOTCHgraphOrderCheck routine check s the consistency of the givenSCOTCHOrdering structure pointed to by ordeptr.Return val uesSCOTCHgr

DescriptionThe SCOTCHgraphOrderComputeList routine computes a block ordering of asubgraph of the graph structure pointed to by grafptr, using the orde

Return val uesSCOTCHmeshInit returns 0 if the mesh structure has been successfully ini-tialized, and 1 else.7.8.2 SCOTCH meshExitSynopsisvoid SCOTCHme

7.8.4 SCOTCH meshSaveSynopsisint SCOTCH meshSave (const SCOTCH Mesh * meshptr,FILE * stream)scotchfmeshsave (doubleprecision (*) meshdat,integer filde

scotchfmeshbuild (doubleprecision (*) meshdat,integer*num velmbas,integer*num vnodbas,integer*num velmnbr,integer*num vnodnbr,integer*num (*) verttab,

stage, to call the SCOTCH meshCheck routine on the newly created SCOTCHMesh structure, prior to any other calls to libScotch routines.Return val uesSC