Специализированный процессор автоматической трассировки (СПТ) соединений между элементами на плоскости[1]

Е.И. Артамонов,

д.т.н., проф., зав. лаб. №18, eiart@ipu.ru,

Л.Н. Сизова,

н.с.,

И.В. Коновалов,
аспир., ivan-k85@mail.ru,

ИПУ РАН, г. Москва

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

This paper gives the structure chart of the dedicated processor for the automatic routing of connections between elements placed on a plane. This processor includes the homogeneous matrix of cells of the model of a routing field, the communication chart of the cells, and the control unit. This paper also contains the schematic circuits of some of the units, describes the principle of operating these units, and shows the results of the functional simulation performed with the VHDL language.

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

рис.1

Структурная схема матрицы М показана на рис.1. Для простоты изображения на рисунке представлен пример из матрицы 5х5 ячеек модели трассировочного поля. Каждая ячейка матрицы пронумерована с внешней стороны. Ячейки в матрице связаны между собой по восьми направлениям: север (0), северо-восток (1), восток (2), юго-восток (3), юг (4), юго-запад (5), запад (6), северо-запад (7). Связи между ячейками (на рисунке обозначены стрелками) показывают направления расчета кратчайшего пути. При этом для примера индексами С обозначена ячейка начала трассы, D - конец трассы, р – препятствие.

Общий принцип расчета весов вершин напоминает процесс распространения фронта волны от точки С до точки D. На рис. 1 фронт каждой волны соответствует одной строке «шага алгоритма» и помечен цифрами внутри ячеек матрицы. Расчеты заканчиваются на - ом шаге, когда фронт волны достигнет вершину D.

рис. 2

Ячейка матрицы спецпроцессора представлена на рис. 2.

Функциональное назначение портов ввода/вывода ячейки следующее:

COM0-COM7 – двунаправленные порты связи ячеек трассировочного поля друг с другом.

DATA(7:0) – шина данных. Двунаправленная 8-разрядная шина, предназначенная для опроса и настройки устройства.

C – тактовый сигнал.

RST – сигнал сброса схемы.

CS – сигнал выбора ячейки для осуществления операций чтения/записи.

WR – сигнал разрешения записи данных в регистры ячейки. При подаче этого сигнала паре с CS в регистры ячейки записывается значение, присутствующее на шине данных DATA(7:0).

RD – сигнал разрешения чтения данных из ячейки. При подаче этого сигнала паре с CS на шину данных DATA(7:0) выставляется значение, хранимое в регистрах ячейки.

Ячейка матрицы спецпроцессора состоит из трех основных частей:

· ячейки памяти;

· схемы сопряжения с соседними ячейками;

· схемы управления.

рис. 3

Принципиальная схема ячейки памяти представлена на рис.3. Она содержит: 8-ми разрядные регистр (FDCPE), две схемы И (AND2B1 и AND2) и одну схему ИЛИ (OR2). Регистр предназначен для хранения приходящего на эту ячейку сигнала, определяющего номер направления распространения волны.

Функциональное назначение сигналов ввода/вывода следующее:

• D(X) – шина данных. 8-разрядная шина предназначена для передачи информации в регистр от соседних ячеек через схемы И по импульсу INT_WR.
• INT_WR – внутренний сигнал записи для ячейки, формируемый из сигналов WR и CS.
• Rst – сброс схемы, установка в начальное состояние всех регистров.
• Q(X) – выходы регистров ячейки. Подключены к шине данных и к схеме управления.
• NACT (not activated) – имеет значение «1» в момент записи информации в регистр. Формируется схемой управления.

На рис.4 представлена принципиальная схема соединений (СС) ячеек модели трассировочного поля. Она содержит левую и правую часть схемы, каждая из которых содержит четыре схемы И (AND2B1) и четыре буфера с разрешающим входом (BUFE) для организации двунаправленной передачи данных по линиям COM0-COM7. Отличием этих частей схемы являются сигналы NCLK, приходящие на левую часть, и сигналы CLK, приходящие на правую часть. Это взаимно инверсные сигналы, формируемые из одного и того же управляющего импульса C, что дает возможность различать длину ортогональных соединений в проводимой трассе от длины диагональных соединений. Функциональное назначение сигналов ввода/вывода на схеме соединений следующее:

