Разработка и исследование композиционных алгоритмов планирования СБИС тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Ерошенко, Илья Николаевич

• Ерошенко, Илья Николаевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Ерошенко, Илья Николаевич

Введение.

1 Анализ и состояние проблемы планирования СБИС.

1.1 Анализ проблемы планирования.

1.2 Представление модулей при планировании СБИС.

1.3 Классификация критериев задачи планирования СБИС.

1.4 Классификация и анализ представлений плана СБИС.

1.5 Анализ существующих методов и подходов к задаче планирования СБИС.

1.6 Выводы.

2 Планирование СБИС на основе композиционного подхода.

2.1 Постановка задачи.

2.2 Представление плана «обобщенная польская запись».

2.3 Поисковая адаптация в задачах САПР.

2.4 Разработка архитектуры генетического поиска для решения задачи планирования СБИС.

2.5 Организация поисковой процедуры на основе коллективной альтернативной адаптации для решения задачи планирования СБИС.

2.6 Разработка архитектуры меметического алгоритма для решения задачи планирования СБИС.

2.7 Выводы.

3 Планирование СБИС с учетом энергопотребления.

3.1 Проблема энергопотребления СБИС.

3.2 Основные подходы к решению проблемы энергопотребления при мультивольтажном проектировании СБИС.

3.3 Постановка задачи.

3.4 Генетический алгоритм назначения напряжений.

3.5 Двухуровневое распараллеливание алгоритма планирования СБИС с учетом энергосбережения.

3.6 Выводы.

4 Программная реализация и экспериментальные исследования разработанных алгоритмов планирования СБИС.

4.1 Обзор библиотек метаэвристик для эволюционных вычислений.

4.2 Архитектура библиотеки GAlib.

4.3 Многопоточная реализация алгоритма назначения напряжений.

4.4 Описание программного продукта.

4.5 Эксперименты.

4.6 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование композиционных алгоритмов планирования СБИС»

Общая характеристика диссертационного исследования

Актуальность работы. В настоящее время современные нанометровые технологии производства СБИС достигли такой степени интеграции, что минимальный размер топологического объекта значительно меньше длины волны, применяемой при фотолитографии. Размерности решаемых задач на всех этапах проектирования существенно увеличились. Такие схемы могут быть спроектированы только на основе иерархического подхода.

Совершенствование технологии производства и резкое повышение функциональной сложности СБИС часто опережают возможности проектирования, что вызывает необходимость в пересмотре разработанных ранее и существующих на сегодняшний день алгоритмов и методов конструкторского проектирования и стимулирует разработку новых эффективных методов и средств их проектирования.

В связи с этим особо актуальна разработка новых эффективных методов решения задач конструкторского проектирования.

При проектировании больших систем часто топологическая схема требуется уже на ранних стадиях проектирования, хотя еще не были спроектированы все модули, т.е. не вся информация обо всех модулях имеется в наличии, часть этой информации может оказаться неточной. Планирование -это ранняя фаза проектирования СБИС. Оно дает информацию о приблизительных значениях площади, задержки, мощности и других рабочих характеристиках. Необходимость снижения энергопотребления наряду с уменьшением площади кристалла и повышением производительности стала одной из важнейших проблем для разработчиков специализированных интегральных схем (ASIC) и систем на кристалле (СнК), которые используются в сетевом оборудовании, мобильных устройствах и других приложениях.

Таким образом, одной из важнейших задач синтеза и формирования топологии СБИС является задача планирования кристалла СБИС.

Основные проблемы задачи планирования кристалла СБИС - это проблема поиска подхода к представлению решения (плана) и проблема построения оптимизационной процедуры поиска решения.

В настоящее время наибольшее распространение получил подход, при котором план строится на основе различного рода деревьев. Однако существующие способы записи и кодирования деревьев предполагают для их модификации использование нелинейных процедур.

Особенностью проектирования СБИС является очень большая область поиска решения. По этой причине существует проблема, связанная с огромным числом возможных проектных решений, которые необходимо исследовать, чтобы выбрать решение, которое бы отвечало входным требованиям.

