Структурная реализация задачи прокладки печатного монтажа

Экспериментальные исследования с динамическими НЛС с несинглетным выводом показали, что они обладают несомненными преимуществами перед соответствующими статическими нечеткими системами в задачах моделирования процессов неизвестного порядка и структуры. В значительной степени это обусловлено наличием дополнительного входа обратной связи, позволяющего более корректным образом отражать в модели динамику процесса при неизвестной его структуре. Кроме того, были сделаны попытки рассмотреть динамические НЛС с точки зрения их принадлежности к общему семейству нелинейных авторегрессионных моделей скользящего среднего. Результаты показали, что при прогнозиро-, -,

, .

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Huang B.Q., Tank Rashid and M-T. Kechadi. Multi-Context Recurrent Neural Network for Time Series Applications // INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE. VOLUME 3, NUMBER 1, 2006. p.p. 1304-2386.

2. Mendel J., Mouzouris G. Non-Singleton fuzzy logic systems: Theory and application”, IEEE Trans. Fuzzy Syst., vol. 5. pp. 56-71, Feb. 1997.

B.B. Лисяк, H.K. Лисяк

СТРУКТУРНАЯ РЕАЛИЗАЦИЯ ЗАДАЧИ ПРОКЛАДКИ ПЕЧАТНОГО

МОНТАЖА*

Существенно (на несколько порядков) можно повысить производительность

-

либо за счет их реализации в суперЭВМ с перестраиваемой архитектурой [1,2], либо в виде специализированного сопроцессора на базе однородной среды [3-5]. Общие принципы и основные технические решения обеих подходов во многом близки, т.к. базируются на структурной реализации алгоритмов решения оптимизационных задач конструирования. Многообразие методов и алгоритмов решения, , , конструктивных элементов одного иерархического уровня в конструктивных элементах следующего иерархического уровня и прокладка электрических соединений печатного монтажа, ставит проблему выбора базового эффективного метода решения указанных задач для реализации его на структурном уровне. Можно обойтись без проблемы выбора, если пойти по пути создания универсального для данного класса задач сопроцессора или набора макроопераций для супер-ЭВМ, однако этот путь представляется малоэффективным по следующим соображениям.

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

* Работа выполнена при поддержке РФФИ (гранты № 07-01-00511, № 06-01-81018) и программ развития научного потенциала высшей школы 2006-2008 гг. (РНП.2.1.2.3193, РНП 2.1.2.2238).

щим названием «случайный поиск», вследствие малой производительности ЭВМ практически не использовался. Однако метод случайного поиска свободен от всех недостатков других классов алгоритмов, кроме одного - требования очень высокой производительности ЭВМ. Наиболее существенное и достаточно «универсальное» достоинство этого метода заключается в независимости каждого нового варианта решения задачи ни от начальных условий, ни от результатов решения на предыду-, .

В последнее время производительность ЭВМ существенно повысилась и метод случайного назначения, обеспечивающий равномерное или экспоненциальное назначение элементов нашёл практическое и успешное применение в системах MASTER и LAMBDA фирмы NEC (Япония) для проектирования БИС на основе вентильных матриц и иерархического проектирования на стандартных ячейках. Если этот метод реализовать структурно в виде того или иного схемного исполне-, -логических задач проектирования ЭА.

Наиболее трудоёмкой задачей конструкторского проектирования ЭА является задача прокладки электрических соединений печатного монтажа, поэтому рассмотрим вариант её структурной реализации. Такой подход предлагался 20-30 лет

,

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

Каждая ячейка однородной среды (ОС), получающая сигнал возбуждения, запоминает направление его прихода. Для случая прихода сигнала возбуждения в ячейку по нескольким направлениям может быть два варианта. Первый вариант -, - . подходов к синтезу ячеек ОС позволяет отдать предпочтение ячейкам, использующим случайный выбор путевой координаты. Такой выбор объясняется тем, что случайный выбор путевой координаты при неоднократной процедуре трассировки даёт возможность выбора наилучшего варианта и, кроме того, экономит аппара-.

При достижении волной возбуждения одной из ячеек, в которой записан признак конечной точки (ПКТ), все ячейки среды перестраиваются с режима передачи возбуждения во всех направлениях на режим передачи возбуждения в направлении, которое при возбуждении запомнила ячейка как первую координату. В ячейках с записанным ПКТ возбуждение поддерживается. В этом режиме в ОС останутся возбуждёнными ячейки, образующие трассу между конечными точками. После этого в ячейки снова подаётся сигнал настройки на режим распространения возбуждения во всех направлениях. В этом случае выполняется поиск кратчайшего пути, соединяющего очередную ячейку с построенным фрагментом трассы. Чередованием описанных режимов передачи сигнала возбуждения достигается поочерёдное присоединение точек к трассе. Когда вся трасса будет построена, то во все ячейки трассы записывается признак принадлежности к трассе. Затем повторяется процедура прокладки следующих трасс.

