Метод синтеза М-автоматов включает следующие этапы.

1. Формирование памяти автомата. Этот этап выполняется также как и для I-автомата. Пусть М(Г) означает М-автомат, синтезируемый по ГСА Г, тогда М(Г₃) имеет память, состоящую из 16-разрядных регистров RA,RB,RC,RD,RS₁ и RS₂.

2. Распределение регистров по шине. В структуре на рис. 4.14 для передачи информации из регистров к операционным элементам используются шины А₁ и А₂, которые являются выходами мультиплексоров М₁ и М₂, поэтому целесообразно разбить множество регистров на два непересекающихся подмножества. Если это невозможно из-за особенностей ГСА, то распределение регистров необходимо выполнить так, чтобы пересечение множеств А₁ÇА₂ было минимальным. Здесь А_i означает множество регистров, связанных с мультиплексором М_i (i=1,2).

Определяющим фактором при распределении регистров являются бинарные операции. Например, если S=A+B, то регистры RA и RB должны быть помещены в разные множества А₁ и А₂. Так, для автомата М(S₃) имеем А₁={A,C,S₁,S₂},A₂={A,B,C,D,S₂}, причём S₂ помещено в оба множества из-за необходимости выполнить микрооперацию L₁(S₂)=S₂+S₂, A,B,C помещены в множество А₂, чтобы операции выполнялись одним инвертором, связанным с шиной А₂.

В нашем случае шины А₁ и А₂ имеют разрядность n =16, совпадающую с разрядностью слов. Если в ОА имеются регистры, разрядность которых меньше разрядности шин, то необходимо осуществлять выравнивание информации, например, по правому краю.

3. Формирование таблицы операторов М-автомата. Как видно из рис. 4.14, для выполнения микроопераций y_n ÎY необходимо выработать сигналы a_i, b_j, c_k,j_g, называемые операторами. Для определения операторов необходимо построить таблицу со столбцами y_n, A₁, A₂, Z, RS, отражающую структуру М-автомата. Например, чтобы выполнить микрооперацию y₇ #C:=A+B, необходимо выполнить совокупность операторов A₁:=RA, A₂:=RB, Z:=A₁+A₂, RC:=Z, которые должны быть записаны в соответствующих столбцах таблицы. Естественно, что одинаковые операторы должны быть обозначены буквами с одинаковыми индексами. Результирующую таблицу назовём таблицей операторов. Таблица операторов М(Г₃) автомата (Табл. 4.2) содержит N=18 строк, что совпадает с числом микроопераций исходной функциональной ГСА Г₃.

4. Формирование логических условий. Как видно из структуры М-автомата, все логические условия формируются схемами, связанными с шиной Z. Поэтому формулы для логических условий функциональной ГСА должны быть преобразованы. Так, условие x₁ # A>0 преобразуется в условие x₁ # Z >0. Для формирования условия x₂ # S₁>S₂ необходимо, чтобы на шину Z были одновременно поданы регистры RS₁ и RS₂, что невозможно. Очевидно, что для хранения одного из слов будет необходим дополнительный регистр RZ, связанный с шиной Z. Если в RZ занести слово S₂,то условие x₂ будет вычисляться как x₂ # Z>RZ. Информация в регистр RZ должна заносится по оператору с₆.

5. Синтез функциональной схемы автомата. Схема М-автомата строится непосредственно по таблице операторов. Здесь столбец RS определяет память автомата и сигналы загрузки информации в память из шины Z. Столбцы А₁ и А₂ определяют мультиплексоры А₁ и А₂, а также сигналы передачи информации из памяти через мультиплексоры к комбинационной схеме. Столбец Z определяет операционные элементы и сигналы, передающую информацию от комбинационной схемы к мультиплексору Z. Схема формирования логических условий реализует условия x_l ÎX, изменённые с учётом структуры схемы ОА.

Функциональная схема автомата М(Г₃) приведена на рис. 4.23.

 

Таблица 4.2

Таблица операторов автомата М(Г₃)

