Файл: 1-337.pdf

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

Рис. 6.19. Двухуровневая организация памяти МПА

Запоминающие устройства микропрограмм

Память микропрограмм может быть реализована запоминающими устройствами

различных типов. В зависимости от типа применяемого ЗУ различают МПА со
статическим и динамическим микропрограммированием [28]. В первом случае в
качестве ПМП используется постоянное ЗУ (ПЗУ) или программируемая логи-
ческая матрица (ПЛМ), во втором — оперативное ЗУ.

Динамическое микропрограммирование в отличие от статического позволяет

оперативно модифицировать микропрограммы УУ, меняя тем самым функцио-
нальные свойства ВМ. Основное препятствие на пути широкого использования

динамического микропрограммирования — энергозависимость и относительно

невысокое быстродействие ОЗУ.

В УУ со статическим микропрограммированием более распространены ПЛМ.

Программируемая логическая матрица является разновидностью ПЗУ, в котором

программируются не только данные, но и адреса, благодаря чему на ПЛМ можно
реализовать как память микропрограмм, так и формирователь адреса следующей
микрокоманды.

ПЗУ содержит полный дешифратор с

 n

-разрядным входом (адресом) и 2^n вы-

ходами. Напротив, ПЛМ имеет неполный дешифратор, количество выходов в ко-
тором меньше,

 2^n, поэтому в ПЛМ некоторые адреса вообще не инициируют

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

зом, возможна выборка одного слова с помощью двух или более адресов или же
выборка нескольких слов с помощью одного адреса, что эквивалентно реализации
функции

 от выбранных слов.

В структуре ПЛМ (рис. 6.20) выделяют три части

• буфер Б, формирующий парафазные значения

 а

1

,

,

 а

1

,

,...,

 входных перемен-

ных

 a

1,

..,

• «И»-матрицу адресов, на выходе которой вырабатываются значения тер-

мов Z

1

,

 Zj

•

 данных, на выходе которой формируются сигналы, представ-

ляющие значения выходных переменных

 c

1

 ...,

 Матрица адресов содержит

2т

 входных цепей (горизонтальные линии) и

 J

 элементов

каждый из входов которых (вертикальные линии) может соединяться с вход-
ной цепью в точках, обозначенных крестиком. Аналогично строится матрица

данных, в которой крестиками обозначены возможные соединения входных

цепей матрицы с

 n j-

входовыми элементами «ИЛИ».

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

Рис. 6.20. Структура программируемой логической матрицы

Соединения в ПЛМ обеспечивают однонаправленную передачу сигналов: в ма-

трице «И» — из любой горизонтальной

 в вертикальную,  в матрице «ИЛИ» —

из любой вертикальной цепи в горизонтальную. Такие соединения осуществляют-
ся за счет диодов или транзисторов.

Процесс установления соединений между горизонтальными и вертикальными

цепями матриц называется программированием ПЛМ (программированием адре-
сов и данных соответственно). Различают ПЛМ с масочным и электрическим про-
граммированием, а также перепрограммируемые логические матрицы. В ПЛМ
первого типа информация заносится посредством подключения диодов или тран-

зисторов к цепям за счет металлизации соответствующих участков матриц, вы-
полняемой через маску (шаблон). В ПЛМ с электрическим программированием
либо устанавливаются нужные соединения (путем пробоя слоя диэлектрика,
(р-п)-перехода), либо уничтожаются ненужные соединения (благодаря выжига-
нию плавких перемычек). Перепрограммируемые ПЛМ позволяют многократно
переписывать информацию. При этом стирание информации производится ульт-
рафиолетовым излучением, а запись — электрическим током.

ПЛМ более экономны по затратам, чем ПЗУ, в трех случаях:

• при выдаче нулевого кода;
• при формировании значения функции «логическое ИЛИ» от нескольких слов;
• при записи одного и того же слова по нескольким адресам.

Чтобы иметь возможность выдать нулевой код из ПЗУ, необходимо обеспе-

чить предварительную запись нуля в определенную ячейку. В ПЛМ для этого до-
статочно обращения по незапрограммированному адресу.

Во втором случае в ПЗУ опять должна

 дополнительная ячей-

ка для хранения кода, специально запрограммированного как логическое «ИЛИ»

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

от нескольких слов. B ПЛМ один адрес может относиться к нескольким словам,
которые на выходе матрицы данных объединяются по схеме «ИЛИ».

В третьем случае в ПЗУ требуется многократная запись одного слова по всем

указанным адресам. Применительно к ПЛМ это означает, что какое-то слово в ма-
трице данных имеет адрес вида

 где XX — разряды с безразличным значе-

нием (цепи соответствующих разрядов буфера не подключены к вертикальным
цепям матрицы адресов).

Минимизация

 слов памяти микропрограмм

Общая задача оптимизации емкости памяти микропрограмм достаточно сложна

и поэтому обычно решается в два этапа. На первом этапе минимизируется количе-
ство слов микропрограммы (количество микрокоманд), на втором этапе — разряд-
ность микрокоманды.

Сначала рассмотрим один из возможных подходов, действующих при разбие-

нии линейной микропрограммы на минимальное количество микрокоманд [3].

Обозначим через  — множество операндов микрооперации y

i

; О

i

 — множество

результатов микрооперации y

i

,. Сигналы управления (СУ) микроопераций y

i

 и y

j

нельзя объединить в одну микрокоманду, если имеет место один из трех случаев
пересечения по данным:

При этом говорят, что y

i

 и y

j

 находятся в отношении

 зависимости по данным:

y

i

 w

g

 y

j

 Графически отношение

 отображается графом зависимости по данным

