База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

курсовые,контрольные,дипломы,рефераты

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

 2Антик М.И.                                 11_03_91  МИРЭА

      _АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА

     Алгоритмы этого типа являются следующим этапом обобщения

описаний вычислительных процессов. Теперь, по сравнению с ал-

горитмами автоматного типа, на каждом шаге, помимо  модифика-

ции памяти, идентифицирующей шаг алгоритма, разрешается изме-

нять любую другую память устройства локально (по частям)  или

глобально (всю сразу).

     Устройство-исполнитель алгоритма этого типа будем  назы-

вать операционным устройством (ОУ).

     ОУ можно рассматривать как один  синхронный  автомат  со

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

используется для идентификации шага алгоритма, остальная  па-

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

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

алгоритма. Такая модель вычислителя особенно удобна для  рас-

чета продолжительности одного такта работы устройства.

     Другой удобной  моделью  вычислителя  является  совокуп-

ность взаимодействующих синхронных автоматов, один из которых

называется управляющим автоматом (УА), а объединение всех ос-

тальных автоматов называется операционным автоматом (ОА).

     УА является исполнителем алгоритма автоматного типа, ко-

торый входит составной частью в любой  алгоритм  процедурного

типа. Кроме того, УА инициирует действия отдельных шагов  ал-

горитма и участвует в их выполнении.

     ОА выполняет все вычисления на отдельных шагах алгоритма

под управлением УА; кроме того, к ОА удобно отнести  все  вы-

числения предикатных функций, оставив УА только анализ вычис-

ленных предикатных значений.

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

дующиe примеры алгоритмов процедурного типа.

     Например, каноническое  описание  синхронного  конечного

автомата может быть интерпретировано (истолковано) как  одно-

шаговый алгоритм процедурного типа.

                              █

                    ┌──────┐  │

                    │   ┌──V──V─────┐

                    │   │ B=FO(S,A) │

                    │   │           │

                    │   │ S:=FS(S,A)│

                    │   └─────┬─────┘

                    └─────────┘

     Исполнитель этого алгоритма состоит  только  из  ОА.  На

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

поэтому управление памятью не требуется, идентифицировать ша-

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

     Например, инкрементор с одноразрядным входом и  однораз-

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

ний:

                              █

                          █ p:=1 █

                              █

                   ┌────────┐ │

                   │  ┌─────V─V───────┐

                   │  │ (p:, b) = a+p │

                   │  └───────┬───────┘

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


                                - 2 -

ОА, реализующий инкрементор в целом, будет следующим:

                         ┌──┬─┐

     a ──────────────────┤HS│S├────_b

                  ┌─┬─┐p │  │ │

начальное значен.─┤S│T├──┤  │P├──┐

                  ├─┤ │  └──┴─┘  │

     SYN ─────────/C│ │          │

                 ┌┤D│ │          │

                 │└─┴─┘          │

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

Конечно, эта реализация совпадает с реализацией алгоритма ав-

томатного типа, если состояние р1 кодируется 1,  а  состояние

р0 - 0.

     Этот пример показывает,что до  начала  вычислений  может

потребоваться начальная установка памяти. На самом  деле  это

необходимо было уже в алгоритмах автоматного  типа,  так  как

код начального  состояния  требует  предварительной  установ-

ки. Ограничимся здесь обозначением этой проблемы,  а  решение

ее, связанное прежде всего с  корректной  синхронизацией  ус-

тройства в первом такте его работы, рассмотрим ниже.

     При рассмотрении процедуры построения автомата Мура  эк-

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

ность ее реализации и на структурном уровне. Например, только

что рассмотренный автомат Мили может быть преобразован  в эк-

вивалентный автомат Мура по одному из следующих вариантов:

     ┌┬─┬┐t┌──┬─┐                            ┌──┬─┐  ┌┬─┬┐

