2. Характеристика задачи оптимального размещения элементов топологии



Скачать 214.04 Kb.
страница1/2
Дата04.07.2013
Размер214.04 Kb.
ТипДокументы
  1   2



1.Цель работы



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

2.Характеристика задачи оптимального размещения элементов топологии



С появлением новой элементной базы (микроконтроллеров, программных логических интегральных схем, транспьютеров) одной из основных задач проектирования вычислительных и управляющих систем стала задача распределения алгоритмов и программ в коллективах вычислителей и микроконтроллерных сетях с последующим расположением отдельных элементов сетей друг относительно друга таким образом, чтобы длина трактов передачи информации была минимальной. Решение указанной задачи выполняется в два этапа: на первом находится оптимальное разбиение алгоритмов на блоки с минимизацией числа внешних информационных обменов (числа внешних связей), на втором – определяется такой порядок закрепления выделенных блоков в узлах сети, при котором наиболее связные блоки располагаются максимально близко к друг другу. Минимизация длины каналов передачи информации в конечном итоге определяет надежностные характеристики систем. С ростом интеграции микросхем процесс их проектирования становится все более трудоемким из-за большого числа (104 – 105) компонентов (транзисторов, резисторов), расположенных на кристалле микросхемы, при их проектировании приходится решать задачи очень большой размерности.

Автоматизированный синтез топологии интегральных схем (топология – рисунок размещения компонентов и соединений на кристалле) сходен с автоматизированным проектированием печатных плат, однако из-за большой размерности задач и специфики компоновки компонентов и ячеек на типовых линейках задачу размещения сводят к размещению компонентов в расположенных одна под другой линейках с минимизацией суммарной длины между компонентами.

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

При решении задачи размещения исходными данными являются монтажное пространство и схема соединений размещаемых в пространстве модулей.

Под монтажным пространством понимают метрическое пространство, в котором устанавливают входящие в нее типовые конструкции (элементы топологии БИС, микросхемы, субблоки, блоки ЭВА и т.д.). Обычно такое пространство для типовой конструкции имеет прямоугольную форму с фиксированными позициями установки элементов. В качестве математической модели монтажного пространства используют неориентированный топологический граф решетки . Для построения графа gif" name="object2" align=absmiddle width=26 height=21> необходимо:

  • плоскость монтажного пространства разбить на элементарные квадратные площадки, стороны которых равны шагу проложения соединений;

  • каждой элементарной площадке поставить в соответствие вершину графа ;

  • соединить между собой ребрами соседние вершины в ортогональных (либо других, разрешенных для прокладки соединений) направлениях.

Таким образом, две вершины графа соединены ребром, если между соответствующими элементарными площадками можно провести соединение.

Расстояние между i-й и j-ой вершинами графа при ортогональном соединении в пространстве с осями можно определить по формуле:

,
где , – координаты расположения вершин , в пространстве .

Функцию расстояний для графа задают матрицей расстояний , где , а – расстояние между парой вершин , .

В качестве математической модели схемы соединений размещаемых элементов используют неориентированный мультиграф , множеству X вершин которого ставится в соответствие множество размещаемых элементов, а ребра U указывают на наличие соединений между элементами [1]. Таким образом, ребро мультиграфа схемы будет указывать не наличие связей между вершинами , , соответствующим элементам схемы.

Для цепей автоматизированной обработки используют матричные эквиваленты мультиграфа [2]: матрицу смежности и матрицу инцидентности. Для задачи размещения удобно воспользоваться матрицей смежности , элементы которой образуются по правилу:

.

Задача размещения сводится к отображению графа схемы в решетку таким образом, чтобы вершины X графа G размещались в узлах решетки и величина суммарной длины связей


была минимальной для всевозможных способов отождествления вершин графа и узлов решетки; – число кратных ребер (связей) между вершинами , графа схемы; – расстояние между вершинами и , отождествленными с узлами .

Рассмотрим возможность реализации методологии ветвей и границ для решения задачи линейного размещения графа в канале.

