Clustering optimization based on simulated annealing algorithm for reconfigurable systems-on-chip

A bottom-up circuit clustering step is one of the most significant steps in the reconfigurable systems-on-chip design flow. Qualitative clustering provides the efficiency of subsequent placement and routing steps. The goals of circuit clustering are following: a) achieving the high density by minimizing the number of clusters; b) decreasing time delays by localizing time-critical connections within a cluster and using fast local routing resources. There are several popular solutions to these issues such as partitioning algorithms, bottom-up clustering and heuristic algorithms. In this paper we present a simulated annealing approach for clustering optimization for the reconfigurable system-on-chip based on the “Almaz-14” FPGA. We analyze and compare our algorithm with three popular approaches: basic clustering; Kernighan-Lin partitioning algorithm; clustering algorithm using Rent's rule. Experimental results on a set of ISCAS'85 and ISCAS'89 benchmarks demonstrate that presented algorithm in cooperation with algorithm using Rent's rule has comparable effectiveness to other clustering algorithms.