Статья

Название статьи МОДЕРНИЗИРОВАННЫЙ МУРАВЬИНЫЙ АЛГОРИТМ СИНТЕЗА ИДЕНТИФИЦИРОВАННОГО ДЕРЕВА ГИЛЬОТИННОГО РАЗРЕЗА ПРИ ПЛАНИРОВАНИИ СБИС
Автор Б. К. Лебедев, О. Б. Лебедев, Е. М. Лебедева
Рубрика РАЗДЕЛ I. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2017
Индекс УДК 004.896
DOI
Аннотация Задача планирования решается на основе модифицированной канонической парадигмы муравьиной колонии. Для представления плана используется бинарное дерево гильотинного разреза с идентифицированными вершинами. Структура дерева разрезов задается в виде польского выражения для бинарного дерева. Сформулированы основные свойства польского выражения, выполнение которых необходимо, чтобы записи соответствовало дерево разрезов. В работе рассматривается подход, при котором формирование структуры дерева разрезов муравьиным алгоритмом и разметка всех вершин дерева производится параллельно. Задача синтеза дерева разрезов с идентификацией вершин сводится к задаче формирования соответствующего польского выражения. Для отражения коллективной эволюционной памяти в течение жизни популяции муравьев и для формирования решения задачи в работе используется полный граф с альтернативными состояниями вершин. Вершины множества X1 соответствуют множеству модулей M. Каждая вершина может находиться в одном из двух альтернативных состояний, соответствующих типу ориентации модуля. Вершины множества X2 соответствуют разрезам. Каждая вершина может находиться в одном из двух альтернативных состояний, соответствующих типу разреза – горизонтальный или вертикальный. Ключевая проблема, которая была решена в данной работе, связана с разработкой композитной структуры пространства решений, позволяющей одновременно учитывать при построении дерева разрезов ориентацию эле-ментов, тип разреза и метку модуля. Разработана структура модифицированного польского выражения позволяющая, учитывать ориентацию элементов, тип разреза и метку модуля. Это позволило снизить временную сложность задачи планирования и повысить качество решения. Процесс поиска решений итерационный. Каждая итерация l включает три этапа. На первом этапе муравей находит решение. Разработаны эвристики поведения муравья при перемещениях в графе поиска решений, позволяющие формировать легитимный маршрут. На втором этапе муравьи откладывают феромон, на третьем этапе осуществляется испарения феромона. Построенный агентом маршрут трансформируется в польское выражение, которое в свою очередь трансформируется в дерево разрезов с идентифицированными вершинами, а дерево разрезов трансформируется в план. Для написания программы планирования СБИС методом муравьиной колонии был использован язык C++ в среде Microsoft Visual Studio 2010 для ОС Windows, так как главный упор делался на скорость работы приложения. Для проведения экспериментов программы была использована процедура синтеза контрольных примеров с известным оптимумом Fопт по аналогии с известным методом AFEKO – Floorplanning Examples with Known Optimal area. Исследованию подвергались примеры, содержащие до 1000 модулей. Оценкой качества служит «степень качества» – величина Fопт/F, где F – оценка полученного решения. Сравнение с известными алгоритмами показало, что при меньшем времени работы у полученных с по-мощью разработанного алгоритма решений отклонение целевой функции от оптимального значения меньше в среднем на 6 %. Временная сложность этого алгоритма зависит от времени жизни колонии l (число итераций), количества вершин графа n и числа муравьев m, и определяется как O(l∙n2∙m).

Скачать в PDF