(ГЗД), вершины которого соответствуют микрооперациям. Дуга (y

i

 ,y

j

) в ГЗД по-

казывает, что микрооперации y

i

 и y

j

 находятся в отношении

 Пример ГЗД при-

веден

 рис.

 Граф зависимости по данным

Если

 y

i

 , y

j

 используют один и тот же функциональный узел

ВМ, то говорят, что они находятся в отношении структурной несовместимости

то есть y

i

 y

j .

Сигналы управления двух микроопераций можно объединить

в одну микрокоманду, если они структурно совместимы и не находятся в отноше-
нии зависимости по данным:

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

Пусть между

 рассматриваемого ГЗД существует сле-

дующая структурная несовместимость:

у

1

 w

c

 у

7

 , у

3

 у

7

 , у

5

 w

c

 у

7

,

Минимальное количество микрокоманд в микропрограмме будет определять-

ся длиной критического пути в графе ГЗД, то есть пути, длина которого макси-
мальна.

На первом шаге алгоритма формируется

 начальное распределение

 (HP), состоя-

щее из блоков

 B

1

 ...,

 где

 М—

 длина критического пути ГЗД. Каждый блок

 B

i

является «заготовкой» микрокоманды

 ,

 в него включаются СУ тех микроопера-

ций, которые могут выполняться не ранее, чем по микрокоманде

 Y

i

 .

Начальное рас-

пределение для нашего примера показано в табл. 6.1.

Таблица

 Основные распределения микроопераций

Так как

 у

1

 независимы по данным от других микроопераций, то они могут

выполняться в блоке

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

 —

 от

 по-

этому

 и  могут выполняться не ранее, чем в блоке

 Основной

принцип построения

 СУ микрооперации

 у

n

 должен помещаться  блок

 В

i

,

 в

блоке

 В

i-1

 находится СУ такой микрооперации

 что

 Полученное

 (см.

табл. 6.1) содержит четыре блока, что равно длине максимального пути в ГЗД (см.
рис.

 и определяет минимально возможное количество МК в микропрограмме.

На втором шаге алгоритма формируется

 повторное распределение

 (ПР), опре-

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

няться микрооперация  Если HP формируется прохождением графа сверху вниз,

то ПР — проходом по ГЗД снизу вверх.

 может выполняться в самом послед-

нем блоке ПР (см. табл. 6.1), поскольку ни одна из микроопераций не зависит по

данным от

 Длина ПР также равна длине максимального пути в ГЗД.

Исходя из HP и ПР, формируется

 критическое распределение

 (КР). В КР вхо-

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

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

 так и в ПР. Так,

 находится в блоке

 В

1

 HP

и в блоке

 В

1

 ПР, следовательно, это критическая микрооперация. К критическим

относятся также микрооперации

 у

4

, у

5

,

 (см. табл. 6.1). Кроме того, критичес-

кое распределение содержит четыре блока и является основой для формирования
набора микрокоманд.

Так как КР было сформировано без учета структурной несовместимости меж-

ду критическими микрооперациями, оно должно быть проверено на ее наличие.

3 2 0

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

Блок, содержащий СУ структурно несовместимых микроопераций, «расщепляет-

 на подблоки, внутри которых нет структурной несовместимости. Тем самым

формируется

 проверенное критическое распределение

 (ПКР). В нашем случае су-

ществует структурная несовместимость между  и

 поэтому блок

 В

4

,

 входящий

 КР, необходимо разделить на два подблока

 и

 (см. табл.

На последнем шаге алгоритма путем размещения оставшихся СУ некритичес-

ких микроопераций по блокам ПКР формируется окончательный набор микроко-
манд (НМК). Каждый блок и подблок ПКР соответствует одной микрокоманде

результирующего НМК. В нашем примере нужно распределить СУ микроопера-
ций

 у

1

,

 Для этого имеется следующее правило: в ПКР ищется самый первый

по номеру блок, в который можно включить СУ микрооперации

 у

n

,

 из последова-

тельности блоков

 ...,

 где

 — блок HP

 блок ПР, содержащие СУ

данной микрооперации. Если размещаемый

 не может быть включен

 в один

из этих блоков из-за структурной несовместимости с уже размещенными в них СУ

микроопераций, то он помещается в специально формируемый блок

 (

i

 = 1,2,...).

В табл. 6.2 показано применение этого правила для окончательного формирова-

ния НМК. Так, СУ микрооперации

 у

i

 быть включен в микрокоманду У,

или в микрокоманду

 СУ микрооперации

 у

1

 включается в

 Y

1

,

 так как он

структурно совместим с СУ микрооперации

 у

2

 принадлежит

 Y

1

.

 СУ микрооперации

у

7

 должен быть включен в одну из микрокоманд У

1

,

 однако его нельзя включить в У,

из-за структурной несовместимости с СУ микрооперации

 Нельзя его помес-

тить  в микрокоманду  вследствие структурной несовместимости

 Поэтому СУ

у

7

 войдет в микрокоманду У

3

.

Таблица 6.2.

 Формирование окончательного НМК •

Последней размещается СУ

 и сначала может показаться, что

он должен быть включен в МК

 но при этом нарушается ограничение, которое

накладывается зависимостью

 данным:

 Поэтому СУ  не может войти

в МК, предшествующую микрокоманде

 которая содержит СУ микрооперации

y

7

 .

 Для исключения подобных ошибок следует корректировать HP после

распределения СУ микрооперации в

 Коррекция заключается в переме-

щении всех СУ микроопераций

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

СУ микрооперации, в блок

 HP, где номер блока равен:

 1. Следова-

тельно, СУ микрооперации  после распределения  можно включить только
в МК

 (см. табл. 6.2).