Задача планирования кристалла СБИС относится к классу Поэтому очень большой класс разработанных к настоящему времени алгоритмов планирования кристалла СБИС основан на различных эвристиках, обеспечивающих получение решений в полиномиальное время. Основным недостатком этих алгоритмов является невысокое качество результатов из-за попадания в локальные ямы, малая пригодность для задач большой размерности, плохая приспособленность для реализации на современных технических средствах. Одним из возможных методов решений этой проблемы является использование методов случайного направленного поиска, основанного на моделировании естественных процессов. К таким относятся методы поисковой адаптации на основе механизмов генетического поиска и эволюционной адаптации. В биологии адаптация означает приспособление живых организмов к изменяющимся окружающим условиям, затем данный термин стал широко употребляться в научно-технической литературе.

Для того чтобы техническая система в процессе функционирования изменялась и улучшала свои параметры, в ее конструкцию можно внедрить подсистему адаптации. Такая идея возникла в процессе наблюдений за живыми организмами.

Процесс разработки проекта на САПР может быть представлен как адаптивный поисковый процесс, целью которого является достижение объектом проектирования оптимального состояния, при котором его оценки эффективности достигают наилучших значений.

Объект адаптации рассматривается как обучающаяся система, помещенная в среду, характеризующуюся вероятностной реакцией.

Значительным шагом в развитии технических устройств для имитации адаптации был предложенный М.Л. Цетлиным подход, основанный на использовании вероятностных обучающихся автоматов.

Работа адаптивной системы моделируется как функционирование некоторого вероятностного автомата, действующего в случайной среде. Адаптивная система представляется в виде двух компонентов: среды и управляющего устройства.

Под средой понимается объект управления (объект оптимизации), а управляющее устройство работает в соответствии с алгоритмом случайного поиска.

Основываясь на этой идее, М.Л. Цетлин поместил в среду, характеризующуюся случайной реакцией, вероятностный автомат адаптации (АА) для реализации функции управляющего устройства. Адаптация автомата производится путем самообучения в процессе его функционирования.

На каждом такте работы адаптивной системы в соответствии со значениями выхода автомата адаптации формируется управляющее воздействие, приводящее к изменению состояния среды и показателя качества. Идеи М.Л. Цетлина легли в основу теории построения алгоритмов альтернативной поисковой адаптации.

Идеи использования методов естественной генетики появились в результате работ Холланда. Генетический алгоритм (ГА) представляет собой адаптивный поисковый метод, который основан на селекции лучших индивидуальностей в популяции, подобно эволюционной теории Дарвина.

Каждому решению соответствует одна или несколько хромосом, которые представляют собой закодированный генетический материал. Хромосомы состоят из генов. Каждый ген имеет свой локус или позицию в хромосоме. Гены могут иметь различные значения: число, строка, сектор, массив и т.д. Решение получается на основе декодирования хромосом.

Преимуществом этих методов является параллельная обработка альтернативных решений, что является мощным средством выхода из локальных оптимумов.

Разработка эволюционных алгоритмов связана с решением проблемы представления - преобразования исходной формулировки задачи в компоненты некоторой адаптивной системы. Обычно существует несколько способов такого представления задачи. Искусство выбора хорошего представления очень существенно для применения методов адаптации к решению оптимизационных задач.

В связи с этим становится актуальным вопрос поиска и разработки эффективных представлений, методов и алгоритмов для решения задачи планирования кристалла СБИС.

Цель диссертационной работы состоит в разработке на основе композиции эволюционных алгоритмов новых эффективных оптимизационных процедур решения задачи планирования кристалла СБИС с учетом требований современных технологий производства.

Задачи, которые необходимо решить для достижения цели:

1. Проведение сравнительного анализа методов оптимизации, использующихся при решении задачи планирования СБИС.

2. Разработка представления исходной формулировки задачи планирования СБИС на основе генетической эволюции с использованием негильотинного представления.

3. Разработка представления исходной формулировки задачи планирования СБИС в виде адаптивного процесса на основе самообучения, моделируемого вероятностными автоматами адаптации для негильотинных планов.

4. Разработка адаптивного меметического алгоритма планирования СБИС на базе общего подхода к построению адаптивных процедур, опирающегося на сочетание принципов адаптации на основе самообучения и генетического поиска.

5. Разработка и исследование генетического алгоритма назначения напряжений для учета энергосбережения при планировании СБИС.

6. Создание программного обеспечения, реализующего разработанные алгоритмы решения задачи планирования.

Объектом исследования является планирование СБИС.

Предметом исследования являются композиционные эволюционные алгоритмы для планирования СБИС.