Для реализации описанного алгоритма ячейка ОС должна выполнять следующие функции:

1) запоминать номер входного канала, по которому пришёл сигнал возбуждения;

2) запоминать признак конечной точки;

3) .

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

Сигнализировать в устройство управления ОС факт возбуждения ячейки, в которой записан ПКТ.

.1

структурной схемы элемента ОС, в которой обозначены:

♦ «Входы (1^и)» - входные информационные шины, по которым в элемент поступает сигнал возбуждения от соседних элементов ОС;

♦ «Выходы (1^и)» - выходные информационные шины, по которым сигнал возбуждения передаётся в соседние элементы ОС;

♦ «Сброс» - управляющая шина установки ОС в исходное положение;

♦ «ПКТ» - шина записи признака конечной точки в элемент ОС;

♦ «Пуск» - шина управления началом прокладки трассы;

♦ «Управление» - шина настройки элемента на передачу сигнала либо в режиме распространения волны поиска соединения, либо в режиме считывания построенной ветви трассы;

♦ «Трасса» - шина записи признака трассы в возбуждённые элементы ОС;

♦ «Достижение» - шина передачи в устройство управления сигнала о достижении волной элемента, в котором записан признак конечной точки;

♦ «Присоединение» - шина передачи в устройство управления сигнала о наличии элементов с признаком конечной точки, но не присоединённых к трассе.

Рис.1. Структурная схема элемента ОС

Появление сигнала на выходе блока активизации элемента свидетельствует о . -тов ОС при приходе сигнала по входным шинам (1^и), либо из устройства управ-

« » « ».

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

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

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

Требование недопустимости пересечения трасс между собой выполняется организацией запрета передачи сигнала возбуждения элементам, в которых признак принадлежности к ранее построенной трассе. Это требование возникает при проектировании одного слоя многослойной печатной платы или межсоединений БИС, а также при проектировании однослойных печатных плат, если по технологии запрещена установка перемычек.

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

Г

Рис. 2. Блок выбора входного сигнала и управления его передачей

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

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

чаться трассы с минимальной длиной среди всех трасс с минимальным числом изгибов. С уменьшением величины задержки можно прийти к другому граничному случаю - получению трасс с минимальным числом изгибов среди всех трасс с ми.

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

- -, -. , -той коммутационной системой, обеспечивающей любые межпроцессорные связи, имеют распределенную оперативную память.

В основе функционирования такой суперЭВМ лежит принцип программи-,

архитектуры под свои задачи. Это предполагает задание:

♦ базовых наборов крупны х математических операций;

♦ базовые наборы групповых коммутаций;

♦ базовые наборы группо вых обращений к памяти.

Ниже рассмотрен вопрос вложимости стохастического метода размещения и компоновки БИС применительно к вышеуказанной архитектуре суперЭВМ.

Общая схема метода случайного размещения сводится к следующему. Очередное сгенерированное случайное число (номер элемента) после анализа либо , . После получения одного варианта размещения вычисляется значения целевой функции и вариант размещения либо запоминается, либо отбрасывается. При каждом последующем варианте размещения генератор случайных чисел не восстанавливается. Таким образом, для реализации алгоритма размещения необходимо выполнить две основные процедуры:

♦ генерацию случайного назначения номеров элементов PODS;

♦ вычислить суммарную длину соединений WDS.

Для реализации структурного аналога генератора случайных чисел можно воспользоваться принципами построения функции RANDU с равномерным зако-.

PODS -

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

Исходной информацией для вычисления целевой функции является сгенерированный вектор размещения и матрица цепей схемы. Соответствующая макрооперация WDC реализует функции параллельного перемножения каждой строки Hi матрицы цепей на вектор размещения, вычисления максимальной и минимальной координаты в полученных строках и нахождения их разностей. Это соответствует нахождению длины каждой цепи.

Макрооперация WDC выполняется параллельно над строками матрицы це, .

После вычисления суммарной длины цепей схемы производится сравнение ее величины с предыдущим значением и в результате вектор размещения либо запоминается, либо отбрасывается. Схема управления окончанием процессора размещения может строится по числу заданных иттераций, по времени работы, по раз-