yn	A1	A2	Z	RS	Комментарий
y1	-	-	Z:=< d1 > j1	RA:=Z c1	RA:=< d1 >
y2	-	-	Z:=< d2 > j2	RB:=Z c2	RB:=< d2 >
y3	-	-	Z:=< d3 > j3	RC:=Z c3	RC:=< d3 >
y4	-	-	Z:=< d4 > j4	RD:=Z c4	RD:=< d4 >
y5	-	A2:=RA b1		RS1:=Z c5
y6	-	A2:=RB b2		RS1:=Z c6
y7	A1:=RA a1	A2:=RB b2	Z:=A1+A2 j6	RC:=Z c3	C:=A+B
y8	A1:=RS1 a2	A2:=RD b3	Z:=A1+A2 j6	RS1:=Z c5	S1:=S1+D
y9	A1:=RS2 a3	A2:=RB b2		RS2:=Z c6
y10	-	A2:=RC b4		RC:=Z c3
y11	A1:=RS1 a2	-	Z:=R1(A1) j8	RS1:=Z c5	S1:=R1(S1)
y12	A1:=RS2 a3	A2:=RS2 b5	Z:=A1+A2 j6	RS2:=Z c6	S2:=L1(S2)
y13	A1:=RC a4	A2:=RD b3	Z:=A1+A2 j6	RD:=Z c4	D:=C+D
y14	A1:=RA a1	-	Z:=R1(A1) j8	RS1:=Z c5	S1:=R1(A)
y15	-	A2:=RC b4		RS2:=Z c6
y16	A1:=RS1 a2	A2:=RA b1	Z:=A1+A2 j6	RS1:=Z c5	S1:=S1+A
y17	A1:=RS2 a3	A2:=RD b3	Z:=A1+A2 j6	RS2:=Z c6	S2:=S2+D
y18	A1:=RC a1	A2:=RB b2	Z:=A1+A2 j6	RD:=Z c4	D:=C+B

 

6. Формирование преобразованной граф-схемы алгоритма. Очевидно, что управляющий автомат для М-автомата должен формировать операторы a_i, b_j, c_k, j_g вместо микроопераций y_n ÎY, содержащихся в функциональной ГСА. Кроме того, в М-автомате допускается выполнение только одной микрооперации за один такт работы. Для проверки значений логических условий также могут понадобиться дополнительные такты работы. Например, для формирования условия x₁ # A>0 необходимо переслать информацию из регистра RA на шину Z. Таким образом, для формирования преобразованной ГСА необходимо:

- представить каждую вершину функциональной ГСА как последовательность операторных вершин, каждая из которых содержит только одну микрооперацию;

- заменить микрооперации в каждой вершине соответствующим набором операторов М-автомата;

- ввести дополнительные операторные вершины для формирования логических условий.

 

 

 

Рис. 4.23. Функциональная схема М-автомата, реализующего граф-схему алгоритма Г₃

 

При „расщеплении” вершин исходной ГСА необходимо учитывать зависимость микроопераций по данным. Микрооперация y_n ÎY зависит по данным от микрооперации y_m ÎY, если результата выполнения микрооперации y _m является операндом для микрооперации y_n. Рассмотрим некоторые примеры (Рис. 4.24)

 

 

 

Рис. 4.24. Формирование преобразованной ГСА

 

 

Микрооперации y₃ и y₄ не зависят по данным (Рис. 4.24,а), поэтому в преобразованной ГСА они могут следовать в произвольном порядке, например < y₃, y₄ > (Рис. 4.24,б). Микрооперация y₅ зависит по данным от микрооперации y₃ (Рис. 4.24,в), поэтому вначале должна выполняться микрооперация y₅, в которой используется значение S₁, не изменённое микрооперацией y₃. Микрооперации y₆ и y₇ взаимосвязаны по данным (Рис. 4.24,д), поэтому любой порядок их выполнения - < y₆, y₇ > или < y₇, y₆ > - приведёт к ошибке. Для устранения этого конфликта необходимо ввести дополнительное слово D, то есть регистр, и дополнительную микрооперацию y₈ # D:=S₁ (Рис4.24,е). Тогда микрооперация y₇ преобразуется к виду y₉ # S₂:=D+C, что приводит к последовательности < y₈, y₆, y₉ >. Такое преобразование связано с увеличением времени выполнения алгоритма и введением дополнительного регистра.

