Статья

Название статьи ИЕРАРХИЧЕСКИЙ ПОДХОД ПРИ РАЗМЕЩЕНИИ КОМПОНЕНТОВ СБИС
Автор В.В. Курейчик, Д.В. Заруба, Д.Ю. Запорожец
Рубрика РАЗДЕЛ II. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2014
Индекс УДК 004.896
DOI
Аннотация Предлагается модифицированный иерархический подход, состоящий из трех уровней, для решения задачи размещения компонентов СБИС. На первом уровне происходит предварительная декомпозиция всего пространства поиска на группы с использованием эволюционного подхода. Геометрические параметры каждой группы определяются суммарной площадью входящих в его состав компонентов. На втором уровне производится размещение внутри декомпозиционных групп на основе модифицированного генетического алгоритма. Модификация алгоритма состоит в использовании адаптированных под решение данной задачи операторов кроссинговера. Предложенные операторы позволяют получать заведомо корректные решения, что снижает время получения окончательного результата. На третьем уровне, на основе генетического поиска, размещаются сами декомпозиционные группы. Для выполнения генетических процедур авторами предложена методика кодирования и декодирования множества альтернативных решений с помощью обратной польской нотации. Проведен вычислительный эксперимент, который позволил подтвердить теоретические оценки быстродействия и эффективности разработанных алгоритмов. Проведено сравнение с биоинспирированными и классическими алгоритмами поиска. Временная сложность разработанного алгоритма равна ~ O(n log n).

Скачать в PDF

Ключевые слова СБИС; автоматизация проектирования; размещение; компоновка; многоуровневая оптимизация; генетический алгоритм; биоинспирированный поиск.
Библиографический список 1. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизации. – М.: Физматлит, 2009. – 384 с.
2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2010. – 368 с.
3. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. – М.: Физматлит, 2012. – 260 с.
4. Курейчик В.В., Курейчик В.Вл. Эволюционный алгоритм проектирования комбинационных логических схем // Известия Кабардино-Балкарского научного центра РАН. – 2013. – № 4 (54). – С. 42-47.
5. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
6. Запорожец Д.Ю., Заруба Д.В., Лежебоков А.А. Об одном способе кодирования решения для задачи размещения // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 183-188.
7. Курейчик В.В., Сороколетов П.В. Концептуальная модель представления решений в генетических алгоритмах // Известия ЮФУ. Технические науки. – 2008. – № 9 (86). – С. 7-12.
8. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа // Известия РАН. Теория и системы управления. – 1999. – № 4.
9. Курейчик В.В., Курейчик Вл.Вл. Биоинспирированный алгоритм разбиения схем при проектировании СБИС // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 23-29.
10. Запорожец Д.Ю., Кудаев А.Ю., Лежебоков А.А. Многоуровневый алгоритм решения задачи параметрической оптимизации на основе биоинспирированных эвристик // Известия Кабардино-Балкарского научного центра РАН. – 2013. – № 4. – С. 21-28.
11. Бова В.В., Курейчик В.В. Интегрированная подсистема гибридного и комбинированного поиска в задачах проектирования и управления // Известия ЮФУ. Технические науки. – 2010. – № 12 (113). – С. 37-42.
12. Курейчик В.В., Курейчик Вл.Вл. Архитектура гибридного поиска при проектировании // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 22-27.
13. Kurejchik V.V., Kurejchik V.M. On genetic-based control // Автоматика и телемеханика. – 2001. – № 10. – С. 174-187.
14. Курейчик В.В., Курейчик В.Вл. Биоиспирированный поиск при проектировании и управлении // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 178-183.
15. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 28-32.

Comments are closed.