Two Novel Multiway Circuit Partitioning Algorithms

Using Relaxed Locking

Ali DAS?DAN?and Cevdet AYKANAT

Department of Computer Engineering and Information Science

Bilkent University

06533 Bilkent, Ankara, Turkey

Abstract

All the previous Kernighan-Lin based circuit partitioning algorithms employ the locking mechanism, which enforces each cell to be moved exactly once per pass. In this paper, we propose for multiway circuit partitioning two novel approaches to overcome this limitation. The proposed approaches are based on our claim that the performance of a partitioning algorithm gets better by allowing each cell to be moved more than once per pass. The first approach introduces the phase concept so that each pass can contain more than one phase, and each cell has a chance to be moved in all the phases. This approach uses the locking mechanism in a relaxed manner in that it does not allow a cell to be moved more than once in a phase. The second approach does not use the locking mechanism at all. It introduces the mobility concept, which allows a cell to be moved more than once per pass. Each approach leads to a Kernighan-Lin based generic algorithm whose parameters can be set in such a way that better performance is obtained by spending more time. By setting these parameters, we generated three versions of each generic algorithm. The proposed algorithms were experimentally evaluated in comparison with Sanchis' multiway circuit partitioning algorithm (FMS algorithm) and the simulated annealing algorithm (SA algorithm) on benchmark circuits. The proposed algorithms outperformed FMS algorithm significantly especially when the number of parts in the partition was large and the circuit was sparse. Their performance is comparable to that of SA algorithm though the running time SA algorithm is far larger than those of the proposed algorithms. We also performed some experiments on the parameters of the proposed algorithms, and provided guidelines for good parameter settings. Besides, we gave a new formulation of multiway circuit partitioning that combined those of the previous approaches, and presented detailed algorithms and their time and space complexity analysis. We observed that experimental results supported our claim. The proposed approaches are effective and efficient, and are applicable to almost all of the previous Kernighan-Lin based algorithms.

1 Introduction

Circuit partitioning deals with the task of dividing (partitioning) a given circuit into two or more blocks (parts) such that the total weight of the signal nets interconnecting these parts is minimized while maintaining a given balance criterion among the part sizes. Since circuits can be appropriately represented by hypergraphs [23], we modeled circuits with hypergraphs, and will use circuit and hypergraph terms interchangeably. Hypergraph partitioning has many important applications in VLSI layout, e.g., [1, 6]. The importance of hypergraph partitioning is mostly due to its connection to the divide-and-conquer paradigm. A partitioning algorithm divides a problem into semi-independent subproblems, and tries to reduce the interaction between these subproblems. This division of a problem into smaller subproblems results in a substantial reduction in the search space of the original problem [25]. Hypergraph partitioning problem is an NP-hard combinatorial optimization (minimization) problem [8, 17], and hence, we should resort to heuristic algorithms to obtain a good solution, or hopefully a near-optimal solution. Moreover, such algorithms should run in low-order polynomial time because the problem sizes are usually very large. We now review the previous work and explain our motivation.

?Current Address: Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield, Urbana, IL 61801, USA