Manual
User Manual:
Open the PDF directly: View PDF .
Page Count: 20
Download | |
Open PDF In Browser | View PDF |
hMETIS∗ A Hypergraph Partitioning Package Version 1.5.3 George Karypis and Vipin Kumar University of Minnesota, Department of Computer Science & Engineering Army HPC Research Center Minneapolis, MN 55455 {karypis, kumar}@cs.umn.edu November 22, 1998 Metis [MEE tis]: 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. ∗ hMETIS is copyrighted by the regents of the University of Minnesota. This work was supported by IST/BMDO through Army Research Office contract DA/DAAH04-93-G-0080, and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities were provided by Minnesota Supercomputer Institute, Cray Research Inc. Related papers are available via WWW at URL: http://www.cs.umn.edu/˜karypis 1 Contents 1 Introduction 3 2 What is hMETIS 2.1 Overview of the Algorithms used in hMETIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 3 hMETIS’s Stand-Alone Programs 3.1 shmetis . . . . . . . . . . . . . 3.2 hmetis . . . . . . . . . . . . . . 3.3 khmetis . . . . . . . . . . . . . 3.4 Format of Hypergraph Input File 3.5 Format of the Fix File . . . . . . 3.6 Format of Output File . . . . . . . . . . . . 4 5 7 8 10 11 11 4 hMETIS’s Library Interface 4.1 HMETIS PartRecursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 HMETIS PartKway . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 11 14 5 General Guidelines on How to Use hMETIS 5.1 Selecting the Proper Parameters . . . . 5.1.1 Effect of the CType Parameter . 5.1.2 Effect of the RType Parameter . 5.2 Computing a k-way Partitioning . . . . 5.2.1 Effect of the Nruns Parameter . 5.2.2 Effect of the Reconst Parameter 15 15 15 16 16 16 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 System Requirements and Contact Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 1 Introduction Hypergraph partitioning is an important problem and has extensive applications in many areas, including VLSI design [2], efficient storage of large databases on disks [13], transportation management, and data-mining [5]. The problem is to partition the vertices of a hypergraph in k roughly equal parts, such that the number of hyperedges connecting vertices in different parts is minimized. A hypergraph is a generalization of a graph, where the set of edges is replaced by a set of hyperedges. A hyperedge extends the notion of an edge by allowing more than two vertices to be connected by a hyperedge. 2 What is hMETIS hMETIS is a software package for partitioning large hypergraphs, especially those arising in circuit design. The algorithms in hMETIS are based on multilevel hypergraph partitioning described in [10, 11, 7], and they are an extension of the widely used METIS graph partitioning package described in [9, 8]. Traditional graph partitioning algorithms compute a partition of a graph by operating directly on the original graph as illustrated in Figure 1(a). These algorithms are often too slow and/or produce poor quality partitions. Multilevel partitioning algorithms, on the other hand, take a completely different approach[6, 9, 8, 10]. These algorithms, as illustrated in Figure 1(b), reduce the size of the graph (or hypergraph) by collapsing vertices and edges (during the coarsening phase), partition the smaller graph (initial partitioning phase), and then uncoarsen it to construct a partition for the original graph (uncoarsening and refinement phase). hMETIS uses novel approaches to successively reduce the size of the hypergraph as well as to further refine the partition during the uncoarsening phase. During coarsening, hMETIS employs algorithms that make it easier to find a high-quality partition at the coarsest graph. During refinement, hMETIS focuses primarily on the portion of the graph that is close to the partition boundary. These highly tuned algorithms allow hMETIS to quickly produce high-quality partitions for a large variety of hypergraphs. Multilevel partitioning algorithms compute a partition at the coarsest graph and then refine the solution! Co Re fin em en tP ha se Traditional partitioning algorithms compute a partition directly on the original graph! n se ar ing e as Ph (a) Initial Partitioning Phase (b) Figure 1: (a) Traditional partitioning algorithms. (b) Multilevel partitioning algorithms. The advantages of hMETIS compared to other similar algorithms are the following: ☞ Provides high quality partitions! Experiments on a large number of hypergraphs arising in various domains including VLSI, databases, and data mining show that hMETIS produces partitions that are consistently better than those produced by other widely used algorithms, such as KL, FM, LA, PROP, CLIP, etc.. ☞ It is extremely fast! Experiments on a wide range of hypergraphs has shown that hMETIS is one to two orders of magnitude faster than other widely used partitioning algorithms. hMETIS can produce extremely high quality bisections of hypergraphs with 100,000 vertices in well under 3 minutes on an R10000-based SGI workstation and a Pentium Pro-based personal computer. 3 2.1 Overview of the Algorithms used in hMETIS In the rest of this section, we briefly describe the various phases of the multilevel algorithm. The reader should refer to [10] for further details. Coarsening Phase During the hypergraph coarsening phase, a sequence of successively smaller hypergraphs is constructed. The purpose of coarsening is to create a small hypergraph, such that a good bisection of the small hypergraph is not significantly worse than the bisection directly obtained for the original hypergraph. In addition to that, hypergraph coarsening also helps in successively reducing the size of the hyperedges. That is, after several levels of coarsening, large hyperedges are contracted to hyperedges connecting just a few vertices. This is particularly helpful, since refinement heuristics based on the Kernighan-Lin algorithm [12, 4] are very effective in refining small hyperedges but are quite ineffective in refining hyperedges with a large number of vertices belonging to different partitions. The group of vertices that are contracted together to form single vertices in the next level coarse hypergraph can be selected in different ways. hMETIS implements various such grouping schemes (also called matching schemes) some of which are described in [10]. Initial Partitioning phase During the initial partitioning phase, a bisection of the coarsened hypergraph is computed. Since this hypergraph has a very small number of vertices (usually less than 100 vertices) many different algorithms can be used without significantly affecting the overall runtime and quality of the algorithm. hMETIS uses multiple random bisections followed by the Fiduccia-Mattheyses(FM) refinement algorithm. Uncoarsening and refinement phase During the uncoarsening phase, the partitioning of the coarsest hypergraph is used to obtain a partitioning for the finer hypergraph. This is done by successively projecting the partitioning to the next level finer hypergraph and using a partitioning refinement algorithm to reduce the cut and thus improve the quality of the partitioning. Since the next level finer hypergraph has more degrees of freedom, such refinement algorithms tend to improve the quality. hMETIS implements a variety of algorithms that are based on the FM algorithm [4]. The details of some of these schemes can be found in [10]. V -Cycle Refinement The idea behind this refinement algorithm is to use the power of the multilevel paradigm to further improve the quality of a bisection. The V -cycle refinement algorithm consists of two phases, namely a coarsening and an uncoarsening phase. The coarsening phase preserves the initial partitioning that is input to the algorithm. We will refer to this as restricted coarsening scheme. In this restricted coarsening scheme, the groups of vertices that are combined to form the vertices of the coarse graphs correspond to vertices that belong only to one of the two partitions. As a result, the original bisection is preserved through out the coarsening process, and becomes the initial partition from which we start performing refinement during the uncoarsening phase. The uncoarsening phase of the V -cycle refinement algorithm is identical to the uncoarsening phase of the multilevel hypergraph partitioning algorithm described earlier. It moves vertices between partitions as long as such moves improve the quality of the bisection. Note that the various coarse representations of the original hypergraph, allow refinement to further improve the quality as it helps it climb out of local minima. 3 hMETIS’s Stand-Alone Programs hMETIS provides the shmetis, hmetis, and khmetis programs that can be used to partition a hypergraph into k parts. The first two programs (shmetis and hmetis) compute a k-way partitioning using multilevel recursive bisection [10]. The shmetis program is suited for those users who want to use hMETIS without getting into the details of the underlying algorithms, while hmetis is suited for those users that want to experiment with the various algorithms used by hMETIS. Both shmetis and hmetis can also compute a k-way partitioning when certain vertices of the hypergraph have preassigned partitions (i.e., there are at most k sets of vertices each fixed to a particular partition). The third program (khmetis) computes a k-way partitioning using multilevel k-way partitioning [8]. This is a new feature of hMETIS 1.5, and the underlying algorithms are still under development. 4 3.1 shmetis The shmetis program is invoked by providing three or four arguments at the command line as follows: shmetis HGraphFile Nparts UBfactor shmetis HGraphFile FixFile Nparts or UBfactor The meaning of the various parameters is as follows: HGraphFile This is the name of the file that stores the hypergraph (the format is described in Section 3.4). FixFile This is the name of the file that stores information about the pre-assignment of vertices to partitions (the format is described in Section 3.5). Nparts This is the number of desired partitions. shmetis can partition a hypergraph into an arbitrary number of partitions, using recursive bisection. That is, for a 4-way partition, shmetis first computes a 2-way partition of the original hypergraph, then constructs two smaller hypergraphs, each corresponding to one of the two partitions, and then computes 2-way partitions of these smaller hypergraphs to obtain the desired 4-way partition1. Note that shmetis, while constructing the smaller hypergraphs, completely removes the hyperedges that were cut during the bisection 2 . UBfactor This parameter is used to specify the allowed imbalance between the partitions during recursive bisection. This is an integer number between 1 and 49, and specifies the allowed load imbalance in the following way. Consider a hypergraph with n vertices, each having a unit weight, and let b be the UBfactor. Then, if the number of desired partitions is two (i.e., we perform a bisection), then the number of vertices assigned to each one of the two partitions will be between (50 − b)n/100 and (50 + b)n/100. For example, for b = 5, then we will be allowing a 45-55 bisection, that is, the number of vertices in each partition will be between 0.45n and 0.55n. Note that this allowed imbalance is applied at each bisection step, so if instead of a 2-way partition we are interested in a 4-way partition, then a UBfactor of 5 will result in partitions that can contain between 0.452n = 0.20n and 0.55 2n = 0.30n vertices. Also note that shmetis does not allow you to produce perfectly balanced partitions. This is a limitation that will be lifted in future releases. Upon successful execution, shmetis displays statistics regarding the quality of the computed partitioning and the amount of time taken to perform the partitioning (the times are shown in seconds). The actual partitioning is stored in a file named HGraphFile.part.Nparts, whose format is described in Section 3.6. Figure 2 shows the output of shmetis for partitioning a hypergraph into four parts. From this figure we see that shmetis initially prints information about the hypergraph, such as its name, the number of vertices (#Vtxs), the number of hyperedges (#Hedges), and also the number of desired partitions (#Parts) and allowed imbalance (UBfactor). Next, prints information about the different bisections that were computed. In this example, since we asked for four partitions, the algorithm computes a total of three bisections, and for each one prints information regarding the size of the hypergraph that is bisected and the quality of the computed bisections. In particular, with respect to quality, it prints the minimum and average number of cuts, and also the balance corresponding to the minimum cut. The overall quality of the obtained partitioning is summarized by computing the following quality measures (in the case of hypergraphs with weighted hyperedges, these definitions are extended in a straight-forward manner): 1. Hyperedge Cut This is the number of the hyperedges that span multiple partitions. The partitioning routines in hMETIS try to directly minimize this quantity. 1 shmetis can handle non-power of 2 partitions, by performing unbalanced bisections. That is, for a 3-way partition it computes a 2-way partition such that the first part has 2/3 of the total number of vertices, and the other part has 1/3. It then it bisects the first part into two equal-size parts, each containing 1/3 of the original number of vertices. 2 The hmetis program allows you to change this behavior. 5 2. Sum of External Degrees The external degree |E(Pi )| of a partition Pi , is defined as the number of hyperedges, that are incident but not fully inside this partition. The sum of the external degrees of a k-way partitioning, is then ki=1 |E(Pi )|. 3. Scaled Cost This is defined as k 1 |E(Pi )| , n(k − 1) i=1 w(Pi ) where w(Pi ) is the sum of the vertex weights of partition Pi (note that if the vertices do not have weights, then w(Pi ) = |Pi |). 4. Absorption This is defined as k |e ∩ Pi | − 1 |e| − 1 i=1 e∈E|e∩P =∅ i where E is the set of hyperedges, |e ∩ Pi | is the number of vertices of hyperedge e that are also in partition Pi , and |e| is the number of vertices in the hyperedge e. ' $ Following these quality measures, shmetis prints the size of the various partitions as well as the external degrees of each partition. Finally, it shows the time taken by the various phases of the algorithm. All times are in seconds. prompt% shmetis ibm02.hgr 4 5 ******************************************************************************* HMETIS 1.5.3 Copyright 1998, Regents of the University of Minnesota HyperGraph Information ----------------------------------------------------Name: ibm02.hgr, #Vtxs: 19601, #Hedges: 19584, #Parts: 4, UBfactor: 0.05 Options: HFC, FM, Reconst-False, V-cycles @ End, No Fixed Vertices Recursive Partitioning... -------------------------------------------------Bisecting a hgraph of size [vertices=19601, hedges=19584, balance=0.50] The mincut for this bisection = 262, (average = 277.8) (balance = 0.46) Bisecting a hgraph of size [vertices=9028, hedges=8501, balance=0.50] The mincut for this bisection = 186, (average = 241.4) (balance = 0.49) Bisecting a hgraph of size [vertices=10573, hedges=10821, balance=0.50] The mincut for this bisection = 192, (average = 193.5) (balance = 0.47) -------------------------------------------------------------------------Summary for the 4-way partition: Hyperedge Cut: 619 (minimize) Sum of External Degrees: 1305 (minimize) Scaled Cost: 4.56e-06 (minimize) Absorption: 19336.20 (maximize) & Partition Sizes & External Degrees: 4669[ 382] 4303[ 276] 5048[ 338] 5581[ 309] Timing Information --------------------------------------------------------Partitioning Time: 73.340sec I/O Time: 0.230sec ******************************************************************************* Figure 2: Output of shmetis for ibm02.hgr and a 4-way partition 6 % 3.2 hmetis The program hmetis is invoked by providing 9 or 10 command line arguments as follows: hmetis HGraphFile Nparts UBfactor Nruns CType RType Vcycle Reconst dbglvl or hmetis HGraphFile FixFile Nparts UBfactor Nruns CType RType Vcycle Reconst dbglvl The meaning of the various parameters is as follows: HGraphFile, FixFile, Nparts, UBfactor The meaning of these parameters is identical to those of shmetis. Nruns This is the number of the different bisections that are performed by hmetis. It is a number greater or equal to one, and instructs hmetis to compute Nruns different bisections, and select the best as the final solution. A default value of 10 is used by shmetis. Section 5.2.1 provides an experimental evaluation of the effect of Nruns in the quality of k-way partitionings. CType This is the type of vertex grouping scheme (i.e., matching scheme) to use during the coarsening phase. It is an integer parameter and the possible values are: 1 Selects the hybrid first-choice scheme (HFC). This scheme is a combination of the first-choice and greedy first-choice scheme described later. This is the scheme used by shmetis. 2 Selects the first-choice scheme (FC). In this scheme vertices are grouped together if they are present in multiple hyperedges. Groups of vertices of arbitrary size are allowed to be collapsed together. 3 Selects the greedy first-choice scheme (GFC). In this scheme vertices are grouped based on the firstchoice scheme, but the grouping is biased in favor of faster reduction in the number of the hyperedges that remain in the coarse hypergraphs. 4 Selects the hyperedge scheme. In this scheme vertices are grouped together that correspond to entire hyperedges. Preference is given to hyperedges that have large weight. 5 Selects the edge scheme. In this scheme pairs of vertices are grouped together if they are connected by multiple hyperedges. You may have to experiment with this parameter to see which scheme works better for the classes of hypergraphs that you are using. Section 5.1.1 provides an experimental evaluation of the various values of CType for a range of hypergraphs. RType This is the type of refinement policy to use during the uncoarsening phase. It is an integer parameter and the possible values are: 1 Selects the Fiduccia-Mattheyses (FM) refinement scheme. This is the scheme used by shmetis. 2 Selects the one-way Fiduccia-Mattheyses refinement scheme. In this scheme, during each iteration of the FM algorithm, vertices are allowed to move only in a single direction. 3 Selects the early-exit FM refinement scheme. In this scheme, the FM iteration is aborted if the quality of the solution does not improve after a relatively small number of vertex moves. Experiments have shown that FM and one-way FM produce better results than early-exit FM. However, early-exit FM is considerably faster, and the overall quality is not significantly worse. Section 5.1.2 provides an experimental evaluation of the various values of RType for a range of hypergraphs. Vcycle This parameter selects the type of V -cycle refinement to be used by the algorithm. It is an integer parameter and the possible values are: 7 0 Does not perform any form of V -cycle refinement. 1 Performs V -cycle refinement on the final solution of each bisection step. That is, only the best of the Nruns bisections are refined using V -cycles. This is the options used by shmetis. 2 Performs V -cycle refinement on each intermediate solution whose quality is equally good or better than the best found so far. That is, as hmetis computes Nruns bisections, for each bisection that matches or improves the best one, it is also further refined using V -cycles. 3 Performs V -cycle refinement on each intermediate solution. That is, each one of the Nruns bisections is also refined using V -cycles. Experiments have shown that the second and third choices offer the best time/quality tradeoffs. If time is not an issue, the fourth choice (i.e., Vcycle = 3) should be used. Reconst This parameter is used to select the scheme to be used in dealing with hyperedges that are being cut during the recursive bisection. It is an integer parameter and the possible values are: 0 This scheme removes any hyperedges that were cut while constructing the two smaller hypergraphs in the recursive bisection step. In other words, once a hyperedge is being cut, it is removed from further consideration. Essentially this scheme focuses on minimizing the number of hyperedges that are being cut. This is the scheme that is used by shmetis. 1 This scheme reconstructs the hyperedges that are being cut, so that each of the two partitions retain the portion of the hyperedge that corresponds to its set of vertices. Section 5.2.2 provides an experimental evaluation of the effect of Reconst in the quality of k-way partitionings. dbglvl This is used to request hMETIS to print debugging information. The value of dbglvl is computed as the sum of codes associated with each option of hmetis. The various options and their values are as follows: 0 Show no additional information. 1 Show information about the coarsening phase. 2 Show information about the initial partitioning phase. 4 Show information about the refinement phase. 8 Show information about the multiple runs. 16 Show additional information about the multiple runs. For example, if we want to see all information about the multiple runs the value of dbglvl should be 8 + 16 = 24. Note that some of the options may generate a lot of output. Use them with caution. Upon successful execution, hmetis displays statistics regarding the quality of the computed partitioning and the amount of time taken to perform the partitioning. The actual partitioning is stored in a file named HGraphFile.part.Nparts, whose format is described in Section 3.6. Figure 3 shows the output of hmetis for a 2-way partition. 3.3 khmetis The khmetis program is invoked by providing 7 command line arguments as follows: khmetis HGraphFile Nparts UBfactor Nruns CType OType Vcycle dbglvl The meaning of the various parameters is as follows: HGraphFile, Nparts, Nruns, CType, Vcycle, dbglvl The meaning of these parameters is identical to those of hmetis. 8 ' prompt% hmetis ibm03.hgr 2 5 10 1 1 3 0 24 ******************************************************************************* HMETIS 1.5.3 Copyright 1998, Regents of the University of Minnesota $ HyperGraph Information ----------------------------------------------------Name: ibm03.hgr, #Vtxs: 23136, #Hedges: 27401, #Parts: 2, UBfactor: 0.05 Options: HFC, FM, Reconst-False, Always V-cycle, No Fixed Vertices Recursive Partitioning... -------------------------------------------------Bisecting a hgraph of size [vertices=23136, hedges=27401, balance=0.50] Cut of trial 0: 979 [0.50] Cut of trial 1: 957 [0.46] Cut of trial 2: 979 [0.50] Cut of trial 3: 982 [0.48] Cut of trial 4: 1010 [0.47] Cut of trial 5: 956 [0.46] Cut of trial 6: 990 [0.50] Cut of trial 7: 957 [0.46] Cut of trial 8: 1142 [0.48] Cut of trial 9: 956 [0.46] The mincut for this bisection = 956, (average = 990.8) (balance = 0.46) -------------------------------------------------------------------------Summary for the 2-way partition: Hyperedge Cut: 956 (minimize) Sum of External Degrees: 1912 (minimize) Scaled Cost: 7.18e-06 (minimize) Absorption: 27029.76 (maximize) & Partition Sizes & External Degrees: 12419[ 956] 10717[ 956] Timing Information --------------------------------------------------------Partitioning Time: 85.190sec I/O Time: 0.280sec ******************************************************************************* Figure 3: Output of hmetis for ibm03.hgr and a 2-way partition % UBfactor This parameter is used to specify the allowed imbalance between the k partitions. This is an integer greater than 5 and specifies the allowed load imbalance as follows. A value of b for UBfactor indicates that the weight of the heaviest partition should not be more than b% greater than the average weight. For example, for b = 8, k = 5, and a hypergraph with n vertices (each having unit vertex weight), the weight of the heaviest partition will be bounded from above by 1.08 ∗ n/5. Note that this specification of the allowed imbalance between the k partitions is different from the specification used by either shmetis or hmetis. OType This determines which objective function the refinement algorithm tries to minimize. It is an integer parameter and the possible values are: 1 Minimizes the hyperedge cut. 2 Minimizes the sum of external degrees (SOED). This feature was introduced with version 1.5.3. Upon successful execution, khmetis displays statistics regarding the quality of the computed partitioning and the amount of time taken to perform the partitioning. The actual partitioning is stored in a file named HGraphFile.part.Nparts, whose format is described in Section 3.6. Figure 4 shows the output of khmetis for a 10-way partitioning. 9 ' prompt% khmetis ibm04.hgr 10 10 10 1 1 2 24 ******************************************************************************* HMETIS 1.5.3 Copyright 1998, Regents of the University of Minnesota $ HyperGraph Information ----------------------------------------------------Name: ibm04.hgr, #Vtxs: 27507, #Hedges: 31970, #Parts: 10, UBfactor: 1.10 Options: HFC, Cut-minimization, V-cycle for Min K-way Partitioning... -----------------------------------------------------Partitioning a hgraph of size [vertices=27507, hedges=31970, balance=1.10] Cut/SOED of trial 0: 3259 7333 [1.10] Cut/SOED of trial 1: 3498 7946 [1.09] Cut/SOED of trial 2: 3397 7728 [1.10] Cut/SOED of trial 3: 3192 7242 [1.10] Cut/SOED of trial 4: 3277 7283 [1.10] Cut/SOED of trial 5: 3314 7555 [1.07] Cut/SOED of trial 6: 3390 7554 [1.10] Cut/SOED of trial 7: 3414 7723 [1.06] Cut/SOED of trial 8: 3307 7357 [1.10] Cut/SOED of trial 9: 3322 7433 [1.10] The mincut for this partitioning = 3192, (average = 3337.0) (balance = 1.10) -------------------------------------------------------------------------Summary for the 10-way partition: Hyperedge Cut: 3192 (minimize) Sum of External Degrees: 7242 (minimize) Scaled Cost: 1.06e-05 (minimize) Absorption: 30250.46 (maximize) & Partition Sizes & External Degrees: 2504[ 701] 2796[ 515] 2728[ 634] 2686[ 794] 2662[ 549] 2706[ 740] 2836[1092] 2906[ 508] 3020[1007] 2663[ 702] Timing Information --------------------------------------------------------Partitioning Time: 136.720sec I/O Time: 0.310sec ******************************************************************************* Figure 4: Output of khmetis for ibm04.hgr and a 10-way partition % Note that khmetis should never be used to compute a bisection (i.e., 2-way partitioning) as it produces worse results than hmetis. Furthermore, the quality of the partitionings produced by khmetis for small values of k will be worse, in general, than the corresponding partitionings computed by hmetis. However, khmetis is particularly useful for computing k-way partitionings for relatively large values of k, as it often produces better partitionings and it can also enforce tighter balancing constraints. 3.4 Format of Hypergraph Input File The primary input of hMETIS is the hypergraph to be partitioned. This hypergraph is stored in a file and is supplied to hMETIS as one of the command line parameters. A hypergraph H = (V, E h ) with V vertices and E h hyperedges is stored in a plain text file that contains |E h | + 1 lines, if there are no weights on the vertices and |E h | + |V | + 1 lines if there are weights on the vertices. Any line that starts with ‘%’ is a comment line and is skipped. The first line contains either two or three integers. The first integer is the number of hyperedges (|E h |), the second is the number of vertices (|V |), and the third integer (fmt) contains information about the type of the hypergraph. In particular, depending on the value of fmt, the hypergraph H can have weights on either the hyperedges, the vertices, or both. In the case that H is unweighted (i.e., all the hyperedges and vertices have the same weight), fmt is omitted. 10 After this first line, the remaining |E h | lines store the vertices contained in each hyperedge–one line per hyperedge. In particular, the i th line (excluding comment lines) contains the vertices that are included in the (i −1)th hyperedge. This format is illustrated in Figure 5(a). Weighted hyperedges are specified as shown in Figure 5(b). The first integer in each line contains the weight of the respective hyperedge. Note, hyperedge weights are integer quantities. Furthermore, note that the fmt parameter is equal to 1, indicating the fact that H has weights on the hyperedges. Finally, weights on the vertices are also allowed, as illustrated in Figure 5(c). In this case, |V | lines are appended to the input file containing the weight of the |V | vertices. Note that the value of fmt is equal to 10. As was the case with hyperedge weights, vertex weights are integer quantities. Figure 5(d) shows the case when both the hyperedges and the vertices are weighted. fmt in this case is equal to 11. Figure 5 shows the HGraphFile expected by hMETIS for the example hypergraphs shown in the figure. It shows the four cases in which the hypergraph is unweighted, has weighted hyperedges, has weighted vertices and has both hyperedges and vertices weighted. The hypergraph shown in Figure 5(a) has four unweighted hyperedges a, b, c, and d. Number of vertices in the hypergraph is 7. When the hypergraph is unweighted, first line of the HGraphFile contains two integers denoting the number of hyperedges and the number of the vertices in the hypergraph. After that, each line corresponds to a hyperedge containing an entry for each vertex in the hyperedge. Hypergraph shown in Figure 5(b) has hyperedge weights equal to 2, 3, 7, and 8 on each of the hyperedge a, b, c, and d respectively. For this weighted hyperedges first line of the HGraphFile consists of three integers. Third integer specify that the hyperedges are weighted and is equal to 1. Each line corresponding to each hyperedge, has first entry equal to its weight. The following entries corresponds to the vertices in the respective hyperedge. The case when both the vertices are weighted fmt is equal to 10, and 7 lines corresponding to the 7 vertices are appended to the input file each containing weight of the respective vertex. This is shown in Figure 5(c). Figure 5(d) shows the case when both the hyperedges and the vertices are weighted. 3.5 Format of the Fix File The FixFile is used to specify the vertices that are pre-assigned to certain partitions. In general, when computing a k-way partitioning, up to k sets of vertices can be specified, such that each set is pre-assigned to one of the k partitions. For a hypergraph with |V | vertices, the FixFile consists of |V | lines with a single number per line. The i th line of the file contains either the partition number to which the i th vertex is pre-assigned to, or -1 if that vertex can be assigned to any partition (i.e., free to move). Note that the partition numbers start from 0. 3.6 Format of Output File The output of hMETIS is a partition file. The partition file of a hypergraph with |V | vertices, consists of |V | lines with a single number per line. The i th line of the file contains the partition number that the i th vertex belongs to. Partition numbers start from 0. If foo.graph is the name of the file storing the hypergraph, the partition for a 2-way partition is stored in a file named foo.graph.part.2. 4 hMETIS’s Library Interface The hypergraph partitioning algorithms in hMETIS can also be accessed directly using the stand-alone library libhmetis.a. This library provides the HMETIS PartRecursive() and HMETIS PartKway() routines. The first routine corresponds to the hmetis whereas the second routine corresponds to the khmetis program. The calling sequences and the description of the various parameters of these routines are as follows: 4.1 HMETIS_PartRecursive HMETIS PartRecursive (int nvtxs, int nhedges, int *vwgts, int *eptr, int *eind, int *hewgts, int nparts, int ubfactor, int *options, int *part, int *edgecut) 11 a a(2) 2 1 1 3 b c(8) GraphFile GraphFile 4 1 1 5 2 4 6 c 7 2 7 5 6 6 4 3 4 4 2 3 8 7 7 1 1 5 2 (a) a 1 a(2) 2 d 5 1 8 1 3 b 3 b(3) 5 3 9 3 3 4 7 9 c(8) 6 c d(7) 5 7 4 7 6 GraphFile 4 7 1 2 1 7 5 6 2 3 5 1 8 7 3 9 3 2 5 8 3 1 2 7 5 6 6 4 3 4 (b) 1 7 d(7) 5 7 4 6 3 b(3) 5 7 2 d GraphFile 4 7 11 2 1 2 3 1 7 5 6 8 5 6 4 7 2 3 4 5 1 8 7 3 9 3 10 5 6 4 4 (c) (d) Figure 5: (a) HGraphFile for unweighted hypergraph, (b) HGraphFile for weighted hyperedges, (c) HGraphFile for weighted vertices, and (d) HGraphFile for weighted hyperedges and vertices 12 nvtxs, nhedges The number of vertices and the number of hyperedges in the hypergraph, respectively. vwgts An array of size nvtxs that stores the weight of the vertices. Specifically, the weight of vertex i is stored at vwgts[i ]. If the vertices in the hypergraph are unweighted, then vwgts can be NULL. eptr, eind Two arrays that are used to describe the hyperedges in the graph. The first array, eptr, is of size nhedges+1, and it is used to index the second array eind that stores the actual hyperedges. Each hyperedge is stored as a sequence of the vertices that it spans, in consecutive locations in eind. Specifically, the i th hyperedge is stored starting at location eind[eptr[i ]] up to (but not including) eind[eptr[i + 1]]. Figure 6 illustrates this format for a simple hypergraph. The size of the array eind depends on the number and type of hyperedges. Also note that the numbering of vertices starts from 0. hewgts An array of size nhedges that stores the weight of the hyperedges. The weight of the i hyperedge is stored at location hewgts[i ]. If the hyperedges in the hypergraph are unweighted, then hewgts can be NULL. nparts The number of desired partitions. ubfactor This is the relative imbalance factor to be used at each bisection step. Its meaning is identical to the UBfactor parameter of shmetis, and hmetis described in Section 3. options part This is an array of 9 integers that is used to pass parameters for the various phases of the algorithm. If options[0]=0 then default values are used. If options[0]=1, then the remaining elements of options are interpreted as follows: options[1] Determines the number of different bisections that is computed at each bisection step of the algorithm. Its meaning is identical to the Nruns parameter of hmetis (described in Section 3.2). options[2] Determines the scheme to be used for grouping vertices during the coarsening phase. Its meaning is identical to the CType parameter of hmetis (described in Section 3.2). options[3] Determines the scheme to be used for refinement during the uncoarsening phase. Its meaning is identical to the RType parameter of hmetis (described in Section 3.2). options[4] Determines the scheme to be used for V -cycle refinement. Its meaning is identical to the Vcycle parameter of hmetis (described in Section 3.2). options[5] Determines the scheme to be used for reconstructing hyperedges during recursive bisections. Its meaning is identical to the Reconst parameter of hmetis (described in Section 3.2). options[6] Determines whether or not there are sets of vertices that need to be pre-assigned to certain partitions. A value of 0 indicates that no pre-assignment is desired, whereas a value of 1 indicates that there are sets of vertices that need to be pre-assigned. In this later case, the parameter part is used to specify the partitions to which vertices are pre-assigned. In particular, part[i] will store the partition number that vertex i is pre-assigned to , and −1 if it is free to move. options[7] Determines the random seed to be used to initialize the random number generator of hMETIS. A negative value indicates that a randomly generated seed should be used (default behavior). options[8] Determines the level of debugging information to be printed by hMETIS. Its meaning is identical to the dbglvl parameter of hmetis (described in Section 3.2). The default value is 0. This is an array of size nvtxs that returns the computed partition. Specifically, part[i ] contains the partition number in which vertex i belongs to. Note that partition numbers start from 0. Note that if options[6] = 1, then the initial values of part are used to specify the vertex pre-assignment requirements. 13 a 2 Hyperedges d 0, 2 0 5 0, 1, 3, 4 3, 4, 6 2, 5, 6 b 4 1 6 3 c eptr: 0 2 6 9 12 eind: 0 2 0 1 3 4 3 4 6 2 5 6 Figure 6: The eptr and eind arrays that are used to describe the hyperedges of the hypergraph. edgecut 4.2 This is an integer that returns the number of hyperedges that are being cut by the partitioning algorithm. HMETIS_PartKway HMETIS PartKway (int nvtxs, int nhedges, int *vwgts, int *eptr, int *eind, int *hewgts, int nparts, int ubfactor, int *options, int *part, int *edgecut) nvtxs, nhedges, vwgt, eptr, eind, hewgts, nparts The meaning of these parameters is identical to meaning of the corresponding parameters of HMETIS PartRecursive. ubfactor This is the maximum load imbalance allowed in the k-way partitioning. Its meaning is identical to the UBfactor parameter of khmetis, Section 3.3. options part This is an array of 9 integers that is used to pass parameters for the various phases of the algorithm. If options[0]=0 then default values are used. If options[0]=1, then the remaining elements of options are interpreted as follows: options[1] Determines the number of different k-way partitionings that is computed. Its meaning is identical to the Nruns parameter of khmetis (described in Section 3.3). options[2] Determines the scheme to be used for grouping vertices during the coarsening phase. Its meaning is identical to the CType parameter of khmetis (described in Section 3.3). options[3] Determines which objective function the partitioning algorithm tries to minimize. Its meaning is identical to the OType parameter of khmetis (described in Section 3.3). The default value is 1 (i.e., minimize the hyperedge cut). options[4] Determines the scheme to be used for V -cycle refinement. Its meaning is identical to the Vcycle parameter of khmetis (described in Section 3.3). options[5] Not used. options[6] Not used. options[7] Determines the random seed to be used to initialize the random number generator of hMETIS. A negative value indicates that a randomly generated seed should be used (default behavior). options[8] Determines the level of debugging information to be printed by hMETIS. Its meaning is identical to the dbglvl parameter of khmetis (described in Section 3.3). The default value is 0. This is an array of size nvtxs that returns the computed partition. Specifically, part[i ] contains the partition number in which vertex i belongs to. Note that partition numbers start from 0. 14 edgecut This is an integer that depending on the value of options[3] returns either the number of hyperedges that are being cut by the partitioning algorithm or the sum of the external degrees of the partitioning. 5 General Guidelines on How to Use hMETIS 5.1 Selecting the Proper Parameters The hmetis program allows you to control the multilevel hypergraph bisection paradigm by providing a variety of algorithms for performing the various phases. In particular, it allows you to control: 1. How the vertices are grouped together during the coarsening phase. This is done by using the CType parameter. 2. How the quality of the bisection is refinement during the uncoarsening phase. This is done by using the RType parameter. In designing the shmetis program, we had to make some choices for the above parameters. However, depending on the classes of the hypergraphs that are partitioned, these default settings may not necessarily be optimal. You should experiment with these parameters to see which schemes work better for your classes of problems. In this section, we present an experimental evaluation of the various choices for CType and RType for various hypergraphs taken from the circuits of the ACM/SIGDA [3] and ISPD98 [1] benchmarks. The characteristics of these circuits are shown in Table 1. We hope that these experiments will help in illustrating the various quality and/or runtime trade-offs that are present in the various choices. Circuit avqsmall avqlarge industry2 industry3 s35932 s38417 s38584 golem3 ibm01 ibm03 ibm05 ibm07 ibm09 ibm11 ibm13 ibm15 ibm17 No. of Vertices (i.e., cells + pins) 21918 25178 12637 15406 18148 23949 20995 103048 12752 23136 29347 45926 53395 70558 84199 161570 185495 No. of Hyperedges (i.e., nets) 22124 25384 13419 21923 17828 23843 20717 144949 14111 27401 28446 48117 60902 81454 99666 186608 189581 Table 1: The characteristics of the various circuits used in the study of the various parameters of hMETIS. 5.1.1 Effect of the CType Parameter Table 2 shows the quality of the bisections produced by hmetis for different vertex grouping schemes. The experiments in this table were performed by setting the remaining parameters of hmetis as follows: Nruns = 20, UBfactor = 5, RType = 1, Vcycle = 1, and Reconst = 0. For each different vertex grouping scheme, the column labeled “Min” shows the minimum cut out of the 20 trials, the column labeled “Avg” shows the average cut over all 20 trials, and the column labeled “Time” shows the overall amount of time required by hmetis (i.e., the time to perform the 20 trials and the final V -cycle refinement). As we can see from this table, different vertex grouping schemes perform better for different circuits. In general, the HFC scheme (that is used by default in shmetis) performs reasonably well for all the circuits (i.e., it is within a few percentage points of the best scheme), but it is not necessarily the best. As this table suggests, one should experiment 15 with the different vertex grouping schemes, to determine which one is suited for the classes of problems that she/he may have. 5.1.2 Effect of the RType Parameter Table 3 shows the quality of the bisections produced by hmetis for different refinement schemes. The experiments in this table were performed by setting the remaining parameters of hmetis as follows: Nruns = 20, UBfactor = 5, CType = 1, Vcycle = 1, and Reconst = 0. For each different refinement scheme, the column labeled “Min” shows the minimum cut out of the 20 trials, the column labeled “Avg” shows the average cut over all 20 trials, and the column labeled “Time” shows the overall amount of time required by hmetis (i.e., the time to perform the 20 trials and the final V -cycle refinement). As we can see from this table, the three refinement schemes offer different quality/time trade-offs. In general, the EEFM scheme requires half the time required by either the FM or the 1WayFM schemes. Moreover, the quality of the bisections produced by EEFM, are in general only slightly worse (if any) than those produced by FM or 1WayFM. For example, in the 17 circuits of Table 3, EEFM performed significantly worse than the other two schemes only for ibm15. From the remaining two refinement schemes, the results of Table 3 suggest that they perform similarly with 1wayFM producing slightly better results and requiring somewhat less time. 5.2 Computing a k-way Partitioning hMETIS can compute a k-way partitioning (for k > 2) using either the multilevel recursive bisection paradigm (implemented by hmetis) or the multilevel k-way partitioning paradigm (implemented by khmetis). In our discussion of khmetis (Section 3.3), we already provided some general guidelines as to when someone should use hmetis or khmetis. In general, when k is large (e.g., k > 16) khmetis should be preferred over hmetis, as it is faster and enforces load imbalance constraints that are more natural than the bisection imbalance constraints enforced by hmetis. In this section we focus our discussion on using hmetis to compute a k-way partitioning. In particular, besides the CType and RType parameters discussed in Section 5.1, the quality of the resulting k-way partitioning also depends on the choice of the Nruns and Reconst parameters. 5.2.1 Effect of the Nruns Parameter Recall from Section 3.2, that Nruns is the number of different bisections that are computed by hmetis during each recursive bisection level. Out of these Nruns bisections, the one with the smallest cut is selected and used to bisect the hypergraph. For example, if Nruns = 20, then in the case of a 4-way partitioning, hmetis will first compute 20 bisections of the original hypergraph, and split it into two sub-hypergraphs based on the best bisection. Then, it will compute 20 bisections of each one of the two sub-hypergraphs, and again select the best solution for each one of the two sub-hypergraphs. However, an alternate approach of computing the 4-way partitioning (using the same overall number of different bisections), is to set Nruns = 5, run hmetis four times, and select the best 4-way partition out of these four solutions. That is, instead of running hmetis xxx.hgr 4 5 20 1 1 1 0 0 we can run hmetis hmetis hmetis hmetis xxx.hgr xxx.hgr xxx.hgr xxx.hgr 4 4 4 4 5 5 5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 and select the best solution. The overall amount of time for both approaches should be comparable (even though the second approach will be somewhat slower as the amount of time it spends in V -cycle refinement is four times higher). However, the quality of the solution obtained from the second approach may be better. 16 17 Circuit avqsmall avqlarge industry2 industry3 s35932 s38417 s38584 golem3 ibm01 ibm03 ibm05 ibm07 ibm09 ibm11 ibm13 ibm15 ibm17 Min 127 127 163 255 43 49 48 1333 181 956 1715 851 638 960 869 2624 2248 HFC, CType=1 Avg Time 145.2 70.48 152.2 90.69 217.2 67.8 267.1 97.46 43.6 46.18 51.8 59.83 49.0 66.45 1357.2 749.55 214.2 74.66 1017.3 216.21 1809.7 321.89 948.1 626.45 704.9 484.33 1159.2 848.06 930.2 939.98 3058.1 2459.89 2371.5 2643.27 Min 131 127 183 249 43 50 48 1336 180 952 1723 876 637 960 861 2625 2220 FC, CType=2 Avg Time 157.4 81.27 159.8 93.41 224.1 68.66 265.9 106.74 43.4 46.81 51.5 61.96 48.6 66.68 1354.5 805.76 193.0 78.58 1022.4 223.65 1792.0 300.06 996.6 569.90 694.1 474.96 1051.5 741.36 897.9 1002.63 2932.7 2059.90 2317.1 2536.81 Min 127 127 162 254 73 49 48 1339 181 978 1738 853 629 965 833 2753 2324 GFC, CType=3 Avg Time 145.6 67.93 133.9 78.24 212.5 60.38 273.8 85.78 73.0 41.69 51.4 55.88 50.0 63.69 1420.2 900.33 241.7 74.28 1153.4 209.34 1808.0 355.94 948.1 603.37 675.5 412.91 1184.8 744.90 935.1 1073.89 3488.4 1903.85 2507.7 2358.99 HEDGE, CType=4 Min Avg Time 127 163.8 111.52 127 163.5 134.92 172 226.4 75.91 255 274.9 121.38 43 51.4 61.50 50 69.8 90.20 48 56.6 91.68 1485 1846.5 1518.37 181 252.5 93.26 962 1045.0 295.90 1747 1856.6 474.70 896 980.2 634.90 636 770.0 597.89 1007 1197.2 1168.02 836 1063.3 1304.32 2676 3190.6 2732.28 2254 2457.4 2848.69 EDGE, CType=5 Min Avg Time 127 174.3 96.99 127 181.5 105.65 170 228.7 70.85 255 289.2 109.94 41 47.2 48.43 50 74.5 79.03 48 59.4 75.26 1642 2159.7 1582.20 181 194.7 69.47 961 1051.3 283.78 1784 1892.5 434.22 852 914.0 629.22 648 718.2 554.23 982 1221.1 925.57 834 987.4 1115.54 2732 3241.8 2609.96 2295 2487.6 2985.52 Table 2: The performance achieved by different vertex grouping schemes (i.e., different values of CType). All the results correspond to bisections computed by hmetis with Nruns = 20, UBfactor = 5, RType = 1, Vcycle = 1, and Reconst = 0. All times are in seconds on a Pentium Pro @ 200 Mhz Circuit avqsmall avqlarge industry2 industry3 s35932 s38417 s38584 golem3 ibm01 ibm03 ibm05 ibm07 ibm09 ibm11 ibm13 ibm15 ibm17 Min 127 127 163 258 43 49 48 1334 181 955 1723 840 637 960 859 2625 2218 FM, RType=1 Avg Time 154.2 69.97 149.5 88.99 212.3 62.04 274.6 97.14 43.4 47.53 51.4 62.14 49.2 65.39 1352.1 704.96 215.8 70.91 1015.5 206.15 1804.2 337.72 935.9 547.09 729.6 488.04 1122.9 778.80 944.3 1080.43 2975.0 2737.74 2406.9 3585.65 1wayFM, RType=2 Min Avg Time 127 148.1 71.55 127 150.1 82.69 165 219.4 64.13 257 277.2 94.30 43 43.5 51.00 49 51.1 64.50 48 48.6 70.95 1333 1350.0 683.02 180 226.9 64.84 956 1010.8 173.65 1699 1765.8 276.10 842 933.9 506.66 629 699.8 477.79 960 1096.7 690.31 851 963.4 755.76 2625 3044.8 2258.74 2239 2380.7 3239.31 Min 127 127 162 241 43 49 47 1336 181 956 1710 855 629 962 832 2856 2218 EEFM, RType=3 Avg Time 143.8 55.51 147.9 61.67 214.8 50.41 271.2 76.88 43.5 38.19 52.2 44.54 48.1 51.84 1359.8 519.59 220.4 48.48 1034.8 143.51 1791.9 195.41 966.9 299.25 691.7 289.51 1103.0 435.30 1029.8 633.73 3082.4 1593.12 2383.4 2181.86 Table 3: The performance achieved by different refinement schemes (i.e., different values of RType). All the results correspond to bisections computed by hmetis with Nruns = 20, UBfactor = 5, CType = 1, Vcycle = 1, and Reconst = 0. All times are in seconds on a Pentium Pro @ 200 Mhz Table 4 shows the quality of the 4- and 8-way partitionings produced by the above two approaches. As we can see from this table, the second approach performs better in 16 cases, worse in 10 cases, and similarly for the remaining 8 cases. Circuit avqsmall avqlarge industry2 industry3 s35932 s38417 s38584 golem3 ibm01 ibm03 ibm05 ibm07 ibm09 ibm11 ibm13 ibm15 ibm17 4-way Nruns=20 4×Nruns=5 228 228 228 228 372 355 775 744 111 111 99 95 131 129 2217 2224 496 501 1686 1687 3081 3062 2234 2183 1709 1708 2331 2368 1663 1740 5167 5190 5442 5385 8-way Nruns=20 4×Nruns=5 370 370 372 372 636 644 1546 1502 163 163 162 151 203 205 2872 2856 758 742 2392 2410 4468 4449 3280 3255 2606 2638 3503 3445 2858 2727 6833 6324 8723 8870 Table 4: The performance achieved for a k-way partitionings using a single k-way partitioning with Nruns = 20, and four k-way partitionings with Nruns = 5. 5.2.2 Effect of the Reconst Parameter Recall from Section 3.2, that the Reconst parameter controls how a hyperedge that is part of the cut is reconstructed in the sub-hypergraphs during recursive bisection. In particular, if Reconst = 0, then a hyperedge that is part of the cut is removed entirely from the sub-hypergraphs, and if Reconst = 1, then the hyperedge is reconstructed in each sub-hypergraph. This is done by creating two hyperedges (one for each partition), that span the vertices of the original hyperedge that are assigned to each partition. 18 The choice for the Reconst parameter can affect the quality and runtime of the k-way partitioning. In particular, if Reconst = 0, then the partitioning algorithm will run faster (as successive hypergraphs will have fewer hyperedges), and if Reconst = 1, then the partitioning algorithm can potentially do a better job in reducing the sum of external degrees (SOED) of the k-way partitioning. This is illustrated in Table 5 that shows the effect of the Reconst parameter on the cut, SOED, and runtime, for a 4-way partitioning. From this table we can see that Reconst = 0, indeed results in a somewhat faster code, and that Reconst = 1, results in partitionings whose SOED is, in general, smaller. However, what is interesting with the results of Table 5, is that Reconst = 0 results in partitionings that have smaller cut, compared to those obtained by setting Reconst = 1. So, if the objective is to obtain a k-way partitioning that has the smaller cut, one should use Reconst = 0. However, if minimizing the SOED is the primary focus, one may want to use Reconst = 1. Circuit avqsmall avqlarge industry2 industry3 s35932 s38417 s38584 golem3 ibm01 ibm03 ibm05 ibm07 ibm09 ibm11 ibm13 ibm15 ibm17 No Reconstruction Reconst = 0 Cut SOED Time 228 568 111.92 253 605 126.82 381 841 107.47 791 1704 173.45 111 232 72.05 100 224 96.78 130 294 106.35 2222 4613 1162.19 496 1003 124.53 1691 3685 285.15 3023 6701 459.12 2212 4670 786.26 1691 3485 790.61 2339 4778 1155.37 1738 3770 1365.23 5103 10815 3339.88 5398 11041 4420.78 With Reconstruction Reconst = 1 Cut SOED Time 246 567 118.28 257 569 137.67 429 884 110.56 821 1647 179.89 111 226 72.07 109 228 99.70 138 291 111.90 2239 4519 1226.58 498 998 128.04 1717 3573 301.55 3119 6611 532.71 2253 4579 850.59 1768 3579 774.53 2412 4862 1198.74 1755 3604 1398.37 5299 10844 3069.92 5421 10984 4854.22 Table 5: The performance achieved for a 4-way partitionings using different settings for the Reconst parameter. All the results correspond to 4-way partitioning computed by hmetis with Nruns = 20, UBfactor = 5, CType = 1, RType = 1, and Vcycle = 1. All times are in seconds on a Pentium Pro @ 200 Mhz 6 System Requirements and Contact Information hMETIS has been written in C and it has been extensively tested on Sun, SGI, Linux, and IBM. Even though, hMETIS contains no known bugs, it does not mean that it is bug free. If you find any problems, please send email to metis@cs.umn.edu with a brief description of the problem. Also, any future updates to hMETIS will be made available on WWW at http://www.cs.umn.edu/˜metis. References [1] Chalres Alpert. The ISPD98 circuit benchmark suite. In Proc. Intl. Symposium of Physical Design, 1998. [2] Charles J. Alpert and Andrew B. Kahng. Recent directions in netlist partitioning. Integration, the VLSI Journal, 19(1-2):1–81, 1995. [3] F. Brglez. ACM/SIGDA design automation benchmarks: Catalyst or anathema? IEEE Design & Test, 10(3):87– 91, 1993. Available on the WWW at http://vlsicad.cs.ucla.edu/˜cheese/benchmarks.html. [4] C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175–181, 1982. 19 [5] Eui-Hong Han, George Karypis, Vipin Kumar, and Bamshad Mobasher. Clustering based on association rule hypergraphs. In Proc. of Workshop on Research Issues on Data Mining and Knowledge Discovery, 1997. [6] Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993. [7] G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. Technical Report TR 98-036, Department of Computer Science, University of Minnesota, 1998. [8] G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96–129, 1998. Also available on WWW at URL http://www.cs.umn.edu/˜karypis. [9] G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998 (to appear). Also available on WWW at URL http://www.cs.umn.edu/˜karypis. A short version appears in Intl. Conf. on Parallel Processing 1995. [10] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partitioning: Application in vlsi domain. In Proceedings of the Design and Automation Conference, 1997. [11] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 1998 (to appear). A short version appears in the proceedings of DAC 1997. [12] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291–307, 1970. [13] S. Shekhar and D. R. Liu. Partitioning similarity graphs: A framework for declustering problmes. Technical Report TR 94–18, University of Minnesota, Department of Computer Science, Minneapolis, MN, 1994. Accepted in Information Systems Journal. 20
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.2 Linearized : Yes Create Date : 2001:04:11 15:04:15 Producer : Acrobat Distiller 4.05 for Windows Modify Date : 2001:04:11 15:04:15-07:00 Page Count : 20EXIF Metadata provided by EXIF.tools