Combining Two Local Search Approaches to Hypergraph Partitioning

Introduction

The focus of our work is on search heuristics for balanced min-cut hypergraph partitioning, a well-known combinatorial optimization problem. In general terms, the problem seeks to assign every ver­ tex of a hypergraph to one of two subsets to minimize the number of connections between the two subsets, subject to having approx­ imately the same number of vertices in each subset. Hypergraph partitioning is important in circuit layout because circuits are often represented by hypergraphs, e.g. in placement by recursive bisec­ tion. Many efficient hypergraph partitioning algorithms have been developed [3, 4) . Here, we discuss the combination of two local search heuristics: the Fiduccia-Mattheyses (FM) hypergraph parti­ tioning heuristic [3], and the biased random walk heuristic, adapted from the WalkSAT SAT solver [5].

Our work is motivated by attempts to generalize well-known local search procedures ~5, 3] beyond their original domains. We developed a SAT solver based on the FM algorithm [3], and a hy­ pergraph partitioner, WalkPart, based on the WalkSAT algorithm from [5] . The WalkPart algorithm is described in Section 3. A detailed description of the SAT solver is beyond the scope of this paper. Our results show that WalkPart outperforms a highly tuned implementation of FM on several circuit benchmarks. The algo­ rithms also produce very different solutions and appear to have different local minima, suggesting that a hybrid strategy might be effective. Empirical results show that the hybrid approach outper­ forms both algorithms, in terms of runtime and solution quality. Our main contributions are summarized as follows.

• We describe the balanced min-cut hypergraph partitioning algorithm, WalkPart, based on the WalkSAT satisfiability solver [5]
• We propose the combination of the FM and WalkPart heuris­ tics to form a "hybrid" heuristic, and perform two experi­ ments
• Empirically, we show that a hybrid strategy achieves signifi­ cantly better performance than either heuristic alone

Combining Two Local Search Approaches to Hypergraph Partitioning

Arathi Ramani and Igor Markov Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor 48109-2122 { ramania,imarkov }@eecs.umich.edu

2 Background and Previous Work

2.1 Hypergraph Partitioning Problem:

A hypergraph H(V,E) is defined as a set, V, of vertices, and a set, E, of hyperedges, where each edge e E E is a set of two or more vertices from V. The k- way hypergraph partitioning problem is stated as follows: Let H(V,E) be a hypergraph with weighted ver­ tices and edges. The problem asks to find a minimum cost parti­ tion pk of the vertices of H to k disjoint subsets. The cost function c(Pk) typically used is edge cut, the sum of the weights of the hy­ peredges cut by the partition (this is called min-cut partitioning). A hyperedge is cut exactly when all of its vertices are in more than one subset. Constraints may be imposed on a partition e.g. limiting the total vertex weight in each subset (balance constraints). The balance-constrained weighted hypergraph partitioning problem is N P-hard. The algorithms in this work deal with the balanced min-cut hypergraph hi-partitioning problem, i.e., we consider only the case where k = 2. In circuit layout, hypergraphs represent cir­ cuits by mapping vertices to signal nodes, and hyperedges to signal nets. In this context, we use the words "node" and "net" to mean "vertex" and "hyperedge" when referring to hypergraphs in this document.

2.2 The Fiduccia-Mattheyses Heuristic

The Fiduccia-Mattheyses (FM) [3] heuristic for hi-partitioning cir­ cuit hypergraphs is an iterative improvement algorithm. FM starts with an arbitrary initial solution and changes the solution by a se­ quence of moves, organized as passes. At the beginning of a pass, all vertices are free to move (unlocked). Each possible move is la­ beled with the immediate change in total cost it would cause (called "gain"). Iteratively, a move with highest gain is selected and exe­ cuted, which may result in a lower, higher or unchanged solution cost 1 · The moved vertex is locked, i.e., not allowed to move again during that pass. Since moving a vertex can change gains of ad­ jacent vertices, all affected gains are updated. Selection and exe­ cution of a best-gain move, followed by gain update, are repeated until every vertex is locked. The best solution seen during the pass is adopted as the starting solution of the next pass. The algorithm terminates when a pass fails to improve solution quality.

The FM heuristic is now used as a component in multi-level partitioning algorithms [4] which create a series of clustered hy­ pergraphs, partition the most clustered with "flat" FM and then refine unclustered versions of the produced partition by applying FM in incremental mode. A highly optimized, leading edge im­ plementation of FM in this context is available in [2]. This work only deals with "flat" partitioning heuristics in the hope that im­ proved flat heuristics will lead to improved multi-level heuristics. This assumption will be verified in our future work.

