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

До недавнего времени считалось, что универсальными управляющими автоматами являются автоматы с программируемой логикой, поскольку они позволяют изменить алгоритм работы без изменения аппаратуры. С появлением ПЛИС с архитектурой FPGA проведенные исследования и разработки показали, что автоматы с жесткой логикой выигрывают по сравнению с автоматами с программируемой логикой не только по быстродействию, но и по аппаратным затратам [1]. Доказано, что для алгоритмов, в которых не менее 75% вершин составляют операторные, оптимизация аппаратных затрат в схеме автомата возможна за счет замены регистра памяти счетчиком [2] (Рис. 1).

Рис. 1. Структура автомата с жесткой логикой на счетчике.

Используем ряд определений из работы [2].

Определение 1.1. Линейной последовательностью состояний (ЛПС) ГСА Г называется конечный кортеж a_g =<a_g1,.. a_gFg>, такой, что для любой пары состояний a_gi, a_gi+1ÎA, где i – номер компоненты кортежа a_g, существует переход <a_gi, a_gi+1> автомата,  интерпретирующего ГСА Г.

Определение 1.2. Состояние a_m Î A^g, где A^g Í A – множество состояний, входящих в кортеж a_g, называется входом ЛПС a_g, если существует переход <a_s,a_m>, где a_s Ï A^g либо a_s Î A^g и соответствует компоненте с большим номером, чем a_m.

Определение 1.3. Состояние a_m Î A^g, называется главным входом ЛПС a_g, если    a_m – начальное состояние автомата, или  a_m – вход ЛПС a_g, переход в который определяется последовательностью логических условий, в которой последний компонент равен нулю.

Определение 1.4. Состояние a_m Î A^g, называется выходом ЛПС a_g, если существует безусловный переход <a_m,a_s>, где a_s Ï A^g , либо выход вершины, отмеченной состоянием a_m, связан с входом условной вершины.

Дальнейшие исследования и разработки в данной работе проводятся для автомата Мили.

Разбиение ГСА на ЛПС позволяет использовать двойную нумерацию состояний вида: <номер ЛПС>:<номер вершины внутри ЛПС>. Такой автомат в работе [1] предложено называть РС₁R-автоматом (Рис. 2).

Рис.2. Структура РС₁R-автомата.

При исследовании РС₁R-автоматов было установлено, что для каждого конкретного алгоритма можно добиться экономии аппаратных затрат если использовать один из четырех предложенных вариантов ЛПС: произвольная ЛПС (более одного входа, более одного выхода), ЛПС с одним входом, ЛПС с одним выходом, ЛПС с одним входом и одним выходом.

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

Сделать это «вручную» даже для сравнительно небольших ГСА требует значительного времени и не гарантирует отсутствия ошибок [3], поэтому актуальным является создание программного средства автоматизации синтеза РС₁R-автоматов.

Требования к системе синтеза автоматов:

Для того чтобы система синтеза могла получить входные данные, предлагается следующее представление исходной ГСА в виде текстового файла:

Для исследования синтезированного системой автомата предлагается использовать среду A-HDL, поэтому результат система должна записать в виде готового VHDL-кода.

Таким образом, целью последующей разработки является создание системы автоматизированного синтеза РС₁R-автоматов, а задачами – исследование при помощи разработанной системы различных вариантов реализации автоматов для одних и тех же ГСА.

Литература

[1] Красичков А.А. Методы синтеза управляющих автоматов на конфигурируемых логических блоках. Диссертация ... канд. техн. наук: 05.13.13 – Донецк: ДонНТУ, 2004. – 137с.

[2] Баркалов А.А. Синтез микропрограммных устройств управления. – Донецк: ДПИ, 1992. – 48 с.

[3] Баркалов А. А. Синтез устройств управления на программируемых логических устройствах. – Донецк: ДонНТУ, 2002 – 262 с.