DEVELOPMENT OF THE DETAILED PLACEMENT ALGORITHM FOR FPGAS
Abstract
Hierarchical field-programmable gate arrays (FPGAs) consist of an array of programmable
logic blocks arranged into groups. Successful routing requires optimal placement of logic elements
within the groups, considering the architectural features of the local interconnections. Classical
algorithms are not able to consider these features. That’s why, the development of new algorithms
is required. In this paper, we present a detailed placement algorithm with a new metric that
allows us to estimate the number of available local interconnections inside the groups of logic
blocks, considering the architectural features of the local interconnections. The detailed placement
algorithm consists of several stages. At the first stage, the group of logic elements is transformed
into a directed graph. Then, the placement order of logic elements in the group is determined using
the breadth-first search algorithm. At the final stage, for each element, according to the obtained
order, the optimal placement in the group is determined, considering the new metric.
If there is no optimal position in the group among the free ones, the occupied positions are
checked. The current element is placed in the occupied position, and a new position is searched
for the replaced element. Such replacements can be performed repeatedly, increasing the probability
of finding the optimal placement configuration. The proposed algorithm was verified on a set
of benchmark circuits ISCAS’85, ISCAS’89, Cpu8080 and VGA. Experimental results show that
the developed algorithm reduces the number of global interconnections used for global routing by
10% on average and increases the number of local interconnections used for detailed routing by
30% on average compared to the sequential placement algorithm. The average routing time remained
unchanged.
References
Mashinostroenie: respublikanskiy mezhvedomstvennyy sbornik nauchnykh trudov: po
materialam Mezhdunarodnoy nauchno-tekhnicheskoy konferentsii «Materialy, oborudovanie i
resursosberegayushchie tekhnologii v mashinostroenii», 06-09 aprelya 2010 goda [Mechanical
engineering: republican interdepartmental collection of scientific papers: based on the materials
of the International scientific and technical conference “Materials, equipment and resource-
saving technologies in mechanical engineering”, April 06-09, 2010]: In 2 vol., ed. by
B.M. Khrustaleva. Minsk: BNTU, 2012, Issue 26, Vol. 2, pp. 255-259.
2. Farooq U., Marrakchi Z., Mehrez H. Tree-based heterogeneous FPGA architectures: application
specific exploration and optimization. Springer Science & Business Media, 2012, pp. 186.
3. Singh A., Parthasarathy G., Marek-Sadowska M. Interconnect resource-aware placement for hierarchical
FPGAs, IEEE/ACM International Conference on Computer Aided Design. ICCAD 2001.
IEEE/ACM Digest of Technical Papers (Cat. No. 01CH37281). IEEE, 2001, pp. 132-136.
4. Boutros A., Betz V. FPGA architecture: Principles and progression, IEEE Circuits and Systems
Magazine, 2021, Vol. 21, No. 2, pp. 4-29.
5. PLIS emkost'yu 21 502 ventiley 5510TS068 [FPGA with a capacity of 21,502 gates
5510TS068]. JSC Mikron. Available at: https://mikron.ru/products/high-relic/
programmiruemaya-logika-fpga/fpga/product/5510ts068/ (accessed 29 January 2022).
6. Petelin O., Betz V. Wotan: evaluating FPGA architecture routability without benchmarks,
ACM Trans. Reconfigurable Technol. Syst., 2018, Vol. 11, No. 2, pp. 1-23.
7. Frolova P.I., Chochaev R.Zh., Ivanova G.A., Gavrilov S.V. Algoritm razmeshcheniya s
optimizatsiey bystrodeystviya na osnove matrits zaderzhek dlya rekonfiguriruemykh sistem na
kristalle [Placement algorithm with performance optimization based on delay matrices for reconfigurable
systems on a chip], Problemy razrabotki perspektivnykh mikro- i
nanoelektronnykh sistem (MES) [Problems in the development of advanced micro- and
nanoelectronic systems (MES)], 2020, Issue 1, pp. 2-7.
8. Frolova P.I., Khvatov V.M., Chochaev R.Zh. Sravnitel'nyy analiz metodov klasterizatsii i
razmeshcheniya skhem dlya rekonfiguriruemykh sistem na kristalle [Comparative analysis of
clustering methods and circuit placement for reconfigurable systems on a chip], Problemy
razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES) [Problems of development
of advanced micro- and nanoelectronic systems (MES)], 2022, Issue 4, pp. 63-70.
9. Kureichik V.V., Zaporozhets D.Y., Zaruba D.V. Partitioning of VLSI fragments based on the
model of glowworm's behavior, Proceedings of the 19th International Conference on Soft
Computing and Measurements, SCM 2016, 2016, pp. 268-272.
10. Li W. et al. UTPlaceF 3.0: A parallelization framework for modern FPGA global placement,
2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 2017,
pp. 922-928.
11. Chen G., et al. RippleFPGA: Routability-driven simultaneous packing and placement for modern
FPGAs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,
2017, Vol. 37, No. 10, pp. 2022-2035.
12. Dhar S., et al. Detailed placement for modern FPGAs using 2D dynamic programming, 2016
IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 2016, pp. 1-8.
13. Nikolić S., Zgheib G., Ienne P. Detailed Placement for Dedicated LUT-Level FPGA Interconnect,
ACM Transactions on Reconfigurable Technology and Systems, 2022, Vol. 15, No. 4, pp. 1-33.
14. Gavrilov S.V., Zheleznikov D.A., Chochaev R.Zh. Razrabotka i sravnitel'nyy analiz metodov
resheniya zadachi razmeshcheniya dlya rekonfiguriruemykh sistem na kristalle [Development
and comparative analysis of methods for solving the placement problem for reconfigurable
systems on a chip], Izvestiya vysshikh uchebnykh zavedeniy. Elektronika [News of higher educational
institutions. Electronics], 2020, Vol. 25, No. 1, pp. 48-57.
15. Fan D.K., Shi P. Improvement of Dijkstra's algorithm and its application in route planning,
2010 seventh international conference on fuzzy systems and knowledge discovery. IEEE. 2010,
Vol. 4, pp. 1901-1904.
16. Dijkstra E.W. A note on two problems in connexion with graphs, Edsger Wybe Dijkstra: His
Life, Work, and Legacy, 2022, pp. 287-290.
17. Bryan D. The ISCAS’85 benchmark circuits and netlist format, North Carolina State University,
1985, Vol. 25, pp. 39.
18. Brglez F., Bryan D., Kozminski K. Combinational profiles of sequential benchmark circuits, 1989
IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 1989, pp. 1929-1934.
19. 8080 Compatible CPU. Available at: https://opencores.org/projects/cpu8080.
20. The OpenCores VGA/LCD Controller. Available at: https://opencores.org/projects/vga_lcd.
