Размещение элементов - одна из основных задач синтеза топологии БИС. При ее решении стремятся, с одной стороны, обеспечить усло-вия 100%-ной трассировки соединений, а с другой - минимизиро-вать искажения сигналов в межэлементных связях. Формальными критериями качества размещения служат различные приближенные оценки (прогнозы) трассировки, правильный выбор и последова-тельность применения которых во многом определяют общие ре-зультаты синтеза топологии. Основными этапами решения задачи размещения элементов матричных БИС являются: выбор критериев размещения, начальное размещение элементов на БМК, итерацион-ная оптимизация начального размещения
В общем случае под задачей размещения элементов БИС пони-мают поиск такого отображения q0 множества элементов схемы Е = {еi; i=1,п) на множество позиций коммутационного поля (КП) S = {sk; k = 1,m}, при котором:
где F - критерий качества размещения; Q = {qi} - множество воз-можных отображений Е на S; Si - подмножество позиций КП, за-нимаемых элементом ei.
Основная цель, которая ставится в процессе размещения, - созда-ние наилучших условий для последующей трассировки соединений схемы. Она же определяет стратегию выбора формального критерия оптимизации F. Однако из-за условности разделения задач размеще-ния и трассировки построить подобный критерий, достаточно точно отражающий условия прокладки соединений на КП, очень трудно.
Единственным "идеальным" в этом смысле критерием является собственно трассировка соединений, как это, например, происходит при ручном проектировании топологии. К сожалению, громадная вычислительная сложность совместного решения задач размещения и трассировки даже для небольших БИС заставляет применять при их конструировании эвристические критерии качест-ва размещения. Это прежде всего различные приближённые оценки тех интегральных параметров трассировки, изменение которых кос-венно характеризует условия её проведения при заданном размеще-нии элементов на КП.
Основное достоинство подобных, критериев - простота расчета при относительно высоком качестве получаемого решения. Недостаток - тенденция к стягиванию групп сильно связанных между собой элементов в минимальные области КП, что затрудняет их после-дующую трассировку.
Необходимость итерационных методов оправдывается тем, что при однопроходном (последовательном) эвристическом алгоритме просто невозможно сделать размещение элементов с заданным каче-ством. Поэтому после последовательных методов обычно всегда применяют итерационные методы.
Итерационные методы основаны на том что производиться кор-рекция полученного при последовательном методе результата путём перестановки пар элементов или групп элементов друг с другом. При этом переставляются вершины по критерию, который необхо-димо улучшить после последовательного метода.