Методы исследования базируются на комплексном использовании результатов теории множеств, теории графов, теории алгоритмов, теории автоматов, исследования операций, математического моделирования, дискретного программирования, оптимизации, эволюционного моделирования, методов конструирования ЭВА, РЭА и СБИС.

Научная новизна результатов, предложенных в диссертационной работе, заключается в следующем:

1. Разработан параллельный генетический алгоритм планирования СБИС, использующий эффективное негильотинное представление плана, специализированный кроссинговер для учета специфики представления плана, механизм регулирования вероятностей операторов кроссинговера, динамический период миграции особей в рамках топологии «кольцо».

2. Модифицирован алгоритм коллективной альтернативной адаптации для поддержки негильотинного представления плана.

3. Разработан параллельный меметический алгоритм планирования СБИС на основе коллективной альтернативной адаптации и генетического поиска.

4. Разработан параллельный генетический алгоритм планирования СБИС с учетом энергопотребления.

Основные положения, выносимые на защиту:

1. Генетический алгоритм планирования кристалла СБИС.

2. Модифицированный алгоритм коллективной альтернативной адаптации для негильотинного представления плана СБИС.

3. Меметический алгоритм планирования кристалла СБИС.

4. Генетический алгоритм назначения напряжений.

Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Разработанные методы эволюционной адаптации на основе самообучения и генетического поиска являются мощным средством выхода из "локальных ям", приводящим к синтезу решений, близких к оптимальным. Алгоритм планирования кристалла СБИС методами эволюционной адаптации реализован в виде программы на языке С++ в среде разработке Microsoft Visual Studio 2010 для операционной системы Windows. Созданная программа (планировщик) позволяет при решении задачи планирования кристалла СБИС осуществлять выбор метода решения: только методами генетического поиска, методами коллективной альтернативной адаптации, моделируемой вероятностными обучающимися автоматами адаптации либо их совместное использование. Помимо этого, имеется возможность учитывать энергопотребление при планировании СБИС благодаря использованию генетического алгоритма назначения напряжений.

Реализация результатов работы. Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в ряде научно-исследовательских работ, проводимых в Южном федеральном университете: грант РФФИ № 11 - 01 - 00122 «Разработка теории и принципов построения интеллектуальных гибридных нечетких генетических, эволюционных и адаптивных методов принятия решений при проектировании и оптимизации», грант РФФИ № 10 - 01 - 00115 «Разработка теории и принципов построения интеллектуальных интегрированных подсистем в задачах проектирования и управления».

Материалы диссертации также использованы в учебном процессе на кафедре САПР в Южном федеральном университете в цикле лекций и практических занятий по курсам «Автоматизация конструкторского и технологического проектирования», «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».

Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на международных научно-технических конференциях «Интеллектуальные САПР» (г. Дивноморск, 2009-2011 гг.), международной конференции по мягким вычислениям и измерениям (г. Санкт-Петербург, 2010 г.) всероссийских научных конференциях «Информационные технологии, системный анализ и управление» (г. Таганрог, 2008-2010 гг.), всероссийских научных конференциях «Технологии Microsoft в теории и практике программирования» (г. Таганрог, 2008-2011 гг.), всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 2010 г.).

Публикации. Результаты диссертации отражены в 21 источнике, включая 3 работы в издании, рекомендованном ВАК, 3 свидетельства о регистрации программ.

Структура и объем диссертации. Диссертация состоит из 156 страниц текста, содержит введение, 4 главы, заключение, список литературы из 106 наименований, 121 рисунок и 8 таблиц.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Ерошенко, Илья Николаевич

4.6 Выводы

Представлен программный продукт, предназначенный для решения задачи планирования СБИС, обладающий дружественным, интуитивно-понятным интерфейсом.

Планировщик СБИС эффективно задействует возможности многоядерных процессоров благодаря использованию библиотеки PPL. На ЭВМ с двухъядерным процессором удалось ускорить вычисления в 1.3 раза.

При соизмеримом энергосбережении, достигающем 50%, представленный алгоритм лучше упаковывает модули, чем аналоги, использующие моделирование отжига в связке с гильотинными планами. По сравнению с планировщиком в работе [106] качество упаковки улучшилось на 8-16%.

Заключение

В ходе выполнения диссертационной работы получены следующие основные результаты:

1. Для решения задачи планирования кристалла СБИС использован подход, основанный на комплексном использовании принципов эволюционной и альтернативной адаптации - самообучения и генетического поиска.

