ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС

  • Б. К. Лебедев Южный федеральный университет
  • О.Б. Лебедев Южный федеральный университет
  • В. Б. Лебедев Московский государственный технический университет имени Н.Э. Баумана
Ключевые слова: Размещение, СБИС, коллективная эволюционная память, оценка полезности, оптимизация, популяционный алгоритм, метод кристаллизации россыпи альтернатив

Аннотация

В работе рассматривается поисковый популяционный алгоритм размещения компо-
нентов СБИС. По аналогии с процессом возникновения и формирования кристаллов из ве-
щества, процесс порождения решения путем последовательного проявления и конкретиза-
ции решения на базе интегральной россыпи альтернатив назван методом кристаллизации
россыпи альтернатив. Решение Qk задачи размещения представляется в виде биективного
отображения Fk=A→P, каждому элементу множества A соответствует один единст-
венный элемент множества P и наоборот. Лежащая в основе алгоритма метаэвристика
кристаллизации россыпи альтернатив выполняет поиск решений с учетом коллективной
эволюционной памяти, под которой подразумевается информация, отражающая историю
поиска решения и памяти поисковой процедуры. Отличительной особенностью используе-
мой метаэвристики является учет тенденции к использованию альтернатив из наилучших
найденных решений. Предложены компактные структуры данных для хранения интерпре-
таций решений и памяти. Алгоритм, связанный с эволюционной памятью, стремится к
запоминанию и многократному использованию способов достижения лучших результатов.
Разработанный алгоритм относится к классу популяционных алгоритмов. Итерационный
процесс поиска решений включает три этапа. На первом этапе каждой итерации конст-
руктивным алгоритмом формируется nq решений Qk. Работа конструктивного алгоритма
базируется на базе показателей основной интегральной россыпи альтернатив – матрицы
R, в которой хранятся интегральные показатели решений, полученных на предыдущих
итерациях. Процесс назначения элемента в позицию включает две стадии. На первой ста-
дии выбирается элемент, а на второй стадии – позиция pj. При этом должно выполняться
ограничение: каждому элементу соответствует одна позиция pj. Рассчитывается оценка
ξk решения Qk и оценка полезности δk множества позиций Pk выбранных агентами. В рабо-
те используется циклический метод формирования решений. В этом случае наращивание
оценок интегральной полезности δk в основной интегральной россыпи альтернатив B вы-
полняется после полного формирования множества решений Q. На втором этапе итера-
ции производится наращивание оценок интегральной полезности δk в основной интеграль-
ной россыпи альтернатив – матрице R. На третьем этапе итерации осуществляетсяснижение оценок полезности δk интегральной россыпи альтернатив R на априори заданную величину δ*. Работа алгоритма завершается после выполнения заданного числа итера-
ций. Сравнительный анализ с другими алгоритмами решения производился на стандартных
тестовых примерах (бенчмарках) корпорации IBМ, при этом решения, синтезируемые ал-
горитмом CAF, превосходят по эффективности решения известных методов в среднем на
6%. Временная сложность алгоритма – О(n2)-О(n3).

Литература

1. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 448 p.
2. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh
proektirovaniya [Models of adaptive behavior of an ant colony in design problems]. Taganrog.
Izd-vo YuFU, 2013, 199 p.
3. Lebedev B.K., Lebedev O.B., Lebedinskiy A.E. Gibridnyy bioinspirirovannyy algoritm
razmeshcheniya bazovykh standartnykh bibliotechnykh elementov pri proektirovanii topologii
poluzakaznoy SBIS [Hybrid bioinspired algorithm for placing basic standard library elements
in the design of the topology of a semi-custom VLSI], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2019, No. 3 (205), pp. 97-110.
4. Kureychik Vl.Vl., Kureychik V.V. Integrirovannyy algoritm razmeshcheniya fragmentov CBIS
[Integrated algorithm for placement of VLSI fragments], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 84-91.
5. Lebedev B.K., Lebedev O.B., Lebedev V.B. Gibridizatsiya roevogo intellekta i geneticheskoy
evolyutsii na primere razmeshcheniya [Hybridization of swarm intelligence and genetic evolution
on the example of placement], Programmnye produkty, sistemy i algoritmy [Software
products, systems and algorithms], 2017, No. 4.
6. Caldwell A.E. Can Recursive Bisection Alone Produce Routable Placements, DAC, 2000,
pp. 477-482.
7. Mourelle M. Swarm intelligent systems. Berlin: Heidelberg: Springer Verlag, 2006, 217 p.
8. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ [Optimization
by the method of сrystallization of alternatives field], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
9. Lebedev B.K., Lebedev V.B. Metod kristallizatsii rossypi al'ternativ [The method of crystallization
of a placer of alternatives], Sb. nauchnykh trudov VII Mezhdunarodnoy nauchnoprakticheskoy
konferentsii “Integrirovannye modeli i myagkie vychisleniya v iskusstvennom
intellekte” [Collection of scientific papers of the VII International scientific-practical
conference “Integrated models and soft computing in artificial intelligence”]. Vol. 2.
M.: Izd-vo Fizmatlit, 2013, pp. 903-912.
10. Ayupov A.B., Marchenko A.M. Metod optimizatsii trassiruemosti v analiticheskom algoritme
razmeshcheniya [Traceability optimization method in the analytical placement algorithm],
Informatsionnye tekhnologii [Information technologies], 2008, No. 2, pp. 12-17.
11. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya: uchebnik [Basics of computeraided
design: textbook]. Mjscow: Izd-vo MGTU im. N.E. Baumana, 2006, 336 p.
12. Sherwani N.A. Algorithms for VLSI Physical Design Automation, Third Edition, Kluwer Academic
Publisher. USA: 2013, 572 p.
13. Alpert C.J. Handbook of Algorithms for Physical design Automation, Auerbach Publications
Taylor & Francis Group. USA, 2009, 349 p.
14. Lebedev B.K., Lebedev V.B., Lebedev O.B. Metody, modeli i algoritmy razmeshcheniya:
monografiya [Placement methods, models and algorithms: monograph]. Rostov-on-Don:
Izd-vo YuFU, 2015, 150 p.
15. Cong J., Romesis M., Xie M. UCLA Optimality Study Project. Available at:
http://cadlab.cs.ucla.edu/~pubbench. 2004.
16. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and
Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey,
CA, 2003, pp. 88-94.
17. Zaporozhets D.Y., Zaruba D.V., Kureichik V.V. Hierarchical approach for VLSI components
placement, Advances in Intelligent Systems and Computing, 2015, pp. 79-87.
18. Kureichik Vl., Kureichik V., Leschanov D., Zaruba D. Hybrid approach for VLSI fragments
placement, Advances in Intelligent Systems and Computing, 2018, pp. 349-358.
19. IBM-PLACE 2.0 benchmark suits. Available at: http://er.cs.ucla.edu/benchmarks/-ibmplace2/
bookshelf/ibm-place2-all-bookshelf-nopad.tar.gz.
20. Adya S.N. ISPD02 IBM-MS Mixed-size Placement Benchmarks. Available at:
http://vlsicad.eecs.umich.edu/BK/ISPD02bench/.
21. Roy J.A., Papa D.A., Markov I.L. Capo: Congestion-Driven Placement for Standard-cell and
RTL Netlists with Incremental Capability, In: Modern Circuit Placement. Series on Integrated
Circuits and Systems. Springer, Boston, MA Springer Science + Business Media, LLC, 2007,
pp. 123-146.
22. Adya S.N. Consistent placement of macro-blocks using floor planning and standard-cell
placement, In Proc. Intl. Symp. on Physical Design, 2002, pp. 12-17.
23. Wang M., Yang X., Sarrafzadeh M. Dragon 2000: Standard-cell Placement Tool for Large
Industry Circuits. ICCAD, 2000, pp. 260-263.
Опубликован
2020-11-22
Выпуск
Раздел
РАЗДЕЛ II. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