СПЕЦПРОЦЕССОР ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА КРАТЧАЙШЕГО ПУТИ МЕЖДУ ОБЪЕКТАМИ НА ПЛОСКОСТИ

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

В настоящее время известны примеры использования специализированных процессоров-ускорителей для решения задач, связанных с визуализацией графической информации. Так, например, суперкомпьютер Roadrunner (IBM) содержит 32000 процессоров, из них 16000 являются процессорами-видеоускорителями, которые ранее были разработаны для игровой приставки Playstation-3 (http://ru.wikipedia.org/wiki/RSX).

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

Задачей настоящего изобретения является расширение арсенала технических средств, направленного на создание 2D модели размещения объектов на плоскости и решения задачи поиска кратчайшего пути на этой модели.

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

Технический результат достигается тем, что спецпроцессор для решения задачи поиска кратчайшего пути между объектами на плоскости содержит параллельно-последовательную схему соединения по восьми ортогональным и диагональным связям процессоров-ускорителей в виде однородной плоской матрицы, в которой каждый процессор-ускоритель реализует функции фиксации точки начала или конца пути, хранения информации о наличии препятствия, о номере направления входных сигналов, вычисления номеров направлений входных сигналов соседних процессоров-ускорителей и передачи их от точки начала пути к точке конца, при этом каждый процессор-ускоритель соединен с восьмью соседними двунаправленными связями для передачи и приема сигналов, соответствующих номеру направления их распространения, и содержит тактовый генератор с прямым и инверсным выходами, восьмиразрядный регистр (FDCPE), две схемы И (AND2B1 и AND2) и одну схему ИЛИ (OR2), причем ортогональные связи регистров каждого процессора-ускорителя соединены с соседними процессорами-ускорителями через ключи BUFE1, управляемые прямым выходом тактового генератора, а диагональные связи регистров каждого процессора-ускорителя соединены с соседними через ключи BUFE2, управляемые инверсным выходом тактового генератора, что дает возможность различать длину ортогональных соединений в поиске кратчайшего пути от длины диагональных соединений.

СПКП выполнен на интегральных схемах (плис XC95288XL серии Vertex 4 фирмы Xilinx).

На фиг.1 представлена структурная схема матрицы М.

На фиг.2 - ячейка матрицы спецпроцессора.

На фиг.3 - принципиальная схема ячейки памяти.

На фиг.4 - принципиальная схема соединений (СС) ячеек модели трассировочного поля.

На фиг.5 - принципиальная схема управления ячейки.

Структура СПКП содержит три основных блока: однородную матрицу М ячеек модели трассировочного поля, схему соединений (СС) между ячейками матрицы М и блок управления (БУ).

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

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

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

СОМ0-СОМ7 - двунаправленные порты связи ячеек трассировочного поля друг с другом.

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

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

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

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

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

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

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

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

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

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

Принципиальная схема ячейки памяти (фиг.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) для организации двунаправленной передачи данных по линиям СОМ0-СОМ7. Отличием этих частей схемы являются сигналы NCLK, приходящие на левую часть, и сигналы CLK, приходящие на правую часть. Это взаимно инверсные сигналы, формируемые из одного и того же управляющего импульса С, что дает возможность различать длину ортогональных соединений в проводимой трассе от длины диагональных соединений. Функциональное назначение сигналов ввода/вывода на схеме соединений следующее:

СОМ0, COM2, COM4, СОМ6 - ортогональные межсоединения соседних ячеек;

СОМ1, COM3, СОМ5, СОМ7 - диагональные межсоединения соседних ячеек;

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

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

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

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