Минимизация разрядности микрокоманды

Пусть записанная в ПМП микропрограмма содержит т микрокоманд У, Y_m. На множестве {у₁,..., у_п} всех микроопераций, чьи СУ входят в эти МК, задается отношение несовместимости w_c , такое что:

Таким образом, несовместимыми являются микрооперации, СУ которых не встречаются вместе ни в одной микрокоманде микропрограммы. Класс несовместимости (КН) С, с У— множество МО, все элементы которого попарно несовместимы. Максимальный класс несовместимости (МКН) — это такой класс, в который нельзя добавить ни одной микрооперации без нарушения отношения несовместимости w_c.

Задача минимизации разрядности микрокоманды формулируется в [3] сле­дующим образом: найти множество классов несовместимости C_;|,..., С,- } та­кое, что

где С-, — количество микроопераций в классе несовместимости, а выражение int(log₂(w + 1)) определяет минимальную разрядность поля ПМП, необходимую для кодирования п микроопераций и признака их отсутствия в конкретной МК. Параметр называют ценой класса С,.

Решение ищется на множестве МКН. Для заданного в табл. 6.3 примера микро­программы получается следующий набор МКН:

C₁= y₁, y _7, y₁₁, C₂= y₂, y _7, y₁₁, C₃= y₃, y _7, y₁₀ ,C₄= y₄, y _7, y₁₀ , C₅= y₄, y ₉ ,

C₆= y₅, y _7, y_10, y₁₁, C₇= y₅, y ₈, C₈= y₅, y _9, y₁₁ , C₉= y₆, y _7, y_10, y₁₁ , C₁₀= y₆, y _9, y₁₁

. Таблица 6.3. Набор микрокоманд

Микрокоманда	СУ микроопераций
Y1	y1, y2, y3, y4,y5,y6
Y2	y3, y7,y8,y9
Y3	y1, y2, y8, y9,y10
Y4	y4,y8,y11
Y5	y6, y8

По набору МКН строится таблица покрытий, в столбце у_п которой записываются все МКН, в которые входит СУ микрооперации у. В табл. 6.4 имеются СУ коопераций у₁ у₂, у₃, у₈, входящих только в один МКН. Такие микрооперации называют различающими микрооперациями, а соответствующие им МКН — существенными МКН.

Таблица 6.4. Таблица покрытий

У1	У2	У3	У4	У5	У6	У7	У8	У9	У10	У11
С1	С2	С3	С4	С6	С9	С1	С7	С5	С3	С1
			С5	С7	С10	С2		С8	С4	С2
				С8		С4		С10	С6	С3
						С6			С9	С6
						С9				С8
										С9
										С10

Решением  задачи является множество МКН, включающее в себя все микро­операции у_п, чьи СУ принадлежат Y. Поскольку допустимо несколько решений, то ищется минимальное, дающее наименьшую разрядность ПМК.

Объем вычислений можно сократить путем применения эвристических пра­вил. Так, существенные МКН (или их подклассы) С_1, С_2,, С₃,, С₇ (см. табл. 6.4) дол­жны входить в любое решение р. Далее, если множество МКН в столбце y_i являет­ся подмножеством множества МКН в столбце у_р то столбец у_j; можно удалить из таблицы покрытий, так как микрооперация у_j,- в любом случае покрывается мень­шим числом МКН из столбца у_j, (говорят, что столбец y_i, доминирует над столбцом у_j). Так, в табл. 6.4 столбец у₁, доминирует над столбцами у₇, и у₁₁, столбец у₃ - над столбцом у₁₀ столбец г/₈ — над столбцом у₅; следовательно, столбцы у₅, у₇, у_№ у_и можно удалить из таблицы покрытий.

Таблица 6.5. Сокращенная таблица покрытий

У4	У6	У9
С4	С9	с5
С5	С10	С8
		С10

После применения этих правил получается сокращенная таблица покрытии (табл. 6.5), по которой покрытия могут быть найдены, например, методом Петри­ка: А' = (С₄ v С₅)(С₉ v С₁₀)(С₅ v C₈ v С₁₀) и после приведения подобных членов и выполнения поглощений типа AvАВ имеем: А' = С₄С₁₀ v C₅C₉ v C₅C₁₀ v C₄C₈ v С₉. Выражению А' соответствуют покрытия {C₄, C_i0}, {C₄, C_8,, C₉}, {C₅, C₉} и {C₅, C₁₀}.

Добавив к этим покрытиям существенные МКН, получим начальное множество решений:

Решение (3_; может быть избыточным, то есть некоторые микрооперации могут покрываться несколькими МКН . Для нахождения требуемого минимального решения необходимо для каждого избыточного решения :

- определить множество неизбыточных решений и их цену;

- выбрать в качестве окончательного решения неизбыточное решение с минимальной ценой.

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