a ──_┤│T│├_┤HS│S├─_b                 a ─────_┤HS│S├─_┤│T│├─_b

   ─/┴┴─┴┘ │  │ │                            │  │ │─/┴┴─┴┘

    C      │  │ │                     C      │  │ │ C

   ─/┬┬─┬┐p│  │ │                    ─/┬┬─┬┐p│  │ │

   ┌_┤│T│├_┤  │P├┐                   ┌_┤│T│├_┤  │P├┐

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

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

     При таких структурных преобразованиях  проще  истолковы-

вать алгоритмы как процедурные.

               █                                 █

        █ p:=1; t:=0 █                       █ p:=1 █

               █                                 █

    ┌────────┐ │                      ┌────────┐ │

    │  ┌─────V─V───────┐              │  ┌─────V─V───────┐

    │  │t:=a;(p:,b)=t+p│              │  │ (p , b):= a+p │

    │  └───────┬───────┘              │  └───────┬───────┘

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

     БЛОК-ТЕКСТ. Способ описания автоматного алгоритма  после

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

алгоритмов в процедурной форме:

     Блок-текст состоит из трех частей:

 1)- Описание переменных и начальных значений памяти.

 2)- Описания функций и связей. Записываются любые функции  и

функциональные связи (в том числе предикатные), не  использу-

ющие запоминания. Переменные из левой части операции  присва-

ивания таких функциональных описаний  используются  в  блоках

процедуры.

 3)- Процедура, состоящая из блоков (микроблоков) операторных

и блоков переходов:

- операторные - в скобках вида  {.....},

- перехода    - в скобках вида  <<...>>;

и те, и другие блоки могут снабжаться метками, стоящими перед

блоком. В блоках перехода используется  оператор  GO  в одной

из двух форм:

        GO m                 - безусловный переход,

        GO (P; m0,m1,m2,...) - условный переход.

здесь m0,m1,... - метки блоков,

      P - предикатное значение,интерпретируемое оператором GO


                                - 3 -

как неотрицательное целое число, являющееся порядковым  номе-

ром метки в списке меток оператора GO. С  этой  метки  должно

быть продолжено выполнение алгоритма. Блоки условных  перехо-

дов эквивалентны предикатным вершинам блок-схемы алгоритма.

     На следующем более сложном примере демонстрируется  пос-

ледовательность синтеза операционного устройства.

     Пример. Вычислитель наибольшего  общего  делителя  (НОД)

двух натуральных чисел (8-разрядных).

     1) Разработаем интерфейс вычислителя:

                 8  ┌──┬─────┬──┐

              ═══╪═>╡I1│ НОД │  │

                    │  │     │  │  8

                 8  │  │     │D ╞══╪══>

              ═══╪═>╡I2│     │  │

                    ├──┤     ├──┤

              ─────>┤rI│     │rO├─────>

                    ├──┤     │  │

              ─────>┤ C│     │  │

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

 I1[7..0], I2[7..0] -входные информационные шины.

 rI -входной сигнал готовности: если rI=1, то на  входах  I1,

I2 готовы операнды.

 D[7..0] -выходная информационная шина .

 rO -выходной сигнал готовности: если rO=1, то готов  резуль-

тат на шине D, который сохраняется до появления новых операн-

дов.

     2) Математическое обоснование алгоритма вычислений:

     Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа-

ется в том, что НОД двух натуральных чисел А и В в случае ра-

венства этих чисел совпадает с любым из них, а  в  случае  их

неравенства совпадает с НОД двух  других  чисел:  меньшего  и

разности между большим и меньшим.  Последовательно,  уменьшая

числа, получим два равных числа -значение одного из них и бу-

