Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 46
Текст из файла (страница 46)
Овннннвнов дов со слоя на слой, степень близости пути к другим и т, д., например в виде аддитивной функции Р„=- ~ а! Р; ()г), (10.15) где а! — весовой коэффициент, учитывающий важность !-го парамет- ра; р! (й) — значение учитываемого параметра. Однако усложнение функции веса увеличивает объем информации на одну ячейку ДРП и время работы первой части алгоритма. Кроме того, не представляется возможным строго обосновать выбор значений ' весовых коэффициентов аь При практической реализации волнового алгоритма важная пробле- ма — сокращение объема памяти, необходимой для запоминания весов ячеек.
При вычислении весов ячеек по (10.14) ячейка может быть в сле- дующих состояниях: свободна, занята или имеет вес от единицы до Ь, где  — максимально возможная длина пути, определяемая как ко- личество составляющих его ячеек ДРП. Необходимое для запоминания состояния одной ячейки ДРП число разрядов памяти: М = — )1ояа(Ь+ 2)Р, (10.16) где ~( — символы ближайшего большего целого. Наиболее эффективными способами кодирования состояния ячеек ДРП являются метод путевых координат, кодирование по модулю 3 и использование базовой последовательности 1, 1, 2, 2, 1, 1, 2, 2, предложенной Акерсом. При выборе последовательности ячеек на этапе построения пути по методу путевых координат для каждой ячейки, начиная с В, в случае соседства по ребрам достаточно знать, от какой соседней ячейки в нее пришла волна: сверху, слева, снизу, справа ( 4, — , Т, « †).
Таким образом, ячейка может иметь следующие признаки:свободна, занята или одну из путевых координат ~, —, '1, . Следовательно, число разрядов на кодирование состояния ячеек А! = ) 1ода 6 Г -- 3. Если в данную ячейку волна приходит из нескольких соседних, то присвоение путевых координат выполняется по заранее заданному правилу приоритетов. При проведении пути достаточно переходить по путевым координатам из ячейки В в ячейку А. Пример проведения пути при использовании данного метода показан на рис. 10.!3, в. Кодирование по модулю 3 базируется на основном требовании к весам: Р„, чь Рд ~ Р„,. Ячейкам, включаемым в последовательные фронты, можно присваивать не сами веса, а их значения по модулю 3, т.
е. 1, 2, 3, 1, 2, 3, ... Количество разрядов на кодирование состояния ячеек Ф = -1 1ода 5г =- 3. Проведение пути заключается в отслеживании отметок. Если ячейка имеет несколько соседних с одинаковыми отметками, то используется правило приоритетных направлений. При движении от ячейки В на рис. 10.13, г использовано следующее правило приоритетов: налево, вверх, направо, вниз. Для определения последовательности ячеек, составляющих путь, достаточно, чтобы при распространении волны ячейкам присваивались значения отметок из заданной последовательности, в которой каждый 21з член имеет разных соседей слева и справа. В методе Акгрса такой последовательностью является 1, 1, 2, 2, 1, 1, 2, 2, ... При построении пути находят ячейки, входящие в заданную последовательность.
В методе Акерса количество разрядов памяти на ячейку ДРП У = — ) )она 4 1 = 2. Если построение последовательности возможно по нескольким направлениям„то выбор осуществляют по приоритетам. Пример нахождения пути с использованием отметок Акерса изображен на рис. 10.13, д. Волновой алгоритм характеризуется высокой эффективностью нахождения пути за счет исследования всех свободных ячеек ДРП, но требует значительного времени иа распространение о) й волны.
В связи с этим используются различные методы ускорения выполнения первого этапа алгоритма. Одним из иих является выбо начальной Р точки (см. (21)). Из рис. 10.14, а Рнс. 10.14. Выбор источника распространения видно, что при выборе в (о) н РаспростРанение полни на янух нсгочннкачестве источника распро- коа (б) странения волны площадки, максимально удаленной от центра платы, просматривается меньшее число свободных ячеек ДРП. Это становится очевидным по мере роста числа протрассированных цепей.
Волее эффективен метод встречной волны (рис. 10.14, б), Выигрыш во времени пропорционален отношению числа исследуемых ячеек при одновременном распространении волны и при распространении волны из одного источника. При непрерывной модели окрестности волны на свободном поле ДРП отношение исследуемых площадей М = = ига(12п (г!2)а! =- 2. Для реальных состояний ДРП выигрыш во времени может отличаться, однако в среднем оценка является объективной. Использование данной идеи приводит к усложнению алгоритма.
Поле распространения волны можно уменьшить, ограничивая его прямоугольником, внутри которого находятся соединяемые площадки. Начальная площадь прямоугольника обычно на 10 — 20% больше площади прямоугольника, проходящего через эти площадки. Если соединение найти не удалось, то границы прямоугольника расширяются. Данный метод обладает большей эффективностью ускорения работы алгоритма по сравнению с вышеописаииьпии. Другая идея ускорения поиска пути заключается в исследовании не всех свободных ячеек ДРП, а лишь по заранее заданным направлениям. Один из таких алгоритмов — лучевой алгоритм Абрайтиса. Для площадок А и В задается количество распространяемых лучей и разрешенные направления их движения. При прохождении луча через ячейку ей присваивается путевая координата. На рис. 10,15, а показан пример проведения пути двухлучевым алгоритмом, причем лучу А, разрешено движение вправо и вниз, лучу А, — вниз и вправо, лу- чу В, — вверх и влево, лучу В, — влево и вверх.
Вероятность нахождения пути этим алгоритмом меньше, чем волновым. Близок к лучевому алгоритм трассировки по магистралям (рис. 10.15, б). Из площадок А и В по свободным ячейкам ДРП проводятся горизонтальные и вертикальные лучи до нх встречи или до препятствий. Если магистрали Мд1 и Мв~ не пересекаются, из ячеек, а) оу' Иж м„, г(вс Рис. 10.10. Пример работы двухлучевого алгоритма (а) и трасси- ровка по магистралям (б) расположенных на этих магистралях, проводят магистрали второго уровня Мд» н Мвю причем Мдз и Мв ортогональны Мд, и Мв, соответственно. Путь существует, если магистрали Мд и Мв некоторого уровня пересекаются, и не существует в противном случае.
Рис. 10.10. Разбиение монтажного поля на равносторонние треуголь- ники (а) и шестиугольники (б) Пока мы рассматривали разбиение рабочего поля на элементарные квадраты, причем соседними считались квадраты с общим ребром, При этом проводники состояли из отрезков прямых, проходящих в двух взаимно перпендикулярных направлениях. Получение составляющих путей с другими углами наклона возможно двумя способами: изменением формы элементарных ячеек и определением их соседства. При разбиении поля на равносторонние треугольники (рис.
10.16, а) пути могут иметь составляющие с углом наклона гг!2 и п(6, при раз- 220 биении на равносторонние шестиугольники — 0 и ~п!3 (рис. 10.16, б). При использовании элементарных ячеек в форме равносторонних треугольников требуется операция асглаживания» углов. Разбиение рабочего поля на треугольники, шестиугольники либо какие-то неправильные фигуры усложняет их адресацию. На практике применяют соединения с углами наклона О, н!2 н ~п/4.
Такие отрезки можно получить, если для квадратной ячейки соседними считать ячейки, имеющие с ней общее ребро или точку (рис. 10.17). На базе такой окрестности можно построить новые уже несимметричные. Например, если для одного слоя МПП в окрестность ячейки с координатами (хо, уо) включить ячейки с координатами (хо, уо+ 1), (хо, уе — 1) и (хо+1, ус+1), (хо — 1, уев — 1), а для соседнего слоя— (хо — 1, уо), (хо + 1, уе) и (хо — 1, ус+ 1), (хе+ 1, уо — 1), то тогда соединения на соседних слоях будут пересекаться под углами и!2 и и/4.
Волновой алгоритм можно у !кйп 1 использовать при различных стратегиях построения цепей, Рис. 10.17. К определению соседства Выполнение первых трех этапов задачи трассировки подразумевает переход к построению следующей цепи после получения конфигурации текущей или установления невозможности этого. Вследствие того, что в цепь могут входить как длинные соединения, так и короткие, при такой стратегии будет нарушен желательный порядок проведения соединений от коротких к длинным.
После длинных отрезков одной цепи могут строиться более короткие первые отрезки следующей цепи. Чтобы избежать этого, проводят сначала соединения, стоящие первыми в списках всей цепей, затем вторые и т. д. Данный подход будет более корректным, если после распределения соединений по слоям определить порядок проведения отрезков по всем цепям каждого слоя. Одна из модификаций алгоритма Ли позволяет исключить этап определения порядка соединения выводов внутри каждой цепи.
В этом алгоритме используется метод встречной волны. Из и элементарных площадок, сопоставленных контактам цепи, одновременно распространяются волны до тех пор, пока не встретятся два фронта. Выполняется вторая часть алгоритма Ли, т. е. строится фрагмент цепи, соединяющий два контакта. Снова распространяются волны, но уже из и — 1 источников. Алгоритм соединяет две ближайшие ячейки илн связанные системы ячеек с учетом преград в виде ранее проведенных соединений. Алгоритмы трассировки, основанные на представлении 0 каналах.
Их можно выделить в качестве самостоятельного класса. Алгоритмы ориентированы на построение трасс в таких монтажных платах, где между рядами и столбцами элементов можно провести совокупность 221 а) юб тЛ т1 тФ тб т7 б,) т2 о4! 447 1 Ча 4! 4 — -1 Рнс. 10.19. Упорядочивание отрезков (а) н распределение нх по магистралям (б) горизонтальных и вертикальных магистралей (рис. 10.18).
Совокупность магистралей называют каналом. К таким платам относятся некоторые типы ДПП, большие гибридные и монолитные интегральные схемы. В таком монтажном пространстве цепь представляет собой последовательность горизонтальных н вертикальных отрезков магистралей с переходными контактами со слоя на слой в местах сопряжения этих отрезков. В алгоритмах трассировки на основе представлений о каналах можно выделить две основные части: распределение отрезков трасс по каналам с учетом их равномерной загрузки и определение положения отрезков на магистралях. В первой части алгоритма для каждой цепи строят возможные на данной системе каРнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
