<<
>>

Проблемная формулировка, термины и определения

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

Задачи разбиения можно разбить на два класса [5.1, 5.2]:

— задачи, в которых осуществляется разбиение схемы на блоки с учетом конструктивных факторов, таких, как размер бло­ков, число блоков и межсоединений между блоками, число внешних выводов у блоков и т.

д.;

— задачи, в которых помимо конструктивных факторов суще­ственны и функциональные характеристики блоков.

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

Существующие алгоритмы разбиения делятся на группы: алгоритмы, использующие методы целочисленного программи­рования; конструктивные; итеративные; смешанные алгоритмы [5.1-5.5]. Алгоритмы первой группы обеспечивают точное ре­шение, но из-за их сложности и больших затрат машинного времени они не нашли широкого практического применения.

Входными данными для конструктивных алгоритмов являют­ся компоненты и связи между ними. Выходными данными явля­ется разбиение схемы на блоки, полученное, как правило, путем последовательного распределения компонентов по блокам. Алго­ритмы этой группы отличаются, с одной стороны, относительным

быстродействием, с другой — низким качеством решений [5.1, 5.6-5.8].

Итеративные алгоритмы дополнительно в качестве исходных данных используют некоторое начальное разбиение схемы. На каждой итерации осуществляется переход к новому разбиению (решению). Изменение разбиения осуществляется с помощью групповых или парных перестановок между блоками. Суть итера­ционного алгоритма — поиск в пространстве решений разбиения с лучшими показателями качества. Отметим, что в качестве на­чального разбиения итеративный алгоритм может использовать либо случайное разбиение, либо разбиение, полученное в резуль­тате работы конструктивного алгоритма [5.1, 5.2, 5.9-5.11].

В свою очередь, итеративные алгоритмы делятся на детерми­нированные и вероятностные.

В детерминированных алгоритмах изменение разбиения (ре­шения) реализуется на основе четкой, детерминированной зави­симости от изменяемого решения. Недостатком является частое попадание в локальный оптимум («локальную яму»).

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

Дальнейшим совершенствованием итерационных алгоритмов является разработка методов, основанных на моделировании естественных процессов. К ним относятся методы моделирова­ния отжига, метод эволюционного моделирования, генетической адаптации [5.12, 5.13-5.15].

Все эти методы относятся к классу методов случайного на­правленного поиска и имеют существенные отличия. К недостат­кам относится то, что они все же в большей степени реализуют стратегии «слепого» поиска, что увеличивает объем просматри­ваемого пространства решений.

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

В работе используется представление задачи разбиения в ви­де адаптивной системы, на основе сочетания принципов самообу­чения, самоорганизации и генетического поиска [5.16-5.18].

5.2.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Проблемная формулировка, термины и определения:

  1. Определение твердости по Бринеллю
  2. Определение твёрдости
  3. Определение прочности на растяжение
  4. 3.4.3 Определение удельного сопротивления монокристаллов германия.
  5. Определение предела прочности при поперечном изгибе
  6. Определение секущих модулей и коэффициентов поперечных деформаций при отсутствии трещин
  7. 1. Понятие и правовое положение органа исполнительной власти
  8. 1.1. Классификация оптических аномалий в кристаллах.
  9. Приложение 8.
  10. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  11. § 5. Основания к отмене или изменению судебных постановлений, вступивших в законную силу
  12. § 1. Понятие и правовая природа банка
  13. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  14. § 2. Сущность производства в суде надзорной инстанции
  15. 1. Производство по делам об административных правонарушениях: общая характеристика
  16. 1. Понятие государственного управления
  17. 3. Классификация органов исполнительной власти. Факторы, влияющие на построение системы органов
  18. 3. Основы административно-правового статуса граждан