Для формирования логических условий также может потребоваться введение дополнительных вершин. Например, для выполнения проверки x₁ # A>0 (Рис. 4.25,а) в преобразованную ГСА необходимо ввести дополнительную вершину для передачи содержимого регистра А на шину Z (Рис. 4.25,б).

Исходя из того, что к моменту проверки операнд должен находиться на шине Z, вершину (Рис. 4.25,в) необходимо преобразовать в последовательность < y₄, y₃ >, что приводит к результату (Рис. 4.25,г) с двумя операторными вершинами. Если же последовательность микроопераций будет иметь вид < y₃, y₄ >, то перед проверкой необходимо выполнить действие Z:=RS, что увеличивает время выполнения алгоритма. Отметим, что порядок выполнения микроопераций - < y₃, y₄ > или < y₄, y₃ > - не будет иметь значения, если в схеме иметься дополнительный регистр RZ, выходы которого связаны со схемой формирования логических условий (Рис. 4.26,а). В этом случае при выполнении микрооперации y₃ необходимо занести в регистр RZ содержимое шины Z, что приводит к двум вариантам преобразованной ГСА (Рис. 4.26,б - 4.26,в).

 

 

 

 

Рис. 4.25. Формирование логических условий

 

 

Рис. 4.26. Формирование логических условий с дополнительным регистром

 

Преобразуем с учётом этих замечаний функциональную ГСА Г₃. Для проверки x₁ # A>0 (Z>0) необходимо, чтобы микрооперация y₁ выполнялась непосредственно перед проверкой логического условия, то есть вершина b₁ представляется последовательностью < y₂, y₃, y₄, y₁ >. Для проверки x₂ # S₁>S₂ (Z>RZ) необходимо выполнить микрооперацию y₁₁ (вершина b₈) непосредственно перед этой проверкой. Следовательно, вершина b₈ преобразуется в последовательность < y₉, y₁₈, y₁₁ >. Как показывает анализ вершин b₂ - b₉ ГСА Г₃, в них отсутствует зависимость по данным, поэтому вершина b₂ =< y₅, y₆, y₇ > (то есть представляется в виде трёх операторных вершин, соответствующим микрооперациям в векторе b₂), b₃ =< y₈, y₉, y₁₀ >, b₄ =< y₁₁, y₁₂, y₁₃ >, b₅ =< y₈ >, b₆ =< y₁₄, y₁₅ >, b₇ =< y₁₆, y₁₇ >, b₉ =< y₁₂ >. Замена микроопераций y_nÎY совокупностью операторов из табл. 4.2 приводит к преобразованной ГСА Г₃(М) (Рис. 4.27) здесь символ „М” подчёркивает тот факт, что ГСА преобразована для выполнения алгоритма М-автоматом.

Определим характеристики автомата М(Г₃), используя методику, рассмотренную для I-автомата.

Производительность Е_м(Г₃)=1, так как каждая операционная вершина преобразованной ГСА содержит по одной микрооперации и ни одной дополнительной вершины не было введено.

Схема включает один сумматор, один инвертор, один сумматор по модулю 2, один многоразрядный инвертор и три мультиплексора. Следовательно, затраты оборудования О_м(Г₃)=1,6.

Длительность такта Т _м(Г₃) определим по формуле (4.2), где t_кс = = t_S +2 t_М + t_R =20 t +4 t +6 t =30 t.

Как и ранее существует три ветви алгоритма, однако в М-автомате они существенно длиннее, чем в I-автомате.

 

Рис. 4.27. Преобразованная граф-схема алгоритма Г₃(М)

 

