Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
статическим отображением входных объектов на выходные: это
исключает возможность работы с объектами, которые "ведут се-
бя" более сложно во времени; невозможно также реализовать
принципиально рекуррентные алгоритмы (см.,например,алгоритм
Евклида для нахождения НОД).
Тем не менее, если формально алгоритм функционального
типа может быть записан, то проектирование устройства надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом на про-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из них в один
функциональный модуль, выполняющий эти операции по очереди.
Такое решение потребует запоминания всех переменных (входных
и выходных),связанных с выполнением этих операций. Требуется
также управление памятью, связанной с этим функциональным мо-
дулем, а также - может быть - управление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурной реализации и, следовательно, к
дискретизации времени неизбежно увеличит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может уменьшиться время следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений - но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры без увели-
чения времени решения, достигнутого в алгоритме функциональ-
ного типа. Сопоставим схеме устройства, реализующего алгоритм
функционального типа, простую модель в виде направленного
графа. Вершины графа будут соответствовать операциям, а дуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальный граф всегда будет
ациклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которые располо-
жены на одном и том же пути в сигнальном графе, либо на аль-
тернативных путях решения.
- 11 -
_МИНИМИЗАЦИЯ АППАРАТУРЫ
Может оказаться, что на одном пути в сигнальном графе
расположены операции, плохо или вовсе не совмещаемые друг с
другом (т.е. совмещение не дает экономии в аппаратуре функци-
онального модуля). Возможно также, что проведенная минимиза-
ция, сохраняющая минимальное время, не позволяет выполнить
ограничение на объем аппаратуры. В таком случае необходима
более глубокая минимизация,охватывающая параллельные ветви
сигнального графа. Минимизация должна быть взаимосвязанной по
всем компонентам ОА: по памяти, функциональным модулям и ком-
мутации.
В настоящее время процедуры минимизации не формализованы
и сводятся к перебору "правдоподобных" вариантов.
Можно предложить следующую последовательность действий:
1)- все "похожие" функции (операции) реализовать на одном
функциональном модуле, например, все суммирования выполнять
на одном сумматоре;
2)-скорректировать алгоритм так, чтобы в одном микроблоке не
выполнялось более одной операции на одном и том же функци-
ональном модуле;
3)- минимизировать память автомата, т.е. число запоминаемых
промежуточных переменных;
Выполнение этих этапов может привести к усложнению ком-
мутации, а значит, и к увеличению этой компоненты в аппарату-
ре ОА. Если ограничение по объему аппаратуры все еще наруше-
но, то повторить этапы 1 - 3 с другим вариантом объединения
функциональных модулей и памяти.
При реализации ОА - во избежание ошибок -необходимо бук-
вально следовать описанию алгоритма, но в то же время, при
проектировании самого алгоритма надо представлять себе реали-
зацию микроблоков. Реализация одних и тех же вычислений может
быть существенно различной по объему аппаратуры.
Например, вычисления в цикле потребуют реализации:
─┬─
│
┌───────V───────┐ A ┌────┐
│ J:=0 │ ┌┬──┬─┐ │ MUX│ ┌────┐
└───────┬───────┘ ││RG│0├───>┤0 │ │ f │
┌──────┐ │ ││ │.│ . │. │A[J] │ │
│ ┌────V──V───────┐ ││ │.│ . │. ├────>┤ │
│ │ ..... │ ││ │.│ . │. │ │ │ B
│ │ │ ││ │ │ │ │ │ ╞══>
│ │ B= f(...,A[J])│ ││ │K├───>┤K │ │ │
│ │ │ ││ │.│ │. │ ══>╡ │
│ │ J:=J+1 │ ││ │.│ │. │ │ │
│ └───────┬───────┘ ││ │.│ │. │ │ │
│ ─V─ └┴──┴─┘ ├─ │ └────┘
│ <K / \ =K J═════════>╡А │
└──────<J==K>─────> └────┘
\__/
(реализация счетчика J не показанa).
- 12 -
Запишем этот фрагмент алгоритма иначе так, чтобы нужный
бит извлекался за счет сдвига в регистре D. Тогда получим:
───┬── A D
│ ┌┬──┬┐ ┌┬──┬─┐ A[J] ┌─────┐
┌───────V───────┐ ││RG││ ││RG│0├─────>┤ f │
│ J:=0 │ ││ ││ ││ │.│ │ │
│ │ ││ ││ ││->│.│ │ │ B
│ D:=A │ ││ │╞══════>╡│ │.│ │ ╞══>
└───────┬───────┘ ││ ││ ││ │ │ │ │
┌──────┐ │ ││ ││ ││ │K├ │ │
│ ┌────V──V───────┐ ││ ││ x ──>┤Dn │.│ │ │
│ │ ..... │ ││ ││ ││ │.│ ══>╡ │
│ │ │ ││ ││ S W││ │.│ │ │
│ │ B= f(...,D[0])│ └┴──┴┘ ─v─v┴┴──┴─┘ └─────┘
│ │ │
│ │ (D,x):=(x,D) │
│ │ │
│ │ J:=J+1 │
│ └───────┬───────┘
│ ─V─
│ <K / \ =K
└──────<J==K>─────>
\__/
Промежуточный регистр A введен для общности, если потребуется
сохранить слово А (чаще всего он и не нужен).
Другой пример: фрагмент алгоритма, реализующий регуляр-
ную запись отдельных бит слова и его реализация имеют вид:
───┬── ┌┬─┬┐B[0]
│ a ────────────┬─────>┤│T│├────>
┌───────V───────┐ │ W││ ││
│ J:=0 │ ┌───┐ │ ─A┴┴─┴┘
└───────┬───────┘ │DC │ ┌──┼─────┘| |
┌──────┐ │ │ 0├─┘ │ | |
│ ┌────V──V───────┐ │ .│. │ ┌┬─┬┐B[K]
│ │ ..... │ │ .│. └─────>┤│T│├────>
│ │ │ │ .│. W││ ││
│ │ a=f(...) │ J ══>╡ │ ─A┴┴─┴┘
│ │ │ │ K├──────────┘
│ │ B[J]:=a │ │ .│
│ │ │ │ .│
│ │ J:=J+1 │ │ .│
│ └───────┬───────┘ └───┘
│ ─V─
│ <K / \ =K
└──────<J==K>─────>
\__/
Слово В нельзя реализовать в виде регистра, а только в виде
отдельных триггеров.
Можно формировать слово с использованием операции сдви-
га при обязательном условии D[K..0], тогда алгоритм и его ре-
ализация имеют вид:
- 13 -
───┬──
│ D B
┌───────V───────┐ ┌──┬──┬┐ ┌┬──┬┐
│ J:=0 │ │ │RG││ ││RG││
└───────┬───────┘ │ │->││ ││ ││
┌──────┐ │ a │ │ │╞═════>╡│ ││
│ ┌────V──V───────┐ ──>┤Dk│ ││ ││ ││
│ │ ..... │ S│ │ ││ W││ ││
│ │ │ ─v┴──┴──┴┘ ─v┴┴──┴┘
│ │ a=f(...) │
│ │ │
│ │ (D,x):=(a,D) │
│ │ │
│ │ J:=J+1 │
│ └───────┬───────┘
│ ─V─
│ <K / \ =K ┌────┐
└──────<J==K>──>┤B:=D├>
\__/ └────┘
В этом случае, так же, как и в предыдущем, чаще всего не ну-
жен промежуточный регистр (В).
_УНИВЕРСАЛЬНЫЙ ОА
Использование при проектировании универсальных ОА с за-
ранее фиксированной и минимизированной структурой оправдано
тем, что такие универсальные ОА изготавливаются промышлен-
ностью в виде БИС большим тиражом и поэтому они сравнительно
дешевы. Такие универсальные ОА входят в микропроцессорные на-
боры 582, 583, 584, 588, 589, 1800, 1804 и т.д., которые на-
зываются микропрограммируемыми, секционными, разрядно-модуль-
ными.
В основе перечисленных универсальных ОА лежит следующая
структура:
╔══════════════════╦═══════════════════════════╗
║ ║ ║
║ ║ SYN┐ ACC ║
║ ┌─┬─────┬┐ ║ ─/┬┬──┬┐ ┌─────┐ ║
║ │ │ RGF ││ ║ C││RG││ │ ALU │ ║
║ │ │ ││ ║ ││ ││ │ │ ║
║ │ │ ││ ╚════>╡│ │╞═════>╡ │ ║