дет НОД исходных чисел.

     3) Блок-схема алгоритма (микропрограмма в содержательном

виде):


                                - 4 -

                              █

                              │

                       ┌──────V──────┐

                     m1│  rO: = 0    │

                       └──────┬──────┘

                              │┌──────────────────┐

                              ││┌─────┐           │

                             ─VVV─    │           │

                             / \ 0    │           │

                            < rI>─────┘           │

                             \_/                  │

                              │1                  │

                       ┌──────V──────┐            │

                       │  rO: = 0    │            │

                       │             │            │

                     m2│   А: = I1   │            │

                       │             │            │

                       │   B: = I2   │            │

                       └──────┬──────┘            │

         ┌───────────────────┐│                   │

         │             ┌─────VV──────┐            │

         │           m3│ (p,S)=A - B │            │

         │             └──────┬──────┘            │

         │                   ─V─         m6       │

         │                   /  \ =0  ┌──────────┐│

         │                z <S==0>───>┤ rO:=1;D=A├┘

         │                   \__/     └──────────┘

         │                    │╪0

         │                    V

         │                 0 / \ 1

         │          ┌───────< p >────────┐

         │  ┌───────V──────┐ \_/ ┌───────V──────┐

         │m4│  (x,B:)=-A+B │   m5│ (x,A:)=A - B │

         │  └───────┬──────┘     └───────┬──────┘

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

     Или в виде блок-текста:

I1[7..0], I2[7..0] --входные шины

D[7..0]            --выходная шина

rI, rO             --сигналы готовности

A[7..0]:, B[7..0]: --память текущих значений

S[7..0]            --разность

z, p               --предикатные переменные

z=┐(!/S) --сжатие(свертка) S[7..0] по ИЛИ-НЕ

         --можно записать иначе z=(S==0)

D=A

-------------------------------------------------------------------

     m1{rO:=0}

     g1<<GO(rI;g1,m2)>>

     m2{rO:=0; A:=I1; B:=I2}

     m3{(p,S)=A-B}

       <<GO(z;g2,m6)>>

     g2<<GO(p;m4,m5)>>

     m4{(x,B:)=-A+B}

       <<GO m3>>

     m5{(x,A:)= A-B}

       <<GO m3>>

     m6{rO:=1}

       <<GO g1>>


                                - 5 -

4) Разработка функциональной схемы операционного автомата.

     В ОА должны быть реализованы все переменные с памятью  и

без,а также вычислительные операции,используемые в алгоритме.

                      A     ╔══════════════════════════════>D

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

                   C││RG││  ║    │   f1=(A-B) │

                    ││  ││  ║   A│            │

         I1═════>══>╡│  │╞══╝  ═>╡   f2=(-A+B)│      ┌─┐

                    ││  ││       │            │S    S│1│

                    ││  ││       │            ╞>   ═>┤ o───>z

                    ┴┴──┴┘       │            │      │ │

                      B          │            │      └─┘

                  ─/┬┬──┬┐       │            │

                   C││RG││       │            ├────────────>p

                    ││  ││B     B│            │

          I2═════>═>╡│  │╞>    ═>╡            │    ─/┬┬─┬┐

                    ││  ││       │            │     C││ │├>rO

                    ││  ││       │            │      ││ ││

            rI─────>┴┴──┴┘       └────────────┘      └┴─┴┘

     Кроме того, в ОА необходимо реализовать все информацион-

ные связи, соответствующие микрооперации коммутации, а  также

микрооперации запоминания (загрузки, записи) и обнуления.

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

    ║                 A     ╔══════════════════════║═══════>D

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

    ║  │ MUX│      C││RG││  ║   │M2*8│ 1─>┤cr  SM│ ║

    ╠═>┤0   │       ││  ││  ║   │    │    ├─     │ ║

I1══║═>┤1   ╞══════>╡│  │╞══╩══>╡    ╞═══>╡I1    │ ║ ┌─┐

    ║  ├    │       ││  ││  A   │    │    │      │ ║ │1│

    ║  │А   │      W││  ││      ├─   │    │     S╞═╩>╡ o───>z

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

    ║   │          │             │        │      │   └─┘

    ║  umA         uA           uiA       │      │

    ║                  B                  │      │

    ║  ┌────┐     ─/┬┬──┬┐      ┌────┐    │      │

    ║  │ MUX│      C││RG││      │M2*8│    │     p├─────────>p

    ╚═>╡0   │       ││  ││ B    │    │    │      │

I2════>╡1   ╞══════>╡│  │╞═════>╡    ╞═══>╡I2    │  C

       ├    │       ││  ││      │    │    │      │ ─/┬┬─┬┐

       │А   │      W││  ││      ├─   │    │      │1─>┤│T│├>rO

       └A───┘     ─A┴┴──┴┘      └A───┘    └──────┘R W││ ││

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

      uMB          uB           uiB             urO uwO

     5) Формулировка требований к управляющему автомату.

     При формировании управляющих сигналов  следует  обратить