2. Существующий генетический алгоритм планирования СБИС был усовершенствован благодаря использованию обобщенной польской записи, наличию различных видов кроссинговера и механизма регулирования частоты их использования.

3. С учетом специфики задачи планирования кристалла СБИС определены объекты коллективной адаптации, разработаны и модернизированы механизмы альтернативной поисковой адаптации, что позволило для решения задачи планирования разработать адаптивную поисковую процедуру, использующую обобщенную польскую запись вместо обычной.

4. Разработана структура процедуры адаптивного поиска, работающая как на основе совместного использования принципов генетического поиска и самообучения (в виде меметического алгоритма), так и по отдельности.

5. Меметический алгоритм планирования был распараллелен для получения более надежных решений, при этом для островной модели использовалась топология «кольцо». Разработанный меметический алгоритм может работать автономно, а может использоваться в рамках современного планирования с учетом энергосбережения благодаря специальной надстройке. Данная надстройка выполнена в виде параллельного генетического алгоритма назначения напряжений и разделения на острова напряжения.

6. Предлагаемый алгоритм планирования с учетом энергосбережения позволяет лучше упаковывать модули по сравнению с планировщиками аналогичного уровня (качество упаковки улучшилось в среднем на 8-16%), при этом показатели энергосбережения не ухудшаются (энергосбережение может достигать 40-50%).

Список литературы диссертационного исследования кандидат технических наук Ерошенко, Илья Николаевич, 2012 год

1. Гулякович Г.Н. и др. Перспективы и проблемы полупроводниковой наиоэлектроники // Электронный научный журнал «Инженерный Вестник Дона», №2. 2012.

2. Лебедев В.Б. Разработка и исследование методов планирования кристалла СБИС на основе эволюционной адаптации: Дис. канд. тех. наук. Таганрог, 2003.- 145 с.

3. Kahng А.В. Classical floorplanning harmful? // Proceedings of the 2000 International Symposium on Physical Design: San Diego, CA, 2000. pp. 207-213.

4. Ерошенко И.Н. Современные тенденции в планировании СБИС // VII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2009. С. 305-310.

5. Ерошенко И.Н. Обзор состояния и перспективы планирования кристалла СБИС // Перспективные информационные технологии и интеллектуальные системы. №39/40(3/4)/2009. С. 74-88.

6. Subbaraj. P. et al. Multi-objective Optimization in VLSI Floorplanning // Control, Computation and Information Systems, Communications in Computer and Information Science, 2011, Volume 140, 1. pp. 65-72.

7. Shanavas I.H., Gnanamurthy R.K. Wirelength Minimization in Partitioning and Floorplanning Using Evolutionary Algorithms // VLSI Design Vol. 2011. 2011.

8. Ma Q. et al. MSV-Driven Floorplanning // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 30 Issue: 8. 2011. pp. 1152 -1162.

9. Haghdad K. et al. Floorplanning for low power 1С design considering temperature variations // Microelectronics Journal Volume 42, Issue 1, January 2011. pp. 89-95.

10. Alpert C. et al. Handbook of Algorithms for Physical Design Automation: Taylor & Francis Group, LLC, 2009. p. 1024.

11. Young F.Y. et al. Placement Constraints in Floorplan Design. // IEEE Transactions on Very Large Scale Integration Systems, 2004. pp. 735-745.

12. Young F.Y. et al. On extending slicing floorplans to handle L/T-shaped blocks and abutment constraints // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001. pp. 800-807.

13. Young F.Y. et al. Slicing floorplans with boundary constraints // IEEE Transactions on Computer-Aided Design, 1999. pp. 1385-1389.

14. Wong D.F. and Liu C.L. A New Algorithm for Floorplan Design // Proc. DAC, 1986. -pp.101-107.

15. Sengupta D. et al. Sequence pair based voltage island floorplanning // IEEE International Green Computing Conference, 2011. pp. 1-6.

16. Nakatake S. et al. The channeled-BSG: a universal floorplan for simultaneous place/route with 1С applications // International Conference on Computer-Aided Design, 1998.-pp. 418-425.

17. Guo P.N. Floorplanning Using a Tree Representation // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 2, FEBRUARY 2001.-pp. 281-289.

18. Chang Y.-C. B*-trees: A New Representation for Non-slicing Floorplans // proc. DAC, 2000.-pp. 458^163.

