Структурный синтез процессора-ускорителя автоматической трассировки соединений между элементами

на плоскости в САПР Decomposer

В.Н. Коновалов,

ст. препод., v.konovalov@list.ru,

КФ МГТУ им. Н.Э. Баумана, г. Калуга,

И.В. Коновалов,

аспир., лаб. 18, ivan-k85@mail.ru,

ИПУ РАН им. В.А. Трапезникова, г. Москва

Аннотация

В статье рассматривается процесс проектирования специализированного процессора-ускорителя с использованием методов многоуровневой декомпозиции, реализованных в САПР Decomposer.

Abstract

Thesis dedicated to hardware tracer synthesis using multilevel decomposition algorithms implemented in CAD Decomposer.

Синтез структурной схемы процессора-ускорителя

Структура процессора-ускорителя содержит три основных блока [3]:

1. однородную матрицу М ячеек модели трассировочного поля;

2. схему соединений (СС) между ячейками матрицы М;

3. блок управления (БУ).

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

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

рис. 1. Структурная схема процессора-ускорителя рис. 2. Структурная схема ячейки процессора-ускорителя

Рассмотрим отдельно взятую ячейку спецпроцессора, структурная схема которой приведена на рис. 2.

Функционально ячейку можно разделить на четыре части:

1) управляющее устройство (УУ), отвечающее за настройку, синхронизацию и чтение состояния ячейки;

2) исполнительное устройство (ИУ), реализующее непосредственно алгоритм запоминания направления входящей волны

3) формирователь исходящей волны (ФИВ), обеспечивающий дальнейшее распространение волны после срабатывания исполнительного устройства ячейки процессора-ускорителя;

4) буферное устройство (БУ), передающее состояние ИУ на общую шину данных процессора-ускорителя при выборе рассматриваемой ячейки входными сигналами и .

Основные входные и выходные сигналы ячейки:

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

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

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

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

– сигнал разрешения чтения данных из ячейки. При подаче этого сигнала паре с на шину данных выставляется состояние исполнительного устройства (направление прихода волны);

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

– Входные сигналы от соседних ячеек.

– Выходные сигналы к соседним ячейкам.

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

Формальное описание исполнительного устройства ячейки процессора-ускорителя

Особое внимание следует уделить исполнительному устройству (ИУ) и его структуре, поскольку его функционирование носит нетривиальный характер, и его реализация с использованием стандартных методов несколько затруднена.

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

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

рис. 3. Исполнительное устройство ячейки спецпроцессора

Описание работы рассматриваемого блока ИУ удобно задать в виде совмещенной таблицы переходов и выходов, содержащей 16 строк (состояний) и 64 столбца (комбинаций на входах схемы).

Синтез схемы блока ИУ в САПР Decomposer

Если разорвать обратные связи в схеме блока ИУ трассировочной ячейки (рис. 3), то получится комбинационное устройство, имеющее 10 входов и 4 выхода. Дальнейший структурный синтез схемы заключается в декомпозиции полученного комбинационного устройства с использованием САПР Decomposer и последующем замыкании обратных связей. Числовую последовательность рассматриваемого комбинационного устройства можно получить развертыванием таблицы переходов блок ИУ по строкам. Полученная последовательность содержит 1024 элемента, т.к. проектируемая комбинационная схема имеет 10 входов.

Последовательность загружается в САПР Decomposer в качестве исходного описания синтезируемой схемы.

Далее следует провести параллельную декомпозицию схемы. Результаты проверки существенной зависимости выходов от входов схемы, выполненной при помощи САПР Decomposer представлены на рисунке 4.

рис. 4. Таблица существенных зависимостей схемы (выход )

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

Далее следует провести синтез каждого отдельно взятого блока. Для этого необходимо сохранить последовательности всех блоков в виде отдельных файлов, и затем для каждого из них создать новый проект в САПР Decomposer. Поскольку рассматриваемые блоки имеют лишь по одному выходу, дальнейший структурный синтез может быть выполнен с использованием алгоритмов последовательной декомпозиции или детализации.

Результаты структурного синтеза полученных блоков в САПР Decomposer приведены на рис. 5 … 8.

рис. 5. Логическая схема блока 1 (выход ) рис. 6. Логическая схема блока 2 (выход )

рис. 7. Логическая схема блока 3 (выход ) рис. 8. Логическая схема блока 4 (выход )

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

Полученные в САПР Decomposer схемы блоков 1…4 были перенесены в программный пакет WebPACK ISE для проведения моделирования и реализации исполнительного устройства ячейки спецпроцессора на микросхемах программируемой логики.

Функциональное моделирование схемы процессора-ускорителя

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

рис. 9. Результаты моделирования синтезированной схемы ИУ

Временные маркеры на диаграмме (рис. 9):

t1 – сброс схемы сигналом (перевод в состояние «0»). Начало первого теста;

t2 – на вход поступает сигнал (волна пришла снизу). Схема переходит в состояние «4». На выходе появляется логическая «1»;

t3 – на вход поступает сигнал (волна пришла слева). Поскольку схема находится в состоянии «4», никаких изменений не происходит;

t4 – сброс схемы сигналом . Начало второго теста;

t5 – на входы и одновременно поступают сигналы. Схема переходит в состояние «9». На выходах и появляются логические «1»;

t6 – на вход поступает сигнал. Схема остается в состоянии «9»;

t7 – сброс схемы сигналом . Начало третьего теста;

t8 – на вход поступает сигнал. Схема переходит в состояние «8». На выходе появляется логическая «1».

Из результатов моделирования видно, что полученное в результате синтеза с использованием САПР Decomposer и методов многоуровневой декомпозиции исполнительное устройство ячейки процессора-ускорителя работает в соответствии с заданным описанием.

На заключительном этапе разработки был изготовлен макетный образец процессора-ускорителя, реализованный на базе программируемой логической интегральной схемы (ПЛИС) xc95288xl фирмы Xilinx (рис. 10).

рис. 10. Фотографии макета процессора-ускорителя

Литература

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 584 с.

2. http://ru.wikipedia.org/wiki/RSX.

3. Артамонов Е.И., Коновалов И.В., Ничипорович Т.А., Тишкевич Е.В. Процессор-ускоритель автоматической трассировки соединений между элементами на плоскости. // Научно-практический журнал «Открытое Образование» 2011. №2 (86). Ч. 2. с. 18-22.