CHIP: Clustering hotspots in layout using integer programming

Clustering algorithms have been explored in recent years to solve hotspot clustering problem in Integrated Circuit design. With various applications in Design for Manufacturability flow such as hotspot library generation, systematic yield optimization and design space exploration, generating good quality clusters along with their representative clips is of utmost importance. With several generic clustering algorithms at our disposal, hotspots can be clustered based on the distance metric defined while satisfying some tolerance conditions. However, the clusters generated from generic clustering algorithms need not achieve optimal results. In this paper, we introduce two optimal integer linear programming formulations based on triangle inequality to solve the problem of minimizing cluster count while satisfying given constraints. Apart from minimizing cluster count, we generate representative clips that best represent the clusters formed. We achieve better cluster count for both formulations in most test cases as compared to the results published in literature on the ICCAD 2016 contest benchmarks as well as the reference results reported in the ICCAD 2016 contest websit