Способы кодирования микроопераций и схемы формирования управляющих сигналов

Отношение совместимости  симметрично,рефлексивно и нетранзитивно.Его удобно задавать с помощью матрицы совместимости S.Матрица S представляет собой квадратную булеву матрицу порядка n (с числом строки столбцов,равным количеству различных микроопераций n),симметричную относительно главной диагонали в силу свойства симметричности отношения совместимости:

S= стр 65

Элементы sij матрицы S принимают  значения 0 или 1,причем

sij= стр65 Главная диагональ  матрицы S при таком определении  ее элементов содержит нули  в силу свойства рефлек-

сивности отношения совместимости. В рассматриваемой постановке решение задачи оптимального кодирования микроопераций включает

следующие этапы:

- построение матрицы S совместимых микроопераций по  заданным множествам микроопераций  и микрокоманд;

- построение всех максимальных  подмножеств совместимых МО для  заданного отношения совместимости;

- выбор из построенных  подмножеств набора подмножеств,удовлетворяющих условиям (2) и (3) приведенной выше постановки задачи (условие (1) обеспечивается на втором этапе построением подмножеств совместимых МО).

Следует отметить,что первый этап не является обязательным,так  как в принципе задание множеств Y и W обеспечивает конструктивное задание и отношения совместимости S.Однако для формализованного решения рассматриваемой задачи кодирования (в особенности при использовании средств автоматизации проектирования) построение марицы S целесообразно.

На первом этапе матрица  совместимости строится следующим  образом.Заданное множество микрокоманд W представляется в матричной форме

- матрицей W микрокоманд.  Строки этой матрицы соответствуют  микрокомандам,а столбцы - микрооперациям.Тогда матрица W является булевой матрицей размера Nxn,а ее элементы wij определяются следующим образом :

0,если МО yj не входит  в микрокоманду wi; wij= 1 в противном случае.

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

S.Поскольку элемент sij принимает единичное значение  только в том случае,если микрооперации несовместимы,т.е. встречаются вместе в одной микрокоманде,то sij обратится в единицу только тогда, когда хотя бы в одной из строк Wk=wk1,wk2,...wkn матрицы W элементы wki и wkj будет равен нулю.Следовательно,можно записать соотношение sij=стр67

Пользуясь этим соотношением,элементы sij матрицы S,начиная с элемента s12, определяются поочередным просмотром всех строк матрицы W для каждой пары микроопераций.При этом благодаря  симметричности матрицы S относительно главной диагонали можно определить только элементы,лежащие правее этой диагонали,т.е.для которых j>i,а затем заполнить левую часть матрицы,учитывая,что sij=sji.

Проиллюстрируем выполнение этого этапа на примере.Пусть  заданы множества Y=y1,y2,...,y10 из 10 микроопераций и W=w1,w2,...w8 из восьми микрокоманд,в операционной части которых заданы следующие микрооперации:

w1=y1,y2,y6;  w4=y3,y4;  w7=y5,y9,y10;          w2=y1,y3,y9;

w5=y4,y5,y9; w8=y6,y7. w3=y2,y8,y10; w6=y5;

Соответствующая матрица S будет  выглядеть следующим образом:

W=стр 67

Тогда,используя выведенное для sij соотношение,определим,что s12=1,так  как уже в первой строке матрицы W элементы w11 и w12 равны единице и,следовательно,в  первой микрокоманде w1 МО y1 и y2 встречаются вместе,а значит,они несовместимы. Аналогично и s13=1,так как во второй строке матрицы W w21=1,т.е. во вторую микрокоманду входят микрооперации y1 и y3.

Следующий элемент s14 матрицы S будет равен нулю,так как ни в одной из строк матрицы W не содержится единицы одновременно в первом и  четвертом столбцах.

Определив каждый из элементов,можно  записать и соответствующий ему симметричный относительно главной диагонали элемент.Поэтому s21=1,s31=1 и S41=0.

Окончательно матрица S для  данного случая будет выглядеть  так:

S= стр.68