внимание не только на операции, которые необходимо  выполнить

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

на этом шаге, это - как правило, операции изменения памяти.

     Будем считать, что операция активна, если  значение  уп-

равляющего сигнала равно 1.


                                - 6 -

Для управления вычислениями  на  каждом  шаге  алгоритма

потребуются следующие управляющие сигналы:

             ║umA│umB│uwA│uwB│uiA│uiB│urO│uwO│

           ══╬═══╪═══╪═══╪═══╪═══╪═══╪═══╪═══╡

           m1║   │   │   │   │   │   │ 1 │ 0 │

           ──╫───┼───┼───┼───┼───┼───┼───┼───┤

           m2║ 1 │ 1 │ 1 │ 1 │   │   │ 1 │ 0 │

           ──╫───┼───┼───┼───┼───┼───┼───┼───┤

           m3║   │   │ 0 │ 0 │ 0 │ 1 │   │ 0 │

           ──╫───┼───┼───┼───┼───┼───┼───┼───┤

           m4║   │ 0 │ 0 │ 1 │ 1 │ 0 │   │ 0 │

           ──╫───┼───┼───┼───┼───┼───┼───┼───┤

           m5║ 0 │   │ 1 │ 0 │ 0 │ 1 │   │ 0 │

           ──╫───┼───┼───┼───┼───┼───┼───┼───┤

           m6║   │   │ 0 │   │   │   │ 0 │ 1 │

           ──╨───┴───┴───┴───┴───┴───┴───┴───┘

     В незаполненных клетках  сигналы  безразличны.

     Заметив, что umA = umB , uiB = ┐uiA , окончательно полу-

чаем:

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

    ║                 A     ╔══════════════════════║═══════>D

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

    ║  │ MUX│      C││RG││  ║   │M2*8│ 1─>┤cr  SM│ ║

    ╠═>╡0   │       ││  ││  ║   │    │    ├─     │ ║

I1══║═>╡1   ╞══════>╡│  │╞══╩══>╡    ╞═══>╡I1    │ ║ ┌─┐

    ║  ├    │       ││  ││      │    │    │      │ ║ │1│

    ║  │А   │      W││  ││      ├─   │    │     S╞═╩>╡ o───>z

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

    ║   └────┐   ┌─┘  B     ┌────┘        ├─     │   └─┘

    ║  ┌────┐│   │─/┬┬──┬┐  │   ┌────┐    │      │

    ║  │ MUX││   │ C││RG││  │   │M2*8│    │     p├─────────>p

    ╚═>╡0   ││   │  ││  ││  │   │    │    │      │

I2════>╡1   ╞│═══│═>┤│  │╞══│══>┤    ╞═══>╡I2    │

       ├    ││   │  ││  ││  │   │    │    │      │

       │А   ││   │ W││  ││  │   ├─   │    │      │   C

       └A───┘│   │─A┴┴──┴┘  │   └A───┘    └──────┘  ─/┬┬─┬┐

        │    │   │ └─┐      │ ┌─┐│                 1─>┤│T│├>rO

        │    │   │   │      ├>┤ o┘                 R W││ ││

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

       umB      uwA  uwB   uiA                   urO uwO

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

       y1       y2   y3    y4                     y5 y6

                      ║y1│y2│y3│y4│y5│y6│

                    ══╬══╪══╪══╪══╪══╪══╡

                    m1║  │  │  │  │ 1│ 0│

                    ──╫──┼──┼──┼──┼──┼──┤

                    m2║ 1│ 1│ 1│  │ 1│ 0│

                    ──╫──┼──┼──┼──┼──┼──┤

                    m3║  │ 0│ 0│ 0│  │ 0│

                    ──╫──┼──┼──┼──┼──┼──┤

                    m4║ 0│ 0│ 1│ 1│  │ 0│

                    ──╫──┼──┼──┼──┼──┼──┤

                    m5║ 0│ 1│ 0│ 0│  │ 0│

                    ──╫──┼──┼──┼──┼──┼──┤

                    m6║  │ 0│  │  │ 0│ 1│

                    ──╨──┴──┴──┴──┴──┴──┘


                                - 7 -

