Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 8.11.2024



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

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

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

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



1. Реферат на тему Apollinaris Von Kostrowitsky Essay Research Paper Guillaume
2. Биография на тему Анакреонт
3. Реферат на тему No Man Is An Island Essay Research
4. Контрольная работа Про Державний Бюджет України на 2010 р
5. Реферат на тему Transnational Corporate System Of The 1990S Essay
6. Реферат Девиантное материнство в современном родительстве
7. Реферат на тему Надання першої долікарської допомоги при нещасних випадках
8. Реферат на тему Robert Bly On Male Violence Essay Research
9. Реферат Управление маркетинговыми проектами
10. Реферат Республіка Перу