Определение формата микрокоманды

На разрядность полей микрокоманды влияют следующие параметры:

• количество различных микроопераций, формируемых УА, в конечном итоге определяет (с учетом выбранного способа кодирования) длину поля микроопераций;
• количество различных логических условий определяет длину поля х;
• количество вершин ГСА связано с общим числом микрокоманд, а следо­вательно, с объемом памяти микропрограмм и разрядностью поля адреса микрокоманды.

Множество микроопераций Y, используемых в заданной ГСА Y={y_l, y₂, …..., y₁₃} мощность множества |Y| = 13. При горизонтальном ко­дировании поле микроопераций будет занимать 13 разрядов. Верти­кальный способ кодирования микроопераций к заданной ГСА неприме­ним, поскольку ГСА содержит вершины с двумя и тремя микроопера­циями. Попробуем реализовать разбиение множества Y на подмножества несовместимых микроопераций. Воспользуемся методом прямого включения, учитывая, что отношение совместимости задано на самой ГСА. Строго гово­ря, следовало бы построить матрицу совместимости микроопераций, но в рассматриваемом примере небольшой размер алгоритма позволяет опреде­лять отношение совместимости непосредственно по ГСА.

На сколько подмножеств следует разбивать исходное множество? По мень­шей мере, на s = 3 в нашем случае. Образуем три подмножества — Y₁, Y₂, Y_З и разместим в них микрооперации операторной вершины, имеющей s микроопераций. Если в ГСА таких вершин несколько— выберем любую из них.

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₃={ y₇, y₈, y₁₃}.

Теперь нераспределенными остались микрооперации (некоторые) " двой­ных" и " одинарных" вершин. Вершина (у₂, у₆)— обе микрооперации несовместимы с уже распределенными, поэтому могут располагаться произвольно, лишь бы они находились в разных подмножествах:

Y₁ ={y₁, y₁₁, y₂}, Y₂={y₄, y₅, y_12, y₆}, Y₃={ y₇, y₈, y₁₃}.

Вершина (у₂, y₉) – y₉ нельзя помещать в Y₁, поскольку совместимая с ней y₂ Y₁. Подмножества лучше заполнять равномерно, поэтому раз­местим у₉ в Y₃:

Y₁ ={y₁, y₁₁, y₂}, Y₂={y₄, y₅, y_12, y₆}, Y₃={ y₇, y₈, y₁₃, y₉}.

Остались две нераспределенные микрооперации - у₃ и у₁₀, первая из кото­рых совместима с у₅, поэтому ее нельзя помещать в Y₂ а вторая несовмес­тима ни с какими другими и может размещаться произвольно. Поместим их в множество, имеющее пока наименьшую мощность — Y₁:

Y₁ ={y₁, y₁₁, y₂, y₃, y₁₀}, Y₂={y₄, y₅, y_12, y₆}, Y₃={ y₇, y₈, y₁₃, y₉}.

Все 13 микроопераций распределились по трем подмножествам, при этом выполняются условия (4.8) (т. е. имеет место разбиение исходного множеств; Y), однако УА обычно должен вырабатывать еще одну микрооперацию, свидетельствующую об окончании выполнения алгоритма и предназначенную для использования не в ОА, а в управляющем автомате верхнего уровня иерархии. Назовем эту микрооперацию y_k и включим в произвольное множество (например, в Y₂), поскольку она, естественно, несовместима ни с од­ной микрооперацией. Итак, имеем следующее распределение:

Y₁ ={y₁, y₁₁, y₂, y₃, y₁₀}, Y₂={y₄, y₅, y_12, y_6, y_k}, Y₃={ y₇, y₈, y₁₃, y₉}.

Для кодирования элементов каждого из трех подмножеств потребуется по три двоичных разряда. Может показаться, что для Y₃ хватит и двух, ведь

|Y₃| = 4 = 2², однако следует учесть, что в каждом подмножестве необходимо предусмотреть один код для случая отсутствия микрооперации из этого под­множества в микрокоманде. Оптимальным разбиением исходного множества будет такое, когда |Y_i| = 2r -1, где r — натуральное число.

В подмножестве Y₃ всего одна " лишняя" микрооперация, а среди кодов Y₁ и Y₂ есть свободные. Попробуем перенести одну из микроопераций из Y₃ в другое подмножество, сохраняя, естественно, требование к попарной несовместимости всех микроопераций одного подмножества. Очевидно, первые три элемента подмножества Y₃ нельзя перенести в другое, т. к. они являются микроопера­циями из " тройных" вершин. Зато микрооперация у₉ совместима только с y₂ Y₁, поэтому у₉ можно перенести в Y₂ Окончательно получим, предвари­тельно упорядочив элементы подмножеств в порядке возрастания индексов:

Y₁ ={y₁, y₂, y₃, y₁₀, y₁₁}, Y₂={y₄, y₅, y_6, y_9, y_12, y_k}, Y₃={ y₇, y₈, y₁₃}.

Теперь мы можем определить размеры полей микрокоманды. Поле микро­операций будет состоять из трех подполей — Y₁, Y₂, Y_З (назовем их по име­нам соответствующих подмножеств), размером в 3, 3 и 2 двоичных разрядов соответственно.

Поле номера условия х должно содержать номер одного из двух логических условий — x₁, х₂ (один разряд?), однако для повышения гибкости процесса микропрограммирования удобно иметь возможность выбирать еще и тожде­ственно истинное и тождественно ложное условия. Итак, поле х занимает два разряда.

Наконец, поле адреса определяется объемом памяти микропрограмм. Если в нашем примере мы будем считать, что разрабатываем УА только для реализации микропрограммы рис. 4.14, а она содержит 8 вершин, не считая на­чальной, конечной и условных, количество микрокоманд (каждая микро­команда — ячейка памяти, имеющая свой адрес), выдаваемых УА, будет ни­как не менее 8, а реально — (1, 2,..., 1, 3) х 8, то для поля адреса в микрокоманде следует отвести 4 разряда (2⁴ = 16 > 1, 3 х 8»11).

В поле адреса будет располагаться адрес памяти — двоичный номер ячейки, а в полях Y_i и х — коды микроопераций и логических условий. Окончатель­но формат микрокоманды будет иметь вид, приведенный на рис. 4.15.