Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)

в каком-либо такте. Причем, если рабочим является срез  (зад-

ний фронт) сигнала синхронизации, то используется элемент  И,

как и показано на рисунке.Если же рабочим является фронт (пе-

редний фронт) сигнала, то используется элемент  ИЛИ.  (Первый

перепад сигнала синхронизации в новом такте  не  должен  быть

рабочим.)

             _ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА

     При проектировании вычислительного устройства  основными

являются ограничения на:

 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─              └┴──┴─┘    ├─   │     └────┘

│    <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 │   ║

     ║    │ │     ││    ║     ││  ││      │     │   ║

     ║    │ │     ││    ╚════>╡│  │╞═════>╡     │   ║

     ║    │ │     ││          ││  ││      │     ╞═══╩═>DO

     ╚═══>╡D│     ││          └┴──┴┘      │     │

          │ │     ││             T        │     │

          │ │     ││          ┌┬──┬┐      │     ╞═════>P

          │ │     ││          ││RG││      │     │

          │ │     │╞═════════>╡│  │╞═════>╡     │

          │ │     ││          ││  ││      │     │

       C W│А│     ││         C││  ││   ╔═>╡     │

      ─o─A┴A┴─────┴┘        ─┬┴┴──┴┘   ║  └──A──┘

    SYN┘ │ ║              SYN┘         ║     ║

         │ ║                           ║     ║

       yW   YA                  DI═════╝      YF

     ALU - арифметико-логическое устройство -  комбинационная

схема с небольшим, но универсальным набором арифметических  и

логических операций.

     RGF - регистровый файл - адресуемая память RAM со стати-

ческой синхронизацией при записи.

     RG'T' - регистр-фиксатор со статической синхронизацией.

     RG'АCC' - регистр-аккумулятор с динамической синхрониза-

цией.

     DI,DO - входная и выходная информационные шины.

                                - 14 -

     Р - предикатные сигналы (флажки).

     YF - сигналы управления выбором функции.

     YA - адрес чтения и/или записи RGF.

     yW - разрешение записи в RGF.

     Память сравнительно большого объема, какой является RGF,

дешевле реализовать со статической  синхронизацией.  Для  то-

го,чтобы такая память могла работать в замкнутом информацион-

ном кольце и при этом не возникали бы гонки, добавляется  еше

один промежуточный регистр RG'T' со  статической  синхрониза-

цией. Если передний фронт является рабочим для регистров  уп-

равляющего автомата и RG'ACC', то на первой фазе  синхрониза-

ции при SYN=1 информация читается  из  RGF;  при  этом  RG'T'

прозрачен. На следующей фазе синхронизации при SYN=0 информа-

ция фиксируется в RG'T', т.е. он закрыт для записи, а  запись

(если она разрешена) производится в RGF. Фиксируется информа-

ция в RGF и RG'ACC' с началом следующего такта, т.е.  на  пе-

реднем фронте сигнала.

                  _ВЗАИМОДЕЙСТВИЕ  ОА  и  УА

     Для исключения гонок при взаимодействии ОА  и  УА  будем

проектировать УА как автомат Мура.  Схема  их  взаимодействия

может быть представлена в виде:

           ╔══════════════════════════╗

           ║┌────┐    ┌┬──┬┐   ┌────┐ ║

           ╚╡ CS │    ││RG││   │CS  ╞<╝

            │    ╞<═╦═╡│  │╞<══╡    │

        ┌───┤  b │  ║ ││  ││   │ c  ├<────┐

        │   └────┘  ║ └┴──┴┴A─ └────┘     │

        │   ┌────┐  ║       └───────────┐ │

        │   │CS  ╞<═╝                   │ │

        │┌──┤ a  ├<───────────────────┐ │ │

    ОА  ││  └────┘                    │ │ │

    ----││----------------------------│-│-│--

    УА  ││РА┌────┐     ┌┬──┬┐  ┌─────┐│ │ │┐

        │└─>┤  CS│     ││RG││  │ CS  ├┘ │ ││

        └──>┤    ╞════>╡│  │╞═>╡     ├──┘ ││Y

         РВ │    │     ││  ││  │     ├────┘│

          ╔>╡  p │     ││  ││  │  y  ╞═╗   ┘

          ║ └────┘     └┴──┴┘  └─────┘ ║

          ╚════════════════════════════╝

Отметим, что РА(t)=f(Y(t))   зависит без сдвига  от  сигналов

                             управления,

             PB(t+1)=F(Y(t)) зависит со сдвигом  от  сигналов

                             управления,

где РА и РВ - предикатные перемнные.

     Продолжительность такта работы схемы определяется наибо-

лее длинными цепями между регистрами. Для данной схемы, кото-

рую будем называть  последовательной  схемой  взаимодействия,

зададимся (так чаще  всего  бывает),  что  такой  критической

цепью является цепь  (CSy,CSa,CSp,RG).  Поэтому  длительность

такта определяется:

     Т > ty + ta + tp + trg,