19. 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. pp. 1115-1118.

20. 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 Volume 13 Issue 2, 2005. pp. 288-292.

21. Lin C.-T. et al. GPE: A New Representation for VLSI Floorplan Problem // IEEE International Conference on Computer Design (ICCD'02), 2002. pp. 42-44.

22. Ерошенко И.Н. Моделирование плана СБИС с использованием бинарных деревьев // Труды Российской школы-семинара аспирантов, студентов и молодых ученых «Информатика, моделирование, автоматизация проектирования». 2010. С. 214—219.

23. Lai M., and Wong D.F. Slicing Tree Is a Complete Floorplan Representation // In Proc. DATE, 2001. pp. 228-232.

24. Лебедев Б.К., Рябов O.B. Построения графа ограничения методом списка глубин для задачи сжатия // Известия ЮФУ. Технические науки. Таганрог: Изд-во ТТИ ЮФУ, 2008.№ 4(81). - С. 51-55.

25. Akers S.B., Geyer J.M. and D.L. Roberts. 1С Mask Layout with a Single Conductor Layer // Proceedings of 7th Design Automation Workshop, 1970. pp. 716.

26. Hsueh M.Y. and Pederson D.O. Computer-Aided Layout of LSI Circuit BuildingBlock // IEEE International Symposium on Circuits and Systems, 1979. pp. 474 -477.

27. Carpenter C.W. and Horowitz M. Generating Incremental VLSI Compaction Spacing Constraints // Proceedings of the 24th ACM/IEEE Design Automation Conference: IEEE Computer Society Press, 1987. pp. 291-297.

28. Sutanthavibul S. et al. An analytical approach to floorplan design and optimization // DAC '90 Proceedings of the 27th ACM/IEEE Design Automation Conference. 1990.-pp. 187-192.

29. Sherwani N. Algorithms for VLSI Physical Design Automation: Kluwer Academic Publisher 1999. p. 608.

30. Гармаш A.B. Решение задачи планирования СБИС на основе квантовых алгоритмов // Перспективные информационные технологии и интеллектуальные системы. 2004. №3. С.47-52.

31. Ерошенко И.Н. Использование природных вычислений в задачах конструкторского проектирования СБИС. // Информатика, вычислительная техника и инженерное образование. №1. Изд-во ТТИ ЮФУ, 2010. С. 19-28.

32. Курейчик В.М. и др. Поисковая адаптация: теория и практика. М.: Физматлит, 2006. — С. 272.

33. Ерошенко И.Н. Применение альтернативной адаптации для планирования СБИС на основе обобщенной польской записи // Труды Конгресса поинтеллектуальным системам и информационным технологиям "AIS-IT'09". -М: Физматлит, 2009. Т.З. С. 77-81.

34. Chen Т.-С. et al. Modern floorplanning based on B*-tree and fast simulated annealing // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006. pp. 637-650.

35. Fang J.-P. et al. A Parallel Simulated Annealing Approach for Floorplanning in VLSI // Proceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing. 2009. pp. 291-302.

36. Qi L. et al. Simulated annealing based thermal-aware floorplanning // International Conference on Electronics, Communications and Control (ICECC), 2011.-pp. 463-466.

37. Курейчик B.B., Курейчик B.M., Родзин С.И. Концепция эволюционных вычислений, инспирированных природными системами. // Известия Южного федерального университета. Технические науки. 2009. Т.93. №4. с. 16-24.

38. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование (обзор) // Известия РАН. Теория и системы управления. -2002, № 1.-С. 127-137.

39. Ерошенко И.Н. Эволюционные вычисления при решении задач конструкторского проектирования СБИС // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT'10". 2010. Т.З.-С. 3-10.

40. Ерошенко И.Н. Обзор современных моделей эволюционных вычислений для решения задачи планирования СБИС // Известия Южного федерального университета. Технические науки. 2010. Т. 120. № 7. С. 45-51.

41. Lin С.-Т. et al. An efficient genetic algorithm for slicing floorplan area optimization // Proceedings of the International Symposium on Circuits And Systems, 2002. pp. 879-882.

42. Hung W.-L. et al. Thermal-aware floorplanning using genetic algorithms // Sixth International Symposium on Quality of Electronic Design, 2005. pp. 634-639.

