Статья

Название статьи ИНТЕГРИРОВАННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ФРАГМЕНТОВ CБИС
Автор В.В. Курейчик, Вл.Вл. Курейчик
Рубрика РАЗДЕЛ II. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2014
Индекс УДК 321.628
DOI
Аннотация Рассмотрена одна из важных задач конструкторского проектирования – задача размещения фрагментов СБИС. Она относится к классу NP-сложных и трудных задач. Приведена постановка задачи размещения. Описаны модели представления задачи размещения и обосновано построение на их основе иерархической многоуровневой декомпозиционной структуры. Сформулирована эвристика, позволяющая выделять связанные фрагменты графовой модели коммутационной схемы в виде строительных блоков, образованных короткими цепями. Предложен комбинированный поиск, реализованный по иерархическому принципу на основе генетических, эволюционных и алгоритмов, моделирующих механизмы принятия решений природными системами. Разработан интегрированный алгоритм, позволяющий распараллеливать процесс решения и частично устранять проблему предварительной сходимости. Проведен вычислительный эксперимент. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов размещения и их поведение для схем различной структуры. В лучшем случае временная сложность алгоритмов ≈O(nlogn), в худшем случае – О(n3).

Скачать в PDF

Ключевые слова Комбинированный поиск; конструкторское проектирование; муравьиный алгоритм; размещение; генетический алгоритм.
Библиографический список 1. Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации. – М.: Физмалит, 2009. – 384 с.
2. Курейчик В.В., Курейчик Вл.Вл. Архитектура гибридного поиска при проектировании // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 22-27.
3. Гладков Л.А, Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2010. – 366 с.
4. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating objects // IEEE Trans. on Systems, Man, and Cybernetics. – 1996. – Part B, No 26(1). – P. 29-41.
5. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. – М.: Физмалит, 2012. – 260 c.
6. Бова В.В., Курейчик В.В. Интегрированная подсистема гибридного и комбинированного поиска в задачах проектирования и управления // Известия ЮФУ. Технические науки. – 2010. – № 12 (113). – С. 37-42.
7. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
8. Курейчик В.В., Курейчик В.М. Генетический алгоритм размещения графа // Известия РАН. Теория и системы управления. – 2000. – № 5. – С. 67-78.
9. Kureichik V.M., Kureichik V.V. Genetic algorithm for the graph placement // Journal of Computer and Systems Sciences International. – 2000. – Vol. 39, No 5. – P. 733-740.
10. Бушин С.А., Курейчик В.В. Размещение узлов и блоков радиоэлектронной и электронно-вычислительной техники на основе бионических методов // Программные продукты и системы. – 2010. – № 1. – С. 12-14.
11. Kurejchik V.V., Kurejchik V.M. On genetic-based control // Автоматика и телемеханика. – 2001. – № 10. – С. 174-187.
12. Курейчик В.В., Сороколетов П.В. Концептуальная модель представления решений в генетических алгоритмах // Известия ЮФУ. Технические науки. – 2008. – № 9 (86). – С. 7-12.
13. Курейчик В.М., Курейчик В.В., Родзин С.И. Модели параллелизма эволюционных вычислений // Вестник РГУПС. – 2011. – № 3. – С. 93-97.

Comments are closed.