Второй этап решения задачи оптимального кодирования,в ходе которого осуществляется построения максимальных подмножеств совместимых МО,выполняется с использованием специальных алгоритмов.Как правило,эти алгоритмы предполагают перебор различных вариантов объединения совместимых МО подмножества.Один из таких алгоритмов рассматривается в [9].

Менее громоздким является алгоритм последовательного построения максимальных подмножеств на базе каждой МО.Алгоритм выполняется за n шагов,в которых последовательно для каждой из микроопераций yi,i=1,n,строится множество Yi=Yi1,Yi2,...YiR всех максимальных подмножеств Yir совместимых микроопераций, включающих МО yi.

На i-м шаге алгоритма анализируется i-я строка Si матрицы S и строится множество Yc=yc1,yc2,...ycm микроопераций,совместимых  с МО yi.В это множество войдут все те МО,для которых соответствующие  элементы Sij матрицы S равны нулю (исключая саму МО yi).

Если множество Yc пусто,то МО yi несовместима ни с какой из микроопераций,а  единственное максимальное подмножество,в  которое она входит,состоит только из одной этой микрооперации yi.

Если множество Yc содержит только один элемент yc1,то микрооперации yi и yc1 образуют единое максимальное подмножество совместимых МО,включающие МО yi.

Если множество Yc содержит более одного элемента,то на основании анализа соответствующих строк матрицы совместимости S,для каждой МО ycj множества Yc строится список (подмножество) Uj=yj1,yj2,...yjq микроопераций множества Yc,несовместимых с МО ycj.

Тогда каждый элемент Yir множества Yi будет включать микрооперацию yi; микрооперации ycj множества Yc,для которых множества Uj пусты (т.е.те,для которых нет несовместимых микроопераций среди МО, совместимых с yi); группу микроопераций множества Yc,совместимых между собой,подмножества Uj для которых не пусты,соответствующую j-му терму функции,получаемой после упрощения выражения

стр 69

каждая скобка которого описывает  условие того,что в строящееся подмножество совместимых микроопераций не входят либо микрооперация ycj,либо несовметимые с ней микрооперации подмножества Uj.

После раскрытия скобок и  упрощения последнего выражения  каждый терм tr будет иметь вид и определять одно из подмножеств Y'ir совместимых между собой микроопераций множества Yc,которые совместимы и с МО yi.Причем для получения подмножества Y'ir необходимо удалить (вычесть) из множества Yc элементы,входящие в терм tr,т.е. Тогда,присоединив к каждому такому подмножеству Y'ir,r=1,R микрооперацию yi (те микрооперации yj множества Yc,для которых подмножества Uj пусты,уже вошли в подмножество Y'ir),получим все максимальные подмножества Yir совместимых МО,содержащих МО yi,т.е.подмножества,являющиеся элементами искомого множества Yi.

После выполнения n шагов  алгоритма будут получены n множеств Yi,i=1,n.Тогда окончательно множество Y= всех максимальных подмножеств Yg совместимых микроопераций заданного множества микроопераций Y для заданной матрицы совместимости S будут объединением множеств Yi,т.е.Y=.

Проиллюстрируем один шаг  описанного алгоритма на примере  построения множества всех всех максимальных подмножеств совместимых микроопераций,содержащих МО y1,для матрицы совместимости S,приведенной на с.68.

Множество  Yc  микроопераций,совместимых          с          МО          y1,есть

Yc=y4,y5,y7,y8,y10,что определяются  по первой строке S1 матрицы S,в  которой элементы s14=s15=s17=s18=s110=0.

Анализируя строки S4,S5,S7,S8,S10 матрицы S,находим для каждой из микроопераций ycj множества Yc подмножества Uj несовместимых МО из числа МО,входящих в множество Yc:

yc1=yc4, U1=y5; yc2=y5, U2=y4,y10; yc3=y7, U3=0;

yc4=y8,U4=y10; yc5=y10,U5=y5,y8.

Тогда в любое максимальное подмножество совместимых МО,содержащее y1,войдут микрооперации y1 и y7 (так как соответствующее y7 подмножество U3 пусто) и группа микроопераций,определяемых одним из термов,получаемым после упрощения выражения

стр70