43. Chen J., Zhu W. A hybrid genetic algorithm for VLSI floorplanning // IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS), 2010.-pp. 128-132.

44. Kureichik V.M. et al. Hybrid evolutionary algorithm of planning VLSI // Proceedings of the 12th annual conference on Genetic and evolutionary computation 2010.-pp. 821-822.

45. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: Изд-во ТРТУ, 2000. 192 с.

46. Ерошенко И.Н. Разработка генетического алгоритма кластерного планирования СБИС // Известия Южного федерального университета. Технические науки 2010 №7(108) С. 54-60.

47. Moni D.J. et al. VLSI Floor Planning relying on Differential Evolution Algorithm // ICGST International Journal on Artificial Intelligence and Machine Learning. Vol. 7. No 1.-2007.-pp. 62-67.

48. Лебедев О.Б. Планирование СБИС на основе метода муравьиной колонии // Известия Южного федерального университета. Технические науки. 2010. Т. 108. №7. - С.67-73.

49. Лебедев Б.К., Лебедев В.Б. Размещение на основе метода пчелиной колонии // Известия Южного федерального университета. Технические науки. 2010. Т. 113. № 12.-С. 12-19.

50. Chiang C.-W. Ant Colony Optimization for VLSI Floorplanning with Clustering Constraints // Journal of the Chinese Institute of Industrial Engineers Volume 26, Issue 6, 2009. pp. 440-448.

51. Luo R., Sun P. A Novel Ant Colony Optimization Based Temperature-Aware Floorplanning Algorithm // Third International Conference on Natural Computation ICNC 2007.-pp. 751-755.

52. Курейчик В.М., Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач // Известия Южного федерального университета. Технические науки. 2010. Т. 120. № 7. С. 30-36.

53. Лебедев Б.К., Лебедев В.Б. Планирование на основе роевого интеллекта и генетической эволюции Известия Южного федерального университета. Технические науки. 2009. Т. 93. № 4. С. 25-33.

54. Sun T.-Y. Floorplanning based on particle swarm optimization // ISVLSI '06 Proceedings of the IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures. 2006. - pp. 5-10.

55. Chen G. et al. A PSO-based intelligent decision algorithm for VLSI floorplanning // Soft Computing A Fusion of Foundations, Methodologies and Applications Volume 14, Number 12. 2010.-pp. 1329- 1329.

56. Ерошенко И.Н. Методы адаптации генетических алгоритмов к задаче планирования СБИС // Труды конгресса по интеллектуальным системам и информационным технологиям «IS-IT'll». М: Физматлит, 2011. Т.З. С. 138— 145.

57. Ерошенко И.Н. Роль гибридизации метаэвристик в задачах оптимизации. // VIII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2010. с. 370 376.

58. Talbi, E.-G. A Taxonomy of Hybrid Metaheuristics // Journal of Heuristics, Kluwer Academic Publishers, 8. pp. 541-564.

59. Giinther R. A Unified View on Flybrid Metaheuristics // Lecture Notes in Computer Science. Vol. 4030. 2010. pp. 1-12.

60. Ерошенко И.Н. Меметическнй алгоритм планирования СБИС // Известия Южного федерального университета. Технические науки. 2010 №12(113) С. 55-62.

61. Maolin Т., Xin Y. A memetic algorithm for VLSI floorplanning // IEEE Transactions On Systems, Man, And Cybernetics—PartB: Cybernetics, 37(1), 2007. -pp. 62-69.

62. Shanavas I. H. et al. Evolutionary Algorithmical Approach for VLSI Floorplanning Problem // International Journal of Computer Theory and Engineering Vol.1, No.4 . 2009. pp. 461-464.

63. L. Wang, Y. Chang, K. Cheng. Electronic Design Automation: Synthesis, Verification, and Test. Morgan Kaufmann, 2009. - p. 972.

64. R.H.J.M. Otten, Automatic floorplan design // Proceedings of the 19th Design Automation Conference, Las Vegas, NV, 1982. pp. 261-267.

65. Курейчик B.M., Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О. Адаптация на основе самообучения. Ростов-на-Дону: РГАСХМ ГОУ 2004. - 146 с.

66. Редько В.Г. Эволюционная кибернетика. -М.: Наука, 2001. 156 с.

67. Лебедев Б.К., Лебедев В.Б. Планирование СБИС на основе эволюционной адаптации // Известия Южного федерального университета. Технические науки. Т. 64, №9. 2006. С. 93-97.

