Одним из основных и наиболее трудоемких этапов проектирования в базисе реконфигурируемых систем на кристалле является размещение элементов. В работе проведен сравнительный анализ методов решения задачи размещения элементов в маршруте топологического синтеза цифровых схем в базисе реконфигурируемых систем на кристалле с островной иерархической архитектурой. Рассмотрены алгоритмы размещения с применением метода имитации отжига. Последовательный многоуровневый алгоритм размещения состоит из двух этапов: глобального размещения групп логических элементов и последовательного детального размещения внутри групп. Конкурентный многоуровневый алгоритм размещения аналогичен первому, но на этапе детального размещения перестановки логических элементов выполнены во всех группах одновременно. В стандартном плоском алгоритме размещения этап глобального размещения отсутствует, а перестановка логических элементов не ограничена рамками групп. Тестирование алгоритмов осуществлено в базисе реконфигурируемой системы на кристалле отечественного производства. Результаты экспериментов показывают, что применение стандартного плоского алгоритма размещения позволяет повысить трассируемость проектируемых схем, уменьшить общую длину межсоединений, а также повысить быстродействие до 49 %.
1. Hauck S., DeHon A. Reconfigurable computing: The theory and practice of FPGA-based computation. San Francisco: CA, Morgan Kaufmann Publishers Inc., 2007. 944 p.
2. Shahookar K., Mazumder P. VLSI cell placement techniques // ACM Computing Sur-veys (CSUR). 1991. Vol. 23. No. 2. P. 143–220.
3. Rose J., Snelgrove W., Vranesic Z. ALTOR: an automatic standard cell layout program // Proc. of the Canadian Conference on VLSI. 1985. P. 169–173.
4. Betz V., Rose J. VPR: a new packing, placement and routing tool for FPGA research. // Proc. of the Seventh International Workshop on Field-Programmable Logic and Applications. Springer-Verlag. 1997. P. 213–222.
5. Baruch Z., Cret O., Giurgiu H. Genetic algorithm for FPGA placement // Proc. of the 12th International Conference on Control Systems and Computer Science (CSCS12). 1999. Vol. 2. P. 121–126.
6. Hajek B. Cooling schedules for optimal annealing // Math. Oper. Res. 1988. Vol. 13. P. 311–329.
7. Ripple 2.0: high quality routability-driven placement via global router integration / X. He, T. Huang, W.-K. Chow et al. // ACM/IEEE Design Automation Conference (DAC). 2013. P. 152:1–152:6.
8. Hajek B. Cooling schedules for optimal annealing // Math. Oper. Res. 1988. Vol. 13. P. 311–329.
9. Gort M., Anderson J.H. Analytical placement for heterogeneous FPGAs // 22nd Intern. Conf. on Field Programmable Logic and Applications (FPL). 2012. P. 143–150.
10. Gavrilov S., Zheleznikov D., Khvatov V., Chochaev R. Clustering optimization based on simulated annealing algorithm for reconfigurable systems-on-chip // 2018 IEEE Conf. of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). Moscow, 2018. P. 1492–1495.
11. Brglez F., Bryan D., Kozminski K. Combinational profiles of sequential benchmark cir-cuits // Proc. of the Intern. Symposium of Circuits and Systems. 1989. P. 1929–1934.
12. Bryan D. The ISCAS ‘85 Benchmark circuits and netlist format. North-Carolina State University, 1985. P. 4.
13. Yang S. Logic synthesis and optimization benchmarks // Technical Report, MCNC, Dec. 1988 MCNC International Workshop on Logic Synthesis, 1989. P. 14.
14. 8051 core: Overview. URL: https://opencores.org/projects/8051 (дата обращения: 18.06.2019).
15. Singh A., Marek-Sadowska M. Efficient circuit clustering for area and power reduction in FPGAs // ACM Transactions on Design Automation of Electronic Systems. 2002. Vol. 7. No. 4. P. 643–663.
16. Gavrilov S., Zheleznikov. D., Chochaev R. Simulated annealing based placement opti-mization for reconfigurable systems-on-chip // 2019 IEEE Conf. of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). Saint Petersburg; Moscow, 2019. P. 1597–1600.
17. Near-linear wirelength estimation for FPGA placement / M. Xu, G. Grewal, S. Areibi et al. // Canadian Journal of Electrical and Computer Engineering. 2009. Vol. 34. No. 3. P. 125–132.
18. McMurchie L., Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs // Third Intern. ACM Symposium on Field-Programmable Gate Arrays. Napa Valley, CA, USA. 1995. P. 111–117.
19. Гаврилов С.В., Железников Д.А., Чочаев Р.Ж., Эннс В.И. Адаптация метода мо-делирования отжига для размещения элементов в базисе реконфигурируемых систем на кристалле // Электронная техника. Сер. 3. Микроэлектроника. 2018. № 4 (172). С. 55–61.