Итак в ГСА Г₃(М) существуют ветви: a₁ =< b₁,…, b₄, b₅,…, b₁₄ >, a₂ =< b₁,…, b₄, b₁₅,…, b₂₂ >, a₃ =< b₁,…, b₄, b₁₅,…, b₂₁, b₁₄ >, n₁ =14, n₂ =12, n₃ =12. Исходя из (4.3), имеем:

 

Итак, автомат М(Г₃) имеет следующие характеристики:

- производительность Е_М(Г₃)=1;

- затраты оборудования О_м(Г₃)=1,6;

- длительность такта Т_М(Г₃)=30 t;

- время выполнения алгоритма Ф_М(Г₃)= 378 t +12,6 t_уа.

 

Отметим, что в М-автомате существует возможность использования однотактных триггеров в регистрах памяти. С этой целью в схему вводится регистр RZ, синхронизируемый сигналом Clock₁ (Рис. 4.28). Информация с выходов регистра RZ заносится в регистры памяти R₁,…,R_K по сигналу Clock₂. При этом все регистры строятся по однотактных триггерах. Если при обычной организации (Рис. 4.14) требуется 2 n K однотактных триггеров, то при использовании дополнительного регистра RZ требуется только n K+ n = n (K+1) триггеров. Такой подход даёт выигрыш в числе триггеров, определяемой как

Очевидно, что стоимость памяти пропорциональна числу триггеров. Поэтому использование дополнительного регистра позволяет уменьшить стоимость памяти М-автомата почти в два раза по сравнению с I-автоматом.

 

 

 

Рис. 4.28.Оптимизация памяти М-автомата

 

4.6. Синтез IM-автоматов с параллельной комбинационной схемой

 

Как уже отмечалось IM_p-автомат представляет собой композицию двух М-автоматов с общей памятью. Рассмотрим метод синтеза IM_p-автомата на примере ГСА Г₃ (Рис. 4.18), используя для него обозначение IM_p(Г₃).

1. Формирование памяти автомата. Анализ слов ГСА Г₃ показывает, что память IM_p(Г₃) - автомата содержит шесть 16-разрядных регистров.

2. Разбиение множества микроопераций на классы. В данном случае множество Y необходимо разбить на два класса - класс одноместных микроопераций Y¹ и класс двухместных микроопераций Y². Для ГСА Г₃ имеем: Y¹={ y₅, y₆, y₁₀, y₁₁, y₁₄, y₁₅, y₁, y₂ } и Y²={ y₇, y₈, y₉, y₁₂, y₁₃, y₁₆, y₁₇, y₁₈, y₃, y₄ }. Отметим, что микрооперация y₁₂ помещена в класс Y², так как она выполняется путём сложения S₂+S₂. Микрооперации занесения начальных значений y₁ - y₄ равномерно распределены на множества Y¹ и Y², что способствует ускорению алгоритма по сравнению с М-автоматом.

3. Распределение регистров по шинам. Для этой цели формируются множества А₁-А₃, соответствующие мультиплексорам М₁-М₃ схемы IM_p-автомата (Рис. 4.15). При распределении используются те же правила, что и для М-автомата.

Для автомата IM_p(Г₃) имеем A₁={A,C,S₁,S₂}, A₂={A,B,S₁,S₂}, A₃={A,B,C,S₁}.

4. Формирование таблицы операторов для одноместных микроопераций. Для решения этой задачи строится таблица со столбцами y_n, A₃, Z₂, RS, отражающая элементы М-автомата, выполняющего одноместные микрооперации. Для автомата IM_p(Г₃) эта таблица имеет восемь строк, что соответствует мощности множества Y¹ (Табл. 4.3).

5. Формирование таблицы операторов для двухместных микроопераций. Эта таблица имеет столбцы y_n, A₁, A₂, Z₁, RS и отражает элементы М-автомата, выполняющего двухместные микрооперации. Для автомата IM_p(Г₃) эта таблица имеет десять строк, что соответствует мощности множества Y² (Табл. 4.4).

Отметим, что суммарно табл. 4.3 и табл. 4.4 имеют 18 строк, что соответствует мощности множества Y=Y¹ÈY² и совпадает с длиной таблицы операторов автомата М(Г₃).

