Реферат

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 22.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. Реферат Анализ хозяйственной деятельности ОАО Маклаковский ЛДК
2. Реферат на тему Вклад императора Хубилая в развитие китайских искусств ремесел и военного дела
3. Курсовая на тему Г Шмоллер Г Шенберг Л Брентано К Брюхер представители исторической 2
4. Реферат на тему Управление стратегическими возможностями организации
5. Контрольная работа на тему Предпринимательство в современной России
6. Реферат Джон Лок як філософ і політик
7. Реферат Известный менеджер Бакунин Михаил Александрович
8. Книга Правила технической эксплуатации электроустановок
9. Реферат Особенности и уникальность рынка недвижимости
10. Реферат Particularidades morfo-sint cticas del lenguaje de f tbol