Ключевые слова Блоки; планирование; дерево разрезов; польское выражение; синтез; альтернатива; парадигма; муравьиный алгоритм.
Библиографический список 1. Kahng A.B. Classical Floorplanning Harmful // ISPD 2000. – P. 207-213.
2. Lin C.-T. et al. GPE: A New Representation for VLSI Floorplan Problem // IEEE International Conference on Computer Design (ICCD'02). – 2002. –P. 42-44.
3. Sengupta D. et al. Sequence pair based voltage island floorplanning // IEEE International Green Computing Conference. – 2011. – P. 1-6.
4. Nakatake S. et al. The channeled-BSG: a universal floorplan for simultaneous place/route with IC applications // International Conference on Computer-Aided Design, November 8-12, 1998. – P. 418-425.
5. Guo P.N. Floorplanning Using a Tree Representation // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – February 2001. – Vol. 20, No. 2. – P. 281-289.
6. Nirmala R.D.G., Rajaram S. Performance Driven VLSI Floorplanning with B*Tree Represen-tation Using Differential Evolutionary Algorithm // Trends in Network and Communications in Computer and Information Science. – 2011. – Vol. 197, Part 2. – P. 445-456.
7. Wang R. et al. An Improved P-admissible Floorplan Representation Based on Corner Block List // Proceedings of the 2005 Asia and South Pacific Design Automation Conference.
– 2005. – P. 1115-1118.
8. Lin J.-M., Chang Y.-W. TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans // IEEE Transactions on Very Large Scale Integration (VLSI) Systems.
– February 2005. – Vol. 13, Issue 2. – P. 288-292.
9. Sassone T.P.G. and Lim S.K. A novel geometric algorithm for fast wire-optimized floorplanning // In Proc. Int. Conf. Comput. Aided Design. – 2003. – P. 74-80.
10. Lai M., and Wong D.F. Slicing Tree Is a Complete Floorplan Representation // In Proc. DATE. – 2001. – P. 228-232.
11. Cheng L., Wong D.F. Floorplan Design for Multi-million Gate FPGAs // DAC. – 2004.
– P. 292-313.
12. Fang J.-P. et al. A Parallel Simulated Annealing Approach for Floorplanning in VLSI // Pro-ceedings of the 9th International Conference on Algorithms and Architectures for Parallel Pro-cessing. – 2009. – P. 291-302.
13. Qi L. et al. Simulated annealing based thermal-aware floorplanning // International Conference on Electronics, Communications and Control (ICECC). – 2011. – P. 463-466.
14. Young F.Y. et al. Slicing floorplans with boundary constraints // IEEE Transactions on Com-puter-Aided Design. – 1999. – P. 1385-1389.
15. Chen T.-C., Chang Y.-W., and Lin S.-C. A new multilevel framework for large-scale intercon-nect-driven floorplanning // IEEE Trans. Comput.-Aided Design Integrat. Circuits Syst.
– 2008. – Vol. 27, No. 2. – P. 286-294.
16. Singhal L. and Bozorgzadeh E. Multilayer floorplanning for reconfig¬urable designs // IET Comput. Digit. Tech. – 2007. – Vol. 1, No. 4. – P. 276-294.
17. Pritha Banerjee, Megha Sangtani, and Susmita Sur-Kolay. Floorplanning for Partially Recon-figurable FPGAs // IEEE Trans. Comput.-Aided Des. Integr. Circuits Sys. – 2011. – Vol. 30, No. 1. – P. 8-17.
18. Chuan-Wen Chiang. Ant Colony Optimization for VLSI Floorplanning with Clustering Con-straints // Journal of the Chinese Institute of Industrial Engineers. – 2009. – Vol. 26, Issue 6.
– P. 440-448.
19. Lin C.-T. et al. An efficient genetic algorithm for slicing floorplan area optimization // Pro-ceedings of the International Symposium on Circuits and Systems. – 2002. – P. 879-882.
20. Chen J., Zhu W. A hybrid genetic algorithm for VLSI floorplanning // IEEE International Con-ference on Intelligent Computing and Intelligent Systems (ICIS). – 2010. – P. 128-132.
21. Shanavas .I H. et al. Evolutionary Algorithmical Approach for VLSI Floorplanning Problem // International Journal of Computer Theory and Engineering. – 2009. – Vol. 1, No. 4. – P. 461-464.
22. Лебедев Б.К., Лебедев В.Б. Планирование СБИС на основе эволюционной адаптации // Известия ТРТУ. – 2006. – № 9 (64). – С. 93-97.
23. Курейчик В.М., Лебедев Б.К., Лебедев В.Б. Планирование сверхбольших интегральных схем на основе интеграции моделей адаптивного поиска // Известия РАН. Теория и сис-темы управления. – 2013. – № 1. – С. 84-101.
24. Tang, Maolin and Yao, Xin. A memetic algorithm for VLSI floorplanning // IEEE Transactions On Systems, Man, And Cybernetics – Part B: Cybernetics. – 2007. – Vol. 37 (1).
25. Лебедев Б.К., Лебедев О.Б. Биоинспирированные методы планирования кристалла СБИС // МЭС-2014. VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2014»: Сборник трудов. – М.: ИППМ РАН, 2012. – С. 171-176.
26. Alpert C.J. In Proceeding of the International Symposium on Physical Design // The ISPD98 circuit benchmark suite. – 1998. – P. 85-90.
27. Cong J., Romesis M. и Xie M. UCLA Optimality Study Project. http://cadlab.cs.ucla.edu/ ~pubbench. 2004.
28. MCNC Electronic and Information Technologies (Online). Available: www.mcnc.org.
29. hMetis [Online]. Available: http://www-users.cs.umn.edu/karypis/metis/ hmet300. HB Floorplan Benchmarks [Online]. Available: http://cadlab.cs.ucla.edu/ cpmo/HBsuite.html.

Comments are closed.