6. Формирование логических условий. Так как информация в регистр RA заносится через шину Z₂, то условие x₁ # A>0 вычисляется, как x₁ # Z>0. Так как содержимое регистров RS₁ и RS₂ может быть одновременно передано на шины Z₁ и Z₂, то условие x₂ # S₁>S₂ вычисляется, как x₂ # Z₁>Z₂, то есть в IM_p(Г₃)-автомате не требуется дополнительный регистр RZ, используемый автоматом M(Г₃).

 

Таблица 4.3

Таблица операторов для одноместных микроопераций

yn	A3	Z2	RS	Комментарий
y1	-	Z2:=<d1> y1	RA:=Z e1	RA:=< d1 >
y2	-	Z2:=<d2> y2	RB:=Z e2	RB:=< d2 >
y5	RA c1		RC:=Z e3
y6	A3:=RB c2		RS1:=Z e4
y10	A3:=RC c3		RC:=Z e5
y11	A3:=RS1 c4	Z2:=R1(A3) y4	RS1:=Z e3	S1:=R1(S1)
y14	A3:=RA c1	Z2:= R1(A3) y4	RS1:=Z e3	S1:=R1(A)
y15	A3:=RC c3	Z2:=<d1> y3	RS2:=Z e4

 

 

Таблица 4.4

Таблица операторов автомата М(Г₃)

yn	A1	A2	Z1	RS	Комментарий
y3	-	-	Z1:=<d3> j1	RC:=Z1 d1	RC:=< d3 >
y4	-	-	Z1:=<d4> j2	RD:=Z1 d2	RD:=< d4 >
y7	A1:=RA a1	A2:=RB b1	Z1:=A1+A2 j3	RC:=Z1 d1	C:=A+B
y8	A1:=RS1 a2	A2:=RD b2	Z1:=A1+A2 j3	RS1:=Z1 d3	S1:=S1+D
y9	A1:=RS2 a3	A2:=RB b1		RS2:=Z1 d4
y12	A1:=RS2 a3	A2:=RS2 b3	Z1:=A1+A2 j3	RS2:=Z1 d4	S2:= S2+ S2
y13	A1:=RC a4	A2:=RD b2	Z1:=A1+A2 j3	RD:=Z1 d2	D:=C+D
y16	A1:=RS1 a2	A2:=RA b4	Z1:=A1+A2 j3	RS1:=Z1 d3	S1:=S1+A
y17	A1:=RS2 a3	A2:=RD b2	Z1:=A1+A2 j3	RS2:=Z1 d4	S2:=S2+D
y18	A1:=RC a4	A2:=RB b1	Z1:=A1+A2 j3	RD:=Z1 d2	D:=C+B

 

 

7. Синтез функциональной схемы автомата. Этот этап выполняется так же, как для М-автомата. Вначале формируется память автомата, затем строится комбинационная схема. Столбец А₁ определяет связи между регистрами и мультиплексором А₁, столбец А₂-А₂, столбец RS задаёт связи между шиной Z₁ и регистрами памяти, столбец Z₁ задаёт операционные элементы для выполнения двухместных микроопераций. Столбец А₃ задаёт связи между памятью и мультиплексором А₃, столбец Z₂ задаёт операционные элементы для выполнения одноместных микроопераций, столбец RS задаёт связи между шиной Z₂ и памятью автомата.

Функциональная схема автомата IM_p(Г₃) представлена на рис. 4.29. Отметим, что как и для М-автомата, память IM_p-автомата может быть синтезирована на однотактных триггерах, однако в этом случае необходимо вводить два однотактных регистра RZ₁ и RZ₂, связанных с соответствующими шинами (Рис. 4.30).

8. Формирование преобразованной граф-схемы алгоритма. В каждом такте IM_p-автомат может выполнять пару микроопераций < y_n, y_m >, где y_n ÎY¹, y_m ÎY². Следовательно, в операторных вершинах преобразованной ГСА должно быть не более двух микроопераций, представленных соответствующими операторами. При преобразовании ГСА необходимо учитывать зависимость между микрооперациями по данным. Например, микрооперации y₁ #S₁:=A+B и нельзя выполнять одновременно, если в y₁ используется инверсное значение слова А.

