Файл: 1-337.pdf

Микропрограммный автомат с программируемой логикой

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

Пусть записанная в ПМП микропрограмма содержит

 т

 микрокоманд

 Y

1

...,

 На

множестве

 у

n

}

 всех микроопераций, чьи СУ входят в эти МК, задается отно-

шение несовместимости

 , такое что:

По набору

 строится таблица покрытий, в столбце

 у

n

 которой записыва-

ются все МКН, в которые входит СУ микрооперации

 у

n

 .

 В табл. 6.4 имеются СУ

микроопераций

 у

1

 у

3

 у

8

,

 входящих только в один МКН. Такие микрооперации

называют различающими микрооперациями,

 а соответствующие им МКН —

 суще-

ственными

Таким образом, несовместимыми являются микрооперации, СУ которых не

встречаются вместе ни в одной микрокоманде микропрограммы.

Класс несовместимости

— множество МО, все элементы которого

попарно несовместимы.

 Максимальный класс несовместимости

 (МКН) — это та-

кой класс, в который нельзя

 ни одной микрооперации без нарушения

отношения

Задача минимизации разрядности микрокоманды формулируется в [3] сле-

дующим образом: найти множество классов несовместимости

 } та-

кое,

где |С

i

| — количество микроопераций в классе несовместимости, а выражение

определяет минимальную разрядность поля ПМП, необходимую

для кодирования

 п

 микроопераций и признака их отсутствия в конкретной МК.

параметр

называют

 класса

 С

i

.

Решение ищется на множестве

 Для заданного в табл. 6.3 примера микро-

программы получается следующий набор МКН:

Решением

 задачи является множество МКН, включающее в себя все микро-

 у

n

 ,

 чьи СУ принадлежат

 Y.

 Поскольку допустимо несколько решений, то

ищется минимальное, дающее наименьшую разрядность ПМК.

Объем вычислений можно сократить путем применения эвристических пра-

вил. Так, существенные МКН (или их подклассы)

 (см. табл.

 6.4)

 дол-

жны входить в любое решение бета. Далее, если множество МКН в

 у

i

 являет-

ся подмножеством множества МКН в столбце

 у

j

 то столбец

 у

j

 можно удалить из

таблицы покрытий, так как микрооперация

 у

j

 в любом случае покрывается мень-

шим числом МКН из столбца

 у

i

 (говорят, что

 у

i

 доминирует

 над столбцом

у

j

 Так, в табл. 6.4 столбец

 у

1

 доминирует над столбцами  и

 у

11

,

 столбец  — над

столбцом

 столбец  — над столбцом

 следовательно, столбцы

можно удалить из таблицы покрытий.

Таблица

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

После применения этих правил получается сокращенная таблица покрытий

(табл. 6.5), по которой покрытия могут быть найдены, например, методом Петри-

 A'

 v

 ^

 v

 ^

 v

 v

 и после приведения подобных членов

и выполнения поглощений типа

 имеем: A

'

 =

 v

 v

 v

Выражению A

'

 соответствуют покрытия

 {С

4

,

 и

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

ство решений:

Решение бета j может быть избыточным, то есть некоторые микрооперации могут

покрываться несколькими МКН

 С

i

,

 принадлежащее бета j. Для нахождения требуемого минималь-

ного решения необходимо для каждого избыточного решения бета j.

3 2 2

 Глава 6. Устройства управления

Таблица 6.4.

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

Микропрограммный автомат с программируемой логикой  3 2 3

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

мальной ценой.

Для нахождения неизбыточных решений годится такая же процедура. Для каж-

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

Пути повышения быстродействия автоматов

микропрограммного управления

Цикл выполнения микрокоманды

 можно представить в виде трех этапов:

• формирования адреса очередной микрокоманды в ФАМ (A

i

);

• выборки по данному адресу микрокоманды из памяти микропрограмм (B

i

);

• исполнения микрокоманды в операционной (ОЧ) или адресной части (АЧ)

вычислительной машины

 (И

i

)

.

Порядок следования этапов определяется способом соединения формировате-

ля адреса следующей микрокоманды и памяти микропрограмм.

Структура МПА (рис. 6.22,

 а)

 с ФАМ и ПМП, связанными непосредственно

друг с другом, не допускает совмещения этапов во времени — здесь этап

 начи-

нается только после выполнения этапа

 И

i

(рис. 6.22,

 б).

 6.22. Построение МПА

 совмещения: а — структурная схема;

б

 — временная диаграмма обработки микрокоманд

В течение цикла

 все узлы заняты обработкой только одной, текущей мик-

рокоманды с номером

 i,

 причем последовательный характер обработки

 не по-

зволяет достичь высокого быстродействия:

Производительность ВМ повышается при одновременной конвейерной обра-

ботке в МПА нескольких микрокоманд, находящихся на различных этапах выпол-

3 2 4

 Глава 6. Устройства управления

нения.

 совмещения во времени этапов

 B

i

 и

 МПА вводятся дополни-

тельные

 элементы, которые хранят результаты обработки на каж-

дом этапе.

В МПА с одним уровнем совмещения

 один запоминающий эле-

мент — конвейерный регистр микрокоманды, подключенный к выходу памяти
микропрограмм (рис. 6.23,

 а).

 В данной структуре реализуется одновременная об-

работка двух микрокоманд: в то время как исполняется находящаяся в РМК i-я
микрокоманда (этап

 в

 вычисляется адрес

 (i +

 1)-й микрокоманды

(этап

 и затем по этому адресу из ПМП выбирается

 (i +

 1)-я микрокоман-

да (этап

 Следовательно, в МПА с одним уровнем совмещения обеспечи-

вается параллельное выполнение этапов

 и

 и этапа

 (рис. 6.23,

Рис.

 6.23. Построение МПА с одним уровнем совмещения: а — структурная схема;

б —

 временная диаграмма обработки микрокоманд

Очевидно, что при

 <  +

 в данной структуре наблюдается вынужденный

простой операционной (или адресной) части

 Этот недостаток устраняется

в МПА с двумя уровнями совмещения (рис. 6.24,

 а),

 в котором ФАМ и ПМП свя-

заны друг с другом двумя конвейерными регистрами — РМК и РАМ. Здесь одно-
временно обрабатываются три микрокоманды: в

 или адресной час-

ти исполняется

 (этап

 И

i

 )

 выбирается из памяти

 а в ФАМ

вычисляется адрес

 (этап

 Как видно из рис. 6.24,

 в такой структуре

совмещается во времени выполнение всех трех

 и

Методы

 обработки обеспечивают

 выигрыш только

при выполнении линейных участков микропрограммы. Если реализуемая  ФАМ
функция управления является условной, а значение условия вырабатывается на

текущем этапе в операционной (адресной) части,

 правильный

 следующей

микрокоманды может быть вычислен только по

 И

i

, ответственного

Контрольные вопросы  3 2 5

Рис. 6.24.

 Построение МПА с двумя уровнями совмещения: а — структурная схема;

б

 — временная диаграмма обработки микрокоманд

за выработку значения условия перехода. В итоге длительность цикла для МПА
с одним уровнем совмещения увеличивается до величины

а для МПА с двумя уровнями совмещения — до величины

Всего, в зависимости от использования регистров — регистра РМК, состоящего

из адресной и микрооперационной частей, регистра РАМ, регистра состояния РГС
(для хранения условия перехода), — можно сформировать

 различных структур

МПА. Эти структуры, их временные диаграммы и оценки эффективности приве-

дены в [32, с. 184-212]. Там же показано, что выбор оптимальной структуры опре-
деляется особенностями конкретной микропрограммы.

Контрольные вопросы

1. Охарактеризуйте основные функции устройства управления.

2. Какие аргументы и результат имеет функция ЦФ-ВК?
3. Какие аргументы и результат имеет функция ЦФ-ФАСК?

а для

 с двумя уровнями совмещения — до величины