Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
12.04.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18280.zip — 95.75 kb
  • algoritm-udalenija-ciklov-v-grafe-vertikalnyx-ogranichenij-zadachi-trassirovki-mnogoslojno_18280_1.rtf — 1621.36 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала
А.М. Марченко, А.П. Плис
Рассмотрена проблема устранения циклических конфликтов при трассировке мног о слойного канала с любым расслоением при размещении контактов на любой стороне. Пре д
ложен алгоритм преобразования графа вертикальных ограничений к ациклическому виду путем расщепления его вершины на минимальное число новых вершин, который, в отличие от известных, использует информацию о контактах цепи, соответствующей выбранной ве р
шине.
Одним из важных этапов автоматизированного проектирования топологии СБИС является трассировка каналов. Каналом называется односвязная прямоугольная область на поверхности кристалла, предназначенная для соединения контактов, принадлежащих одной и той же цепи. В первой постановке задачи контакты располагались на двух противоположных сторонах канала,
а трассировка была разрешена в двух коммутационных слоях. При этом в одном слое размещались горизонтальные сегменты соединений, а в другом - вертикальные. Такой канал называется HV - кан а лом [1].
Качество решения задачи трассировки во многом определяет окончательный результат проектирования таких широко распространенных типов кристаллов, как тракты передачи данных, в которых каналы занимают около 20% общей
площади. В канальной трассировке можно в ы делить
три основные задачи:
1. Построение графа вертикальных ограничений.
2. Удаление циклов из графа вертикальных ограничений.
3. Укладка горизонтальных сегментов в канале.
Известно много эвристических алгоритмов канальной трассировки, которые эффективно решают задачу укладки горизонтальных сегментов при условии, что граф вертикальных ограничений не содержит циклов [2-4].



Ваше мнение



CAPTCHA