ABSTRACT
This chapter presents a historical survey of partitioning and clustering techniques ranging from move-based methods to multilevel techniques to mathematical formulations including quadratic, linear, and integer programming approaches. It introduces the basic concepts and notations relevant to partitioning and clustering and describes move-based partitioning techniques. The chapter also describes mathematical partitioning formulations and clustering techniques, which are employed in multilevel partitioners. It outlines the most significant developments in the field of iterative improvement-based partitioning. The chapter discusses a few noteworthy improvements to the original Fiduccia-Mattheyses (FM) implementation that have helped the acceptance of FM as the most popular partitioning technique. The combinatorial nature of very large scale integrated physical design problems lends itself nicely to formulations involving graphs or matrices. In addition to the usual balance constraints, partitioning formulations may include constraints for vertices that are assigned to a specific block. Hierarchical techniques merge all vertices into clusters at the same time.
