METIS 5.1.x Manual
Contents
1. Convert a mesh into a ETIS_MeshToNodal METIS_MeshToNodal graph ETIS_MeshToDual METIS_MeshToDual Utility routines ETIS EstimateMemory Deprecated New utility routines METIS_SetDefaultOptions METIS_Free Table 2 Mapping between the old 4 x and the new 5 x API 3 Overview of METIS METIS is a serial software package for partitioning large irregular graphs partitioning large meshes and computing fill reducing orderings of sparse matrices METIS has been developed at the Department of Computer Science amp Engineering at the University of Minnesota and is freely distributed Its source code can downloaded directly from http www cs umn edu metis and is also included in numerous software distributions for Unix like operating systems such as Linux and FreeBSD The algorithms implemented in METIS are based on the multilevel graph partitioning paradigm 4 3 2 which has been shown to quickly produce high quality partitionings and fill reducing orderings The multilevel paradigm illustrated in Figure 1 consists of three phases graph coarsening initial partitioning and uncoarsening In the graph coarsening phase a series of successively smaller graphs is derived from the input graph Each successive graph is constructed from the previous graph by collapsing together a maximal size set of adjacent pairs of vertices This process continues until the size of the graph has been reduced to jus2. METIS_CTYPE_SHEM Sorted heavy edge matching options METIS_OPTION_IPTYPE Determines the algorithm used during initial partitioning Possible values are METIS_IPTYPE_GROW Grows a bisection using a greedy strategy METIS_IPTYPE_ RANDOM Computes a bisection at random followed by a refinement METIS_IPTYPE_EDGE Derives a separator from an edge cut METIS_IPTYPE_NODE Grow a bisection using a greedy node based strategy options METIS_OPTION_RTYPE Determines the algorithm used for refinement Possible values are METIS_RTYPE_F FM based cut refinement METIS_RTYPE_GREEDY Greedy based cut and volume refinement METIS_RTYPE_SEP2SIDED Two sided node FM refinement METIS_RTYPE_SEP1SIDED One sided node FM refinement options METIS_OPTION_NCUTS Specifies the number of different partitionings that it will compute The final partitioning is the one that achieves the best edgecut or communication volume Default is 1 options METIS_OPTION_NSEPS Specifies the number of different separators that it will compute at each level of nested dissection The final separator that is used is the smallest one Default is 1 options METIS_OPTION_NUMBERING Used to indicate which numbering scheme is used for the adjacency structure of a graph or the element node structure of a mesh The possible values are 0 C style numbering is assumed that starts from 0 1 Fortran styl
3. Partition a graph gpmetis METIS_PartGraphRecursive METIS_PartGraphKway Partition a mesh mpmetis METIS_PartMeshNodal METIS PartMeshDual Compute a fill reducing ndmet is ETIS_NodeND ordering of a sparse matrix Convert a mesh into a m2gmetis METIS_MeshToNodal graph IS_MeshToDual E Table 3 An overview of METIS command line and library interfaces METIS provides a set of stand alone command line programs for computing partitionings and fill reducing order ings as well as an application programming interface API that can be used to invoke its various algorithms from C C or Fortran programs The list of stand alone programs and API routines of METIS is shown in Table 3 The API routines allow the user to alter the behavior of the various algorithms and provide additional routines that partition graphs into unequal size partitions and compute partitionings that directly minimize the total communication volume 3 1 Partitioning a graph METIS can partition an unstructured graph into a user specified number k of parts using either the multilevel recursive bisection 4 or the multilevel k way partitioning 3 paradigms Both of these methods are able to produce high quality partitions However METIS s multilevel k way partitioning algorithm provides additional capabilities e g minimize the resulting subdomain connectivity graph enforce contiguous partitions minimize alternative objectives
4. or a nodal graph i e each node becomes a graph vertex and then uses the graph partitioning API routines to partition this graph METIS utilizes a flexible approach for creating a graph for a finite element mesh which allows it to handle meshes with different and possibly mixed element types e g triangles tetrahedra hexahedra etc The functionality provided by mpmet is is achieved by the METIS_PartMeshNodal and METIS_PartMeshDual API routines 3 5 Partitioning for heterogeneous parallel computing architectures Heterogeneous computing platforms containing processing nodes with different computational and memory capabil ities are becoming increasingly more common METIS graph and mesh partitioning programs and API routines are designed to partition a graph into k parts such that each part contains a pre specified fraction of the total number of vertices elements nodes In addition in the case of multi constraint partitioning these pre specified fractions are provided for each one of the vertex weights By matching the weights specified for each partition to the relative com putational and memory capabilities of the various processors these routines can be used to compute partitionings that balance the computations on heterogeneous architectures 3 6 Computing a fill reducing ordering of a sparse matrix METIS provides the ndmet is program and its associated METIS_NodeND API routine for computing fill reducing orderings of spars
5. shows how the v4 x command line programs map to the new set of command line programs provided by the 5 0 version of METIS As part of these changes none of the functionality offered by the old programs has been removed On the contrary the new programs have been extended to substantially increase the type of partitionings and orderings that can be computed by them This was achieved by expanding the number of optional parameters that these programs can take which allow users to have a complete access to all of METIS functionality Prior to this release if users wanted to access some of the advance features of METIS they had to write their own programs based on the supplied API 2 1 1 Migration issues In order to support the enhanced functionality offered by the new command line programs the format of the graph mesh files has changed Section 4 1 In the case of the graph file the new format is backwards compatible so graphs written for the earlier format will work correctly when used by gometis and ndmet is However the new mesh file format is not backward compatible and as such they should not be used with momet is and m2gmetis Fortunately they can be easily converted to the new format by a slightly modifying their header line 2 2 Changes in the API routines Table 2 shows how the v4 x API routines map to the new set of APIs provided by the 5 0 version of METIS The number of distinct core functions has been reduced to seven by expandi
6. for each constraint all partitions are assumed to be of the same size ufactor int Specifies the maximum allowed load imbalance among the partitions It is this described under METIS_OPTION_UFACTOR in Section 5 4 Note that in the case of multiple constraints the same load imbalance tolerance is applied to all the constraints Use ubvec to provide per constraint load imbalance tolerances 13 ubvec string Specifies the per constraint allowed load imbalance among partitions The string must contain a space separated list of floating point numbers one for each of the constraints For example for three constraints the string can be 1 02 1 2 1 35 indicating a desired maximum load imbalance of 2 20 and 35 respectively The load imbalance is defined in a way similar to ufactor If supplied this parameter takes priority over ufactor niter int Specifies the number of iterations for the refinement algorithms at each stage of the uncoarsening process Default is 10 ncuts int Specifies the number of different partitionings that it will compute The final partitioning is the one that achieves the best edgecut or communication volume Default is 1 nooutput Specifies that no partitioning file should be generated seed int Selects the seed of the random number generator dbglvl int Specifies the type of progress debugging information that will be printed to stdout The supplied value corresponds to the addition bitwise
7. www cs umn edu metis 7 Copyright amp license notice METIS is copyrighted by the Regents of the University of Minnesota It is licensed under the Apache License Version 2 0 the License you may not use this file except in compliance with the License You may obtain a copy of the License at http www apache org licenses LICENSE 2 0 Unless required by applicable law or agreed to in writing software distributed under the License is distributed on an AS IS BASIS WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND either express or implied See the License for the specific language governing permissions and limitations under the License References 1 Bruce Hendrickson Graph partitioning and parallel solvers Has the emperor no clothes In Proc of Irregu lar 1998 1998 2 G Karypis and V Kumar Multilevel algorithms for multi constraint graph partitioning In Proceedings of Super computing 1998 3 G Karypis and V Kumar Multilevel k way partitioning scheme for irregular graphs Journal of Parallel and Distributed Computing 48 1 96 129 1998 4 G Karypis and V Kumar A fast and high quality multilevel scheme for partitioning irregular graphs SIAM Journal on Scientific Computing 20 1 359 392 1999 5 B W Kernighan and S Lin An efficient heuristic procedure for partitioning graphs The Bell System Technical Journal 49 2 291 307 1970 35
8. Specifies the number of iterations for the refinement algorithms at each stage of the uncoarsening process Default is 10 nseps int Specifies the number of different separators that it will compute at each level of nested dissection The final separator that is used is the smallest one Default is 1 nooutput Specifies that no ordering file should be generated 16 seed int Selects the seed of the random number generator dbglvl int Similar to the corresponding option of gpmet is help Displays the command line options along with a description 17 m2gmetis options meshfile graphfile Description Converts a mesh into a graph that is compatible with METIS Parameters meshfile The name of the file that stores the mesh to be converted Section 4 1 2 graphfile The name of the file that will store the generated graph Options gtype string Specifies the type of the graph to be generated The possible values are dual Generates the dual graph of the mesh default nodal the nodal graph of the mesh ncommon int applies only when gtype dual Similar to the corresponding option of mpmet is dbglvl int Similar to the corresponding option of gpmet is help Displays the command line options along with a description 18 graphchk graphfile fixedfile Description Checks the graph for format correctness and consistency Parameters graphfile The name of the file that stores the graph to be checked Section 4 1 2 fix
9. and for returning status codes 5 2 Use of NULL parameters METIS API routines take a large number of parameters allowing the user to model complex graphs and specify complex partitioning ordering requirements However for most uses of METIS this level of complexity may not be required For that purpose and to also simplify the complexity associated with using its API METIS allows the application to specify a NULL value to many of these optional advanced parameters The API routines that will be described in subsequent sections will mark these parameters by following them with a NULL 5 3 C C and Fortran Support The various routines in METIS API can be called from either C C or Fortran programs Using C C with METIS API is quite straightforward as METIS is written entirely in C However METIS API fully supports Fortran as well This support comes in three forms 1 All the scalar arguments in the routines are passed by reference to facilitate Fortran programs 2 All the routines take a parameter called numflag or an opt ions parameter called METIS_OPTION_NUMBERING indicating whether or not the numbering of the graph or mesh starts from 0 or 1 In C programs numbering usu ally starts from 0 whereas in Fortran programs numbering starts from 1 3 METIS API incorporates alternative names for each of the routines to facilitate linking the library with Fortran programs In particular for every function METIS A
10. array A mesh with n elements is stored in a plain text file that contains n 1 lines The first line i e the header line contains information about the size and the type of the mesh while the remaining n lines contain the nodes that make up each element The first line contains two integer parameters The first parameter is the number of elements n in the mesh The second parameter which is optional is the number of weights associated with each element This is equivalent to the ncon parameter of the graph file and is used to specify the weights of the vertices in the dual graph If this parameter is omitted the weights of the vertices in the dual graph are assumed to be 1 The current mesh format does not allow for the specification of weights with the vertices in the nodal graph If you need to partition the nodal graph of a mesh whose vertices can have different weights then the m2gmet is routine should be used to first create the nodal graph which should 10 Graph File Graph File 7 11 AO Oa Or ids 2 NE 222 134 113241 5421 53422212 2367 2 LB a S 136 1 1 30 36 2 547 524276 6 4 6645 Weighted Graph Weights on edges a Unweighted Graph 1 1 1 5 2 2 1 2 Graph File Graph File 7 11 011 E 7 11 010 3 2113241 re 0 8 2 553422212 dad 2 3 8 321326275 q KIA A 1113362 O iT 6524276 Hide 1 11 8 6 Bae rate 221547 12164 c Weighted Graph Weights bo
11. depends on the following factors i the total communication volume ii the maximum amount of data that any particular processor needs to send and re ceive and iii the number of messages a processor needs to send and receive METIS multilevel k way partitioning approaches can be used to directly minimize the total communication volume resulting from the partitioning first fac tor In addition METIS also provides support for minimizing the third factor which essentially reduces the number of startups and indirectly up to a point reduces the second factor 3 3 Support for multi phase and multi physics computations The traditional graph partitioning problem formulation is limited in the types of applications that it can effectively model because it specifies that only a single quantity be load balanced Many important types of multi phase and multi physics computations require that multiple quantities be load balanced simultaneously This is because synchronization steps exist between the different phases of the computations and so each phase must be individually load balanced That is it is not sufficient to simply sum up the relative times required for each phase and to compute a partitioning based on this sum Doing so may lead to some processors having too much work during one phase of the computation and so these may still be working after other processors are idle and not enough work during another Instead it is critical that e
12. etc and as such it may be preferable than multilevel recursive bisection METIS stand alone program for partitioning Multilevel Partitioning Coarsening Phase aseyd Buluasieooun Initial Partitioning Phase Figure 1 The three phases of multilevel k way graph partitioning During the coarsening phase the size of the graph is successively decreased During the initial partitioning phase a k way partitioning is computed During the multilevel refinement or uncoarsening phase the partitioning is successively refined as it is projected to the larger graphs Go is the input graph which is the finest graph G 1 is the next level coarser graph of G G4 is the coarsest graph a graph is gomet is and the functionality that it provides is achieved by the METIS_PartGraphRecursive and METIS PartGraphKway API routines 3 2 Alternate partitioning objectives The objective of the traditional graph partitioning problem is to compute a k way partitioning such that the number of edges or in the case of weighted graphs the sum of their weights that straddle different partitions is minimized This objective is commonly referred to as the edge cut When partitioning is used to distribute a graph or a mesh among the processors of a parallel computer the objective of minimizing the edge cut is only an approximation of the true communication cost resulting from the partitioning 1 The communication cost resulting from a k way partitioning generally
13. of error 33 5 12 Utility routines int METIS _SetDefaultOptions idx_t options METIS_NOPTIONS Description Initializes the options array into its default values Parameters options The array of options that will be initialized It s size should be at least METIS_NOPTIONS Returns METIS_OK Indicates that the function returned normally int METIS_Free idx_t ptr Description Frees the memory that was allocated by either the METIS MeshToDual or the METIS MeshToNodal rou tines for returning the dual or nodal graph of a mesh Parameters ptr The pointer to be freed This pointer should be one of the xadj or adjncy returned by METIS API routines Returns METIS_OK Indicates that the function returned normally 34 6 System requirements and contact information METIS is written entirely in ANSI C and is portable on most Unix systems that have an ANSI C compiler the GNU C compiler will do It has been tested on Linux SunOS and OSX Instructions on how to build and install METIS can be found in the file Install txt of the distribution METIS have been extensively tested on a number of different architectures However even though METIS contains no known bugs this does not mean that all of its bugs have been found and fixed If you have any problems please send email to karypis cs umn edu with a brief description of the problem Also any future updates to METIS will be made available on WWW at http
14. th vertex belongs to Partition numbers start from 0 up to the number of partitions minus one 4 2 2 Ordering file The ordering file of a graph with n vertices consists of n lines with a single number per line The th line of the ordering file contains the new order of the th vertex of the graph The numbering in the ordering file starts from 0 Note that the ordering file stores what is referred to as the the inverse permutation vector iperm of the ordering Let A be a matrix and let A be the reordered matrix The inverse permutation vector maps the ith row column of A into the iperm i row column of A 4 3 Programs 12 gpmetis options graphfile nparts Description Partitions a graph into a specified number of parts The computed partitioning is stored in a file named graphfile part nparts where graphfile and nparts correspond to the specified parameters Parameters graphfile The name of the file that stores the graph to be partitioned Section 4 1 1 nparts The number of parts that the graph will be partitioned into It should be greater than 1 Options ptype string Specifies the scheme used for computing the partitioning Possible values rb Multilevel recursive bisectioning kway Multilevel k way partitioning default ctype string Specifies the scheme used to match the vertices of the graph during the coarsening Possible values rm Random matching shem Sorted heavy edge matching default iptype str
15. weight of all the edges is the same This format is illustrated in Figure 2 a Note the optional fmt parameter is skipped in this case However there are cases in which the edges in G have different weights This is accommodated as shown in Figure 2 b Now the adjacency list of each vertex contains the weight of the edges in addition to the vertices that is connected with If v has k vertices adjacent to it then the line for v in the graph file contains 2 x k numbers each pair of numbers stores the vertex that v is connected to and the weight of the edge Note that the fmt parameter is equal to 001 indicating the fact that G has weights on the edges In addition to having weights on the edges weights on the vertices are also allowed as illustrated in Figure 2 c In this case the value of fmt is equal to 011 and each line of the graph file first stores the weight of the vertex and then the weighted adjacency list Finally Figure 2 d illustrates the format of the input file when the vertices of the graph contain multiple weights 3 in this example In this case the value of fmt is equal to 010 and the value of ncon is equal to 3 since we have three sets of vertex weights Each line of the graph file stores the three weights of the vertices followed by the adjacency list 4 1 2 Mesh file The primary input of the mesh partitioning programs in METIS is the mesh to be partitioned This mesh is stored in a file in the form of the element node
16. METIS A Software Package for Partitioning Unstructured Graphs Partitioning Meshes and Computing Fill Reducing Orderings of Sparse Matrices Version 5 1 0 George Karypis Department of Computer Science amp Engineering University of Minnesota Minneapolis MN 55455 karypis cs umn edu March 30 2013 Metis MEE tis Metis is the Greek word for wisdom Metis was a titaness in Greek mythology She was the consort of Zeus and the mother of Athena She presided over all wisdom and knowledge METIS is copyrighted by the regents of the University of Minnesota Related papers are available via WWW at URL http www cs umn edu karypis Contents 1 2 Introduction What is new in version 5 0 2l 22 Changes m the command line Programs lt lt s soeces a e aa ee ee A SEM e S ZLI Migration ISSUES re oo e ore co aut A ee a E e ee ew aS Changes mihe API RUIRES ecos e aS Re ee SOE a ee Zal MISMO MISSUES ys a Beem e E e god e a eee Overview of METIS 3 1 de 33 3 4 3 5 3 6 a Paintings APO oi ba koe ed Be eS oH Ee EA DRE Beet BAS Alternate partitioning objectives ooo ens ee es Support for multi phase and multi physics computations o o PATO LAS 2 sos ins A es A A A Hee wae eS Partitioning for heterogeneous parallel computing architectures o a Computing a fill reducing ordering of a sparse matrix o e Convetting a mesh into a graph coc se
17. OMPRESS METIS_OPTION_CCORDER METIS_OPTION_SEED METIS_OPTION_PFACTOR METIS_OPTION_NUMBERING METIS_OPTION_DBGLVL perm iperm These are vectors each of size nvixs Upon successful completion they store the fill reducing per mutation and inverse permutation Let A be the original matrix and A be the permuted matrix The arrays perm and iperm are defined as follows Row column of A is the perm row column of A and row column of A is the iperm row column of A The numbering of this vector starts from either 0 or 1 depending on the value of opt ions METIS_OPTION_NUMBERING Returns METIS_OK Indicates that the function returned normally ETIS_ERROR_INPUT Indicates an input error M METIS_ERROR MEMORY Indicates that it could not allocate the required memory M ETIS_ERROR Indicates some other type of error 31 5 11 Mesh to graph conversion routines int METIS MeshToDual idx_t ne idx_t nn idx_t eptr idx_t eind idx_t ncommon Description This function is used to generate the dual graph of a mesh Parameters ne nn eptr eind ncommon idx_t numflag idx_t xadj idx_t adjncy The number of elements in the mesh The number of nodes in the mesh The pair of arrays storing the mesh as described in Section 5 6 Specifies the number of common n
18. OR of the various values described in Section 5 4 for METIS_OPTION_DBGLVL The default value is 0 no progress debugging information help Displays the command line options along with a description 14 mpmetis options meshfile nparts Description Partitions a mesh into a specified number of parts The computed partitioning is stored in two files named meshfile npart nparts that stores the partitioning of the nodes and meshfile epart nparts that stores the partitioning of the elements The meshf ile and npart s components of those files correspond to the specified parameters The format of the partitioning files is described in Section 4 2 1 Parameters meshfile The name of the file that stores the mesh to be partitioned Section 4 1 2 nparts The number of parts that the mesh will be partitioned into It should be greater than 1 Options gtype string Specifies the graph to be used for computing the partitioning The possible values are dual Partition the dual graph of the mesh default nodal Partition the nodal graph of the mesh ncommon int applies only when gtype dual Specifies the number of common nodes that two elements must have in order to put an edge between them in the dual graph Given two elements e and ez containing n and na nodes respectively then an edge will connect the vertices in the dual graph corresponding to e and ez if the number of common nodes between them is greater than or equal to min ncomm
19. PI provides four additional names one all capital one all lower case one all lower case with _ appended to it and one with _ appended to it For example for METIS _PartGraphKway METIS API provides METIS_PARTGRAPHKWAY metis_partgraphkway metis_partgraphkway and metis_partgraphkway_ These extra names allow the library to be di rectly linked into Fortran programs on a wide range of architectures including Cray SGI and HP If you still encounter problems linking with the library let us know so we can include appropriate support 5 4 Options array Most of the API routines take as a parameter an array called options which allow the application to fine tune and modify various aspects of the internal algorithms used by METIS The application must define this array as idx_t options METIS_NOPTIONS and the meaning of its various entries are as follows 20 options METIS_OPTION_PTYPE Specifies the partitioning method Possible values are METIS_PTYPE_RB Multilevel recursive bisectioning METIS_PTYPE_KWAY Multilevel k way partitioning options METIS_OPTION_OBJTYPE Specifies the type of objective Possible values are METIS_OBJTYPE_CUT Edge cut minimization METIS_OBJTYPE_VOL Total communication volume minimization options METIS_OPTION_CTYPE Specifies the matching scheme to be used during coarsening Possible values are METIS_CTYPE_RM Random matching
20. _OPTION_CCORDER Specifies if the connected components of the graph should first be identified and ordered separately 0 Does not identify the connected components 1 Identifies the connected components options METIS OPTION PFACTOR Specifies the minimum degree of the vertices that will be ordered last If the specified value is x gt 0 then any vertices with a degree greater than 0 1 x average degree are removed from the graph an ordering of the rest of the vertices is computed and an overall ordering is computed by ordering the removed vertices at the end of the overall ordering For example if x 40 and the average degree is 5 then the algorithm will remove all vertices with degree greater than 20 The vertices that are removed are ordered last i e they are automatically placed in the top level separator Good values are often in the range of 60 to 200 i e 6 to 20 times more than the average Default value is 0 indicating that no vertices are removed Used to control whether or not the ordering algorithm should remove any vertices with high degree i e dense columns This is particularly helpful for certain classes of LP matrices in which there a few vertices that are connected to many other vertices By removing these vertices prior to ordering the quality and the amount of time required to do the ordering improves options METIS_OPTION_UFACTOR Specifies the maximum allowed load imbalance among the partitions A value of
21. all elements are integer SW W2 Wneon V1 1 V2 2 Uk Ek where s is the size of the vertex w1 W2 Wncon are the ncon vertex weights associated with this vertex v1 Uk are the vertices adjacent to this vertex and ez ejz are the weights of these edges The vertices i e the various v entries are numbered starting from 1 not from 0 as is often done in C Furthermore the vertex sizes and vertex weights must be integers greater or equal to 0 whereas the edge weights must be strictly greater than 0 Vertex size versus vertex weights The graph format allows for the specification of both vertex sizes and vertex weights These two quantities are used by METIS for two entirely different purposes The vertex weights are used for ensuring that the computed partitionings satisfy the specified balancing constraints e g the sum of the weights of the vertices assigned to each partition is the same across the partitions On the other hand the vertex sizes are used for determining the total communication volume when gpmet is and mpmet is are invoked with the objt ype vol option Additional details on how the vertex size is used to determine the communication volume are provided in Section 5 7 which provides the precise formula for computing the total communication volume Examples Figure 2 illustrates the format by providing some examples The simplest format for a graph G is when the size and weight of all vertices and the
22. ates that the function returned normally ETIS_ERROR_INPUT Indicates an input error M METIS_ERROR MEMORY Indicates that it could not allocate the required memory M ETIS_ERROR Indicates some other type of error 32 int METIS MeshToNodal idx_t ne idx_t nn idx_t eptr idx_t eind idx_t numflag idx_t xadj idx_t adjncy Description This function is used to generate the nodal graph of a mesh Parameters ne The number of elements in the mesh nn The number of nodes in the mesh eptr eind The pair of arrays storing the mesh as described in Section 5 6 numflag Used to indicate which numbering scheme is used for eptr and eind The possible values are 0 C style numbering is assumed that starts from 0 1 Fortran style numbering is assumed that starts from 1 xadj adjncy These arrays store the adjacency structure of the generated graph The format is of the adjacency structure is described in Section 5 5 Memory for these arrays is allocated by METIS API using the standard malloc function It is the responsibility of the application to free this memory by calling free METIS provides the METIS_F ree that is a wrapper to C s free function METIS_OK Indicates that the function returned normally ETIS_ERROR_INPUT Indicates an input error M METIS_ERROR MEMORY Indicates that it could not allocate the required memory M ETIS_ERROR Indicates some other type
23. ause each interface vertex v needs to be sent to all of its Nadj v partitions The above model can be extended to instances in which the amount of data that needs to be sent for each node is different In particular if s is the amount of data that needs to be sent for vertex v referred to as the vertex size then Equation 1 can be re written as totalv 5 syNad v Q vEV METIS API supports this weighted totalv model by using an array called vsize such that the amount of data that needs to be sent due to the th vertex is stored in vsize i Note that the amount of data that needs to be sent is different from the weight of the vertex The former corresponds to communication cost whereas the later corresponds to the computational cost Note that for partitioning algorithms to correctly minimize the totalv the graph should reflect the true information exchange requirements of the underlying computations For instance the dual graph of a finite element mesh does not correctly model the underlying communication whereas the nodal graph does Which one is better When partitioning is used to distribute a graph or a mesh among the processors of a parallel computer the edgecut is only an approximation of the true communication cost resulting from the partitioning On the other hand by minimizing the totalv we can directly minimize the overall communication cost Despite of that for many graphs the solutions obtained by minimizing the edgecut o
24. d for METIS_PartGraphRecursive METIS_OPTION_CTYPE ETIS_OPTION_IPTYPE METIS_OPTION_RTYPE METIS_OPTION_NO2HOP ETIS_OPTION_NCUTS METIS_OPTION_NITER METIS_OPTION_SEED METIS_OPTION_UFACTOR METIS_OPTION_NUMBERING METIS_OPTION_DBGLVL The following options are valid for METIS_PartGraphKway 26 objval part Returns M ry ETIS_OP al ION_OBJTYPE METIS_OPTION_CTYPE ETIS_OPTION_IPTYP ETIS_OP ETIS_OP M M METIS_OP M M ETIS_OP E ION_RTYPE METIS_OPTION_NO2HOP TIS_OPTION_NCUTS ION_NITER METIS_OPTION_UFACTOR METIS_OPTION_MINCONN ION_CONTIG METIS_OPTION_SEED METIS _OPTION_NUMBERING ION_DBGLVL Upon successful completion this variable stores the edge cut or the total communication volume of the partitioning solution The value returned depends on the partitioning s objective function This is a vector of size nvtxs that upon successful completion stores the partition vector of the graph The numbering of this vector starts from either 0 or 1 depending on the value of options METIS_OPTION_NUMBERING IS_OK ry TS ERROR_INPUT IS ERROR_MEMORY M ME M TS ERROR Indicates that the function returned normally Indicates an input error Indicates that it could no
25. e matrices based on the multilevel nested dissection paradigm 4 The nested dissection paradigm is based on computing a vertex separator for the the graph corresponding to the matrix The nodes in the separator are moved to the end of the matrix and a similar process is applied recursively for each one of the other two parts The multilevel nested dissection paradigm is quite effective in producing re orderings that incur low fill in 3 7 Converting a mesh into a graph METIS provides the m2gmet is program for converting a mesh into the graph format used by METIS This program can generate either the nodal or dual graph of the mesh The corresponding API routines are METIS _MeshToNodal and METIS _MeshToDual Since METIS does not provide API routines that can directly compute a multi constraint partitioning of a mesh these routines can be used to first convert the mesh into a graph which can then be used as input to METIS graph partitioning routines to obtain such partitionings 4 METIS stand alone programs METIS provides a variety of programs that can be used to partition graphs partition meshes compute fill reducing orderings of sparse matrices as well as programs to convert meshes into graphs appropriate for METIS s graph parti tioning programs 4 1 Input file formats The various programs in METIS require as input either a file storing a graph or a file storing a mesh The format of these files are described in the followi
26. e nodes that is used for computing the total communica tion volume as described in Section 5 7 A NULL value can be passed when the objective is cut or when all nodes have an equal size nparts The number of parts to partition the mesh tpwgts NULL This is an array of size nparts that specifies the desired weight for each partition The target partition weight for the ith partition is specified at tpwgts i the numbering for the partitions starts from 0 The sum of the tpwgts entries must be 1 0 A NULL value can be passed to indicate that the graph should be equally divided among the partitions options NULL This is the array of options as described in Section 5 4 The following options are valid METIS_OPTION_PTYPE METIS_OPTION_OBJTYPE ETIS_OPTION_CTYPE METIS_OPTION_IPTYPE ETIS_OPTION_RTYPE METIS_OPTION_NCUTS METIS_OPTION_NITER METIS_OPTION_SEED ETIS_OPTION_UFACTOR METIS_OPTION_NUMBERING METIS_OPTION_DBGLVL objval Upon successful completion this variable stores either the edgecut or the total communication vol ume of the nodal graph s partitioning epart This is a vector of size ne that upon successful completion stores the partition vector for the elements of the mesh The numbering of this vector starts from either 0 or 1 depending on the value of options METIS_OPTION_NUMBERING npart This is a vector of size nn
27. e numbering is assumed that starts from 1 options METIS_OPTION_NITER Specifies the number of iterations for the refinement algorithms at each stage of the uncoarsening process Default is 10 options METIS_OPTION_SEED Specifies the seed for the random number generator 21 options METIS_OPTION_MINCONN Specifies that the partitioning routines should try to minimize the maximum degree of the subdomain graph i e the graph in which each partition is a node and edges connect subdomains with a shared interface 0 Does not explicitly minimize the maximum connectivity 1 Explicitly minimize the maximum connectivity options METIS_OPTION_NO2HOP Specifies that the coarsening will not perform any 2 hop matchings when the standard matching approach fails to sufficiently coarsen the graph The 2 hop matching is very effective for graphs with power law degree distributions O Performs a 2 hop matching 1 Does not perform a 2 hop matching options METIS OPTION CONTIG Specifies that the partitioning routines should try to produce partitions that are contiguous Note that if the input graph is not connected this option is ignored 0 Does not force contiguous partitions 1 Forces contiguous partitions options METIS_OPTION_COMPRESS Specifies that the graph should be compressed by combining together vertices that have identical adjacency lists 0 Does not try to compress the graph 1 Tries to compress the graph options METIS
28. eater or equal to zero If all the vertices of the graph have the same weight i e the graph is unweighted then the vwgt can be set to NULL The weights of the edges if any are stored in an additional array called adjwgt This array contains 2m elements and the weight of edge adjncy Jj is stored at location adjwgt 7 The edge weights must be integers greater than zero If all the edges of the graph have the same weight 1 e the graph is unweighted then the adjwgt can be set to NULL 5 6 Mesh data structure All of the mesh partitioning and mesh conversion routines in METIS take as input the element node array of a mesh This element node array is stored using a pair of arrays called ept r and eind which are similar to the xadj and adjncy arrays used for storing the adjacency structure of a graph The size of the ept r array is n 1 where n is the number of elements in the mesh The size of the eind array is of size equal to the sum of the number of nodes in all the elements of the mesh The list of nodes belonging to the ith element of the mesh are stored in consecutive locations of eind starting at position eptr i up to but not including position eptr 1 1 This format makes it easy to specify meshes of any type of elements including meshes with mixed element types that have different number of nodes per element As it was the case with the format of the mesh file described in Section 4 1 2 the ordering of the nodes in each element
29. edfile This is an optional parameter that specifies the name of the file to store the fixed input graph This file will only be generated if there were errors in the input file 19 5 Metis API The various routines implemented in METIS stand alone programs can be directly accessed from a C C or Fortran program by using the supplied library In the rest of this section we describe METIS API by first describing various calling and usage conventions the various data structures used to pass information into and get information out of the routines followed by a detailed description of the calling sequence of the various routines 5 1 Header files Any program using METIS API needs to include the met is h header file This file provides function prototypes for the various API routines and defines the various data types and constants used by these routines During METIS installation time the met is h defines two important data types and their widths These are the idx_t data type for storing integer quantities and the real_t data type for storing floating point quantities The idx_t data type can be defined to be either a 32 or 64 bit signed integer whereas the real_t data type can be defined to be either a single or double precision float point number All of METIS API routines take as input arrays and or scalars that are of these two data types In addition met is h defines various enum data types for specifying various options
30. ful when direct methods are used to solve sparse systems of linear equations A good ordering of a sparse matrix dramatically reduces both the amount of memory as well as the time required to solve the system of equations Furthermore the fill reducing orderings produced by graph partitioning algorithms are par ticularly suited for parallel direct factorization as they lead to high degree of concurrency during the factorization phase Graph partitioning is also used for solving optimization problems arising in numerous areas such as design of very large scale integrated circuits VLSI storing and accessing spatial databases on disks transportation management and data mining 2 What is new in version 5 0 Version 5 0 represents nearly a complete re write of the code base whose purpose was to streamline and unify the stand alone programs and API provide better support for 64 bit architectures enhance its functionality and reduce the memory requirements by re factoring its internal memory management routines As a result both the stand alone programs and APT routines have changed making it incompatible with the earlier versions of METIS However in order to minimize the code changes that the revised API will require the new API relies heavily on reasonable default values for most of the new parameters that it introduced The following represents a list of some of the major functionality related changes and enhancements that are ac cessible by b
31. he possible values are edge Derive the separator from an edge cut default node Grow a bisection using a greedy node based strategy rtype string Specifies the scheme to be used for refinement The possible values are lsided One sided node based refinement default 2sided Two sided node based refinement ufactor int Specifies the maximum allowed load imbalance between the left and right partitions during each bisection It is this described under METIS_OP TION_UFACTOR in Section 5 4 when the number of partitions Default is 30 indicating a load imbalance of 1 03 pfactor int Specifies the minimum degree of the vertices that will be ordered last It is this described under METIS_OPTION_PFACTOR in Section 5 4 Default value is 0 indicating that no vertices are re moved no2hop Specifies that the coarsening will not perform any 2 hop matchings when the standard matching approach fails to sufficiently coarsen the graph The 2 hop matching is very effective for graphs with power law degree distributions If the quality of the orderings when compared to that obtained by earlier versions of METIS is low then this option can be specified to turn off this type of matching nocompress Specifies that the graph should not be compressed by combining together vertices that have identical adjacency lists ccorder Specifies if the connected components of the graph should first be identified and ordered separately niter int
32. ing applies only when ptype rb Specifies the scheme used to compute the initial partitioning of the graph Possible values grow Grows a bisection using a greedy strategy default random Computes a bisection at random followed by a refinement objtype string applies only when ptype kway Specifies the partitioning s objective function Possible values cut Edgecut minimization default vol Total communication volume minimization no2hop Specifies that the coarsening will not perform any 2 hop matchings when the standard matching approach fails to sufficiently coarsen the graph The 2 hop matching is very effective for graphs with power law degree distributions If the quality of the partitionings when compared to that obtained by earlier versions of METIS is low then this option can be specified to turn off this type of matching contig applies only when ptype kway Specifies that the partitioning routines should try to produce partitions that are contiguous Note that if the input graph is not connected this option is ignored minconn applies only when ptype kway Specifies that the partitioning routines should try to minimize the maximum degree of the subdomain graph i e the graph in which each partition is a node and edges connect subdomains with a shared interface tpwegts filename Specifies the name of the file that stores for each constraint the target weights for each partition Section 4 1 3 By default
33. ints It should be at least 1 xadj adjncy The adjacency structure of the graph as described in Section 5 5 vwet NULL The weights of the vertices as described in Section 5 5 vsize NULL The size of the vertices for computing the total communication volume as described in Section 5 7 adjwgt NULL The weights of the edges as described in Section 5 5 nparts The number of parts to partition the graph tpwgts NULL This is an array of size nparts xncon that specifies the desired weight for each partition and constraint The target partition weight for the ith partition and jth constraint is specified at tpwgts i ncon 3 the numbering for both partitions and constraints starts from 0 For each constraint the sum of the tpwgts entries must be 1 0 ie gt tpwgts i ncon j 1 0 A NULL value can be passed to indicate that the graph should be equally divided among the partitions ubvec NULL This is an array of size ncon that specifies the allowed load imbalance tolerance for each constraint For the ith partition and th constraint the allowed weight is the ubvec j tpwgts i ncon j fraction of the jth s constraint total weight The load imbalances must be greater than 1 0 A NULL value can be passed indicating that the load imbalance tolerance for each constraint should be 1 001 for ncon 1 or 1 01 for ncon 1 options NULL This is the array of options as described in Section 5 4 The following options are vali
34. is not important 5 7 Partitioning objectives The partitioning algorithms in METIS can be used to compute a balanced k way partitioning that minimizes either the number of edges that straddle partitions edgecut or the total communication volume totalv In the rest of this section we briefly describe these two objectives and provide some suggestions on when they should be used Minimizing the edgecut Consider a graph G V E and let P be a vector of size V such that Pfi stores the number of the partition that vertex 2 belongs to The edgecut of this partitioning is defined as the number of edges that straddle partitions That is the number of edges v u for which P v 4 Plu If the graph has weights associated with the edges then the edgecut is defined as the sum of the weight of these straddling edges Minimizing the total communication volume Consider a graph G V E and let P be a vector of size V such that P stores the number of the partition that vertex i belongs to Let Vp C V be the subset of interface or boarder vertices That is each vertex v Vp is connected to at least one vertex that belongs to a different partition For each vertex v V let Nadj v be the number of domains other than P v that the vertices adjacent to v belong to 24 The totalv of this partitioning is defined as totalv 5 Nadjlv 1 vEVp Equation 1 corresponds to the total communication volume incurred by the partitioning bec
35. ng sections 4 1 1 Graph file The primary input of the partitioning and fill reducing ordering programs in METIS is the undirected graph to be partitioned or ordered This graph is stored in a file and is supplied to the various programs as one of the command line parameters A graph G V E with n vertices and m edges is stored in a plain text file that contains n 1 lines excluding comment lines The first line referred to as the header line contains information about the size and the type of the graph while the remaining n lines contain information for each vertex of G Any line that starts with is a comment line and is skipped The header line contains either two n m three n m fmt or four n m fmt ncon parameters The first two parameters n m are the number of vertices and the number of edges respectively Note that in determining the number of edges m an edge between any pair of vertices v and u is counted only once and not twice i e we do not count the edge v u separately from u v For example the graph in Figure 2 contains 11 vertices The fmt parameter is used to specify if the graph file contains information about vertex sizes vertex weights and edge weights The fmt parameter is a three digit binary number If the least significant bit is set to 1 i e the Ist bit from right to left then the graph file provides information about the weights of the edges If the second least significant bit is
36. ng the calling sequence of the new routines to provide the functionally offered by the old specialized routines In most cases the functionality provided by the new API routines is a superset of that offered by the old routines especially in the areas related to partitioning for heterogeneous computing architectures multi constraint partitioning and communication volume based partitioning objectives 2 2 1 Migration issues Since the calling sequence of all the API routines and in some cases their names has changed migrating to the new API will require code modifications To ensure that these modifications are minimal the new API routines allow users to provide NULL as the argument to many of the parameters for which there are reasonable defaults Thus we expect the migration to the new API will be rather straightforward as long as the application does not want to take advantage of the newly added capabilities Operation 4 x routine 5 x routine Partition a graph METIS_PartGraphRecursive METIS_PartGraphRecursive METIS mCPartGraphRecursive M ETIS_WPartGraphRecursive METIS_PartGraphKway METIS_PartGraphKway METIS mCPartGraphkKway METIS_WPartGraphKway METIS PartGraphVkKway METIS WPartGraphVKway Partition a mesh ETIS_PartMeshNodal METIS_PartMeshNodal ETIS_PartMeshDual METIS PartMeshDual Compute a fill reducing ETIS_EdgeND METIS_NodeND ordering of a sparse matrix ETIS_NodeND ETIS_NodeWND
37. odes that two elements must have in order to put an edge between them in the dual graph Given two elements e and ez containing n and na nodes respectively then an edge will connect the vertices in the dual graph corresponding to e and ez if the number of common nodes between them is greater than or equal to min ncommon n 1 ngo 1 The default value is 1 indicating that two elements will be connected via an edge as long as they share one node However this will tend to create too many edges increasing the memory and time requirements of the partitioning The user should select higher values that are better suited for the element types of the mesh that wants to partition For example for tetrahedron meshes ncommon should be 3 which creates an edge between two tets when they share a triangular face i e 3 nodes numflag Used to indicate which numbering scheme is used for eptr and eind The possible values are 0 C style numbering is assumed that starts from 0 1 Fortran style numbering is assumed that starts from 1 xadj adjncy These arrays store the adjacency structure of the generated dual graph The format is of the adjacency structure is described in Section 5 5 Memory for these arrays is allocated by METIS API using the standard malloc function It is the responsibility of the application to free this memory by calling free METIS provides the METIS_F ree that is a wrapper to C s free function METIS_OK Indic
38. of the constraints from romcnum up to and including t ocnum for the partitions starting from frompid up to and including topid will be assigned a target weight of twgt If topid is not supplied then topid frompid If tocnum is not supplied then tocnum fromcnum If fromcnum tocnum then fromcnum 0 and tocnum ncon l If the file does not contain a twgt specification for all the target partition weight constraint combinations then the twgt for the unspecified ones is determined by equally distributing the left over portion of the total weight for each constraint It is important that for each constraint the sum of the specified t wgts values is less than or equal to 1 0 For example assuming that ncon 1 nparts 5 then the following tpwgt s file O l 4 3 specifies the following target partition weights part 0J 2 part 1 2 part 2 15 part 3 15 and part 4 0 3 Note that the 15 fractions for part 2 and part 3 are due to the equal distribution of the left over weight 1 0 7 4 2 Output file formats The output of METIS is either a partition or an ordering file depending on whether METIS is used for graph mesh partitioning or for sparse matrix ordering The format of these files are described in the following sections 4 2 1 Partition file The partition file of a graph with n vertices consists of n lines with a single number per line The th line of the file contains the partition number that the
39. on n 1 n2 1 The default value is 1 indicating that two elements will be connected via an edge as long as they share one node However this will tend to create too many edges increasing the memory and time requirements of the partitioning The user should select higher values that are better suited for the element types of the mesh that wants to partition For example for tetrahedron meshes ncommon should be 3 which creates an edge between two tets when they share a triangular face i e 3 nodes ptype ctype iptype objtype contig minconn tpwets ufactor niter ncuts nooutput seed dbglvl help Similar to the corresponding options of gpmet is Notes The current version of mpmetis supports only single constraint partitioning 15 ndmetis options graphfile Description Computes a fill reducing ordering of the vertices of the graph using multilevel nested dissection The computed ordering is stored in a file named graphfile iperm whose format is described in Section 4 2 2 Parameters graphfile The name of the file that stores the graph to be re ordered Section 4 1 1 Options ctype string Specifies the scheme to be used to match the vertices of the graph during the coarsening The possible values are rm Random matching default shem Sorted heavy edge matching iptype string applies only when ptype rb Specifies the scheme to be used to compute the initial vertex separator of the graph T
40. oros osos e a eS e a 32 METIS MeskToDual crios an a a A eee es 32 METTS MeshToNodal sorae mace nee a a a Bee Y 33 2 1 UUN IQU MES cocos ro ee a ES be a SS 34 METIS DELDEFSUIEONEADOS cocinada id SESS 34 METIS PYS6 Le ee A e we ee a AA E a A 34 System requirements and contact information 35 Copyright license notice 35 1 Introduction Algorithms that find a good partitioning of highly unstructured graphs are critical for developing efficient solutions for a wide range of problems in many application areas on both serial and parallel computers For example large scale numerical simulations on parallel computers such as those based on finite element methods require the distribution of the finite element mesh to the processors This distribution must be done so that the number of elements assigned to each processor is the same and the number of adjacent elements assigned to different processors is minimized The goal of the first condition is to balance the computations among the processors The goal of the second condition is to minimize the communication resulting from the placement of adjacent elements to different processors Graph partitioning can be used to successfully satisfy these conditions by first modelling the finite element mesh by a graph and then partitioning it into equal parts Graph partitioning algorithms are also used to compute fill reducing orderings of sparse matrices These fill reducing orderings are use
41. oth the command line programs and the API routines e Multi constraint partitioning can be used in conjunction with minimization of the total communication volume e All graph and mesh partitioning routines take as input the target sizes of the partitions which among others allow them to compute partitioning solutions that are well suited for parallel architectures with heterogeneous computing capabilities e When multi constraint partitioning is used the target sizes of the partitions are specified on a per partition constraint pair e The multilevel k way partitioning algorithms can compute a partitioning solution in which each partition is contiguous e All partitioning and ordering routines can compute multiple different solutions and select the best as the final solution e The mesh partitioning and mesh to graph conversion routines can operate on mixed element meshes e The command line programs provide full access to the entire set of capabilities provided by METIS API Operation 4 x stand alone program 5 x stand alone program Partition a graph pmetis gpmetis kmetis Partition a mesh partnmesh mpmetis partdmesh Compute a fill reducing oemetis ndmetis ordering of a sparse matrix onmetis Convert a mesh into a graph mesh2nodal m2gmet is mesh2dual Graph format checker graphchk graphchk Table 1 Mapping between the old 4 x and the new 5 x command line programs 2 1 Changes in the command line programs Table
42. part Returns This is a vector of size ne that upon successful completion stores the partition vector for the elements of the mesh The numbering of this vector starts from either 0 or 1 depending on the value of options METIS_OPTION_NUMBERING This is a vector of size nn that upon successful completion stores the partition vector for the nodes of the mesh The numbering of this vector starts from either 0 or 1 depending on the value of options METIS_OPTION_NUMBERING METIS_OK E E IS_ERROR_MI IS_ERROR_INPUT E IS_ERROR Indicates that the function returned normally Indicates an input error EMORY Indicates that it could not allocate the required memory Indicates some other type of error 29 int METIS PartMeshNodal idx_t ne idx_t nn idx_t eptr idx_t eind idx_t vwet idx_t vsize idx_t nparts real_t tpwgts idx_t options idx_t objval idx_t epart idx_t npart Description This function is used to partition a mesh into k parts based on a partitioning of the mesh s nodal graph Parameters ne The number of elements in the mesh nn The number of nodes in the mesh eptr eind The pair of arrays storing the mesh as described in Section 5 6 vwet NULL An array of size nn specifying the weights of the nodes A NULL value can be passed to indicate that all nodes have an equal weight vsize NULL An array of size nn specifying the size of th
43. plays information related to the elimination of connected com ponents Note that the numeric values are provided for use with the dbglv1 option of METIS stand alone pro grams For the API routines it is sufficient to OR the above constants If an application does not want to take advantage of this capability then it can just supply a NULL as the value for that parameter For those applications that will like to modify certain elements of the algorithms METIS provide the METIS_SetDefaultOptions routine to set the options to their default values After that the application can just modify the the options that is interested in modifying This is illustrated as follows idx_t options METIS_NOPTIONS METIS _SetDefaultOptions options options METIS_OPTION_NSEPS 10 options METIS_OPTION_UFACTOR 100 METIS_NodeND options 5 5 Graph data structure All of the graph partitioning and sparse matrix ordering routines in METIS take as input the adjacency structure of the graph and the weights of the vertices and edges if any The adjacency structure of the graph is stored using the compressed storage format CSR The CSR format is a widely used scheme for storing sparse graphs In this format the adjacency structure of a graph with n vertices and m edges is represented using two arrays xadj and adjncy The xadj array is of size n 1 whereas the adjncy array is of size 2m this is because fo
44. r each edge between vertices v and u we actually store both v u and u v The adjacency structure of the graph is stored as follows Assuming that vertex numbering starts from 0 C style then the adjacency list of vertex 2 is stored in array adjncy starting at index xadj z and ending at but not including index xadj i 1 e adjncy xadj 12 through and including adjncy xadj i 1 1 That is for each vertex 2 its adjacency list is stored in consecutive locations in the array adjncy and the array xadj is used to point to where it begins and where it ends Figure 3 b illustrates the CSR format for the 15 vertex graph shown in Figure 3 a 23 3 4 5 1 4 9 10 1 12 1d 14 a A sample graph xadj 025 8 11 13 16 20 24 28 31 33 36 39 42 44 ladjncy 1502613724839061015711268 12379 1348 145 116 10127 11 138 12 149 13 b CSR format Figure 3 An example of the CSR format for storing sparse graphs The weights of the vertices if any are stored in an additional array called vwgt If ncon is the number of weights associated with each vertex the array vwgt contains n ncon elements recall that n is the number of vertices The weights of the ith vertex are stored in ncon consecutive entries starting at location vwgt 1 x ncon Note that if each vertex has only a single weight then vwgt will contain n elements and vwgt 7 will store the weight of the ith vertex The vertex weights must be integers gr
45. r minimizing the totalv are comparable This is especially true for graphs corresponding to well shaped finite element meshes This is because for these graphs the degrees of the various vertices are similar and the objectives of minimizing the edgecut or the totalv behave the same On the other hand if the vertex degrees vary significantly e g graphs corresponding to linear programming matrices then by minimizing the totalv we can obtain a significant reduction in the total communication volume In terms of the amount of time required by these two partitioning objectives minimizing the edgecut is faster than minimizing the totalv For this reason the totalv objective should be used only for problems in which it actually reduces the overall communication volume 25 5 8 Graph partitioning routines int METIS PartGraphRecursive idx_t nvtxs idx_t ncon idx_t xadj idx_t adjncy idx_t vwgt idx_t vsize idx_t adjwgt idx_t nparts real_t tpwegts real_t ubvec idx_t options idx_t objval idx_t part int METIS_PartGraphKway idx_t nvtxs idx_t ncon idx_t xadj idx_t adjncy idx_t vwgt idx_t vsize idx_t adjwgt idx_t nparts real_t tpwgts real_t ubvec idx_t options idx_t objval idx_t part Description Is used to partition a graph into k parts using either multilevel recursive bisection or multilevel k way partition ing Parameters nvtxs The number of vertices in the graph ncon The number of balancing constra
46. rra al eee METIS stand alone programs 4 1 Input tiletormats 2 402044 adepan e E A e a Ss ALI Graphi eo e ew ee OER A ERE ES a See ee bbe bea as AL Mestblle 0 o ok ak Ba ea eA aS BRE eS ee Ea SG He S 15 Tartgetpariton weights fie cocos SEEDS Cow ESSERE ENS AA EH OSS Az Oupa ile formas co ee Re EE ew ee RE ee ee oN al AA ae aed Se Re dE Meee Re ads Re ee a a Ree 422 Ordening De sok a eed ae Se AAAS ES ea Se be oe BS a Re ae a 4 DIOBTAM S soe o Ee eR Ea Ee RA ewe eee he eee bead UPMSCELE pops rra bk eo oe ae a dm Be ee eS MOSES od Se BK as oe BSE pe RR a aU ee Bae CIA ca cb BB Re da Ra E ACE EN MAGQUELTS LA ee ee A a we ol El ee eA ee ae E pa pa sax le Shy dae Se O BAG Te hl tee dy Gee METIS API AN 22 Useor NULL PAr MeiciS 6 ede e a A a E EE Ja Ces and Porta SUPpp op ke eR ia ad eee ee we SA OPONE AMAY co cosa data A e A a AE eG ee Oot E o RN SO Mesh data sucre sao ds a a 37 Pamitomng objectives ss cap e a a a ee ba ee o 5 8 Graph paritioning routes csc Cee pa a A E METIS Par GrapORSCUES TS eo ed re e A ee BLES PareuGraph kway 4 4 ge 5 66 Ree Rd Re ee es of Mesh par tioning FOUEMES ceco s ee ete ee He he eee A g METTES rere MSS a RR a ak ee a Me ee RA METIS PartMeshNodal 045 sas ce ee ee Oe eT Ow we RR we 5 10 Sparse Matrix Reordering Routines s s ee ew ee ee PE DOGS as eae a A A eee eh ee BS 4 hb Ss A N WN 00 00 00 00 1 A Ur Ur Ur Ur amp oO o 3 11 Mesh to sraph Conversion routines
47. set to 1 i e the 2nd bit from right to left then the graph file provides information about the weights of the vertices Finally if the third lest significant bit is set to 1 i e the 3rd bit from right to left then the graph file provides information of the sizes of the vertices For example if fmt is 011 then the graph file provides information about both vertex weights and edge weights Note that when the fmt parameter is not provided it is assumed that the vertex sizes vertex weights and edge weights are all equal to 1 The ncon parameter specifies the number of vertex weights associated with each vertex of the graph The value of this parameter determines whether or not METIS will use the multi constraint partitioning algorithms Section 3 3 If this parameter is omitted then the vertices of the graph are assumed to have a single weight Note that if ncon is greater than 0 then the file should contain the required vertex weights and the fmt parameter should be set appropriately i e the 2nd bit from right to left should be set to 1 The remaining n lines store information about the actual structure of the graph In particular the th line excluding comment lines contains information that is relevant to the th vertex Depending on the value of the fmt and ncon parameters the information stored at each line is somewhat different In the most general form when fmt 11 and ncon gt 1 each line will have the following structure
48. t a few hundred vertices In the initial partitioning phase a partitioning of the coarsest and hence smallest graph is computed using relatively simple approaches such as the algorithm developed by Kernighan Lin 5 Since the coarsest graph is usually very small this step is very fast Finally in the uncoarsening phase the partitioning of the smallest graph is projected to the successively larger graphs by assigning the pairs of vertices that were collapsed together to the same partition as that of their corresponding col lapsed vertex After each projection step the partitioning is refined using various heuristic methods to iteratively move vertices between partitions as long as such moves improve the quality of the partitioning solution The uncoarsening phase ends when the partitioning solution has been projected all the way to the original graph METIS uses novel approaches to successively reduce the size of the graph as well as to refine the partition during the uncoarsening phase During coarsening METIS employs algorithms that make it easier to find a high quality partition at the coarsest graph During refinement METIS focuses primarily on the portion of the graph that is close to the partition boundary These highly tuned algorithms allow METIS to quickly produce high quality partitions and fill reducing orderings for a wide variety of irregular graphs unstructured meshes and sparse matrices Operation Stand alone program API routine
49. t allocate the required memory Indicates some other type of error 27 5 9 Mesh partitioning routines int METIS PartMeshDual idx_t ne idx_t nn idx_t eptr idx_t eind idx_t vwet idx_t vsize Description idx_t ncommon idx_t nparts real_t tpwgts idx_t options idx_t objval idx_t epart idx_t npart This function is used to partition a mesh into k parts based on a partitioning of the mesh s dual graph Parameters ne nn eptr eind The number of elements in the mesh The number of nodes in the mesh The pair of arrays storing the mesh as described in Section 5 6 vwet NULL An array of size ne specifying the weights of the elements A NULL value can be passed to indicate that all elements have an equal weight vsize NULL ncommon nparts An array of size ne specifying the size of the elements that is used for computing the total communi cation volume as described in Section 5 7 A NULL value can be passed when the objective is cut or when all elements have an equal size Specifies the number of common nodes that two elements must have in order to put an edge between them in the dual graph Given two elements e and e2 containing n and na nodes respectively then an edge will connect the vertices in the dual graph corresponding to e and ez if the number of common nodes between them is greater than or equal to min ncommon n 1 n2 1 The default value is 1 indicating that t
50. th on vertices and edges d Multi Constraint Graph Figure 2 Storage format for various type of graphs After the first line the remaining n lines store the element node array In particular for element 2 line 1 stores the ncon integer weights associated with the zth element if the optional ncon parameter has been specified followed by the nodes that this element is made off The weights and nodes are separated by spaces The numbering of the nodes starts from 1 The nodes of each element can be stored in any order The mesh file allows for mixed elements meshes and as such the number of nodes that are supplied in each line can vary 4 1 3 Target partition weights file The graph and mesh partitioning routines take as input an optional file that specifies the target weights of the various partitions using the tpwgts option This file contains a sequence of lines whose format are of the form frompid topid fromcnum tocnum twgt be subsequently edited to include the required weights prior to using gpmet is to partition it 11 where frompid and topid specify partition numbers numbering starting from 0 f romcnum and tocnum specify constraint numbers numbering starting from 0 and twgt is a floating point number specifying a fraction of the total weight 1 e better be lt 1 0 The parts in square brackets indicate optional parts The meaning of the above specification is as follows For each
51. that upon successful completion stores the partition vector for the nodes of the mesh The numbering of this vector starts from either 0 or 1 depending on the value of options METIS_OPTION_NUMBERING METIS_OK Indicates that the function returned normally ETIS_ERROR_INPUT Indicates an input error M METIS_ERRORMEMORY Indicates that it could not allocate the required memory M ETIS_ERROR Indicates some other type of error 30 5 10 Sparse Matrix Reordering Routines int METIS NodeND idx_t nvtxs idx_t xadj idx_t adjncy idx_t vwgt idx_t options idx_t perm idx_t iperm Description This function computes fill reducing orderings of sparse matrices using the multilevel nested dissection algo rithm Parameters nvtxs The number of vertices in the graph xadj adjncy The adjacency structure of the graph as described in Section 5 5 vwet NULL An array of size nvtxs specifying the weights of the vertices If the graph is weighted the nested dissection ordering computes vertex separators that minimize the sum of the weights of the vertices on the separators A NULL can be passed to indicate a graph with equal weight vertices or unweighted options NULL This is the array of options as described in Section 5 4 The following options are valid METIS_OPTION_CTYPE METIS_OPTION_RTYPE METIS_OPTION_NO2HOP METIS_OPTION_NSEPS METIS_OPTION_NITER METIS_OPTION_UFACTOR METIS_OPTION_C
52. very processor have an equal amount of work from each phase of the computation METIS includes partitioning routines that can be used to partition a graph in the presence of such multiple balancing constraints Each vertex is now assigned a vector of m weights and the objective of the partitioning routines is to minimize the edge cut subject to the constraints that each one of the m weights is equally distributed among the domains For example if the first weight corresponds to the amount of computation and the second weight corresponds to the amount of storage required for each element then the partitioning computed by the new algorithms will balance both the computation performed in each domain as well as the amount of memory that it requires The multi constraint partitioning algorithms and their applications are further described in 2 The gomet is program invokes the multi constraint partitioning routines whenever the input graph specifies more that one set of vertex weights and all of its graph partitioning API routines allow for the specification of multiple balancing constraints 3 4 Partitioning a mesh METIS provides the mpmet is program for partitioning meshes arising in finite element or finite volume methods This program take as input the element node array of the mesh and compute a k way partitioning for both its elements and its nodes This program first converts the mesh into either a dual graph i e each element becomes a graph vertex
53. wo elements will be connected via an edge as long as they share one node However this will tend to create too many edges increasing the memory and time requirements of the partitioning The user should select higher values that are better suited for the element types of the mesh that wants to partition For example for tetrahedron meshes ncommon should be 3 which creates an edge between two tets when they share a triangular face i e 3 nodes The number of parts to partition the mesh tpwgts NULL This is an array of size nparts that specifies the desired weight for each partition The target partition weight for the ith partition is specified at tpwgts i the numbering for the partitions starts from 0 The sum of the tpwgts entries must be 1 0 A NULL value can be passed to indicate that the graph should be equally divided among the partitions options NULL objval This is the array of options as described in Section 5 4 The following options are valid 7 METIS_OPTION_PTYPE METIS _OPTION_OBJTYPE ETIS_OPTION_CTYPE METIS_OPTION_IPTYPE ETIS_OPTION_RTYPE METIS_OPTION_NCUTS METIS_OPTION_NITER METIS_OPTION_SEED METIS_OPTION_UFACTOR METIS_OPTION_NUMBERING METIS_OPTION_DBGLVL Upon successful completion this variable stores either the edgecut or the total communication vol ume of the dual graph s partitioning 28 epart n
54. x indicates that the allowed load imbalance is 1 x 1000 The load imbalance for the jth constraint is defined to be max w j 1 t 5 i where w j i is the fraction of the overall weight of the jth constraint that is as signed to the th partition and t j i is the desired target weight of the jth constraint for the ith partition 1 e that specified via tpwgts For ptype rb the default value is 1 1 e load imbalance of 1 001 and for ptype kway the default value is 30 1 e load imbalance of 1 03 22 options METIS_OPTION_DBGLVL Specifies the amount of progress debugging information will be printed during the execution of the algo rithms The default value is O no debugging progress information A non zero value can be supplied that 1s obtained by a bit wise OR of the following values ETIS_DBG_INFO 1 Prints various diagnostic messages ETIS_DBG_TIME 2 Performs timing analysis ETIS_DBG_COARSEN 4 Displays various statistics during coarsening ETIS_DBG_REFINE 8 Displays various statistics during refinement ETIS_DBG_IPART 16 Displays various statistics during initial partitioning ETIS_DBG_MOVEINFO 32 Displays detailed information about vertex moves during refine ment ETIS_DBG_SEPINFO 64 Displays information about vertex separators ETIS_DBG_CONNINFO 128 Displays information related to the minimization of subdomain connectivity ETIS_DBG_CONTIGINFO 256 Dis
Download Pdf Manuals
Related Search