· COM0, COM2, COM4, COM6 – ортогональные межсоединения соседних ячеек

· COM1, COM3, COM5, COM7 – диагональные межсоединения соседних ячеек.

· Q(0) – Q(7) - выходы регистров ячейки.

· CLK, NCLK – внутренние взаимноинверсные тактовые сигналы.

рис.4

рис.5

Принципиальная схема управления ячейки представлена на рис.5. Она содержит: две схемы И (AND2), две группы буферов с разрешающим входом (BUFE8) для организации двунаправленной шины данных DATA(7:0), схему ИЛИ (OR8), один ключ (BUF) и две схемы НЕ (INV).

Функциональное назначение сигналов ввода/вывода этой части схемы описано выше.

Функциональное моделирование СПТ

Функциональное моделирование СПТ проводилось с использованием специализированного программного пакета Modelsim XE. На рис. 6 показана временная диаграмма работы отдельно взятой ячейки спецпроцессора.

Временные маркеры на диаграмме:

t1-t2 – установка схемы в исходное состояние. Формирование строба на входе RST.

t2 – установка лог. «1» на входах выбора ячейки (CS) и чтения (RD). При этом на шине данных (DATA(7:0)) появляется значение регистров ячейки.

t3 – «включение» тактового импульса C.

t4 – начало формирования приходящего сигнала (волны). На вход COM1 от соседней ячейки поступает логический «0».

t5 – окончание формирования приходящего сигнала (волны), начало формирования исходящих сигналов. На вход COM1 от соседней ячейки поступает лог «1», формируя тем самым передний фронт, приводящий к срабатыванию ячейки. После чего остальные линии связи (COMx) переключаются в режим выходов, и на них формируются взаимно инверсные сигналы (на ортогональных и диагональных направлениях соответственно).

рис.6

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

Препятствия в схеме формируются записью в соответствующую ячейку числа 0xFF, что вызовет полное отключение ячейки от связанных с ней соседей. Ячейка при этом не реагирует на сигналы, приходящие от «соседей» и препятствует распространению волны.

На рис.7 показаны результаты моделирования СПТ. 1-й желтый маркер на рисунке показывает начало работы схемы (после настройки параметров). 2-й желтый маркер – окончание работы схемы. Признаком окончания работы является появление ненулевого значения на шине данных при чтении конечной ячейки (адреса:3-ий столбец, 0-ая строка). Фиксация трассы производится последовательным переключаем адресов ячеек, двигаясь по сохраненным в регистрах направлениям к точке старта. Время работы СПТ составляет около 400 мксек.

рис.7

Литература

1. Артамонов Е.И., Сизова Л.Н. Автоматическая трассировка соединений (АТС). Свидетельство о государственной регистрации N2008613903 от 15 августа 2008г.

2. Артамонов Е.И. Варианты структурной организации программно-технического комплекса для решения задачи поиска кратчайшего пути // 9-я международная конференция "Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта" (CAD/CAM/PDM - 2009), М.:ИПУ РАН, 2009, ISBN 978-5-91450-047-1, С.48-53.

3. Артамонов Е. И., Коновалов И.В., Сизова Л.Н.,Тенякшев А.М., Тишкевич Е. Программно-технический комплекс (ПТК) автоматической трассировки соединений между элементами на плоскости // Материалы 37-й междунар. конф. и дикуссионного научного клуба «Информационные технологии в науке, социологии, экономике и бизнесе (IT+SE'10)». — Открытое образование. — 2010. С.132-134.

---

[1] Работа частично финансируется по проекту РФФИ 08-07-00067-а «Теоретическое обоснование и разработка макета процессора – ускорителя на основе механизма гипермассового параллелизма для решения (NP-полных) задач»