1 In a problem with balance constraints, moves should also not violate the legality constraint

2.3 The WalkSAT Satisfiability Solver

The WalkSAT algorithm [5] is a stochastic local search heuristic for Boolean Satisfiability. WalkSAT is an improvement on GSAT (Selman et a!., 1992), a greedy algorithm that starts with a random assignment and flips variables one at a time. The variable chosen for flipping is always the one that would cause the greatest im­ mediate reduction in the number of violated clauses. WalkSAT [5] improves on GSAT by using a biased random walk to avoid getting stuck in local minima.

To select the next variable to flip, WalkSAT picks a clause at random from the unsatisfied clauses. With probability p, it flips a variable picked randomly from this clause. With probability I - p it flips the variable that would cause the least number of clauses to be violated when flipped.

3 The WalkPart Algorithm

The WalkPart algorithm is a stochastic local search algorithm for balance-constrained hypergraph bisection. It performs a sequence of moves, until a preset maximum number of moves is reached. A "move" moves a vertex from one partition to another, if balance constraints are not violated. Moves are chosen using criteria sim­ ilar to WalkSAT: with probability p, a vertex is picked at random, and with probability I - p, a vertex is chosen to minimize some cost function. The selected vertex is then moved to the other par­ tition (if balance constraints allow). After a move, the costs of vertices adjacent to the moved vertex will change, and these are updated.

The move selection procedure is explained in more detail as follows. A net from among the cut nets is chosen at random. With probability p, a vertex is chosen from that net at random, and with probability I - p, the vertex that minimizes the cost function under the decision heuristic in use is chosen from the net. If a chosen move is illegal, the selection process is repeated until a legal move is found.

Due to space constraints, we describe only the decision heuris­ tic that performed best on the benchmarks in this paper, the nor­ malized node score heuristic.

Normalized Score Heuristic: The FM heuristic is concerned with the "gain" of a node, determined by the number of nets that can be "cut" or "uncut" by moving the node. Therefore, it only considers "critical" nets that can be cut or uncut in a single move. It is mentioned in [4] that a more thorough measure would also estimate the effort required to uncut the net. We propose a new measure, the "score" of a node, defined as the number of moves required to uncut the net if the node in question was moved. In practice, scores are normalized to avoid bias due to net sizes. We can quickly approximate the score for a given node for a partic­ ular net as follows. Consider a node, ni, presently in partition j U = 0/ I). Let ek be a hyperedge containing ni , dk be the degree of ek> and mk,j be the number of nodes from edge ek in partition j, including ni . Then the normalized score of ni due to ek is m,r 1 . e, The total node score is the sum of the scores due to all nets in which the node occurs. The idea of using a score comes from the work in [6], which discusses an adaptation of WalkSAT to formu­ las with pseudo-boolean constraints. In WalkPart, with probability I - p the algorithm picks the node from the chosen net with the minimum score. For the benchmarks in this paper, our empirical results are strongest when this heuristic is used, and when p = 0. 1.

4 Hybrid Partitioner

Through empirical evaluation, we observe that WalkPart often out­ performs a leading-edge implementation of FM [2], on standard industry circuit benchmarks [!]. Also, WalkPart frequently does well on benchmarks where FM does not, implying that both algo­ rithms do not find similar solutions or search in the same areas of the search space. These observations suggest that a hybrid algo­ rithm might be able to exploit the strengths of both.

The hybrid approach alternates runs ofFMPart (the FM imple­ mentation available in [2]) and WalkPart. It is known that FMPart reduces the net cut greatly in the first few passes, and then spends time performing more passes for relatively small improvements. The hybrid algorithm starts by performing one or more passes of FMPart, and then performs moves of WalkPart to improve FM­ Part's solution. Control then switches back to FMPart, and so on. A combined FMPart-WalkPart pass constitutes one pass of the hy­ brid algorithm. A preset number of hybrid passes are run before the algorithm terminates. The use of a WalkSAT-Iike randomized component makes it difficult to find obvious convergence criteria. We hope to address this issue in future works. In practice, we observe that the tendency of FM to converge rapidly causes con­ siderable reductions in net cut in a fairly small number of passes. This can be seen from our results in Section 5. Many stochastic local search approaches use such preset limits because of the un­ predictable nature of the search.

