| Application of SAT Approach to Switch Blocks Routing for Reconfigurable System-on-a-chip |
|
 |
|
|
| Authors |
| | Zhukov D.V. |
| | Zheleznikov D.A. |
| | Zapletina M.A. |
| Date of publication |
| | 2020 |
| DOI |
| | 10.31114/2078-7707-2020-1-26-32 |
|
| Abstract |
| | The paper presents the SAT based approach to detailed routing of the switch blocks in an island style reconfigurable system-on-a-chip. The goal of the routing procedure is to find such a combination of internal switching elements of a switch block that guarantees all project nets are completely routed without any conflicts. An important advantage of the presented SAT approach in compare to the other routing algorithms is the possibility to prove mathematically if the current design is routable or not. In the SAT approach, a system of Boolean equations is composed for each switch block. It consists of the intrinsic (basic) and conflict constraints. The basic constraints occur from the architecture of the switch block. The previously routed nets cause the conflict constraints that are produced by the early routing iterations. The constraints are converted into a Boolean system of equations that is processed by the SAT solver. The paper presents the detailed routing task solved for the switch blocks of two types. Their main difference, shown in a flexibility parameter, is the quantity of tracks the current pin of the switch block can be connected to. The computational tests confirmed the presented algorithm meets the requirements of the netlist full routability and minimization of routing runtime. The algorithm being implemented in C has linear complexity. |
| Keywords |
| | reconfigurable system-on-a-chip, SAT, detailed routing, island style architecture, hierarchical routing. |
| Library reference |
| | Zhukov D.V., Zheleznikov D.A., Zapletina M.A. Application of SAT Approach to Switch Blocks Routing for Reconfigurable System-on-a-chip // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2020. Issue 1. P. 26-32. doi:10.31114/2078-7707-2020-1-26-32 |
| URL of paper |
| | http://www.mes-conference.ru/data/year2020/pdf/D041.pdf |
