Cevdet Aykanat
email: aykanat@cs.bilkent.edu.tr

B Barla Cambazoglu

Bora Uçar

Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices 1

Keywords: hypergraph partitioning, multi-level paradigm, recursive bisection, direct k-way refinement, multi-constraint, fixed vertices

K-way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct K-way refinement, instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct K-way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning.

1 Introduction

Motivation

In the literature, combinatorial models based on hypergraph partitioning are proposed for various complex and irregular problems arising in parallel scientific computing [START_REF] Aykanat | Permuting sparse rectangular matrices into block-diagonal form[END_REF][START_REF] Cambazoglu | Hypergraph-partitioning-based remapping models for image-space-parallel direct volume rendering of unstructured grids[END_REF][START_REF] ¸atalyürek | Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication[END_REF][START_REF] Dingle | Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models[END_REF][START_REF] Uçar | Revisiting hypergraph models for sparse matrix partitioning[END_REF][START_REF] Vastenhouw | A two-dimensional data distribution method for parallel sparse matrix-vector multiplication[END_REF], VLSI design [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF][START_REF] Lengauer | Combinatorial Algorithms for Integrated Circuit Layout[END_REF], software engineering [START_REF] Bisseling | Partitioning a call graph[END_REF], and database design [START_REF] Demir | Clustering spatial networks for aggregate query processing: a hypergraph approach[END_REF][START_REF] Demir | A link-based storage scheme for efficient aggregate query processing on clustered road networks[END_REF][START_REF] Koyuturk | Iterative-improvement-based declustering heuristics for multi-disk databases[END_REF][START_REF] Liu | A hypergraph based approach to declustering problems[END_REF][START_REF] Shekhar | Efficient join-index-based spatialjoin processing: a clustering approach[END_REF]. These models formulate an original problem as a hypergraph partitioning problem, trying to optimize a certain objective function (e.g., minimizing the total volume of communication in parallel volume rendering, optimizing the placement of circuitry on a dice area, minimizing the access to disk pages in processing GIS queries) while maintaining a constraint (e.g., balancing the computational load in a parallel system, using disk page capacities as an upper bound in data allocation) imposed by the problem. In general, the solution quality of the hypergraph partitioning problem directly relates to the formulated problem. Hence, efficient and effective hypergraph partitioning algorithms are important for many applications.

Definitions

A hypergraph H = (V, N ) consists of a set of vertices V and a set of nets N [START_REF] Berge | Graphs and Hypergraphs[END_REF]. Each net n j ∈ N connects a subset of vertices in V. The set of vertices connected by a net n j are called its pins and denoted as P ins(n j ). The size of a net n j is equal to the number of its pins, that is, s(n j ) = |P ins(n j )|. A cost c(n j ) is associated with each net n j . The nets connecting a vertex v i are called its nets and denoted as Nets(v i ). The degree of a vertex v i is equal to the number of its nets, that is, d(v i ) = |Nets(v i )|. A weight w(v j ) is associated with each vertex v i . In case of multi-constraint partitioning, multiple weights w 1 (v i ), w 2 (v i ), . . . , w T (v i ) may be associated with a vertex v i , where T is the number of constraints. Π = {V 1 , V 2 , . . . , V K } is a K-way vertex partition if each part V k is non-empty, parts are pairwise disjoint, and the union of parts gives V. In Π, a net is said to connect a part if it has at least one pin in that part. The connectivity set Λ j of a net n j is the set of parts connected by n j . The connectivity λ j = |Λ j | of a net n j is equal to the number of parts connected by n j . If λ j = 1, then n j is an internal net. If λ j > 1, then n j is an external net and is said to be cut.

The K-way hypergraph partitioning problem (e.g., see [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF]) is defined as finding a vertex partition Π = {V 1 , V 2 , . . . , V K } for a given hypergraph H = (V, N ) such that a partitioning objective defined over the nets is optimized while a partitioning constraint is maintained.

In general, the partitioning objective is to minimize a cost function defined over the cut nets. Frequently used cost functions [START_REF] Lengauer | Combinatorial Algorithms for Integrated Circuit Layout[END_REF] include the cut-net metric cutsize(Π) = n j ∈Ncut c(n j ), [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF] where each cut net incurs its cost to cutsize(Π), and the connectivity-1 metric

cutsize(Π) = n j ∈Ncut c(n j )(λ j -1), (2)
where each cut net n j incurs a cost of c(n j )(λ j -1) to cutsize(Π). In Eqs. 1 and 2, N cut denotes the set of cut nets. In this work, we use the connectivity-1 metric.

Typically, the partitioning constraint is to maintain one or more balance constraints on the part weights. A partition Π is said to be balanced if each part V k satisfies the balance criteria

W t (V k ) ≤ (1 + ǫ t )W t avg ,
for k = 1, 2, . . . , K and t = 1, 2, . . . , T.

In Eq. 3, for the t-th constraint, each weight W t (V k ) of a part V k is defined as the sum of the weights w t (v i ) of the vertices in that part, W t avg is the weight that each part must have in the case of perfect balance, and ǫ t is the maximum imbalance ratio allowed. In case of hypergraph partitioning with fixed vertices [START_REF] Alpert | Hypergraph partitioning with fixed vertices[END_REF], there is an additional constraint on part assignment of some vertices, i.e., a number of vertices are assigned to parts prior to partitioning with the condition that, at the end of the partitioning, those vertices will remain in the part that they are assigned to.

Issues in hypergraph partitioning

The hypergraph partitioning problem is known to be NP-hard [START_REF] Lengauer | Combinatorial Algorithms for Integrated Circuit Layout[END_REF], and the algorithms used in partitioning a hypergraph are heuristics. Consequently, the partitioning algorithms must be carefully designed and implemented for increasing the quality of the optimization. At the same time, the computational overhead due to the partitioning process should be minimized in case this overhead is a part of the entire cost to be minimized (e.g., the duration of preprocessing within the total run-time of a parallel application).

The very first works (mostly in the VLSI domain) on hypergraph partitioning used the recursive bisection (RB) paradigm. In the RB paradigm, a hypergraph is recursively bisected (i.e., two-way partitioned) until the desired number of parts is obtained. At each bisection step, cut-net removal and cut-net splitting techniques [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF] are adopted to optimize the cut-net and connectivity-1 metrics, respectively. Iterative improvement heuristics based on vertex moves or swaps between the parts are used to refine bisections to decrease the cutsize. The performance of iterative improvement heuristics deteriorate in partitioning hypergraphs with large net sizes [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF] and small vertex degrees [START_REF] Goldberg | Heuristic improvement technique for bisection of VLSI networks[END_REF]. Moreover, those improvement heuristics do not have a global view of the problem, and hence solutions are usually far from being optimal.

The multi-level hypergraph partitioning approach emerged as a remedy to these problems [START_REF] Bui | A heuristic for reducing fill in sparse matrix factorization[END_REF]. In multi-level bisection, the original hypergraph is coarsened into a smaller hypergraph after a series of coarsening levels, in which highly coherent vertices are grouped into supervertices, thus decreasing the sizes of the nets. After the bisection of the coarsest hypergraph, the generated coarse hypergraphs are uncoarsened back to the original, flat hypergraph. At each uncoarsening level, a refinement heuristic (e.g., FM [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF] or KL [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF]) is applied to minimize the cutsize while maintaining the partitioning constraint. The multi-level partitioning approach has proven to be very successful [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF][START_REF] Hendrickson | The Chaco user's guide: Version 2.0[END_REF][START_REF] Karypis | hMETIS: a hypergraph partitioning package[END_REF][START_REF] Karypis | MeTiS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices[END_REF][START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF] in optimizing various objective functions.

With the widespread use of hypergraph partitioning in modeling computational problems outside the VLSI domain, the RB scheme adopting the FMbased local improvement heuristics turned out to be inadequate due to the following reasons. First, in partitioning hypergraphs with large net sizes, if the partitioning objective depends on the connectivity of the nets (e.g., the connectivity-1 metric), good partitions cannot always be obtained. The possibility of finding vertex moves that will reduce the cutsize is limited, especially at the initial bisection steps, where net sizes are still large, as nets with large sizes are likely to have large numbers of pins on both parts of the bisection [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF]. Second, in partitioning hypergraphs with large variation in vertex weights, targeted balance values may not always be achieved since the imbalance ratio needs to be adaptively adjusted at each bisection step. Third, the RB scheme's nature of partitioning hypergraphs into two equally weighted parts restricts the solution space. In general, imbalanced bisections have the potential to lead to better cutsizes [START_REF] Simon | How good is recursive bisection?[END_REF]. Finally, several formulations that are variations of the standard hypergraph partitioning problem (e.g., multiple balance constraints, multi-objective functions, fixed vertices), which have recently started to find application in the literature, are not appropriate for the RB paradigm.

As stated above, the RB scheme performs rather poorly in problems where a hypergraph representing the computational structure of a problem is augmented by imposing more than one constraints on vertex weights or introducing a set of fixed vertices into the hypergraph. In the multi-constraint partitioning case, the solution space is usually restricted since multiple constraints may further restrict the movement of vertices between the parts.

Equally weighted bisections have a tendency to minimize the maximum of the imbalance ratios (according to multiple weights) to enable the feasibility of the following bisections. This additional restriction has manifested itself as 20% to 30% degradation in cutsizes with respect to the single-constraint formulation in some recent applications [START_REF] Karypis | Multilevel algorithms for multi-constraint graph partitioning[END_REF][START_REF] Uçar | Partitioning sparse matrices for parallel preconditioned iterative methods[END_REF][START_REF] Walshaw | Multiphase mesh partitioning[END_REF].

In partitioning with fixed vertices, the RB-based approaches use fixed vertices to guide the partitioning at each bisection step. A set of vertices fixed to a certain subset of parts (a practical option is to select the vertices fixed to the first K/2 parts) are placed in the same part in the first bisection step. As there is no other evident placement information, the same kind of action is taken in the following bisection steps as well. Note that this is a restriction since any bisection that keeps the vertices fixed to half of the parts in the same side of the partition is feasible. That is, parts can be relabeled after the partitioning took place according to the fixed vertex information. In other words, there are combinatorially many part labelings that are consistent with the given fixed vertex information, and the RB-based approaches do not explore these labelings during partitioning. Combined with the aforementioned shortcomings of the RB scheme, this can have a dramatic impact on the solution quality. In Section 5.4, we report cutsize improvements up to 33.30% by a carefully chosen part labeling combined with K-way refinement.

Contributions

In this work, we propose a new multi-level hypergraph partitioning algorithm with direct K-way refinement. Based on this algorithm, we develop a hypergraph partitioning tool capable of partitioning hypergraphs with multiple constraints. Moreover, we extend the proposed algorithm and the tool in order to partition the hypergraphs with fixed vertices. The extension is to temporarily remove the fixed vertices, partition the remaining vertices, and then optimally assign the fixed vertices to the obtained parts prior to direct K-way refinement. The fixed-vertex-to-part assignment problem is formulated as an instance of the maximum-weighted bipartite graph matching problem.

We conduct experiments on a wide range of hypergraphs with different properties (i.e., number of vertices, average net sizes). The experimental results indicate that, in terms of both execution time and solution quality, the proposed algorithm performs better than the state-of-the-art RB-based algorithms provided in PaToH [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF]. In the case of multiple constraints and fixed vertices, the obtained results are even superior.

The rest of the paper is organized as follows. In Section 2, we give an overview of the previously developed hypergraph partitioning tools and a number of problems that are modeled as a hypergraph partitioning problem in the literature. The proposed hypergraph partitioning algorithm is presented in Section 3. In Section 4, we present an extension to this algorithm in order to encapsulate hypergraph partitioning with fixed vertices. In Section 5, we verify the validity of the proposed work by experimenting on well-known benchmark datasets. The paper is concluded in Section 6.

Previous work on hypergraph partitioning

Hypergraph partitioning tools

Although hypergraph partitioning is widely used in both academia and industry, the number of publicly available tools is limited. Other than the Mondriaan partitioning tool [START_REF] Vastenhouw | A two-dimensional data distribution method for parallel sparse matrix-vector multiplication[END_REF], which is specialized on sparse matrix partitioning, there are five general-purpose hypergraph partitioning tools that we are aware of: hMETIS [START_REF] Karypis | hMETIS: a hypergraph partitioning package[END_REF], PaToH [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF], MLPart [START_REF] Caldwell | Improved algorithms for hypergraph bipartitioning[END_REF], Parkway [START_REF] Trifunovic | Parkway 2.0: a parallel multilevel hypergraph partitioning tool[END_REF], and Zoltan [START_REF] Devine | Parallel hypergraph partitioning for scientific computing[END_REF], listed in chronological order. hMETIS [START_REF] Karypis | hMETIS: a hypergraph partitioning package[END_REF] is the earliest hypergraph partitioning tool, published in 1998 by Karypis and Kumar. It contains algorithms for both RB-based and direct Kway partitioning. The objective functions that can be optimized using this tool are the cut-net metric and the sum of external degrees metric, which simply sums the connectivities of the cut nets. The tool has support for partitioning hypergraphs with fixed vertices.

PaToH [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF] was published in 1999 by C ¸atalyürek and Aykanat. It is a multilevel, RB-based partitioning tool with support for multiple constraints and fixed vertices. Built-in objective functions are the cut-net and connectivity-1 cost metrics. A high number of heuristics for coarsening, initial partitioning, and refinement phases are readily available in the tool.

MLPart [START_REF] Caldwell | Improved algorithms for hypergraph bipartitioning[END_REF] Parkway [START_REF] Trifunovic | Parkway 2.0: a parallel multilevel hypergraph partitioning tool[END_REF] is the first parallel hypergraph partitioning tool, published in 2004 by Trifunovic and Knottenbelt. It is suitable for partitioning large hypergraphs in multi-processor systems. The tool supports both the cut-net and connectivity-1 cost metrics. Also, Sandia National Lab's Zoltan toolkit [START_REF] Devine | Zoltan data management services for parallel dynamic applications[END_REF] contains a recently developed parallel hypergraph partitioner [START_REF] Devine | Parallel hypergraph partitioning for scientific computing[END_REF]. This partitioner is based on the multilevel RB paradigm and currently supports the connectivity-1 cost metric.

Applications of hypergraph partitioning

Hypergraph partitioning has been used in VLSI design [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF][START_REF] Dasdan | Two novel multiway circuit partitioning algorithms using relaxed locking[END_REF][START_REF] Karypis | Multilevel hypergraph partitioning: applications in VLSI domain[END_REF][START_REF] Lengauer | Combinatorial Algorithms for Integrated Circuit Layout[END_REF][START_REF] Schweikert | A proper model for the partitioning of electrical circuits[END_REF] since 1970s. The application of hypergraph partitioning in parallel computing starts by the work of C ¸atalyürek and Aykanat [START_REF] ¸atalyürek | Decomposing irregularly sparse matrices for parallel matrix-vector multiplication[END_REF][START_REF] ¸atalyürek | Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication[END_REF]. This work addresses 1D (rowwise or columnwise) partitioning of sparse matrices for efficient parallelization of matrix-vector multiplies. Later, C ¸atalyürek and Aykanat [START_REF] ¸atalyürek | A fine-grain hypergraph model for 2D decomposition of sparse matrices[END_REF][START_REF] ¸atalyürek | A hypergraph-partitioning approach for coarsegrain decomposition[END_REF] and Vastenhouw and Bisseling [START_REF] Vastenhouw | A two-dimensional data distribution method for parallel sparse matrix-vector multiplication[END_REF] proposed hypergraph partitioning models for 2D (nonzero-based) partitioning of sparse matrices. In these models, the partitioning objective is to minimize the total volume of communication while maintaining the computational load balance. These matrix partitioning models are used in different applications that involve repeated matrix-vector multiplies, such as computation of response time densities in large Markov models [START_REF] Dingle | Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models[END_REF], restoration of blurred images [START_REF] Uçar | Parallel image restoration using surrogate constraints methods[END_REF], and integer factorization in the number field sieve algorithm in cryptology [START_REF] Bisseling | Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Lanczos algorithm: a case study[END_REF].

In parallel computing, there are also hypergraph partitioning models that address objectives other than minimizing the total volume of communication. For example, Aykanat et al. [START_REF] Aykanat | Permuting sparse rectangular matrices into block-diagonal form[END_REF] consider minimizing the border size in permuting sparse rectangular matrices into singly bordered block diagonal form for efficient parallelization of linear programming solvers, LU and QR factorizations. Another example is the communication hypergraph model proposed by Uçar and Aykanat [START_REF] Uçar | Encapsulating multiple communication-cost metrics in partitioning sparse rectangular matrices for parallel matrix-vector multiplies[END_REF] for considering message latency overhead in parallel sparse matrix-vector multiples based on 1D matrix partitioning.

Besides matrix partitioning, hypergraph models are also proposed for other parallel and distributed computing applications. These include workload partitioning in data aggregation [START_REF] Chang | A hypergraphbased workload partitioning strategy for parallel data aggregation[END_REF], image-space-parallel direct volume rendering [START_REF] Cambazoglu | Hypergraph-partitioning-based remapping models for image-space-parallel direct volume rendering of unstructured grids[END_REF], data declustering for multi-disk databases [START_REF] Koyuturk | Iterative-improvement-based declustering heuristics for multi-disk databases[END_REF][START_REF] Liu | A hypergraph based approach to declustering problems[END_REF], and scheduling filesharing tasks in heterogeneous master-slave computing environments [START_REF] Kaya | Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master-slave environments[END_REF][START_REF] Kaya | Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories[END_REF][START_REF] Khanna | A hypergraph partitioning based approach for scheduling of tasks with batch-shared IO[END_REF].

Formulations that extend the standard hypergraph partitioning problem (e.g., multiple vertex weights and fixed vertices) also find application. For instance, multi-constraint hypergraph partitioning is used for 2D checkerboard partitioning of sparse matrices [START_REF] ¸atalyürek | A hypergraph-partitioning approach for coarsegrain decomposition[END_REF] and parallelizing preconditioned iterative methods [START_REF] Uçar | Partitioning sparse matrices for parallel preconditioned iterative methods[END_REF]. Hypergraph partitioning with fixed vertices is used in formulating the remapping problem encountered in image-space-parallel volume rendering [START_REF] Cambazoglu | Hypergraph-partitioning-based remapping models for image-space-parallel direct volume rendering of unstructured grids[END_REF].

Finally, we note that hypergraph partitioning also finds application in problems outside the parallel computing domain such as road network clustering for efficient query processing [START_REF] Demir | Clustering spatial networks for aggregate query processing: a hypergraph approach[END_REF][START_REF] Demir | A link-based storage scheme for efficient aggregate query processing on clustered road networks[END_REF], pattern-based data clustering [START_REF] Ozdal | Hypergraph models and algorithms for data-patternbased clustering[END_REF], re- ducing software development and maintenance costs [START_REF] Bisseling | Partitioning a call graph[END_REF], topic identification in text databases [START_REF] Clifton | TopCat: Data mining for topic identification in a text corpus[END_REF], and processing spatial join operations [START_REF] Shekhar | Efficient join-index-based spatialjoin processing: a clustering approach[END_REF].

K-way hypergraph partitioning algorithm

The proposed algorithm follows the traditional multi-level partitioning paradigm. It includes three consecutive phases: multi-level coarsening, initial partitioning, and multi-level K-way refinement. Fig. 1 illustrates the algorithm.

Multi-level coarsening

In the coarsening phase, a given flat hypergraph H 0 is converted into a sufficiently small hypergraph H m , which has vertices with high degrees and nets with small sizes, after m successive coarsening levels. At each level ℓ, an intermediate coarse hypergraph H ℓ+1 = (V ℓ+1 , N ℓ+1 ) is generated by coarsening the finer parent hypergraph H ℓ = (V ℓ , N ℓ ). The coarsening phase results in a sequence H 1 , H 2 , . . . , H m of m coarse hypergraphs.

The coarsening at each level ℓ is performed by coalescing vertices of H ℓ into supervertices in H ℓ+1 . For vertex grouping, agglomerative or matching-based heuristics may be used. In our case, we use the randomized heavy-connectivity matching heuristic [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF][START_REF] ¸atalyürek | Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication[END_REF]. In this heuristic, vertices in vertex set V ℓ are visited in a random order. In the case of unit-cost nets, every visited, unmatched vertex v i ∈ V ℓ is matched with a currently unmatched vertex v j ∈ V ℓ that shares the maximum number of nets with v i . In the case of nets with variable costs, v i is matched with a vertex v j such that n h ∈C ij c(n h ) is the maximum over all unmatched vertices that share at least one net with v i , where

C ij = {n h : n h ∈ Nets(v i ) ∧ n h ∈ Nets(v j )}, i.e., C ij denotes the set of nets that connect both v i and v j . Each matched vertex pair (v i ∈ V ℓ , v j ∈ V ℓ ) forms a single supervertex in V ℓ+1 .
As the coarsening progresses, nets with identical pin sets may emerge. Such nets become redundant for the subsequent coarser hypergraphs and hence can be removed. In this work, we use an efficient algorithm for identical net detection and elimination. This algorithm is similar to the algorithm in [START_REF] Ashcraft | Compressed graphs and the minimum degree algorithm[END_REF], which is later used in [START_REF] Hendrickson | Improving the run time and quality of nested dissection ordering[END_REF] for supervariable identification in nested-dissectionbased matrix reordering.

RB-based initial partitioning

The objective of the initial partitioning phase is to obtain a K-way initial partition Π m = {V m 1 , V m 2 , . . . , V m K } of the coarsest hypergraph H m before direct K-way refinement. For this purpose, we use the multi-level RB scheme of PaToH to partition H m into K parts. We have observed that it is better to avoid further coarsening within PaToH since H m is already coarse enough. At each bisection step of PaToH, we use the greedy hypergraph growing heuristic to bisect the intermediate hypergraphs and the tight boundary FM heuristic [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF][START_REF] ¸atalyürek | Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication[END_REF] for refinement. At the end of the initial partitioning phase, if the current imbalance is over the allowed imbalance ratio ǫ, a balancer, which performs vertex moves (starting with the moves having highest FM gains, i.e., the highest reduction in the cutsize) among the K parts at the expense of an increase in the cutsize, is executed to drop the imbalance below ǫ.

Although possibilities other than RB exist for generating the initial set of vertex parts, RB emerges as a viable and practical method. A partition of the coarsest hypergraph H m generated by RB is very amenable to FM-based refinement since H m contains nets of small sizes and vertices of high degrees.

Multi-level uncoarsening with direct K-way refinement

Every uncoarsening level ℓ includes a refinement step, followed by a projection step. In the refinement step, which involves a number of passes, partition Π ℓ is refined by moving vertices among the K vertex parts, trying to minimize the cutsize while maintaining the balance constraint. In the projection step, the current coarse hypergraph H ℓ and partition Π ℓ are projected back to H ℓ-1 and Π ℓ-1 . The refinement and projection steps are iteratively repeated until the top-level, flat hypergraph H 0 with a partition Π 0 is obtained. This algorithm is similar to the one described in [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF].

At the very beginning of the uncoarsening phase, a connectivity data structure Λ and a lookup data structure δ are created. These structures keep the connectivity of the cut nets to the vertex parts. Λ is a 2D ragged array, where each 1D array keeps the connectivity set of a cut net. That is, Λ(n i ) returns the connectivity set Λ i of a cut net n i . No information is stored in Λ for internal nets. δ is an |N cut | by K, 2D array to lookup the connectivity of a cut net to a part in constant time. That is, δ(n i , V k ) returns the number of the pins that cut net

n i has in part V k , i.e., δ(n i , V k ) = |P ins(n i ) ∩ V k |.
Both Λ and δ structures are allocated once at the beginning of the uncoarsening phase and maintained during the projection steps. For this purpose, after each coarsening level, a mapping between the nets of the fine and coarse hypergraphs is computed so that Λ and δ arrays are modified appropriately in the corresponding projection steps. Since the pin counts of the nets on the parts may change due to the uncoarsening, the pin counts in the δ array are updated by iterating over the cut nets in the coarse hypergraph and using the net map created during the corresponding coarsening phase. Similar to the net map, vertex maps are computed in the coarsening steps to be able to determine the part assignments of the vertices in the fine hypergraphs during the projection. Part assignments of vertices are kept in a 1D P art array, where P art(v i ) shows the current part of vertex v i .

During the refinement passes, only boundary vertices are considered for movement. For this purpose, a FIFO queue B of boundary vertices is maintained. A vertex v i is boundary if it is among the pins of at least one cut net n j . B is updated after each vertex move if the move causes some non-boundary vertices to become boundary or some boundary vertices become internal to a part. Each vertex v i has a lock count b i , indicating the number of times v i is inserted into B. The lock counts are initially set to 0 at the beginning of each refinement pass. Every time a vertex enters B, its lock count is incremented by 1. No vertex v i with a b i value greater than a prespecified threshold is allowed to re-enter B. This way, we avoid moving the same vertices repeatedly. The boundary vertex queue B is randomly shuffled at the beginning of each refinement pass.

For vertex movement, each boundary vertex v i ∈ B is considered in turn. The move of vertex v i is considered only to those parts that are in the union of the connectivity sets of the nets connecting v i , excluding the part containing v i , if the move satisfies the balance criterion. Note that once the imbalance on part weights is below ǫ, it is never allowed to rise above this ratio during the direct K-way refinement. After gains are computed, the vertex is moved to the part with the highest positive FM gain. Moves with negative FM gains as well as moves with non-positive leave gains are not performed. A refinement pass terminates when queue B becomes empty. No more refinement passes are made if a predetermined pass count is reached or improvement in the cutsize drops below a prespecified threshold.

For FM-based move gain computation for a vertex v i , we use the highly efficient algorithm given in Fig. 2. This algorithm first iterates over all nets connecting vertex v i and computes the leave gain for v i . If the leave gain is not positive, no further positive move gain is possible and hence the algorithm simply returns. Otherwise, the maximum arrival loss is computed by iterating over all nets connecting v i as well as a separate move gain for all parts (excluding v i 's current part) that are connected by at least one cut net of v i . Finally, a total move gain is computed for each part by adding the move gain for the part to the leave gain and subtracting the maximum arrival loss. The maximum move gain is determined by taking the maximum of the total move gains.

Extension to multiple constraints

Extension to multi-constraint formulation requires verifying the balance constraint for each weight component. As before, zero-gain moves are not performed. During the coarsening phase, the maximum allowed vertex weight is set according to the constraint which has the maximum total vertex weight over all vertices. In the initial partitioning phase, the multi-constraint RBbased partitioning feature of PaToH is used with default parameters to obtain an initial K-way partition.

Extensions to hypergraphs with fixed vertices

Our extension to partitioning hypergraphs with fixed vertices follows the multi-level paradigm, which is, in our case, composed of three phases: coarsening with modified heavy-connectivity matching, initial partitioning with maximum-weighted bipartite graph matching, and K-way direct refinement compute-fm-gains(v i , P art, Λ, δ)

⊲ compute the leave gain by iterating over all nets connecting v i leaveGain ← 0 for each net n j ∈ N ets(v i ) do if δ(n j , P art(v i )) = 1 then leaveGain ← gain + c(n j ) ⊲ if there is no positive leave gain, simply return if leaveGain = 0 then return NO-PART-TO-MOVE ⊲ compute the maximum arrival loss by iterating over all nets connecting v i ⊲ and the move gains for all parts (excluding P art(v i )) ⊲ connected by at least one of the cut nets of v i targetP arts ← ∅ maxArrivalLoss ← 0 for each net n j ∈ N ets(v i ) do maxArrivalLoss ← maxArrivalLoss + c(n j ) if λ j > 1 then ⊲ find the parts v i can move and compute the respective move gains

for each part V k ∈ Λ(n j ) -P art(v i ) do if V k ∈ targetP arts then ⊲ insert part V k in the set of parts that v i can move to targetP arts ← targetP arts ∪ {V k } M oveGain(V k ) ← 0 ⊲ update the move gain to part V k M oveGain(V k ) ← M oveGain(V k ) + c(n j )
⊲ compute the maximum move gain and the part v i will be moved to maxM oveGain ← -∞ for each part V k ∈ targetP arts do ⊲ check if the move satisfies the balance criterion if with locked fixed vertices. Throughout the presentation, we assume that, at each coarsening/uncoarsening level ℓ, f ℓ i is a fixed vertex in the set F ℓ of fixed vertices, and o ℓ j is an ordinary vertex in the set O ℓ of ordinary vertices, where O ℓ = V ℓ -F ℓ . For each part V 0 k , there is a set F 0 k of fixed vertices that must end up in V 0 k at the end of the partitioning such that F 0 = F 0 1 ∪ F 0 2 . . . ∪ F 0 K . We also assume that the weights of the fixed vertex sets are fairly balanced.

W (V k ) + w(v i ) < (1 + ǫ)W avg then M oveGain(V k ) ← M oveGain(V k ) + (leaveGain -maxArrivalLoss) if M oveGain(V k ) > maxM oveGain then maxM oveGain ← M oveGain(V k ) maxP art ← V k return maxP art, maxM oveGain
For the coarsening phase of our algorithm, we modify the heavy-connectivity matching heuristic such that no two fixed vertices f ℓ i ∈ F ℓ and f ℓ j ∈ F ℓ are matched at any coarsening level ℓ. However, any fixed vertex f ℓ i in a fixed vertex set F ℓ k can be matched with an ordinary vertex o ℓ j ∈ O ℓ , forming a fixed supervertex f ℓ+1 i in F ℓ+1 k . Ordinary vertices are matched as before. Consequently, fixed vertices are propagated throughout the coarsening such that In the initial partitioning phase, a hypergraph Hm = (O m , Ñ m ) that is free from fixed vertices is formed by temporarily removing fixed supervertices from H m . In Hm , Ñ m is a subset of nets in N m whose pins contain at least two ordinary vertices, i.e., Ñ m = {n m i :

|F ℓ+1 k | = |F ℓ k |, for k = 1,
n m i ∈ N m ∧ |O m ∩ P ins(n m i )| > 1}.
Note that the nets that connect only one ordinary vertex are not retained in Hm since single-pin nets do not contribute to the cutsize at all. After Hm is formed, it is partitioned to obtain a K-way vertex partition Πm = {O m 1 , O m 2 , . . . , O m K } over the set O m of ordinary vertices. Partition Πm induces an initial part assignment for each ordinary vertex in V m , i.e.,

o m i ∈ O m k ⇒ P art(v m i ) = V m k .
However, this initial assignment induced by Πm may not be appropriate in terms of the cutsize since fixed vertices are not considered at all in computation of the cutsize. Note that cutsize( Πm ) is a lower bound on cutsize(Π m ). A net n j has the potential to increase the cutsize by its cost times the number of fixed vertex parts that it connects, i.e., by c(n m j ) λm j , where λm

j = | Λm j | = |{F m k : P ins(n m j ) ∩F m k = ∅}|. Therefore, U = cutsize( Πm ) + n m j c(n m j ) λm
j is an upper bound on cutsize(Π m ). At this point, a relabeling of ordinary vertex parts must be found so that the cutsize is tried to be minimized as the fixed vertices are assigned to appropriate parts. We formulate this relabeling problem as a maximum-weighted bipartite graph matching problem [START_REF] Chartrand | Applied and Algorithmic Graph Theory[END_REF]. This formulation is valid for any number of fixed vertices.

In the proposed formulation, the sets of fixed supervertices and the ordinary vertex parts form the two node sets of a bipartite graph B = (X , Y). That is, in B, for each fixed vertex set F m k , there exists a node x k ∈ X , and for each ordinary vertex part O m ℓ of Πm , there exists a node y ℓ ∈ Y. The bipartite graph contains all possible (x k , y ℓ ) edges, initially with zero weights. The weight of an edge (x k , y ℓ ) is increased by the cost of every net that connects at least one vertex in both F m k and O m ℓ . That is, a net n m j increases the weight of edge (x k , y ℓ ) by its cost c(n m j ) if and only if

P ins(n m j ) ∩ F m k = ∅ and P ins(n m j ) ∩ O m ℓ = ∅. This weight on edge (x k , y ℓ ) corresponds to a saving of c(n m j ) from upper bound U if F m k is matched with O m ℓ .
In this setting, finding the maximum-weighted matching in bipartite graph B corresponds to finding a matching between fixed vertex sets and ordinary vertex parts which has the minimum increase in the cutsize when fixed vertices are re-introduced into Hm . Each edge (x k , y ℓ ) in the resulting maximumweighted matching M matches a fixed vertex set to an ordinary vertex part. Using M, ordinary vertex parts are relabeled. Vertices in O m ℓ are reassigned to part V m k if and only if edge (x k , y ℓ ) is in M. Note that the fixed vertices in F m k are in part V m k and hence the partition conforms to the given partition on fixed vertices. This relabeling induces an initial partition Π m . Here, cutsize(Π m ) = U-weight(M), where weight(M) is the weight of matching M and is equal to the saving on the cutsize. Since M is the maximum-weighted matching, this defines an optimum solution for the relabeling problem. Fig. 3(a) shows a sample, coarse hypergraph H m , where fixed and ordinary vertices are respectively represented as triangles and circles. For ease of presentation, unit net costs are assumed and only the nets connecting the fixed vertices and ordinary vertices are displayed since all cost contribution on the edges of the constructed bipartite graph are due to such nets. Note that, in this example, the upper bound on cutsize(Π m ) is U = 3+11 = 14. The linear assignment of fixed vertex sets to ordinary vertex parts (i.e., F m k matched with O m k , for k = 1, 2, . . . , K) has a cost saving of weight(M) = 1 + 1 + 1 + 1 = 4. Hence, cutsize(Π m ) = U -weight(M) = 14-4 = 10. Hence, cutsize(Π m ) = U -weight(M) = 14-7 = 7. This cutsize is 10-7 = 3 less than the cutsize achieved by linear assignment.

1 1 1 1 1 1 1 2 3 2 (b) (a) x 3 O m 3 F m 2 F m 3 F m 4 O m 1 x 1 x 2 O m 2 x 4 O m
During the K-way refinement phase, Π m is refined using a modified version of the algorithm described in Section 3.3. Throughout the uncoarsening, the fixed vertices are locked to their parts and are not allowed to move between the parts. Hence, each fixed vertex f 0 i whose corresponding supervertex in the m-th level is f m i ends up in part V 0 k if and only if f m i ∈ F k .

Experiments

Experimental platform

In the experiments, a Pentium IV 3.00 GHz PC with 1 GB of main memory, 512 KB of L2 cache, and 8 KB of L1 cache is used. All algorithms are implemented in C and are compiled in gcc with -O3 optimization option. Due to the randomized nature of some of the heuristics, the results are reported by averaging the values obtained in 20 different runs, each randomly seeded.

The hypergraphs used in the experiments are the row-net hypergraphs [START_REF] ¸atalyürek | Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication[END_REF] of some widely used square sparse matrices obtained from the University of Florida Sparse Matrix Collection [START_REF] Davis | University of Florida Sparse Matrix[END_REF]. The properties of the hypergraphs are given in Table 1, where the hypergraphs are sorted in increasing order of the number of pins. In all hypergraphs, the number of nets is equal to the number of vertices, and the average vertex degree is equal to the average net size since all matrices are square matrices. Since the internal data structures maintained during the partitioning do not fit into the memory for the Hamrle3, cage13, and pre2 datasets, they are partitioned on a PC with 2 GB main memory, all other parameters remaining the same. We compare the proposed algorithm, referred to here as kPaToH, with PaToH [START_REF] ¸atalyürek | PaToH: partitioning tool for hypergraphs[END_REF] for two reasons. First, the implementation of kPaToH is based on PaToH. Second, in previous experiments (e.g., see [START_REF] ¸atalyürek | ISPD98 benchmark[END_REF][START_REF] Duff | Parallel preconditioners based on partitioning sparse matrices[END_REF]), PaToH was found to be performing better than the other hypergraph partitioners.

In the tables, the minimum cutsizes (Min cutsize) and average cutsizes (Avg cutsize) achieved by both partitioners are reported over all datasets together with their average partitioning times (Avg time), for varying number K of parts, where K ∈ {32, 64, 128, 256, 512}. The rightmost two columns in Tables 2, 5, 6, and 8 show the percent average cutsize improvement (%Cutsize) and the speedup (Spdup) of kPaToH over PaToH. The averages over all datasets are displayed as a separate entry at the bottom of these tables. Unless otherwise stated, the maximum number of K-way refinement passes in kPa-ToH is set to 3. Since identical net elimination brings around 5% improvement on the execution time of kPaToH but no speedup on PaToH, we run both Pa-ToH and kPaToH without identical net elimination for a fair comparison. In single-constraint partitioning, weight

w 1 (v i ) of a vertex v i is set equal to its vertex degree d(v i ), i.e., w 1 (v i ) = d(v i ).
The allowed imbalance threshold is set to 10% and is met in all experiments. PaToH is executed with default options.

Experiments on standard hypergraph partitioning

Table 2 displays the performance comparison of PaToH and kPaToH for standard hypergraph partitioning. According to the averages over all datasets, as K increases, kPaToH begins to perform better in reducing the cutsize compared to PaToH. The average cutsize improvement of 4.82% at K = 32 rises to 6.81% at K = 256. A similar behavior is observed in the improvement of kPa-ToH over PaToH in the minimum cutsizes achieved. In the speedups kPaToH obtains over PaToH, a slight decrease is observed as K increases. However, even at K = 256, kPaToH runs 1.62 times faster than PaToH and is 1.78 times faster on the overall average.

According to Table 2, except for a single case (the language dataset with K = 32), kPaToH achieves lower cutsizes than PaToH for all datasets and K values. In general, kPaToH performs relatively better in reducing the cutsize on hypergraphs having average net sizes between 6 and 20. This is expected since PaToH is already very effective in partitioning hypergraphs with low net sizes (e.g., language and Hamrle3). On the other hand, in partitioning hypergraphs with very large net sizes (e.g., barrier2-1 and bmw3 2), the performance gap between the partitioners begins to decrease. This is mainly due to performing only the moves with positive gains. Such moves are rare when the nets are highly connected to the parts.

Tables 3 and4 show the overall percent execution time dissection of the PaToH and kPaToH algorithms, respectively. The tables further display the percent execution time dissection of coarsening and uncoarsening phases for both algorithms. These experiments are conducted on three datasets (language, pre2, and hood) each with different average net size characteristics (3.05, 9.04, and 48.83, respectively), for K = 32 and K = 256. The dissection of both PaToH and kPaToH algorithms is according to the traditional multi-level partitioning paradigm, which involves an initialization phase followed by the coarsening, initial partitioning, and uncoarsening phases. In case of PaToH, these phases are repeated for each hypergraph produced via bisection, and hence the cost of splitting the hypergraph into two after bisections is also considered.

According to Tables 3 and4, the main overhead of PaToH is at the coarsening step, whereas the percent overhead of uncoarsening is relatively more dominant in case of kPaToH. In general, as K increases from 32 to 256, percent uncoarsening and splitting overheads of PaToH slightly increase. In case of kPaToH, the K-way initial partitioning phase is what most suffers from large K values. In kPaToH, the behavior of the uncoarsening phase is dataset dependent. As the average net size increases, the percent overhead of uncoarsening begins to increase with increasing K. This is because the refinement step, which takes the most of the uncoarsening time, is not affected by changing K if the average net size is low as in the case of the language dataset.

In the hood dataset, the increase in the percent overhead of the uncoarsening phase from 27.1% to 57.7% as K goes from 32 to 256 is due to the increase in the solution space, which prevents quick termination of the refinement phase.

Experiments on multi-constraint partitioning

Tables 5 and6 show the performance of PaToH and kPaToH in multi-constraint partitioning (2 and 4 constraints, respectively). In the 2-constraint case, a unit weight is used as the second vertex weight for all vertices, i.e., w 2 (v i ) = 1, in addition to the first vertex weight w 1 (v i ) = d(v i ). In the 4-constraint case, random integer weights

w 3 (v i ) = α i , where 1 ≤ α i ≤ w 1 (v i )-1, and w 4 (v i ) = w 1 (v i )-α i
are respectively used as the third and fourth vertex weights.

As seen from Tables 5 and6, kPaToH performs much better than PaToH. A comparison of Tables 2,5, and 6 shows that increasing number of partitioning constraints favors kPaToH. On average, the cutsize improvement of kPaToH over PaToH, which is 5.82% in the single-constraint case, increases to 20.98% in the 2-constraint case and further increases to 40.02% in the 4-constraint case. In other words, the degradation in the solution qualities of kPaToH is considerably less than that of PaToH as the number of constraints increases.

The speedups, although being slightly lower, are close to the speedups in the single-constraint case. This slight decrease stems from the fact that the overhead that multi-constraint partitioning introduces to the FM-based refinement algorithm is higher in kPaToH compared to PaToH.

Experiments on partitioning with fixed vertices

In experiments on partitioning hypergraphs with fixed vertices, we use hypergraphs emerging in a real-life problem [START_REF] Cambazoglu | Hypergraph-partitioning-based remapping models for image-space-parallel direct volume rendering of unstructured grids[END_REF]. The properties of the hypergraphs are given in Table 7. In naming the datasets, the numbers after the dash indicate the number F of fixed vertices in the hypergraph, e.g., there are F = 32 fixed vertices in the BF-32 dataset. In the experiments, each part is assigned an equal number of fixed vertices. In CC datasets, the net size variation is low, whereas, in BF and OP datasets, the net sizes show high variation. creases and F increases. This is due to the fact that the disability of PaToH to recursively bisect fixed vertices between two parts in a way that will lead to better cutsizes in the following bisections becomes more pronounced if the number of fixed vertices per part is high. In general, compared to PaToH, the relative performance of kPaToH in minimizing the cutsize is better in BF and OP datasets, which have high variation in net sizes.

In Table 9, we report performance results in terms of the cutsize on a subset of the hypergraphs selected from Table 1. In each hypergraph, we randomly fix F = 128, 256, 512 vertices to K = 128, 256, 512 parts in a round-robin fashion and partition the hypergraph using both PaToH and kPaToH. For kPaToH, we explore the percent improvement due to bipartite graph matching (BGM) and hence try it both with and without BGM. In Table 9, "kPaToH w/ BGM" corresponds to an implementation of the approach described in Section 4, whereas "kPaToH w/o BGM" corresponds to an implementation in which the fixed vertex sets are arbitrarily matched with the ordinary vertex parts.

Basically, kPaToH provides superior results over PaToH in partitioning hypergraphs with fixed vertices due to (i) K-way refinement and (ii) BGM performed during the the initial partitioning phase. We provide Table 9 to illustrate the share of these two factors in the overall cutsize improvement. According to Table 9, the share of BGM in the total cutsize improvement is quite variable, ranging between 4.12% and 54.10%. In general, better results are achieved by BGM for hypergraphs having large net sizes. It is hard to make a judgment about the behavior with increasing F and K values. This is due to the fact that many other factors affect the performance of BGM. Among these factors, the performance is dependent on the connectivity of the regular and fixed vertices, distribution of fixed vertices on the parts, the ratio of F to the number of regular vertices, and the ratio of F to K. These are hard to assess (also see [START_REF] Alpert | Hypergraph partitioning with fixed vertices[END_REF] for comments on the bipartitioning case). The averages over F and K values are provided in Table 10.

Conclusion

We argued that the hypergraph partitioning with multiple constraints and fixed vertices problems should be tackled with a direct K-way refinement approach. In order to support our claim, we presented a careful implementation of a multi-level direct K-way refinement algorithm. We discussed extensions of this algorithm for partitioning hypergraphs with multiple constraints and fixed vertices. Extension to the multi-constraint case adopts standard hypergraph partitioning techniques. In order to extend the algorithm to the fixed vertex case, we proposed specialized coarsening and initial partitioning with a novel formulation that uses bipartite graph matching. The experiments con-

  was published in 2000 by Caldwell et al. This is an open source hypergraph partitioning tool specifically designed for circuit hypergraphs and partitioning-based placement in VLSI layout design. It has support for partitioning with fixed vertices.

Fig. 1 .

 1 Fig. 1. The proposed multi-level K-way hypergraph partitioning algorithm.

Fig. 2 .

 2 Fig.2. The algorithm for computing the K-way FM gains of a vertex v i .

2 ,

 2 . . . , K and ℓ = 0, 1, . . . , m -1. Hence, in the coarsest hypergraph H m , there are |F m | = |F 0 | fixed supervertices.

1 Fig. 3 .

 13 Fig. 3. (a) A sample coarse hypergraph. (b) Bipartite graph representing the hypergraph in Fig. 3(a) and assignment of parts to fixed vertex sets via maximum-weighted matching shown by bold edges.

Fig. 3 (

 3 Fig. 3(b) displays the bipartite graph constructed for the sample hypergraph in Fig. 3(a), without displaying the zero-weight edges for clarity. In this figure, triangles and circles denote the sets of fixed vertices and ordinary vertex parts, respectively. As seen in Fig. 3(b), there exists an edge (x 2 , y 3 ) with a weight of 2. This is because two unit-cost nets connect F m 2 and O m 3 . In the figure, the set of bold edges shows the maximum-weighted matching M = {(x 1 , y 2 ), (x 2 , y 4 ), (x 3 , y 1 ), (x 4 , y 3 )}, which assigns the vertices in F m 1 , F m 2 , F m 3 , and F m 4 to O m 2 , O m 4 , O m 1 , and O m 3 , respectively. As seen in the figure, matching

Table 1

 1 Properties of the datasets used in the experiments

	Dataset	# of vertices	# of pins	Avg. net size
	dawson5	51,537	1,010,777	19.61
	language	399,130	1,216,334	3.05
	Lin	256,000	1,766,400	6.90
	poisson3Db	85,623	2,374,949	27.74
	helm2d03	392,257	2,741,935	6.99
	stomach	213,360	3,021,648	14.16
	barrier2-1	113,076	3,805,068	33.65
	Hamrle3	1,447,360	5,514,242	3.81
	pre2	659,033	5,959,282	9.04
	cage13	445,135	7,479,343	16.80
	hood	220,542	10,768,436	48.83
	bmw3 2	227,362	11,288,630	49.65

Table 2

 2 Performance of PaToH and kPaToH in partitioning hypergraphs with a single partitioning constraint and no fixed vertices

			Min. cutsize	Avg. cutsize	Avg. time		Improvement
	Dataset	K	PaToH	kPaToH	PaToH	kPaToH	PaToH	kPaToH	%Cutsize	Spdup
	dawson5	32	6,959	6,286	7,468	6,907	1.524	0.715	7.51	2.13
		64	11,293	10,136	11,907	10,643	1.809	0.934	10.62	1.94
		128	19,058	17,140	19,393	17,767	2.099	1.291	8.39	1.63
		256	29,655	28,035	30,351	28,396	2.380	1.762	6.44	1.35
	language	32	94,210	94,178	95,399	95,956	12.266	9.721	-0.58	1.26
		64	107,299	106,728	108,432	107,758	13.064	9.830	0.62	1.33
		128	119,636	117,781	120,234	119,184	13.835	9.992	0.87	1.38
		256	131,251	130,679	131,690	131,526	14.489	10.303	0.12	1.41
	Lin	32	49,458	43,926	50,800	44,733	5.763	4.751	11.94	1.21
		64	68,994	60,107	70,645	60,832	6.632	5.505	13.89	1.20
		128	91,701	79,910	93,622	80,878	7.471	6.510	13.61	1.15
		256	119,529	105,567	121,346	105,916	8.327	7.942	12.72	1.05
	poisson3Db	32	40,599	38,212	41,759	39,314	9.358	7.867	5.85	1.19
		64	59,198	56,075	60,013	57,371	10.407	9.072	4.40	1.15
		128	84,630	81,849	86,118	82,896	11.366	10.416	3.74	1.09
		256	121,733	114,384	123,051	116,147	12.240	11.738	5.61	1.04
	helm2d03	32	13,016	12,487	13,591	12,965	7.689	2.845	4.61	2.70
		64	19,677	18,841	20,251	19,236	8.757	3.228	5.01	2.71
		128	29,169	27,660	29,696	28,096	9.801	3.790	5.38	2.59
		256	42,763	40,517	43,079	40,950	10.850	4.717	4.94	2.30
	stomach	32	26,231	25,757	27,054	26,184	6.635	3.327	3.22	1.99
		64	37,885	36,732	38,918	37,113	7.795	4.097	4.64	1.90
		128	54,651	52,150	55,370	52,817	8.968	5.175	4.61	1.73
		256	78,289	74,863	79,143	75,572	10.156	6.774	4.51	1.50
	barrier2-1	32	52,877	51,472	53,560	52,623	9.797	7.292	1.75	1.34
		64	73,864	71,879	75,037	73,149	11.135	8.609	2.52	1.29
		128	102,750	99,629	104,035	100,679	12.406	9.895	3.23	1.25
		256	142,833	135,074	143,995	136,757	13.526	11.372	5.03	1.19
	Hamrle3	32	35,728	35,419	36,814	36,747	21.190	8.798	0.18	2.41
		64	52,475	51,813	53,770	52,885	24.201	9.772	1.65	2.48
		128	75,818	73,923	76,851	75,194	26.802	11.418	2.16	2.35
		256	106,555	105,704	107,983	106,384	29.187	13.687	1.48	2.13
	pre2	32	82,591	75,860	85,456	80,238	24.406	15.070	6.11	1.62
		64	108,714	99,609	112,486	105,476	28.484	16.929	6.23	1.68
		128	139,605	120,469	143,879	122,822	32.250	18.071	14.64	1.78
		256	177,310	137,899	183,037	141,091	35.702	19.743	22.92	1.81
	cage13	32	369,330	339,563	373,617	345,740	45.887	45.590	7.46	1.01
		64	490,789	448,407	497,744	455,056	51.035	49.528	8.58	1.03
		128	643,278	584,178	647,609	589,316	55.754	52.972	9.00	1.05
		256	824,294	749,315	829,962	752,394	59.928	56.450	9.35	1.06
	hood	32	22,799	22,204	24,392	23,041	15.693	5.386	5.54	2.91
		64	37,877	37,058	39,855	38,239	18.383	6.607	4.05	2.78
		128	60,039	56,903	61,087	58,198	20.983	8.073	4.73	2.60
		256	91,007	86,009	92,367	87,284	23.515	10.303	5.50	2.28
	bmw3 2	32	29,861	28,298	31,129	29,792	15.383	5.545	4.30	2.77
		64	44,208	42,465	45,376	43,820	18.150	6.682	3.43	2.72
		128	65,752	63,652	67,551	64,956	20.853	8.065	3.84	2.59
		256	100,504	97,714	102,548	99,341	23.454	10.196	3.13	2.30
	AVERAGE	32	1.000	0.950	1.000	0.952	1.000	0.606	4.82	1.88
		64	1.000	0.947	1.000	0.945	1.000	0.611	5.47	1.85
		128	1.000	0.938	1.000	0.938	1.000	0.633	6.18	1.77
		256	1.000	0.934	1.000	0.932	1.000	0.679	6.81	1.62

Table 3

 3 Percent dissection of PaToH execution time

		language		pre2		hood
	Execution phase	K = 32	K = 256	K = 32	K = 256	K = 32	K = 256
	INITIALIZATION	1.0	0.9	1.1	0.8	2.1	1.4
	COARSENING	73.5	70.9	84.5	82.8	86.3	84.6
	Visit order computation	0.8	1.2	0.5	0.6	0.2	0.3
	Vertex matching	72.3	70.0	73.6	74.2	80.7	81.4
	Vertex mapping	2.2	2.7	1.1	1.1	0.5	0.5
	Hypergraph construction	24.7	26.1	24.8	24.1	18.6	17.8
	INITIAL PARTITIONING	1.9	1.9	1.0	1.3	0.4	0.9
	UNCOARSENING	19.1	20.6	9.5	10.6	4.6	5.8
	Initial gain computations	27.0	27.0	32.8	30.7	19.9	20.1
	Refinement	44.2	43.4	17.4	24.1	18.5	29.4
	Projection	28.8	29.6	49.8	45.2	61.6	50.5
	SPLITTING	4.5	5.7	3.9	4.5	6.6	7.3

Table 4

 4 Percent dissection of kPaToH execution time

		language		pre2		hood
	Execution phase	K = 32	K = 256	K = 32	K = 256	K = 32	K = 256
	INITIALIZATION	2.9	2.8	3.7	2.8	12.0	6.4
	COARSENING	45.2	38.5	32.1	22.6	56.8	28.8
	Visit order computation	0.4	0.4	0.6	0.6	0.2	0.2
	Vertex matching	81.0	84.5	70.5	73.5	76.7	77.9
	Vertex mapping	1.3	1.3	1.2	1.2	0.5	0.6
	Hypergraph construction	17.3	13.8	27.7	24.7	22.6	21.3
	INITIAL PARTITIONING	4.5	11.3	4.4	11.8	4.1	7.1
	UNCOARSENING	47.4	47.4	59.8	62.8	27.1	57.7
	Initialization	1.5	6.2	1.3	5.4	1.5	4.3
	Refinement	88.3	82.7	91.6	84.8	87.9	85.6
	Projection	10.2	11.1	7.1	9.8	10.6	10.1

Table 8

 8 illustrates the performance results obtained in partitioning hypergraphs with fixed vertices. These results are impressive as kPaToH outperforms PaToH by up to 31.28% in reducing the cutsize. On the overall average, kPaToH incurs a lower cutsize (between 17.09% and 21.07%) than PaToH. At the same time, kPaToH is around 2.3 times faster on the average. In general, kPaToH shows better cutsize performance than PaToH as K de-

Table 5

 5 Performance of PaToH and kPaToH in partitioning hypergraphs with two partitioning constraints

			Min. cutsize	Avg. cutsize	Avg. time		Improvement
	Dataset	K	PaToH	kPaToH	PaToH	kPaToH	PaToH	kPaToH	%Cutsize	Spdup
	dawson5	32	11,294	7,721	12,598	8,209	1.418	0.749	34.84	1.89
		64	18,342	12,206	19,446	13,240	1.673	1.003	31.91	1.67
		128	28,382	21,065	30,553	22,383	1.919	1.380	26.74	1.39
		256	45,929	34,469	48,331	35,921	2.142	1.839	25.68	1.16
	language	32	110,620	100,817	114,748	102,026	10.342	9.547	11.09	1.08
		64	124,426	113,295	127,849	114,223	11.024	9.662	10.66	1.14
		128	135,843	125,074	140,173	126,498	11.742	9.489	9.76	1.24
		256	149,615	138,889	154,821	139,876	12.159	10.024	9.65	1.21
	Lin	32	60,912	44,377	62,727	46,004	5.060	4.661	26.66	1.09
		64	84,861	61,455	86,483	62,713	5.805	5.386	27.49	1.08
		128	114,890	81,905	117,727	83,223	6.509	6.385	29.31	1.02
		256	151,652	108,679	153,346	109,597	7.177	7.702	28.53	0.93
	poisson3Db	32	47,813	38,750	50,122	41,726	8.138	7.858	16.75	1.04
		64	71,849	58,218	74,269	59,538	9.099	8.939	19.83	1.02
		128	104,590	84,667	108,143	85,879	9.964	10.213	20.59	0.98
		256	152,908	119,271	154,651	120,802	10.703	11.515	21.89	0.93
	helm2d03	32	21,292	13,322	22,531	14,056	6.491	2.875	37.62	2.26
		64	30,305	20,056	32,557	20,693	7.384	3.244	36.44	2.28
		128	44,819	29,254	46,078	30,100	8.240	3.788	34.68	2.18
		256	62,859	42,427	64,195	43,225	9.046	4.694	32.67	1.93
	stomach	32	34,168	26,555	35,787	27,906	6.051	3.365	22.02	1.80
		64	48,082	38,487	49,632	39,917	7.088	4.154	19.57	1.71
		128	66,512	55,439	68,199	56,549	8.115	5.211	17.08	1.56
		256	92,662	77,772	95,056	79,367	9.128	6.693	16.51	1.36
	barrier2-1	32	63,376	55,270	65,498	57,687	8.711	6.958	11.92	1.25
		64	89,650	78,398	92,626	80,831	9.876	8.354	12.73	1.18
		128	125,234	110,596	127,423	113,046	10.949	9.881	11.28	1.11
		256	171,482	151,321	177,107	155,823	11.922	11.449	12.02	1.04
	Hamrle3	32	49,678	37,991	54,846	39,470	19.498	9.015	28.04	2.16
		64	66,303	54,298	74,097	56,011	22.257	10.013	24.41	2.22
		128	94,701	77,382	99,669	79,023	24.763	11.544	20.71	2.14
		256	132,449	110,070	135,964	110,872	27.072	13.729	18.46	1.97
	pre2	32	106,199	80,682	114,920	88,445	22.688	15.680	23.04	1.45
		64	139,973	112,521	155,620	121,046	26.474	17.567	22.22	1.51
		128	200,692	168,097	207,614	173,300	29.936	19.665	16.53	1.52
		256	270,510	216,747	280,857	224,725	33.100	22.134	19.99	1.50
	cage13	32	432,428	368,686	443,298	381,828	37.214	45.613	13.87	0.82
		64	568,292	485,297	582,279	499,532	41.490	49.207	14.21	0.84
		128	736,109	635,187	746,979	649,153	45.307	52.391	13.10	0.86
		256	942,314	824,163	957,385	832,816	48.754	56.081	13.01	0.87
	hood	32	30,184	23,793	32,279	26,388	14.767	5.552	18.25	2.66
		64	48,580	40,285	50,910	42,097	17.206	6.695	17.31	2.57
		128	73,857	61,670	76,913	63,410	19.544	8.078	17.56	2.42
		256	112,224	92,946	114,197	94,975	21.818	10.050	16.83	2.17
	bmw3 2	32	42,905	32,222	45,457	34,446	14.068	5.718	24.22	2.46
		64	60,947	49,109	65,546	51,274	16.512	6.982	21.77	2.36
		128	94,851	73,221	101,070	77,762	18.881	8.500	23.06	2.22
		256	148,610	114,732	157,599	118,964	21.160	10.881	24.51	1.94
	AVERAGE	32	1.000	0.777	1.000	0.776	1.000	0.691	22.36	1.66
		64	1.000	0.797	1.000	0.785	1.000	0.697	21.55	1.63
		128	1.000	0.807	1.000	0.800	1.000	0.723	20.03	1.55
		256	1.000	0.807	1.000	0.800	1.000	0.779	19.98	1.42

Table 6

 6 Performance of PaToH and kPaToH in partitioning hypergraphs with four partitioning constraints

			Min. cutsize		Avg. cutsize		Avg. time		Improvement
	Dataset	K	PaToH	kPaToH	PaToH	kPaToH	PaToH	kPaToH	%Cutsize	Spdup
	dawson5	32	13,737	8,037	14,781	8,600	1.439	0.768	41.82	1.87
		64	19,318	13,124	22,841	13,909	1.692	1.037	39.11	1.63
		128	33,860	22,513	36,084	23,885	1.941	1.425	33.81	1.36
		256	51,794	38,509	56,280	39,956	2.161	1.917	29.01	1.13
	language	32	139,353	101,153	141,895	102,487	9.580	9.756	27.77	0.98
		64	148,714	113,760	151,633	114,933	10.229	10.014	24.20	1.02
		128	156,375	125,636	163,899	127,946	10.842	10.161	21.94	1.07
		256	165,782	141,125	175,689	145,699	11.365	11.131	17.07	1.02
	Lin	32	91,234	44,949	98,966	46,184	5.019	4.709	53.33	1.07
		64	120,349	62,380	125,700	63,297	5.730	5.431	49.64	1.06
		128	152,362	83,325	157,968	84,282	6.399	6.432	46.65	0.99
		256	187,114	109,471	192,952	110,604	7.031	7.754	42.68	0.91
	poisson3Db	32	64,204	39,871	72,387	42,610	8.029	7.953	41.14	1.01
		64	92,385	58,116	95,745	61,079	8.965	9.080	36.21	0.99
		128	124,979	85,237	129,528	88,489	9.775	10.361	31.68	0.94
		256	170,152	121,870	175,514	125,055	10.496	11.642	28.75	0.90
	helm2d03	32	24,307	13,639	27,429	14,398	6.701	2.907	47.51	2.31
		64	37,354	20,599	38,828	21,319	7.642	3.298	45.09	2.32
		128	51,410	30,342	53,462	31,087	8.541	3.856	41.85	2.21
		256	69,835	44,079	73,373	44,834	9.420	4.782	38.90	1.97
	stomach	32	47,275	26,410	51,908	28,022	6.038	3.378	46.02	1.79
		64	65,598	39,246	69,666	40,304	7.063	4.172	42.15	1.69
		128	85,852	56,244	89,528	57,189	8.092	5.225	36.12	1.55
		256	115,517	80,401	118,783	81,813	9.097	6.830	31.12	1.33
	barrier2-1	32	87,700	57,078	93,946	59,268	8.633	7.066	36.91	1.22
		64	113,469	80,217	121,148	83,535	9.817	8.405	31.05	1.17
		128	150,990	113,913	159,412	116,518	10.841	10.080	26.91	1.08
		256	203,583	161,848	208,792	164,935	11.864	11.711	21.00	1.01
	Hamrle3	32	105,671	38,587	115,453	39,776	20.145	9.071	65.55	2.22
		64	139,438	52,876	146,122	55,972	22.900	10.126	61.70	2.26
		128	175,186	77,831	181,742	79,631	25.409	11.685	56.18	2.17
		256	216,312	110,674	222,124	111,749	27.646	13.905	49.69	1.99
	pre2	32	222,989	88,430	240,992	92,342	21.903	16.071	61.68	1.36
		64	280,190	115,309	288,496	128,862	25.308	18.233	55.33	1.39
		128	333,089	178,247	349,267	189,243	28.463	20.495	45.82	1.39
		256	407,435	237,041	418,959	251,744	31.515	23.375	39.91	1.35
	cage13	32	734,084	370,648	780,736	384,668	34.957	46.229	50.73	0.76
		64	881,612	492,560	928,273	505,252	38.757	50.003	45.57	0.78
		128	1,040,360	643,380	1,073,786	654,515	42.286	52.965	39.05	0.80
		256	1,222,315	824,847	1,257,893	839,154	45.385	56.801	33.29	0.80
	hood	32	46,844	25,305	50,503	27,537	14.786	5.575	45.47	2.65
		64	68,600	41,293	74,043	43,224	17.212	6.695	41.62	2.57
		128	97,104	63,427	102,604	65,988	19.536	8.063	35.69	2.42
		256	140,910	96,733	145,102	98,625	21.798	10.026	32.03	2.17
	bmw3 2	32	56,881	33,049	64,026	35,743	14.105	5.816	44.17	2.43
		64	83,150	51,511	89,492	54,225	16.518	7.085	39.41	2.33
		128	116,628	76,555	127,693	81,583	18.853	8.888	36.11	2.12
		256	177,088	120,850	185,200	125,376	21.093	11.153	32.30	1.89
	AVERAGE	32	1.000	0.549	1.000	0.532	1.000	0.716	46.84	1.64
		64	1.000	0.585	1.000	0.574	1.000	0.725	42.59	1.60
		128	1.000	0.634	1.000	0.624	1.000	0.757	37.65	1.51
		256	1.000	0.680	1.000	0.670	1.000	0.817	32.98	1.37

Table 7

 7 Properties of the hypergraphs used in the experiments on partitioning hypergraphs with fixed vertices

	Dataset	# of vertices	# of nets	# of pins Avg. net size
	BF-32	28,930	4,800	688,018	143.34
	BF-64	28,962	9,600	930,412	96.92
	BF-128	29,026	19,200	1,335,049	69.53
	CC-32	56,374	4,800	1,133,858	236.22
	CC-64	56,406	9,600	1,472,295	153.36
	CC-128	56,470	19,200	2,094,107	109.07
	OP-32	68,190	4,800	1,276,595	265.96
	OP-64	68,222	9,600	1,629,169	169.70
	OP-128	68,286	19,200	1,924,807	100.25

Table 8

 8 Performance of PaToH and kPaToH in partitioning hypergraphs with fixed vertices

			Min. cutsize	Avg. cutsize	Avg. time		Improvement
	Dataset	K	PaToH	kPaToH	PaToH	kPaToH	PaToH	kPaToH	%Cutsize	Spdup
	BF-32	32	9,474	7,507	9,639	7,604	5.394	2.018	21.11	2.67
		64	11,343	9,379	11,799	9,623	5.906	2.186	18.44	2.70
		128	14,962	12,695	15,212	12,916	6.309	2.373	15.09	2.66
	BF-64	32	17,790	13,538	18,625	13,691	5.152	2.088	26.49	2.47
		64	21,473	16,583	22,010	16,867	5.726	2.309	23.37	2.48
		128	25,548	21,354	26,406	21,652	6.284	2.585	18.00	2.43
	BF-128	32	34,522	24,234	35,751	24,568	5.770	2.709	31.28	2.13
		64	39,837	28,855	41,521	29,366	6.569	3.003	29.28	2.19
		128	47,448	36,180	48,652	36,589	7.006	3.298	24.79	2.12
	CC-32	32	9,534	8,438	9,668	8,619	4.865	2.248	10.85	2.16
		64	12,608	10,931	12,927	11,123	5.547	2.472	13.96	2.24
		128	17,635	14,796	17,873	14,956	6.172	2.771	16.32	2.23
	CC-64	32	17,466	15,349	17,952	15,512	4.623	2.671	13.59	1.73
		64	21,397	19,161	21,740	19,316	5.344	3.040	11.15	1.76
		128	28,088	24,685	28,729	25,010	6.012	3.282	12.94	1.83
	CC-128	32	33,201	28,803	34,298	28,986	5.407	3.677	15.49	1.47
		64	40,036	34,947	40,677	35,225	6.233	4.218	13.40	1.48
		128	49,454	43,960	50,315	44,321	6.965	4.556	11.91	1.53
	OP-32	32	8,717	6,953	8,935	7,042	18.714	6.159	21.18	3.04
		64	10,367	8,530	10,804	8,622	19.485	6.372	20.19	3.06
		128	13,155	11,135	13,463	11,313	21.275	6.697	15.97	3.18
	OP-64	32	15,693	12,507	16,402	12,668	17.462	6.010	22.76	2.91
		64	18,823	15,028	19,399	15,178	19.317	6.291	21.76	3.07
		128	22,972	18,745	23,404	19,238	20.020	6.757	17.80	2.96
	OP-128	32	30,418	22,440	31,076	22,717	13.119	5.073	26.90	2.59
		64	34,735	25,876	35,157	26,505	14.981	5.425	24.61	2.76
		128	39,643	31,807	40,642	32,133	16.047	5.971	20.94	2.69
	AVERAGE	32	1.000	0.802	1.000	0.789	1.000	0.448	21.07	2.35
		64	1.000	0.814	1.000	0.804	1.000	0.437	19.57	2.42
		128	1.000	0.835	1.000	0.829	1.000	0.437	17.09	2.40

Table 9

 9 Performance of kPaToH with and without bipartite graph matching (BGM) in partitioning hypergraphs with a randomly selected number (F ) of fixed vertices

				Avg. cutsize	%Improvement	%Share of
					kPaToH	kPaToH	kPaToH	kPaToH	BGM in the
	Dataset	F	K	PaToH	w/o BGM w/ BGM w/o BGM w/ BGM improvement

Table 10

 10 Averages of the results provided in Table9over F and K ducted on benchmark datasets indicate that the proposed algorithm is quite fast and effective in minimizing the cutsize compared to the state-of-the-art hypergraph partitioning tool PaToH. Especially, in the multi-constraint and fixed vertices domain, the obtained results are quite promising in terms of both execution time and solution quality. On average, the cutsize improvement of kPaToH over PaToH is around 20% and 40% at the 2-constraint and 4-constraint cases, respectively. Similarly, in partitioning hypergraphs with fixed vertices, kPaToH outperforms PaToH by up to 33% in cutsize as it runs 2.3 times faster on average.

	Averages over F			Averages over K
		%Improvement	%Share of		%Improvement	%Share of
		kPaToH	kPaToH	BGM in the		kPaToH	kPaToH	BGM in the
	F	w/o BGM w/ BGM	improvement	K	w/o BGM w/ BGM	improvement
	256	9.57	14.38	32.03	128	14.18	18.73	24.42
	512	11.40	17.46	33.29	256	10.64	16.61	34.46
	1024	14.10	20.24	29.60	512	10.25	16.75	36.03

 [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF]This work is partially supported by the Scientific and Technological Research Council of Turkey (T ÜB İTAK) under project EEEAG-106E069. 2 The work of this author was supported by the Scientific and Technological Research Council of Turkey (T ÜB İTAK) under the program 2219, by the University Research Committee of Emory University, and by Agence Nationale de la Recherche through project ANR-06-CIS6-010.