РАЗРАБОТКА АЛГОРИТМА ДЕТАЛЬНОГО РАЗМЕЩЕНИЯ НА ПЛИС
Аннотация
Иерархические программируемые логические интегральные схемы (ПЛИС) состоят
из множества логических блоков, объединенных в группы. Для успешной трассировки необ-
ходимо оптимальное размещение элементов в пределах групп с учётом особенностей ар-
хитектуры локальных связей. Классические алгоритмы не способны обеспечить учёт раз-
личных особенностей архитектуры. Решение данной проблемы возможно только путем
разработки специализированных алгоритмов. В данной работе представлен алгоритм де-
тального размещения, в котором для вычисления оптимальных позиций элементов в группе
была разработана новая метрика, позволяющая оценить количество доступных локальных
связей между элементами в группах логических блоков с учётом особенностей архитекту-
ры связей между ними. Алгоритм детального размещения состоит из нескольких этапов.
На первом этапе группа логических элементов представляется в виде ориентированного
графа. На втором этапе определяется порядок размещения логических элементов в группе
с помощью алгоритма поиска в ширину. На финальном этапе для каждого элемента, со-
гласно полученному порядку, определяется оптимальное размещение в группе с учётом
разработанной метрики. Если среди свободных позиций для размещения в группе нет оп-
тимальной, то проверяются занятые позиции. Текущий элемент назначается на занятую
позицию, а для замененного элемента выполняется поиск новой. Такая замена может про-
водиться многократно, увеличивая вероятность нахождения оптимальной конфигурации.
Предложенный алгоритм был реализован и протестирован на наборах тестовых схем.
На основе результатов тестирования выполнено сравнение представленного алгоритма с
алгоритмом последовательного размещения. Сравнение алгоритмов показало, что применение разработанного алгоритма в маршруте проектирования в базисе специализированной ПЛИС позволяет сократить в среднем на 10% количество задействованных в трасси-
ровке глобальных коммутационных шин и увеличить количество используемых локальных
трассировочных ресурсов в среднем на 30%. Полученные результаты подтверждают работоспособность алгоритма и доказывают, что внедрение учета архитектуры внутренних связей ПЛИС повышает эффективность использования доступных трассировочных
ресурсов.
Литература
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.
