Методические указания к выполнению курсового проекта «Проектирование процессора эвм» по курсу «Организация эвм, комплексов и систем» для студентов дневного отделения специальности 2201 Ижевск 2001г (стр. 7 из 12)

	Y1	Y2	Y12	Y3	Y4	Y7	YK
Y0		x7
Y1	x2
Y2		x5
Y12	1
Y3		x5
Y4	x4
Y7	1

Таблица 4

	Y1	Y2	Y3	Y4	Y7	YK
Y0			x1x5
Y1	x2
Y2		X5
Y3		X5
Y4	x4
Y7	1

5.2. Построение объединенных подматриц

Задача объединения ГСА Г_1,…,Г_Q может быть разбита на несколько независимых подзадач меньшей размерности. Для этого исходные МСА М_q (q=1,…,Q) разбиваются на подматрицы M_q¹ ,…, M_q^Tq таким образом , что для любых двух подматриц M_q^P и M_q^S (p,s

{1,…,T_q}) пересечение множеств исходящих и входящих операторов пусто: A_q^P A_q^S= , B_q^P B_q^S= (где {A} –исходящие, а {B} – входящие операторы). Метод разбиения для МСА М₁ иллюстрируется рис. 15. Подматрицы, полученные в результате разбиения МСА М₁, М₂, М₃, приведены на рис.18.

На множестве всех полученных таким образом подматриц (см. рис.18) введём отношение объединимости, согласно которому две подматрицы

M_q^S и M_r^f объединимы (M_q^S M_r^f), если и только если пересечение множеств их исходящих или входящих операторов не пусто:

(( A_q^S A_r^f ) ( B_q^S B_r^f ))=1,

где A_q^S (B_q^S) и A_r^f (B_r^f) - множества исходящих ( входящих ) операторов подматриц M_q^S и M_r^f соответственно . Очевидно, что это отношение рефлексивно , симметрично, но не транзитивно. Построим граф этого отношения. Каждой подматрице ставится в соответствие вершина графа. Две вершины M_q^S и M_r^f соединяются ребром, если M_q^S

M_r^f (рис.16). Тогда, очевидно, для нахождения множества всех объединимых подматриц необходимо найти все компоненты связности этого графа. Подматрицы, попавшие в одну компоненту , подлежат объединению. В графе на рис. 16 четыре подграфа( подграф может состоять и из одной изолированной вершины). Значит необходимо решать 4, но существенно более простые задачи объединения следующих подматриц:

;

;

;

;

Таким образом, множество объединимых подматриц

, , порождает одну объединённую подматрицу и т.д. Построение объединенных подматриц выполняется следующим образом.

1). Строки объединённой подматрицы обозначим операторами , входящими в объединение множеств исходящих операторов в подматрицах , порождающих объединенную подматрицу . Точно так же столбцы её обозначим операторами,

входящими в объединение множеств входящих операторов в порождающих подматрицах.

2).Элемент

_ij (т.е. стоящий на пересечении Y_i и Y_j ) объединенной подматрицы равен , где ( _ij)_q-элемент МСА М_q, стоящий на пересечении строки Y_i и столбца Y_j.

Объединенные подматрицы М₀¹_{, …,} М₀⁴ приведены на рис.19. Каждый оператор Y_i отмечает только один столбец и только одну строку во всем множестве объединенных подматриц, что вытекает из способа их построения.

5.3. Учет распределения сдвигов

Так как выбранные коды МСА являются кодами операций для каждой из реализуемых команд, ни один оператор внутри граф-схем не меняет значений переменных p₁,…,p_N (относительно этих переменных имеем пустое распределение сдвигов). В связи с этим полученные объединенные подматрицы можно упростить. Так переход к Y₂¹ в подматрице М₀¹ происходит всегда при р₁=р₂=1 ( в столбце Y₂¹ не встречаются другие определяющие коньюнкции , кроме р₁р₂). Поэтому в строке Y₂¹ (см. подматрицу М₀⁴) заменяем р₁р₂ на 1. Аналогичным образом просматриваются все столбцы в подматрицах М₀¹_{, …,} М₀⁴ и делаются соответствующие упрощения в строках. Удаляемые переменные

и обведены кружком.

5.4. Построение системы скобочных формул перехода

Тот факт, что от любого оператора ГСА или МСА Y_i(i=0,1,…,T) возможен переход к операторам из множества {Y₁,…Y_j,…,Y_T, Y_K} можно описать с помощью выражения