В результате несложных преобразований получим

стр 70

Правая часть этого  выражения содержит три терма T1= которые определяют три подмножества:

Y'11=Yc\y5,y8=y4,y7,y10;

Y'12=Yc\y5,y10=y4,y7,y8; Y'13=Yc\y4,y10=y5,y7,y8. Присоединив к  полученным

подмножествам          микрооперацию          y1,получим          множество

У1=Y11,Y12,Y13 всех максимальных подмножеств совместимых микроопераций,включающих МО y1,где

Y11=y1,y4,y7,y10, Y12=y1,y4,y7,y8, Y13=y1,y5,y7,y8.

Выполнив аналогичные  шаги алгоритма для остальных  микроопераций и объединив множества Уi,i=1,10,получим множество У= стр71

Осуществляемая на третьем  этапе процедура выбора совокупности подмножеств совместимых МО,обеспечивающих минимальное суммарное количество разрядов,необходимое для кодирования входящих в них МО,эквивалентна задаче о поиске покрытия минимальной цены и может быть выполнена с помощью метода Петрика или алгоритма извлечения Рота [10].Покрытию в данном случае подлежат все микрооперации множества Y,а элементами покрытия являются построенные на втором этапе максимальные подмножества совместимых микроопераций.Цена покрытия является суммой цен элементов покрытия,а цена элемента покрытия (подмножества совместимых МО) равна числу разрядов,необходимых для кодирования всех составляющих его МО и пустой микрооперации.

Можно показать,что из-за необходимости добавления пустой МО к каждому из подмножеств (см.с.65) в покрытии следует использовать только те максимальные подмножества Ygm,мощность которых #2k (k-целое),и те немаксимальные подмножества,мощность которых равна 2k-1 [13].Немаксимальные подмножества легко получить,исключая по одной или более МО из максимальных подмножеств.

В этом методе второй и третий этапы задачи кодирования совмещаются и находится такая совокупность Уa=Y1,Y2,...,YL подмножеств совместимых микроопераций,которая отвечает первым двум условиям постановки задачи (с.64),т.е. где Y - заданное множество микроопераций.

Метод прямого включения  не обеспечивает минимума разрядности  операционной части МК,хотя получаемое при его помощи решение оказывается достаточно близким к минимальному.

Процесс распределения микроопераций  множества Y = y[1], y[2],...,y[n] по подмножествам Y[1], Y[2],... осуществляется за n шагов. На начальном (первом) шаге вводится подмножество Y[1], состоящее только из МО y[1]. На i-м шаге для микрооперации y[i] отыскивается подмножество Y[j], в которое можно включить эту микрооперацию.

Такое включение возможно, если МО y[i] совместима со всеми МО, вошедшими  в Y[j] после выполнения предшествующих шагов. Если среди подмножеств Y[1], Y[2],..., Y[k], образованных в предшествующих i-1 шагах, нет ни одного такого подмножества, то вводится новое подмножество Y[k+1] и в него включается MO y[i].

Процесс распределения микроопераций  удобно описывать матрицей включения R = |r[j,i]|, строка R[j] которой соответствует  подмножеству Y[j] совместимых МО, а  i-й  столбец  -  микрооперации  y[i].  Элемент r[j,i] матрицы R равен единице, если МО  y[i]  входит  в  подмножество Y[j], и нулю в противном случае. Тогда условие  включения  микрооперации y[i] в подмножество Y[j] можно записать в виде k=n

\/ r[j,k]*s[i,k] = 0, k=1 где s[i,k] - элемент  заданной матрицы совместимости S. Иначе говоря, мик-

рооперация y[i] включается в  строку R[j] матрицы R, если эта строка  и

строка и строка S[i] матрицы S не содержат единиц в одноименных  столбцах (что является условием совместимости МО y[i] со всеми МО, входящими в строку R[j]). Для иллюстрации прямого включения рассмотрим распределение микроопераций множества Y = y[1],y[2],...,y[10], отноше-

ние совместимости между  которыми задано матрицей совместимости S, приведенной на стр.68. Ш а г 1. Матрица R будет состоять из одной строки, соответствующей подмножеству Y[1]=y[1]:

R(1) = |1 0 0 0 0 0 0 0 0 0 0 |.

Ш а г 2. Поскольку r[1,1]*s[2,1]=1 (т.е. МО y[1] и y[2] несовместимы), назначается новое подмножество Y[2]=y[2], а матрица R будет выглядеть следующим образом:

|1 0 0 0 0 0 0 0 0 0 0 |

R(2) = |    |

|0 1 0 0 0 0 0 0 0 0 0 |.

Ш а г 3. Так как r[1,1]*s[3,1]=1, а k=10 \/ r[2,k]*s[3,k] = 0 k=1 (т.е. МО y[3] несовместима с МО y[1], но сов-

местима с МО y[2]), то МО y[3] включается в подмножество Y[2], и матрица R приобретает вид:

|1 0 0 0 0 0 0 0 0 0|

R(3) = |  |

|0 1 1 0 0 0 0 0 0 0|.

Ш а г 4. Так как k=10 \/ r[1,k]*s[4,k] = 0, k=1 то МО y[4] включается в подмножество Y[1]:

|1 0 0 1 0 0 0 0 0 0|

R(4) = |  |

|0 1 1 0 0 0 0 0 0 0|.

Выполнив последующие  шаги 5...10, окончательно получим:

|1 0 0 1 0 0 1 1 0 0|

|0 1 1 0 1 0 0 0 0 0|

R(10) = |0 0 0 0 0 1 0 0 1 0|

|0 0 0 0 0 0 0 0 0 1|,

чему соответствуют подмножества Y[1] = y[1],y[4],y[7],y[8];  Y[2]  =

y[2],y[3],y[5]; Y[3] = y[6],y[9]; Y[4] = y[10].  Тогда

для кодирования операционной части МК (с учетом пустых микроопераций) потребуется 3+2+2+1=8 двоичных разрядов. Коды микроопераций могут быть выбраны произвольно, например, сле-

дующим образом: Поле Y[1]: y[1] - 001, y[4] - 010, y[7] - 011, y[8] - 100, 000 - пустая микрооперация; поле Y[2]: y[2] - 01, y[3] - 10, y[5] - 11, 00 - пустая МО; поле Y[3]: y[6] - 01, y[9] - 10, 00 - пустая МО; поле Y[4]: y[10] - 1, 0 - пустая МО. При таком  кодировании операционная часть, например, микрокоманды w[2]=y[1],y[3],y[9] имеет вид 00110100. Полученное решение является близким к минимальному, так как  для рассматриваемого примера одно из минимальных покрытий, полученных при выполнении третьего этапа кодирования методом Петрика, будет включать подмножества Y[1]=y[1],y[7],y[10],Y[2]=y[2],y[3],y[5] Y[3]=y[4],y[6],y[8], Y[4]=y[9], что потребует для кодирования операционной части 7 разрядов. В заключение следует указать, что матрица совместимости S не обязательно формируется по заданному множеству микрокоманд W, а может составляться исходя из функционального назначения микроопераций и особенностей структуры процессора. Например, совместимыми могут быть МО, управляющие выполнением различных действий в одном функциональном узле операционного устройства: сумматоре, сдвигателе, шине данных и т.д. Так, если в сумматоре реализуются микрооперации арифметического суммирования, вычитания, суммирования мо модулю 2, логического сложения, то все эти МО можно считать совместимыми, поскольку невозможно выполнение в одной микрокоманде двух или более из названных МО. В таких случаях операционная часть МК обычно разбивается на функциональные поля, в каждом из которых закодированы МО, управляющие каким-либо отдельным функциональным узлом процессора. Если матрица S составлена на основе заданного множества микрокоманд, то при внесении изменений в микропрограмму могут появиться такие операторы, которые придется реализовывать за несколько тактов. Это вызвано тем, что соответствующую им микрокоманду нельзя будет записать при принятом кодировании микроопераций из-за того, что в ней должны будут присутствовать две или более МО, относящиеся к одному подмножеству. Если матрица S составлена на основе функциональных особенностей МО, то такая ситуация исключается.