Multilevel circuit partitioning

摘要: Many previous works in partitioning have used some underlying clustering algorithm to improve performance. As problem sizes reach new levels of complexity, a single application is insufficient produce excellent solutions. Recent work has illustrated the promise multilevel approaches. A recursively clusters instance until its size smaller than given threshold, then unclusters instance, while applying refinement algorithm. In this paper, we propose that exploits latest innovations classical iterative Our method also uses technique control number our matching-based Experimental results show heuristic outperforms numerous existing bipartitioning heuristics with improvements ranging from 6.9 27.9% for 100 runs and 3.0 20.6% just ten (while using less CPU time). Further, generates solutions better best known mincut bipartitionings seven ACM/SIGDA benchmark circuits, including golem3 (which over 100000 cells). We present quadrisection which compare favorably partitionings obtained by GORDIAN cell placement tool. been as basis an effective package.