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

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

□количество различных микроопераций, формируемых УА, в конечном итоге определяет (с учетом выбранного способа кодирования) длину поля микроопераций;

□ количество различных логических условий определяет длину поля x;

□ количество вершин ГСА связано с общим числом микрокоманд, а следовательно, с объемом памяти микропрограмм и разрядностью поля адреса микрокоманды.

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

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

Теперь разместим по множествам микрооперации следующей вершины, содержащей (в нашем случае) три микрооперации:

Заметим, что первая микрооперация второй рассматриваемой вершины совпадает с первой микрооперацией первой вершины. Она уже присутствует в множестве поэтому не включается вторично. Наконец, разместим микрооперации третьей "тройной" вершины:

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

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

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

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

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

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

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

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

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

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

Рис. 4.15. Формат микрокоманды