| Partitioning Algorithm Based on Simulated Annealing for Reconfigurable Systems-on-Chip |
|
 |
|
|
| Authors |
| | Gavrilov S.V. |
| | Zheleznikov D.A. |
| | Chochaev R. |
| | Khvatov V.M. |
| Date of publication |
| | 2018 |
| DOI |
| | 10.31114/2078-7707-2018-1-199-204 |
|
| Abstract |
| | Partitioning is one of the most significant steps in the reconfigurable systems-on-chip design flow. High-quality partitioning ensures effective placement and routing steps. The goals of circuit partitioning are following: a) achieving the high density by minimizing the number of groups; b) decreasing time delays by localizing time-critical connections within a group and using fast local routing resources. There are several popular partitioning problem solutions, such as top-down decomposition algorithms, bottom-up clustering and different heuristic algorithms. In this paper we present a simulated annealing approach for partitioning optimization for the reconfigurable system-on-chip (RSoC) based on the “Almaz-14” FPGA. This RSoC contains more than twenty thousand logic elements arranged into groups of size 256. It has typical island architecture with rich local and poor global routing resources therefore partitioning step becomes vital for successful placement and routing. In our work we use simulated annealing for optimization the initial solution generated by iRAC clustering algorithm. The cost function is based on Rent's rule and it is a function of: (1) Rent’s exponent of each cluster, (2) number of LE in each cluster, (2) total number of LE in the circuit and (3) total number of clusters. Such parameters as annealing schedule, initial and final temperature values were obtained experimentally. We analyze and compare our algorithm with three popular approaches: basic clustering; Kernighan-Lin partitioning algorithm; clustering algorithm iRAC. Each method was verified on the set of benchmark circuits ISCAS-85 and ISCAS-89. The algorithms were configured in such way to divide the benchmark circuits into an equal number of clusters. Benchmark circuits were placed using the algorithm based on the simulated annealing method with modified cost function and routed by using the modified algorithm A* with stop at the first iterations of rip-up and reroute procedure. Experimental results demonstrate that presented algorithm with initial placement generated by iRAC algorithm has comparable effectiveness to other partitioning algorithms. |
| Keywords |
| | design automation; clustering; Rent’s rule; Kernighan-Lin algorithm; Simulated Annealing. |
| Library reference |
| | Gavrilov S.V., Zheleznikov D.A., Chochaev R., Khvatov V.M. Partitioning Algorithm Based on Simulated Annealing for Reconfigurable Systems-on-Chip // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2018. Issue 1. P. 199-204. doi:10.31114/2078-7707-2018-1-199-204 |
| URL of paper |
| | http://www.mes-conference.ru/data/year2018/pdf/D083.pdf |