Структура вычислителя:

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

                  ══>╡I1                              │

                     │                                │

                  ══>╡I2         ОА                  D╞══>

                     │                                │

                  ┌──/C                             rO├──>

                  │  │                                │

                  │  │z  p umB uwA uwB uiA urO uwO    │

                  │  └┬──┬──A───A───A───A───A───A─────┘

                  │   │  │  │   │   │   │   │   │

                  │   │  │  │   │   │   │   │   │

                  │  ┌V──V──┴───┴───┴───┴───┴───┴─────┐

                  │  │z  p  y1  y2  y3  y4  y5  y6    │

                  │  │                                │

                  ┴──/C                               │

                     │           УА                   │

                  ──>┤rI                              │

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

     УА должен выполнять следующий алгоритм автоматного типа,

представленный в виде блок-текста:

     m1{xxxx10}

     g1<<GO(rI;g1,m2)>>

     m2{111x10}

     m3{x000x0}

       <<GO(z;g2,m6)>>

     g2<<GO(p;m4,m5>>

     m4{0011x0}

       <<GO m3>>

     m5{0100x0}

       <<GO m3>>

     m6{x0xx01}

       <<GO g1>>

              _МИКРОПРОГРАММИРОВАНИЕ. ОПРЕДЕЛЕНИЯ.

     МИКРООПЕРАЦИЯ - базисное (элементарное) действие,  необ-

ходимое для получения (вычисления) значения одной  или  более

переменных.

     Микрооперация присваивания В=А означает, что  переменные

левой части получают  значения  выражения  из  правой  части.

Всегда разрядность левой части равна разрядности правой  час-

ти. При этом биты, расположенные на одной и той же позиции  в

левой и правой частях, равны.

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

чения в правой части микрооперации присваивания  обозначаются

(х). Например:

     (В[7],x,B[6..0]) = (A[7..0],x)

означает арифметический сдвиг влево на один разряд  8-разряд-

ного числа с присваиванием  произвольного  значения  младшему

разряду и с потерей старшего после знака разряда.  А,  напри-

мер, микрооперация

     (B[7..0],d) = (A[7],A[7..0])

означает арифметический сдвиг вправо на один разряд.

Микрооперация

     (p,S[3..0]) = A[3..0] + B[3..0] + q

описывает действие, выполняемое стандартным 4-разрядным  сум-

матором, если ( А,В,q ) являются его непосредственными входа-

ми, а ( р,S ) - выходами.

     Микрооперация ( : ) - двоеточие -  означает  запоминание

(изменение значения) в памяти устройства. Переменная типа па-

мять сохраняет свое значение между двумя  очередными  присва-

иваниями.


                                - 8 -

     Микрооперации всегда входят в состав микрооператоров.

     МИКРООПЕРАТОР - набор взаимосвязанных микроопераций (или

одна микрооперация ), выполняемых одновременно и  необходимых

для получения одного или более  значений. Например:

     ( e,D:) = R1 + R2 + c

Фрагмент аппаратуры, реализующей этот микрооператор,  мог  бы

быть, например, таким:

          ┌───┐

   c      │MUX│

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

││T │├───>┤0  │    ┌────┐      │MUX│       D

└┴──┴┘ ──>┤1  │    │  SM│      │   │    ┌┬──┬┐

       ──>┤А  ├───>┤cr  │  ═══>╡0  ╞═══>╡│RG│╞══>

          ├───┤    │   S╞═════>╡1  │    └┴──┴┘

  R1      │MUX│    │    │  ═══>╡А  │

┌┬──┬┐    │   │    │    │      └───┘

││RG│╞═══>╡0  ╞═══>╡I1  │      ┌───┐

└┴──┴┘ ══>╡1  │    │    │      │MUX│

       ══>╡А  │    │    │      │   ├────────────>e

          ├───┤    │   p├─────>┤0  │

  R2      │MUX╞═══>╡I2  │  ───>┤1  │

┌┬──┬┐    │   │    └────┘  ───>┤А  │

││RG│╞═══>╡0  │                └───┘

└┴──┴┘ ══>╡1  │

       ══>╡А  │

          └───┘

Имена всех переменных, используемых  в  этом  микрооператоре,

означают выполнение микроопераций коммутации ( транспортиров-

ки ). Значения переменных  коммутируются на входы суммматора,

а результат суммирования - в места расположения переменных.

     МИКРОБЛОК - набор микрооператоров, выполняемых  одновре-

менно ( в одном такте ) и синхронно. В одном микроблоке любо-

му из битов присваивается только одно значение.

     Синхронность означает, что во всех микрооператорах одно-

го микроблока используется только "старое" значение памяти.

Например:

     { (p,A):= A + B

       (C,r):= A + D }

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

же  старое  значение А.

     В то же время в микроблоке:

     { (C,x):= A + D

       (x,A)= C + B }

в первом микрооператоре используется  новое значение А , а во

втором - старое значение С. Разумеется, эти два действия  вы-

полняются одновременнo на двух разных сумматорах.

     При реализации микроблока { A:= B ; B:= 0 }  обязательна

синхронная реализация В:=0 ( хотя обычно такое действие проще

реализовать асинхронно, но это приводит к  ошибке  ).  Другой

правильный вариант: можно выполнить  В:=0  асинхронно,  но  в

следющем такте.

     Всегда предполагается, что предикат  вычисляется  вместе

(в одном такте) с тем микроблоком, за которым непосредственно

следует его использование.Таким образом, здесь, также как и в

микроблоке, используется старое значение памяти, существовав-

шее перед входом в микроблок.  Это  связано  с  особенностями

взаимодействия ОА и УА. Например:


                                - 9 -

        █                                            █

   █ CT:=(╪0)█                                  █ CT:=(╪0)█

        █                                            █

        │                                            │

   ┌────V───┐                                   ┌────V───┐

 m1│ CT:=3  │                                 m1│ CT:=3  │

   └────┬───┘                                   └────┬───┘

┌──────>│                                    ┌──────>│

│      ─V─                                   │      ─V─

│     /   \ =0                               │     /   \ =0

│    <CT==0>─>                               │    <CT==0>─>

│     \___/                                  │     \___/

│       │╪0                                  │       │╪0

│  ┌────V───┐                                │  ┌────V───┐

│m2│........│                                │m2│........│

│  │        │                                │  │        │

│  │CT:=CT-1│                                │  │CT:=CT-1│

│  └────┬───┘                                │  └────┬───┘

└───────┘                                    │  ┌────V───┐

                                             │m3│........│

                                             │  └────┬───┘

                                             └───────┘

В первом случае цикл будет выполнен 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─              └┴──┴─┘    ├─   │     └────┘

│    <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  │ └─┴─┘уст. нач. зн.

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

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

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

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

2Антик М.И.                                 11_03_91  МИРЭА      _АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА      Алгоритмы этого типа являются следующим этапом обобщения описаний вычислительных процессов. Теперь, по сравнен

 

 

 

Внимание! Представленный Реферат находится в открытом доступе в сети Интернет, и уже неоднократно сдавался, возможно, даже в твоем учебном заведении.
Советуем не рисковать. Узнай, сколько стоит абсолютно уникальный Реферат по твоей теме:

Новости образования и науки

Заказать уникальную работу

Похожие работы:

АТС типа "Квант"
Дискретизация и квантование изображений
Методы размещения и трассировки печатных плат на примере модуля памяти
Расчет усилителя звуковой частоты
Микроэлектроника и функциональная электроника (разработка топологии ИМС)
Многопозиционная фазовая модуляция в системах спутниковой связи с МДЧ
Моделирование дискретной случайной величины и исследование ее параметров
Моделирование распределения потенциала в МДП-структуре
Задача обработки решеток
Моделирование систем радиосвязи и сетей радиовещания (для студентов специальности «РРТ»)

Свои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru