RECENT DIRECTIONS IN NETLIST PARTITIONING - A SURVEY

This survey describes research directions in netlist partitioning duri ng the past two decades in terms of both problem formulations and solu tion approaches. We discuss the traditional min-cut and ratio cut bipa rtitioning formulations along with multi-way extensions and newer prob lem formulations, e.g., constraint-driven partitioning (for FPGAs) and partitioning with module replication. Our discussion of solution appr oaches is divided into four major categories: move-based approaches, g eometric I representations, combinatorial formulations, and clustering approaches. Move-based algorithms iteratively explore the space of fe asible solutions according to a neighborhood operator; such methods in clude greed, iterative exchange, simulated annealing, and evolutionary algorithms. Algorithms based on geometric representations embed the c ircuit netlist in some type of ''geometry'', e.g., a 1-dimensional lin ear ordering or a multi-dimensional vector space; the embeddings are c ommonly constructed using spectral methods. Combinatorial methods tran sform the partitioning problem into another type of optimization, e.g. , based on network flows or mathematical programming. Finally, cluster ing 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 b enchmarking in the VLSI CAD partitioning literature and some perspecti ves on more promising directions for future work.