где tj- время установления соответствующего компонента цепи.

     Чтобы сократить длину этой цепи, применяют другой  вари-

ант взаимодействия автоматов - конвейерный:

                                - 15 -

                 ╔══════════════════════════╗

                 ║┌────┐    ┌┬──┬┐   ┌────┐ ║

                 ╚╡ CS │    ││RG││   │CS  ╞<╝

                  │    ╞<═╦═╡│  │╞<══╡    │

      ┌───────────┤  b │  ║ ││  ││   │ c  ├<────┐

      │    FF     └────┘  ║ └┴──┴┴A─ └────┘     │

      │  ┌┬──┬┐   ┌────┐  ║       └───────────┐ │

      │┌─┤│RG│╞<══╡ CS ╞<═╝                   │ │

      ││ ││  ││   │  a ├<───────────────────┐ │ │

      ││ └┴──┴┴A─ └────┘                    │ │ │

   ОА ││       └──────────────────────────┐ │ │ │

   ---││----------------------------------│-│-│-│--

   УА ││                              MK  │ │ │ │

      ││  PA ┌────┬────┐            ┌┬──┬┐│ │ │ │┐

      │└────>┤  CS│ CS │            ││RG│├┘ │ │ ││

      │   РВ │    │    │            ││  │├──┘ │ ││Y

      └─────>┤    │    ╞═══════════>╡│  │├────┘ ││

             │    │    │            ││  │├──────┘│

           ╔>╡  p │  y │            ││  │╞═╗     ┘

           ║ └────┴────┘            └┴──┴┘ ║

           ╚═══════════════════════════════╝

     При этом варианте взаимодействия такой длинной цепи, как

в предыдущем случае, не возникает.Эта цепь  разделена  регис-

трами RG'FF' (регистр флажков) и RG'MK' (регистр  микрокоман-

ды) на две цепи. Продолжительность такта становится меньше  и

ее можно определить следующим образом:

     T > max( ta,(tp + ty) )+ trg ,

     При конвейерном варианте взаимодействия

     PA(t+1)=f(Y(t)), т.е. и эти значения стали  зависить  со

сдвигом от сигналов управления. Тогда фрагмент микропрограммы

     mS{...;pA=f(...)}

       << GO(pA;mi,mj)>>,

выполняемый в последовательной схеме за  один  такт,  в  кон-

вейерном варианте за один такт выполнен быть не может и  дол-

жен быть модифицирован следующим образом:

     mS{...,pA=f(...)}

     mS'{нет операции}

        << GO(pA;mi,mj)>>

Таким образом, время выполнения этого фрагмента не только  не

уменьшилось, но даже возросло несмотря на уменьшение  продол-

жительности каждого из тактов. Зато во всех остальных  случа-

ях (при безусловных переходах, при переходах по значению  РВ)

время выполнения микропрограммы уменьшается.

           _НАЧАЛЬНАЯ ИНИЦИАЛИЗАЦИЯ СИНХРОННОЙ СХЕМЫ

     Пусть устройство, кроме сигнала синхронизации SYN, имеет

еще один сигнал Н, обозначающий начало и конец синхронной ра-

боты устройства. При Н=0 - нерабочее состояние - можно выпол-

нять начальную установку значений памяти устройства.  Измене-

ние значения Н с 0 на 1 происходит в случайный момент времени

(асинхронно), но при этом начальный  такт  работы  устройства

должен быть полным. "Затягивание" асинхронного  сигнала  Н  в

синхронный режим происходит с помощью простейшего синхронного

автомата с диаграммой:

                ┌──────────┐        ┌────────┐

                V  0H/CONST│        V  1H/SYN│

              █▀▀▀█────────┘      █▀▀▀█──────┘

             >▌ 0 ▐──────────────>▌ 1 ▐──────┐

              █▄▄▄█ 1H/CONST      █▄▄▄█ 0H/X │

                л                            │

                └────────────────────────────┘

У этого автомата простейшей является функция  переходов,  так

как  диаграмма  автомата  совпадает  с  диаграммой  переходов

                                - 16 -

D-триггера.

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

выглядит следующим образом (для синхронизации по фронтам):

 а)-по переднему фронту,            б)- по заднему фронту:

                 ┌──┐                               ┌──┐

SYN ──┬──────────┤ 1├── CC         SYN ──┬──────────┤ &├── CC

      │ ┌─┬─┐  ┌─┤  │                    │ ┌─┬─┐  ┌─┤  │

      └─/C│T│  │ └──┘                    └─\C│T│  │ └──┘

        │ │ ├  │                           │ │ ├──┘

      ┌─┤D│ │  │                         ┌─┤D│ │

      │ ├─┤ o──┘                         │ ├─┤ o─

      ├─oR│ │                            ├─oR│ │

   H  │ └─┴─┘уст. нач. зн.            H  │ └─┴─┘уст. нач. зн.

    ──┴───────────────────             ──┴───────────────────

Такая разница в цепях условной синхронизации, как уже  объяс-

нялось выше, определяется тем, что первый перепад сигнала  СС

не должен быть рабочим.