- •Глава 6
- •Устройства управления
- •Кодирование микрокоманд
- •Обеспечение последовательности выполнение микрокоманд
- •Адресация микрокоманд
- •Организация памяти микропрограмм
- •Запоминающие устройства микропрограмм
- •Минимизация количества слов памяти микропрограмм
- •Минимизация разрядности микрокоманды
- •Пути повышения быстродействия автоматов микропрограммного управления
- •Контрольные вопросы
Минимизация количества слов памяти микропрограмм
Общая задача оптимизации емкости памяти микропрограмм достаточно сложна и поэтому обычно решается в два этапа. На первом этапе минимизируется количество слов микропрограммы (количество микрокоманд), на втором этапе — разрядность микрокоманды.
Сначала рассмотрим один из возможных подходов, действующих при разбиении линейной микропрограммы на минимальное количество микрокоманд [3].
Обозначим через li — множество операндов микрооперации уi, Оi — множество результатов микрооперации yi. Сигналы управления (СУ) микроопераций yi и yj нельзя объединить в одну микрокоманду, если имеет место один из трех случаев пересечения по данным:
При этом говорят, что yi и yj - находятся в отношении wg зависимости по данным: . Графически отношение wg отображается графом зависимости по данным (ГЗД), вершины которого соответствуют микрооперациям. Дуга (yi, yj ) в ГЗД показывает, что микрооперации yi и yj находятся в отношении wg. Пример ГЗД приведен на рис. 6.21.
Рис. 6.21. Граф зависимости по данным
Если две микрооперации yi, yj используют один и тот же функциональный узел ВМ, то говорят, что они находятся в отношении структурной несовместимости wс, то есть yj wc у Сигналы управления двух микроопераций можно объедим в одну микрокоманду, если они структурно совместимы и не находятся в отношении зависимости по данным:
yi,, yj МК, если (уi, c, yj) (уi, c, yj)≠
Пусть между микрооперациями yv ..., уа рассматриваемого ГЗД существует следующая структурная несовместимость:
Минимальное количество микрокоманд в микропрограмме будет определяться длиной критического пути в графе ГЗД, то есть пути, длина которого максимальна.
На первом шаге алгоритма формируется начальное распределение (HP), состоящее из блоков Bv ..., Вм, где М— длина критического пути ГЗД. Каждый блок Bt является «заготовкой» микрокоманды Yi в него включаются СУ тех микроопераций которые могут выполняться не ранее, чем по микрокоманде Уi. Начальное распределение для нашего примера показано в табл. 6.1.
Таблица 6.1. Основные распределения микроопераций
Блок |
Распределение МО |
Блок |
ПКР |
||
HP |
ПР |
КР |
|||
B1 |
У1 У2 У7 |
У2 |
У2 |
B1 |
У2 |
В2 |
Уз, У8 |
У 1 Уз |
Уз |
В2 |
У3 |
Вз |
У4 |
У4 У7 |
У4 |
Вз |
У4 |
B4 |
У5 У6 |
У5, У6, У 8 |
У5, У6 |
B41 |
У5 |
|
|
|
|
B42 |
У6 |
Так как y1 y2, у7 независимы по данным от других микроопераций, то они могут выполняться в блоке В1. Микрооперация у3 зависит по данным от у2, а y8 — от у7, поэтому микрооперации y3 и у8 могут выполняться не ранее, чем в блоке В2. Основной принцип построения HP: СУ микрооперации уп должен помещаться в блок Bi если в блоке Bi-1 находится СУ такой микрооперации ут, что ут wgyn. Полученное HP (см. табл. 6.1) содержит четыре блока, что равно длине максимального пути в ГЗД (см. рис. 6.21), и определяет минимально возможное количество МК в микропрограмме. На втором шаге алгоритма формируется повторное распределение (ПР), определяющее максимальный по номеру блок Вг в котором еще в состоянии выполняться микрооперация уп. Если HP формируется прохождением графа сверху вниз, то ПР — проходом по ГЗД снизу вверх. Так, y8 может выполняться в самом последнем блоке ПР (см. табл. 6.1), поскольку ни одна из микроопераций не зависит по ДЭДным от y8. Длина ПР также равна длине максимального пути в ГЗД.
Исходя из HP и ПР, формируется критическое распределение (КР). В КР входят СУ критических микроопераций, то есть таких, которые находятся в блоках с одинаковыми номерами как в HP, так и в ПР. Так, СУ у2 находится в блоке Bt HP и в блоке В1 ПР, следовательно, это критическая микрооперация критическим носятся также микрооперации у3, у4, у5, у6 (см. табл. 6.1). Кроме того, критическое распределение содержит четыре блока и является основой для формирования набора микрокоманд.
Так как КР было сформировано без учета структурной несовместимости между критическими микрооперациями, оно должно быть проверено на ее наличие.
Блок, содержащий СУ структурно несовместимых микроопераций, «расщепляется» на подблоки, внутри которых нет структурной несовместимости. Тем самым формируется проверенное критическое распределение (ПКР). В нашем случае существует структурная несовместимость между у5 и у6, поэтому блок В входящий в КР, необходимо разделить на два подблока В41 и В42 (см. табл. 6.1).
На последнем шаге алгоритма путем размещения оставшихся СУ некритических микроопераций по блокам ПКР формируется окончательный набор микрокоманд (НМК). Каждый блок и подблок ПКР соответствует одной микрокоманд результирующего НМК. В нашем примере нужно распределить СУ микроопераций yv у, у8. Для этого имеется следующее правило: в ПКР ищется самый первый по номеру блок, в который можно включить СУ микрооперации уп, из последовательности блоков Вн, ..., Вк, где Вн — блок HP и Вк — блок ПР, содержащие СУ данной микрооперации. Если размещаемый СУ у„ не может быть включен ни в один из этих блоков из-за структурной несовместимости с уже размещенными в них СУ микроопераций, то он помещается в специально формируемый блок B'K(i= 1t2, ) В табл. 6.2 показано применение этого правила для окончательного формирования НМК. Так, СУ микрооперации у1 должен быть включен в микрокоманду У1 или в микрокоманду У2. СУ микрооперации у, включается в МК У,, так как он структурно совместим с СУ микрооперации у2 е У,. СУ микрооперации у7 должен быть включен в одну из микрокоманд У„ У2, Y3, однако его нельзя включить в У, из-за структурной несовместимости с СУ микрооперации у2. Нельзя его поместить и в микрокоманду У, вследствие структурной несовместимости с у3. Поэтому СУ у7 войдет в микрокоманду У3.
Последней размещается СУ микрооперации, и сначала может показаться, что он должен быть включен в МК У2, но при этом нарушается ограничение, которое накладывается зависимостью по данным: у7 wgys. Поэтому СУ уа не может войти в МК, предшествующую микрокоманде У3, которая содержит СУ микрооперации у7. Для исключения подобных ошибок следует корректировать HP после каждого распределения СУ микрооперации в МК У,. Коррекция заключается в перемещении всех СУ микроопераций уп, зависящих по данным от распределении СУ микрооперации, в блок В1HP, где номер блока равен: i =j + 1. Следовательно, СУ микрооперации уа после распределения у7 можно включить то в МК У, (см. табл. 6.2).