Пусть задан граф решетки , в котором число столбцов k равно числу вершин размещаемого графа , а число строк . Задача состоит в том, чтобы отобразить вершины графа в ячейки графа решетки по критерию минимума суммарной длины ребер графа G, т.е. найти подстановку
,
где – номера позиций графа решетки, а – вершины размещаемого графа.

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

Для эффективного решения задачи линейного размещения методом ветвей и границ необходимо:

  1. выбрать метод нахождения нижней границы суммарной длины ребер графа;

  2. выбрать метод ветвления дерева решений, позволяющий отсекать ветви, содержащие заведомо непригодные решения.

Для определения нижней границы суммарной длины L(G) ребер графа G воспользуемся понятием стандартного графа .

Пусть дан произвольный граф , причем , и задана решетка с шагом, равным 1,число узлов которой больше или равно . Граф G произвольным образом отображен в решетку. Тогда ребра графа G будут иметь вес (N – вес наиболее длинного ребра графа) в зависимости от расстояния между вершинами, которым инцидентны указанные ребра.

Нетрудно видеть, что если имеет размеры , то . Введем понятие стандартного графа для графа , отображенного в решетку. Граф имеет столько же вершин и ребер, сколько граф G, т.е. , .

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

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

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

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

Пусть вершины фиксированы соответственно в позициях графа решетки. Нефиксированные вершины графа G могут располагаться в свободных узлах графа решетки произвольным образом. При этом суммарная длина состоит из трех частей:

  1. Суммарная длина ребер, смежных только фиксированным вершинам:

Величина является точным значением и определяется из способа построения матрицы геометрии .

  1. Суммарная длина ребер, связывающих фиксированные и нефиксированные вершины

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

  1. Суммарная длина ребер, смежных только нефиксированным вершинам, которая определяется как суммарная длина ребер стандартного графа, построенного на вершинах, и оставшихся неучтенных ребер графа.

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

Похожие:

2. Характеристика задачи оптимального размещения элементов топологии iconВопрос ы к экзамену по теории вероятностей математической статистике
Перестановки из «п» элементов. Размещения из «п» элементов по «к». Сочетания из «п» элементов по «к»
2. Характеристика задачи оптимального размещения элементов топологии iconЛекции «Тема для самостоятельного изучения учащимися: «Сочетания, размещения, перестановки с повторениями»
Определение: размещения из n элементов, в каждое из которых входит m элементов, причем один и тот же элемент может повторяться в...
2. Характеристика задачи оптимального размещения элементов топологии iconРешение Рассмотрим задачу оптимального управления: при. Запишем функцию Лагранжа
Привести пример задачи оптимального управления, в которой функция не является непрерывно дифференцируемой
2. Характеристика задачи оптимального размещения элементов топологии iconСравнительная характеристика размещения растений подклассов
Сравнительная характеристика размещения растений подклассов rosidae и asteridae в ряду фитоценозов биогеохимического ландшафта
2. Характеристика задачи оптимального размещения элементов топологии iconРешение задачи оптимального размещения лицея в городе на основе энтропийного подхода
И не уделяется должного внимания удобству расположения их для всех жителей близлежащих территорий. Для многих людей это создает определенные...
2. Характеристика задачи оптимального размещения элементов топологии icon2 Универсальные алгоритмы для неограниченной задачи размещения
Наиболее ранней публикацией, в которой гриди процедура используется для решения задачи размещения средств обслуживания, является,...
2. Характеристика задачи оптимального размещения элементов топологии iconВ. Е. Мешков, Прудий А. В
Следовательно, представляется возможным свести решение задачи синтеза топологии локальной вычислительной сети (лвс) к решению упомянутой...
2. Характеристика задачи оптимального размещения элементов топологии iconПериодический закон Д. И. Менделеева и система химических элементов. Свойства нейтральных атомов
...
2. Характеристика задачи оптимального размещения элементов топологии iconТема «Математическая теория оптимального управления»
Предметом математической теории оптимального управления является методы решения задач, в которых учитываются изменения изучаемых...
2. Характеристика задачи оптимального размещения элементов топологии iconМеталлы побочных подгрупп
Характеристика переходных элементов – меди, хрома, железа по их положению в периодической системе химических элементов Д. И. Менделеева...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org