Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
│ └────┬───┘
└───────┘
В первом случае цикл будет выполнен 4 раза; во втором - если
в микроблоке m3 нет операций, модифицирующих СТ, - 3 ра-
за. ( Обратите внимание на начальное значение СТ!)
МИКРОКОМАНДА - набор сигналов, поступающий из УА в ОА и
интерпретируемый как управляющий,т.е. необходимый для выпол-
нения всех микроопераций одного микроблока. Сигналы, входящие
в микрокоманду, могут принимать участие в микрооперациях и в
качестве информационных.
Микрокомандой также иногда называют слово управляющей
памяти (обычно ПЗУ), являющееся частью УА. Для различения
этих понятий слово управляющей памяти будем называть МИКРО-
ИНСТРУКЦИЕЙ.
МИКРОПРОГРАММА СОДЕРЖАТЕЛЬНАЯ - алгоритм, представленный
в виде микроблоков и предикатных блоков в одной из принятых
форм, например, в виде блок-схемы или блок-текста.
МИКРОПРОГРАММА КОДИРОВАННАЯ - аппаратная форма содержа-
тельной микропрограммы в виде кодов, заполняющих управляющую
память.
_КАНОНИЧЕСКАЯ СТРУКТУРА ОПЕРАЦИОННОГО АВТОМАТА
В общем случае каноническая структура операционного ав-
томата имеет вид:
███████████████████████████████████████████████████████████
█ █
█ ┌──────────┐ ┌┬──────┬┐ ┌──────────┐ ┌───────┐ █
██>╡коммутация│ ││память││ │коммутация│ │функции▐███
│ ▐███>╡│ │▐██>╡ ▐██>╡ │
██>╡ │ ││ ││ │ │ │ ▐███>
└─A────────┘ ─/─┴┴───A──┴┘ └──A───────┘ └──A────┘
█ ┌─┐│CC █ █ █
█ SYN─>┤&├┘ █ █ █
█ ┌┤ │ █ █ █
█ yC│└─┘ █ █ █
└────────────────────────────────────────────────┘
сигналы управления
Столь четкого разграничения операций на зоны (память, комму-
тация, функции) может и не быть. Например, такие широко ис-
пользуемые функции как сдвиги либо хорошо совмещаются с
коммутацией, либо интегрируются с регистрами хранения.Также
часто интегрируются с хранением функции инкремента и
- 10 -
декремента (счетчики обычные и реверсивные).
Особо выделим сигнал yС, управляющий доступом синхросиг-
налов в ОА. Такой вариант управления, называемый условной
синхронизацией, позволяет запретить любые изменения памяти ОА
в каком-либо такте. Причем, если рабочим является срез (зад-
ний фронт) сигнала синхронизации, то используется элемент И,
как и показано на рисунке.Если же рабочим является фронт (пе-
редний фронт) сигнала, то используется элемент ИЛИ. (Первый
перепад сигнала синхронизации в новом такте не должен быть
рабочим.)
_ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА
При проектировании вычислительного устройства основными
являются ограничения на:
1)- время вычисления;
2)- объем аппаратуры, реализующей вычисления;
3)- тип применяемых базовых функций.
ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ
Алгоритм функционального типа обладает максимальным по-
тенциальным параллелизмом (в рамках данной алгоритмической
идеи), и,следовательно, его реализация в виде КС обладает
максимальным быстродействием по сравнению с любыми другими
вычислителями. Невозможность реализации вычислителя в виде КС
может быть обусловлена следующими причинами:
- слишком велик объем аппаратуры КС;
- функциональное представление и его реализация являются
статическим отображением входных объектов на выходные: это
исключает возможность работы с объектами, которые "ведут се-
бя" более сложно во времени; невозможно также реализовать
принципиально рекуррентные алгоритмы (см.,например,алгоритм
Евклида для нахождения НОД).
Тем не менее, если формально алгоритм функционального
типа может быть записан, то проектирование устройства надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом на про-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из них в один
функциональный модуль, выполняющий эти операции по очереди.
Такое решение потребует запоминания всех переменных (входных
и выходных),связанных с выполнением этих операций. Требуется
также управление памятью, связанной с этим функциональным мо-
дулем, а также - может быть - управление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурной реализации и, следовательно, к
дискретизации времени неизбежно увеличит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может уменьшиться время следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений - но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры без увели-
чения времени решения, достигнутого в алгоритме функциональ-
ного типа. Сопоставим схеме устройства, реализующего алгоритм
функционального типа, простую модель в виде направленного
графа. Вершины графа будут соответствовать операциям, а дуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальный граф всегда будет
ациклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которые располо-
жены на одном и том же пути в сигнальном графе, либо на аль-
тернативных путях решения.
- 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─ └┴──┴─┘ ├─ │ └────┘
│
└──────
__/
(реализация счетчика 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─
│ └──────