<<
>>

Разбиение цепей на фрагменты

Пусть имеется совмещенный эскиз трассировки T, отвечаю­щий вышеперечисленным ограничениям (см. рис. 11.1). Опреде­лим на эскизе местоположение основных узлов, в которых могут

располагаться межслойные переходы, реализующие разнесение соединений по слоям [11.5].

В первую очередь узлы размещаются на концах горизон­тальных и вертикальных отрезков. На рис. 11.7 приведен эскиз трассировки с расположенными на нем основными узлами.

Затем последовательно просмат­риваются точки пересечения про­водников.

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

Рис. 11.7. Эскиз трассировки с расположенными на нем ос­новными узлами

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

На рис. 11.8, б вводимые на проводнике 1дополнительные узлы для точек пересечения проводника 1с проводниками 2, 3, 4 совпадают, так как между проводниками 2, 3и 3, 4межслойные переходы не помещается.

На рис. 11.9 показаны узлы, введенные на эскизе трасси­ровки T. Часть соединения (цепи), связывающую два соседних межслойных перехода, назовем фрагментом.

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

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

В связи с этим производится коррекция разбиения. Последо­вательно выбираются бесконфликтные фрагменты. Бесконфликт­ный фрагмент fiсливается с любым смежным ему фрагментом fj. При этом удаляется узел, инцидентный фрагментам fiи fj∙.

Рис. 11.9. Эскиз трассировки с расположенными на нем основными и дополни­тельными узлами

Рис. 11.10. Эскиз с минимизированным числом узлов

На рис. 11.9 точками помечены удаляемые узлы, а на рис. 11.10 показано скорректированное разбиение на участки с минимизи­рованным числом узлов, обеспечивающих возможные варианты размещения соединений по слоям (в том числе и оптимальный).

Псевдокод алгоритма разбиения совмещенного эскиза трас­сировки на фрагменты с минимизированным числом узлов пред­ставлен ниже.

Algorithm разбиение_на_фрагменты begin

эскиз = ИСХОДНЫЕ_ДАННЫЕ;

узлы=К0НЦЫ (эскиз);

узлы = ПЕРЕСЕЧЕНИЕ (эскиз, узлы); фрагменты = РАЗБИЕНИЕ (эскиз, узлы); бесконфликт = ВЫДЕЛЕНИЕ (фрагменты, эскиз); while (бесконфликт= O) do

{фрагмент = ВЫБОР (бесконфликт); фрагменты = СЛИЯНИЕ (фрагменты, фрагмент); узлы = УДАЛЕНИЕ_УЗЛ (фрагменты, узлы);

бесконфликт = УДАЛЕНИЕ_ФРАГМ (фрагменты, фрагмент); };

end

В массиве эскиз хранятся исходные данные, описывающие совмещенный эскиз трассировки. C помощью процедуры КОНЦЫ (эскиз) формируется массив узлы, в который входят узлы, по­мещаемые на концах горизонтальных и вертикальных отрезков.

Процедурой ПЕРЕСЕЧЕНИЕ (эскиз, узлы) в массив узлы добавляют узлы, помещаемые возле точек пересечения провод­ников. Процедурой РАЗБИЕНИЕ (эскиз, узлы) формируется множество фрагментов в соответствии с выбранными узлами. Затем процедурой ВЫДЕЛЕНИЕ (фрагменты, эскиз) выделя­ется массив бесконфликт, содержащий бесконфликтные фраг­менты.

Далее циклически, пока не будут удалены все бесконфликт­ные фрагменты, выполняются следующие действия. Процедурой ВЫБОР (бесконфликт) выбирается очередной бесконфликт­ный фрагмент. Затем процедурой СЛИЯНИЕ (фрагменты, фрагмент)осуществляется слияние выбранного бесконфликт­ного фрагмента и коррекция массива фрагменты. Процедурой УДАЛЕНИЕ_УЗЛ (фрагменты, узлы) удаляются узлы после слияния и осуществляется коррекция массива узлы. Процедурой УДАЛЕНИЕ_ФРАГМ (фрагменты, фрагмент) осуществляется удаление подвергшегося слиянию бесконфликтного фрагмента из массива бесконфликт.

11.3.

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

Еще по теме Разбиение цепей на фрагменты:

  1. ОСНОВНЫЕ ВЫВОДЫ ПО ГЛАВЕ 4
  2. Способы измерений и порядок проведения испытаний
  3. РАСЧЕТ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ С ОДНОСТОРОННИМИ ОПОРНЫМИ СВЯЗЯМИ
  4. Результаты расчетов и экспериментов
  5. Расчет железобетонных конструкций методом конечных элементов
  6. Тема 16. Производство по делам об административных правонарушениях
  7. 3.1. Формирование стратегии развития системы персональных финансов
  8. ГЛОССАРИЙ
  9. Анализ содержания учебного материала школьных учебников с позиции их ориентации на достижение личностных результатов обучения
  10. Введение
  11. Глава I. ОПТИЧЕСКИЕ АНОМАЛИИ В КРИСТАЛЛАХ.
  12. 2. Права и обязанности сторон по договору купли-продажи.
  13. ГЛАВА 2. ИССЛЕДОВАНИЕ СОДЕРЖАНИЯ И СТРУКТУРЫ ПРОФЕССИОНАЛЬНОЙ ДЕФОРМАЦИИ ЛИЧНОСТИ СУБЪЕКТА ТРУДА (МЕНЕДЖЕРА КОММЕРЧЕСКОЙ ОРГАНИЗАЦИИ)
  14. 34. Наем жилого помещения на коммерческой основе: юридическая характеристика, элементы, срок, отличие от договора социального найма.
  15. Приложение 17.
  16. Антонов Ярослав Валерьевич. Электронное голосование в системе электронной демократии: конституционно-правовое исследование. Диссертация на соискание ученой степени кандидата юридических наук. Москва - 2015, 2015
  17. Рентгенофазовый анализ
  18. Фигуры, промежуточные между кругом и правильными многоугольниками