68. Емельянов В.В, Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003. - С. 432.

69. Day W.H.E., EdelsBrunner Н. Efficient algorithms for agglomerative hierarchical clustering methods // Journal of Classification. Volume 1, Number 1. 1984. pp. 7— 24.

70. D.-S. Chen, С.-Т. Lin and Y.-W. Wang. A robust genetic algorithm for rectangle packing problem // Journal of Combinatorial Optimization 2006. vol. 13, no. 2.

71. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: Изд-во ТРТУ, 2000. - 192 с.

72. Moscato, P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms // Caltech Concurrent Computation Program (report 826), 1989.

73. The International Technology Roadmap for Semiconductors — ITRS 2007 Edition: Tech. rep., Ed. by ITRS: International Technology Roadmap for Semiconductors, 2007. http://www.itrs.net.

74. Piguet C. Low-Power CMOS Circuits: Technology, Logic Design and CAD Tools. Boca Raton: CRC Press, 2005. - p. 867.

75. Yu В., Dong S.and GOTO S. Multi-Voltage and Level-Shifter Assignment Driven Floorplanning. // IEEE 8th International Conference on ASIC, 2009. pp. 1264-1267.

76. Yu В., Dong S., GOTO S. and Chen S. Voltage-Island Driven Floorplanning Considering Level-Shifter Positions // Proceedings of the 19th ACM Great Lakes symposium on VLSI, 2009. pp. 51-56.

77. Hung W.-L. Temperature-Aware Voltage Islands Architecting in System-on-Chip Design // Proceedings of the 2005 International Conference on Computer Design.2005. -pp. 689-696.

78. Hu J., Shin Y., Dhanwada N., and Marculescu R. Architecting Voltage Islands in Core-based System-on-a-chip Designs // Proceedings of the 2004 International Symposium on Low Power Electronics and Design. 2004. pp. 180-185.

79. Ma Q.and Young F.Y. Voltage Island-Driven Floorplanning // ICCAD, 2007. -pp. 644-649.

80. Мак W.K. and Chen J.W. Voltage island generation under performance requirement for soc designs // ASP DAC, 2007. pp. 798-803.

81. Lee W.P. and Chang Y.W. An ILP algorithm for postfloorplanning voltage-island generation considering powernetwork planning. ICCAD, 2007. pp. 650-655.

82. Wu H., Liu I.M. and Wang Y. Post-placement voltage island generation under performance requirement // Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, 2005. pp. 309-316.

83. Ching R. and Young F.Y. Post-placement voltage island generation // Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, 2006. pp. 641-646.

84. Lee W.-P. Voltage Island Aware Floorplanning for Power and Timing Optimization // IEEE/ACM International Conference on Computer-Aided Design,2006.-pp. 389—394.

85. Chen С.-Н. and Tollis I. G. Area Optimization of Slicing Floorplans in Parallel // VLSI Design, vol. 2, no. 2, 1994. pp. 143-156.

86. Cohoon J.P. Distributed Genetic Algorithms for the Floorplan Design Problem // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Volume: 10, Issue: 4. 1991.-pp. 483^192.

87. Tang M., Lau R. Y. K. A Parallel Genetic Algorithm for Floorplan Area Optimization // Seventh International Conference on Intelligent Systems Design and Applications. 2007. -pp.801-806.

88. Ерошенко И.Н. Платформы для эволюционных вычислений: проблемы и перспективы развития. // Труды X Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», 2010. С. 123-124.

89. Luke S. ECJ: A Java-based Evolutionary Computation and Genetic Programming Research System-http://www.cs.umd.edu/proiects/plus/ec/eci/

90. Keijzer M. et al. Evolving Objects: A General Purpose Evolutionary Computation Library // Lecture Notes in Computer Science. Vol 2310. 2002. pp. 829- 888.

91. Cahon S. ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics // Journal of Heuristics, 10, 2004. pp. 357-380.

92. Wall M. GAlib: A С++ Library of Genetic Algorithm Components -http://lancet.mit.edu/ga/.

93. Open BEAGLE http://beagle.gel.ulaval.ca/

94. MSDN http://msdn.microsoft.com/ru-ru/library/dd492418(v=VS.100).aspx

95. Ma Q., Young E.F.Y. Multivoltage Floorplan Design // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 29 No: 4. -2010.-pp. 607-617.