личным характеристикам случайного процесса и др. Производительность макрокомпьютера при решении задачи размещения методом случайного назначения оценим как отношение общего числа операций к суммарному времени их выполнения. При этом будем исходить из того, что необходимо выполнить размещение N компонент, а матрица цепей схемы имеет размерность 5N*N, т.е. число схемы L=5N. Тогда производительность макрокомпьютера составит 650 Мфлопс. Время получения одного варианта размещения равно 0,04 сек.

, , , вектора подстановки намного меньше, чем время выполнения макроопераций вычисления целевой функции. Поэтому производительность макрокомпьютера на задаче размещения определяется практически производительностью микроопераций WDC. Отсюда следует, что при реализации на макрокомпьютере алгоритмов размещения основанных на парных перестановках будет достигнута таже производительностью в 620 Мфлопс. Структурное отличие при этом будет заключаться в использовании вместо макрооперации GVP макроопиерации замены пар элементов, которая выполняется существенно быстрее макрооперации GVP. (GVP -генерация вектора подстановки).

Рассмотренная схема применения метода случайного размещения компонентов БИС и соответсвующие ей макрооперации позволяет решить и задачу компоновки (р^биения) схемы на фрагменты. При этом необходимо сделать искусст-, , , -

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

дающим параметры разбиения и координаты фрагментов, а затем модифицирован-

WDC. , ,

затрачиваемое на модификацию, намного меньше времени выполнения макроопе-

WDC, -

поновки фрагментов БИС будет иметь ту же величину, что и при решении задачи , . . 620 .

На рис.3 показана структурная схема организации макроопераций при решении на суперЭВМ задач размещения и компоновки элементов БИС, где

RAN - макрооперация генерирования случайных чисел;

SORT - макрооперация сортировки номеров элементов и анализа признака окончания формирования вектора ;

WDS - макрооперация вычисления целевой функции ;

ANAL - макрооперация анализа Ll и Lt-1 значений целевой функции

методом

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ли сяк В.В., Калашников В А., Тищенко В А. Разработка высокопроизводительных САПР на базе Супермакрокомпьютера // Материалы Всесоюзного семинара «Создание интеллектуальных САПР СБИС и электронных средств». - М.: Радио и связь, 1990.

2. . ., . . -лельных ЭВМ с перестраиваемой архитектурой // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». Материалы международной научно-технической конференции. - Таганрог: Изд-во ТРТУ, 1999, №3. - С. 200-203.

3. Берш тейн Л.С., Лисяк В.В., Рабинович В.А. С б. Методы расчёта и автоматизация проектирования устройств микроэлектронных ЦВМ. ИК АН УССР. - Киев, 1975. - С. 39-52.

4. Лисяк В.В., Курейчик В.М., Соколец М.Г. Устройство для решения комбинаторнологических задач. А.С.2019454, СССР. № 482751; Приоритет от 22.04.74; Бюллетень № 32 от 30.08.75

5. Берштейн Л.С., Лисяк В.В., Рабинович В.А. Ячейка однородной среды. АС. 2051062, СССР. - № 646328; Приоритет от 9.08.74; Бюллетень № 5 от 5.02.79.

АЛ. Долгий, А.Е. Хатламаджиян

ГИБРИДНАЯ МОДЕЛЬ ИНТЕРПРЕТАЦИИ ДЕФОРМАЦИЙ В БАЛЛАСТНОЙ ПРИЗМЕ И ОСНОВНОЙ ПЛОЩАДКЕ ЗЕМЛЯНОГО ПОЛОТНА НА ОСНОВЕ ЦЕЛЕВОГО ПРЕОБРАЗОВАНИЯ ХАФА И НЕЙРОННОЙ СЕТИ КОХОНЕНА*

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

Как показывает практика, надзор за полотном, основанный преимущественно на визуальном контроле, зачастую оказывается неэффективным. Поэтому в настоящее время активно применяется георадиолокационное методы контроля, позволяющие восстанавливать структуру зондируемой среды по данным георадара. При этом возникает задача автоматической локализации и интерпретации деформаций слоев земляного полотна.

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

Первичную классификацию осуществляет гибридная модель локализации аномалий и восстановления структуры земляного полотна по георадиолокацион-ным данным, объединяющая два различных метода обработки информации: целевое преобразование Хафа для обнаружения гипербол и искусственная нейронная сеть Кохонена. Структурная схема гибридной модели представлена на рис.1.

В предлагаемой гибридной модели вначале детектируются балластные мешки . .

На первом этапе производится выделение информативных пиков радаро-граммы с помощью одноименного модуля (МВИП), основанном на использовании многослойного персептрона [3].

* Работа выполнена при поддержке РФФИ (гранты № 07-01-00075, № 07-07-00010) 180