Преобразованная граф-схема алгоритма Г₃(IM_p) приведена на рис. 4.31.

Отметим, что в ГСА Г₃(IM_p) введена дополнительная вершина для передачи содержимого регистров RS₁ на шину Z₁ и RS₂ - Z₂. Для осуществления передачи Z₂:=RS₂ введены дополнительные связи с₅, y₅, которые отсутствуют в таблице операторов. Для передачи Z₁:=RS₁ используется операция сложения Z₂:=RS₂+0. Вершина b₁₄ введена для возможности проверки условия x₂ # Z₁>Z₂.

Определим характеристики автомата IM_p(Г₃), используя формулы (4.1) - (4.3).

Производительность Е_р(Г₃) автомата IM_p(Г₃) определяется по формуле (4.1). Преобразованная ГСА Г₃(IM_p) содержит О(Г₃)=15 операторных вершин, содержащих суммарно N(Г₃)=22 микрооперации исходной ГСА Г₃. Отметим, что вершина b₁₄ не содержит микрооперации y_n ÎY. Итак, Е_р(Г₃)=22/15=1,47.

Схема автомата IM_p(Г₃) содержит по одному сумматору, сумматору по модулю два, инвертору и сдвигателю, а также пять мультиплексоров. Следовательно, затраты оборудования О_р(Г₃)=1,8.

Время такта Т_р(Г₃)= t_S +2 t_M + t_R =20 t +4 t +6 t =30 t.

 

 

Рис. 4.29. Функциональная схема автомата IM_p(Г₃)

 

 

Рис. 4.30. Оптимизация памяти IM_p-автомата

 

 

Рис. 4.31. Преобразованная граф-схема алгоритма Г₃(IM_p)

Как и ранее, ГСА Г₃(IM_p) содержит три ветви: a₁ =< b₁,…, b₈ >, a₂ =< b₁, b₂, b₉,…, b₁₄, b₈ >, a₃ =< b₁, b₂, b₉,…, b₁₅ >, n₁ =8, n₂ = n₃ =9. Исходя из (4.3), имеем

 

 

Итак, автомат М(Г₃) имеет следующие характеристики:

- производительность Е_М(Г₃)=1,47;

- затраты оборудования О_м(Г₃)=1,8;

- длительность такта Т_М(Г₃)=30 t;

- время выполнения алгоритма Ф_М(Г₃)= 260 t + 8,7 t_уа.

 

4.7. Синтез IM-автомата с последовательной комбинационной схемой

 

Комбинационная схема IM_s-автомата состоит из трёх схем Ф₁ - Ф₃, включённых последовательно (Рис. 4.16). Для эффективного использова-ния этих схем необходимо сформировать комбинированные микрооперации, соответствующие этой структуре. Рассмотрим метод синтеза IM_s-автомата на примере ГСА Г₃ (Рис. 4.18), используя для него обозначение IM_s(Г₃).

1. Формирование памяти автомата. Как и в предыдущих случаях, память IM_s(Г₃)-автомата состоит из регистров RA,RB,RC,RD,RS₁,RS₂.

2. Разбиение регистров по шинам. Для этой цели формируются множества А₁ и А₂, соответствующие мультиплексорам М₁ и М₂. Мультиплексор М₁ связан со схемой Ф₁, осуществляющей операцию инвертирования, поэтому регистру RA,RB и RC должны входить в множество А₁. Итак, для автомата IM_s(Г₃) имеем А₁={A,B,C,S₁,S₂}, А₂={A,B,D,S₂}.