5 Results

In this section, we discuss the empirical performance of our al­ gorithms. We cannot include the results of all our experiments with different tuning and parameter settings due to limited space. We present results of two relatively simple experiments that illus­ trate the utility of the hybrid technique. The benchmarks used are standard IBM circuit partitioning benchmarks [ 1). Although the benchmarks are chosen from the VLSI domain, all the algo­ rithms discussed here are general and can be used on instances from any application. fn the experiments, WalkPart uses the nor­ malized score heuristic, and randomness quotient p = 0. I. 2 We use the FM partitioning package by Caldwell et. al., available at [2], for the FM component. WalkPart is written in C++.

fn the first experiment, we run I 0 hybrid passes after first run­ ning FM once to completion. Each hybrid pass performs 100,000 WalkPart moves followed by a single FMPart pass. The solution after a pass is used as the starting solution for the next pass. Results for this experiment are shown in Table I.

The hybrid algorithm is compared against FMPart and Walk­ Part, run individually. WalkPart uses the normalized score heuris­ tic and p = 0.1, with two different move limits: 500,000 and 2,000,000. Because some moves are picked randomly, increas­ ing the move limit does not always produce better solutions. We show results for the move limit where net cut was lower. For each benchmark we report average solution quality and runtime over three independent starts on a 1.2 GHz AMD Athlon processor with 1-2GB, running Linux.

fn the table, columns 1-3 describe benchmark statistics. The benchmarks are named ibmno+t%, where ibm indicates an IBM benchmark, no is the serial number, t indicates the balance con­ straint. Tolerances specify the maximum legal disparity between subset weights as a percentage of total vertex weight. The next three columns give WalkPart's number of moves, runtime and re­ sulting net cut. The next four columns show runtimes and net cuts for FM and the hybrid algorithm. The lowest net cut out of the 3 algorithms is boldfaced. The last two columns show the ratio of net cut and runtime of the hybrid algorithm to net cut and runtime ofFMPart. Averages are shown at the bottom.

We observe that the hybrid algorithm achieves smaller cuts than both FMPart and WalkPart on most benchmarks. This is to be expected, since hybrid passes are run on a solution produced by FMPart. Nevertheless, we can make some important observations. First, FMPart frequently converges when a much better solution is achievable. Second, it is possible to achieve a better solution by introducing a randomized component with a different decision heuristic (normalized score). Walk Part can be used to lead FMPart out of local minima by performing random moves, after which FM­ Part can be run again to find a better solution. However, this exper­ iment has a runtime cost. On average, this strategy improves run time by 30% over FMPart, but is 1.7 times slower.

Our second experiment improves runtime by avoiding the initial run of FMPart. This experiment also uses I 0 hybrid passes. Each pass consists of 2 passes of FMPart followed by 50,000 moves ofWalkPart. Results for this experiment are in Table 3.

'Parameter settings were not chosen arbi trarily. After testing, we chose the values that gave best overall performance.

It is clear that the second hybrid configuration is competitive with FMPart and WalkPart in terms of runtime, and frequently pro­ duces better solutions. Also, while either FMPart or WalkPart may achieve lower net cut than the hybrid algorithm, it is very rare that both of them do so. The hybrid approach is usually close to the best solution achieved by either. On average, the second hybrid configuration improves net cut by 15% and is about 7% faster than FMPart alone.

6 Conclusions and Future Work

In this work, we introduce our "crossover" hypergraph partitioning algorithm, WalkPart. We combine WalkPart with the well-known Fiduccia-Mattheyses (FM) heuristic for hypergraph partitioning to produce a hybrid heuristic that draws on the strengths of both tech­ niques. We achieve substantial improvement over FMPart with a very simple approach that requires almost no tuning.

Our first experiment shows that net cuts achieved by FM, a widely used algorithm for this application, can be significantly im­ proved (by 30%), albeit with a runtime cost. However, our second experiment reduces net cuts by an average of 15%, and runtime by 7% over FM. Our results show that combining these two heuris­ tics results in a search procedure that is more powerful than either heuristic used alone. Strong empirical results for the proposed hy­ brid algorithm motivate further research. We are incorporating our flat partitioning algorithms into the multilevel framework [ 4, 2] and plan to make it available for use in CAD tools. We are also continu­ ing our investigation of effective search procedures for partitioning and looking for new techniques that can be hybridized with exist­ ing ones.