Recent directions in netlist partitioning: a survey

This survey describes research directions in netlist partitioning during the past two decades in terms of both problem formulations and solution approaches, and discusses methods which combine clustering with existing algorithms (e.g., two-phase partitioning).

Abstract

This survey describes research directions in netlist partitioning during the past two decades in terms of both problem formulations and solution approaches. We discuss the traditional min-cut and ratio cut bipartitioning formulations along with multi-way extensions and newer problem formulations, e.g., constraint-driven partitioning (for FPGAs) and partitioning with module replication. Our discussion of solution approaches is divided into four major categories: move-based approaches, geometric representations, combinatorial formulations, and clustering approaches. Move-based algorithms iteratively explore the space of feasible solutions according to a neighborhood operator; such methods include greed, iterative exchange, simulated annealing, and evolutionary algorithms. Algorithms based on geometric representations embed the circuit netlist in some type of "geometry", e.g., a 1-dimensional linear ordering or a multi-dimensional vector space; the embeddings are commonly constructed using spectral methods. Combinatorial methods transform the partitioning problem into another type of optimization, e.g., based on network flows or mathematical programming. Finally, clustering algorithms merge the netlist modules into many small clusters; we discuss methods which combine clustering with existing algorithms (e.g., two-phase partitioning). The paper concludes with a discussion of benchmarking in the VLSI CAD partitioning literature and some perspectives on more promising directions for future work.