3. Формирование комбинированных микроопераций. Структура IM_s-автомата соответствует последовательности микроопераций <инверсия, двухместная операция, сдвиг>. Комбинированные микрооперации соответствуют последовательностям < инверсия, двухместная операция сдвиг >,< инверсия, двухместная операция >,< инверсия, сдвиг >. В ГСА Г₃ можно выделить следующие последовательности: S₁=<y₅(b₂), y₈(b₃), y₁₁(b₄)>, S₂=<y₆(b₂), y₉(b₃), y₁₂(b₄)>, S₃=<y₁₀(b₃), y₁₃(b₄)>, S₄=<y₁₅(b₆), y₁₇(b₇)>, S₅=<y₁₆(b₇), y₁₁(b₈)>. Здесь y_n(b_i) обозначает микрооперацию y_n из вершины b_i. В последовательность S₂ введена микрооперация y₁₂, что требует введения в ОА операционного элемента - сдвигателя на один разряд влево. Такое введение оправдано тем, что назначение IM_s-автомата - уменьшение времени выполнения алгоритма.

Полученные последовательности порождают комбинированные микрооперации. Последовательности S₁ соответствует комбинированная микрооперация

Сформируем модифицированное множество микроопераций Y₀ IM_s-автомата, исключив из Y микрооперации, входящие только в последовательности S_j. Так, микрооперация y₅ входит в S₁ и не входит ни в один блок ГСА Г₃, кроме блока b₂. Поэтому микрооперация y₅ исключается из Y. Микрооперация y₈ входит в блок b₃ (последовательностью S₁) и в блок b₅, следовательно, микрооперацию y₈ исключить нельзя. Итак, для ГСА Г₃ имеем Y₀={ y₁,…, y₄, y₇, y₈, y₉, y₁₂, y₁₄, y₁₈, y₁₉,…, y₂₃ }.

4. Формирование таблицы операторов IM_s-автомата. Эта таблица отражает выполнение микроопераций y_n ÎY₀ операционным автоматом с заданной структурой (Рис. 4.16). Таблица имеет столбцы y_n, A₁, A₂, A₃, A₄, Z, RS (Табл. 4.5). Как видно из табл. 4.5, если микрооперация y_n не использует ресурсы схемы Ф_i (i=1,2,3), то схема Ф_i служит просто для передачи информации. Это соответствует прямой связи, например, между А₁ и А₃, управляемой оператором a₁. Чтобы не вводить такую связь в схему Ф₂, при выполнении операции А₄:=А₁ (микрооперация y₁₄) используется сумматор схемы Ф₂. Так как информация на шине А₂ отсутствует и А₃ºА₁ (по оператору a₁), то имеем b₁ # А₄:=А₂+А₃=0+А₃=А₁. Такое выполнение микрооперации не влияет на длительность такта автомата, так как этот параметр расчитывается, исходя из времени выполнения самой медленной микрооперации на каждом из уровней Ф₁-Ф₃.

5. Формирование логических условий. Этот этап выполняется аналогично его выполнению в М-автомате. Схема y связана с шиной Z, поэтому проверяемая информация должна быть передана на эту шину. Условие x₁ # A>0 вычисляется как x₁ # Z>0, а для проверки условия x₂ # S₁>S₂ необходимо ввести в схему регистр RZ, в который по оператору с₆ заносится новое значение слова S₂, вычисленное комбинационной схемой. Теперь условие x₂ вычисляется как x₂ # Z>RZ.

6. Синтез функциональной схемы автомата. Схема строится по таблице операторов, используя те же правила, что и для IM_p-автомата. Отметим, что схема IM_S(Г₃)-автомата (Рис. 4.32) содержит сдвигатель L₁, чего не было в M(Г₃)- и IM_р(Г₃)-автоматах, для уменьшения числа вершин.

 

 

Таблица 4.5

Таблица операторов автомата IM_S(Г₃)

