Partitioning optimization by iterative reassignment of the hierarchically built clusters with border elements

摘要

This article presents a new approach for electronic circuit partitioning. The idea is the usage of hierarchically built clusters of arbitrary sizes created from the border elements of nets that belong to the cut. The implementation of such approach helps to improve the quality of solution by reducing the danger of being trapped in the local minima and also enables the decrease of the runtime. The process consists of four stages. At the first stage, some initial partitioning is either carried out by a constructive algorithm or generated randomly. At the second stage, two Optimal Reduction Trees are constructed from border elements. The remaining fragments are considered as single elements without border elements. All of these trees clusters are arranged by the gain of transferring from one of the remaining partitions to the other. The third stage is the main optimization phase. Iterative optimization procedures consisting in exchanging and transferring of the arbitrary size clusters chosen by the transfer gain are performed during it. The perturbation of the solution concerning the transference of one or a few clusters from one partition to another is used at the fourth stage to escape from the local extrema. The developed approach has been shown to demonstrate a performance with high quality results.