yn	A1	A2	A3	A4	Z	RS
y1	-	-	-	-	Z:=< d1 > g1	RA:=Z c1
y2	-	-	-	-	Z:=< d2 > g2	RB:=Z c2
y3	-	-	-	-	Z:=< d3 > g3	RC:=Z c3
y4	-	-	-	-	Z:=< d4 > g4	RD:=Z c4
y7	A1:=RA a1	A2:=RB b1	A3:=A1 a1	A4:=A2+A3 b1	Z:=A4 g5	RC:=Z c3
y8	A1:=RS1 a2	A2:=RD b2	A3:=A1 a1	A4:=A2+A3 b1	Z:=A4 g5	RS1:=Z c5
y9	A1:=RS2 a3	A2:=RB b1	A3:=A1 a1	A4:=A2ÅA3 b1	Z:=A4 g5	RS2:=Z c6
y12	A1:=RS2 a3	A2:=RS2 b3	A3:=A1 a1	A4:=A2+A3 b1	Z:=A4 g5	RS2:=Z c6
y14	A1:=RA a1	-	A3:=A1 a1	A4:=A2+A3 b1	Z:=R1(A4) g6	RS1:=Z c5
y18	A1:=RC a4	A2:=RB b1	A3:=A1 a1	A4:=A2+A3 b1	Z:=A4 g5	RD:=Z c4
y19	A1:=RA a1	A2:=RD b2		A4:=A2+A3 b1	Z:=R1(A4) g6	RS1:=Z c5
y20	A1:=RB a5	A2:=RB b1		A4:=A2ÅA3 b1	Z:=L1(A4) g7	RSs:=Z c6
y21	A1:=RC a4	A2:=RD b2		A4:=A2+A3 b1	Z:=A4 g5	RD:=Z c4
y22	A1:=RC a4	A2:=RD b2		A4:=A2+A3 b1	Z:=A4 g5	RS2:=Z c6
Y23	A1:=RS1 a2	A2:=RS1 b4	A3:=A1 a1	A4:=A2+A3 b1	Z:=R1(A4) g6	RS1:=Z c5

 

7. Формирование преобразованной граф-схемы алгоритма.

Преобразованная ГСА IM_S(Г₃) содержит микрооперации y_n ÎY₀, выраженные через операторы IM_S-автомата. При формировании ГСА Г(IM_S) необходимо учитывать зависимость по данным между микрооперациями y_n ÎY₀. Для нашего примера ГСА Г₃(IM_S) представлена на рис. 4.33.

Определим характеристики автомата IM_S(Г₃), используя формулы (4.1) - (4.3).

Преобразованная ГСА Г₃(IM_S) содержит О(Г₃)=15 операторных вершин, в которых содержится N(Г₃)=22 микрооперации из исходной ГСА Г₃. Таким образом, производительность автомата IM_S(Г₃) Е_S(Г₃)=22/14=1,46.

 

 

Рис. 4.32. Функциональная схема IM_S(Г₃)-автомата

 

Схема автомата IM_S(Г₃) содержит один сумматор, один инвертор, один сумматор по модулю 2, сдвигатель вправо и сдвигатель влево, а также пять мультиплексоров. Следовательно, затраты оборудования О_S(Г₃)=1,9.

Время такта ОА в данном случае складывается из 4 t_M, t_I, t_S, t_Sh и t_R. Следовательно время такта Т_р(Г₃)=38 t.

Как и ранее, ГСА Г₃(IM_p) содержит три ветви: a₁ =< b₁,…, b₉ >, a₂ =< b₁,…, b₄, b₁₀,…, b₁₄, b₉ >, a₃ =< b₁,…, b₄, b₁₀,…, b₁₅ >, n₁ =9, n₂ = n₃ =10. Итак, суммарное число вершин в ветвях n(Г₃)=29, среднее число вершин в ветви n_S (Г₃)=9,7. По формуле (4.3) имеем время выполнения алгоритма

Итак, IМ(Г₃)-автомат имеет характеристики:

- производительность Е_М(Г₃)=1,46;

- затраты оборудования О_м(Г₃)=1,9;

- длительность такта Т_М(Г₃)=38 t;

- время выполнения алгоритма Ф_М(Г₃)= 328,6 t +9,7 t_уа.

Естественно, параметр Ф_S(Г

⇐ Предыдущая12

Поделиться:

Воспользуйтесь поиском по сайту: