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

Запуск микропрограммы выполнения операции осуществляется путем передачи кода операции из РК на вход преобразователя, в котором код операции преобразуется в начальный (первый) адрес микропрограммы^. Этот адрес поступает через ФАСМ в регистр адреса микрокоманды. Выбранная по адресу А_п из ПМП микрокоманда заносится в РМК. Каждая микрокоманда в общем случае содержит микрооперационную (МО) и адресную (А) части. Микрооперационная часть микрокоманды поступает на дешифратор микрокоманды, на выходе которого образуются управляющие сигналы, инициирующие выполнение микроопераций в исполнительных устройствах и узлах ВМ. Адресная часть микрокоманды подается в ФАСМ, где формируется адрес следующей микрокоманды А_ш.Этот адрес может зависеть от адреса на выходе преобразователя кода операции Ли, адресной части текущей микрокоманды А и значений осведомительных сигналов (флагов) X, поступающих от исполнительных устройств. Сформированный адрес микрокоманды снова записывается в РАМ, и процесс повторяется до окончания микропрограммы.

Разрядность адресной (#а)^и микрооперационной (Я_мо) частей микрокоманды определяются из соотношений

(6.1)

(6,2)

где Ν_ΜΚ— общее количество микрокоманд; N_Cy— общее количество формируемых сигналов управления.

В свою очередь, необходимая емкость памяти микропрограмм равна

Кодирование микрокоманд

Информация о том, какие сигналы управления должны быть сформированы в процессе выполнения текущей МК, в закодированном виде содержится в микрооперационной части (МО) микрокоманды. Способ кодирования микроопераций во многом определяет сложность аппаратных средств устройства управления и его скоростные характеристики. Применяемые в микрокомандах варианты кодирования сигналов управления можно свести к трем группам: минимальное кодирование (горизонтальное микропрограммирование), максимальное кодирование (вертикальное микропрограммирование) и групповое кодирование (смешанное микропрограммирование). Структуры микропрограммных автоматов при различных способах кодирования микроопераций показаны на рис. 6.9 [12,28].

При горизонтальном микропрограммировании (см. рис. 6.9, а) под каждый сигнал управления в микрооперационной части микрокоманды выделен один разряд (#мо ~N_Cy)3ro позволяет в рамках одной микрокоманды формировать любые сочетания СУ, чем обеспечивается максимальный параллелизм выполнения микроопераций. Кроме того, отсутствует необходимость в декодировании МО и выходы регистра микрокоманды могут быть непосредственно подключены к соответствующим управляемым точкам ВМ. Широкому распространению горизонтального микропрограммирования тем не менее препятствуют большие затраты на хранение микрооперационных частей микрокоманд (Е_М(у N_MK * #_су)причем эффек-

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

Рис. 6.9. Структуры МПАпри различных способах кодирования микроопераций:

а — минимальном; б— максимальном; в — максимальном с шифратором;

Г— горизонтально-вертикальном; д — вертикально-горизонтальном

тивность использования ПМП получается низкой,, так как при большом числе микроопераций в каждой отдельной МК реализуется лишь одна или несколько из них, то есть подавляющая часть разрядов МО содержит нули.

При максимальном (вертикальном) кодировании (см. рис. 6.9, б) каждой микрооперации присваивается определенный код, например, ее порядковый номер в полном списке возможных микроопераций. Этот код и заносится в МО. Микрооперационная часть МК имеет минимальную длину, определяемую как двоичный логарифм от числа управляющих сигналов (микроопераций) по формуле (6.2). Такой способ кодирования требует минимальных аппаратных затрат в ПМП на хранение микрокоманд, однако возникает необходимость в дешифраторе ДшМК, который должен преобразовать код микрооперации в соответствующий сигнал управления. При большом количестве СУ дешифратор вносит значительную временную задержку, а главное — в каждой МК указывается лишь один сигнал управления, инициирующий только одну микрооперацию, за счет чего увеличиваются длина микропрограммы и время ее реализации.

., Последний недостаток устраняется при подключении к выходам ДшМК шифратора (Ш) (см. рис. 6.9, в),что приводит к увеличению количества СУ, формируемых одновременно.. Естественно, что помимо кодов отдельных микроопераций должны быть предусмотрены коды, представляющие и определенные комбинации микроопераций. Для повышения универсальности шифратор целесообразно строить на базе запоминающего устройства.

Вариант, представленный на рис. 6.9, в, рационален, если

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

где ЛГр— количество выходов дешифратора. При этих условиях аппаратные затраты на хранение микрооперационных частей МК относительно малы:

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

откуда ясно, что при близких Л^и N_D вариант теряет смысл.

Минимальное и максимальное кодирование являются двумя крайними точками широкого спектра возможных решений задачи кодирования СУ. Промежуточное положение занимает групповое или смешанное кодирование.

Здесь все сигналы управления (микрооперации) разбиваются на К групп

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

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

Каждой группе Y, выделяется отдельное поле в микрооперационной части МК, общая разрядность которой равна

где JV . — количество СУ, представляемых 1-й полем (группой).

СУ/

Общая емкость памяти микропрограмм рассмотренного варианта кодирования определяется из выражения:

При вертикально-горизонтальном способе (см. рис. 6.9, д) все множество сигналов управления (микроопераций) также делится на несколько групп, однако в группу включаются сигналы управления (микрооперации), наиболее часто встречающиеся вместе в одном такте. Поле МО делится на две части: МО и М0_г. Поле MOj, длина которого равна максимальному количеству сигналов управления (микроопераций) в группе, кодируется горизонтально, а поле М0_г, указывающее на принадлежность к определенной группе, — вертикально. Со сменой группы меняются и управляемые точки, куда должны быть направлены сигналы управления из каждой позиции МО,. Это достигается с помощью демультиплексоров (Цмп), управляемых кодом номера группы из поля MQ,

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

При горизонтальном, вертикальном и горизонтально-вертикальном способах кодирования микроопераций каждое поле микрокоманды несет фиксированные функции, то есть имеет место прямое кодирование. При косвенном кодировании одно из полей отводится для интерпретации других полей. Примером косвенного кодирования микроопераций может служить вертикально-горизонтальное кодирова-н и е . .

Иногда используется двухуровневое кодирование микроопераций. На первом уровне с вертикальным кодированием выбирается микрокоманда, поле МО которой является адресом горизонтальной микрокоманды второго уровня — нанокоманды. Данный способ сочетания вертикального и горизонтального микропрограммирования часто называют нанопрограммированием. Метод предполагает двухуровневую систему кодирования микроопераций и, соответственно, двухуровневую организацию управляющей памяти (рис 6.10).

Рис. 6.10. Нанопрограммное устройство управлен Верхний уровень управления образуют микропрограммы, хранящиеся в памяти микропрограмм. В микрокомандах используется вертикальное кодирование микроопераций. Каждой микрокоманде соответствует нанокоманда, хранящаяся в управляющей памяти нижнего уровня — памяти нанокоманд. В нанокомандах применено горизонтальное кодирование микроопераций. Именно нанокоманды используются для непосредственного формирования сигналов управления. Микрокоманды вместо закодированного номера СУ содержат адресную ссылку на соответствующую нанокоманду.

Такой подход, сохраняя все достоинства горизонтального микропрограммирования, позволяет значительно сократить суммарную емкость управляющей памяти. Дело в том, что число различных сочетаний сигналов управления, а следовательно, количество «длинных» нанокоманд, обычно невелико. В то же время практически все микрокоманды многократно повторяются в различных микропрограммах, и замена в микрокомандах «длинного» горизонтального управляющего поля на короткую адресную ссылку дает ощутимый эффект. Проиллюстрируем это примером.

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

Пусть в системе вырабатывается 200 управляющих сигналов, а общая длина микропрограмм составляет 2048 микрокоманд. Предположим также, что реально используется только 256 различных сочетаний сигналов управления. В случае обычного УУ с горизонтальным микропрограммированием емкость управляющей памяти составила бы 2048 х 200 ,= 409 600 бит. При нанопрограммировании требуется память микропрограмм емкостью 2048 х 8 = 16 384 бит и Память наноко-манд емкостью 256 х 200 =51 200 бит. Таким образом, суммарная емкость обоих видов управляющей памяти равна 67 584 битам.

Иначе говоря, нанопамять реализует функцию шифратора управляющих сигналов (см. рис. 6.9, в). Справедливы следующие соотношения: R_M < R^ Е_м» Е_ц, где Е Rm~ емкость и разрядность микропамяти; Е_н,, R_H— емкость и разрядность памяти нанокоманд.

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

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

Двухуровневая память рассматривается как способ для уменьшения необходимой емкости ПМП, ее использование целесообразно только при многократном повторении микрокоманд в микропрограмме.

При разбиении микрокоманды на поля могут действовать два принципа: по функциональному назначению СУ и по ресурсам. Функциональное кодирование предполагает, что каждое поле соответствует одной функции внутри ВМ. Например, информация в аккумулятор может заноситься из различных источников, и для указания источника в микрокоманде может быть отведено одно поле, где каждая кодовая комбинация прикреплена к определенному источнику. При ресурсном кодировании ВМ рассматривается как набор независимых ресурсов (память, УВВ, АЛУ и т. п.), и каждому из ресурсов в микрокоманде отводится свое поле.

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

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

Большей частью микрокоманды в микропрограмме выполняются последовательно, однако в общем случае очередность микроопераций не является фиксированной. По этой причине в УУ необходимо предусмотреть эффективную систему реализации переходов. Переходы, как безусловные, так и условные, являются неотъемлемой частью любой микропрограммы.

Адресация микрокоманд

При выполнении микропрограммы адрес очередной микрокоманды относится к одной из трех категорий:

; · определяется кодом операции команды;

_: ' · является следующим по порядку адресом;

■, · является адресом перехода.

Первый случай имеет место только один раз в каждом цикле команды, сразу же вслед за ее выборкой. Как уже отмечалось ранее, каждой команде из системы команд ВМ соответствует «своя» микропрограмма в памяти микропрограмм, поэто-ί му первое действие, которое нужно произвести после выборки команды, — преоб-- разовать код операции в адрес первой МК соответствующей микропрограммы. Это может быть выполнено с помощью аппаратного преобразователя кода операции ; (см. рис. 6.8). Такой преобразователь обычно реализуется в виде специального ЗУ, ^!■: хранящего начальные адреса микропрограмм в ПМП. Для указания того, как дол-\ жен вычисляться адрес следующей МК в микрокоманде, может быть выделено ' специальное однобитовое поле. Единица в этом поле означает, что _мк должен быть

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

сформирован на основании кода операции. Подобная МК обычно располагается в конце микропрограммы этапа выборки или в микропрограмме анализа кода операции.

Дальнейшая очередность выполнения микрокоманд микропрограммы может быть задана путем указания в каждой МК адреса следующей микрокоманды (принудительная адресация) либо путем автоматического увеличения на единицу адреса текущей МК (естественная адресация) [21].

В обоих случаях необходимо предусмотреть ситуацию, когда адрес следующей микрокоманды зависит от состояния осведомительных сигналов — ситуацию перехода. Для указания того, какое условие должно быть проверено, в МК вводится поле условия перехода (УП). Поле УП определяет номер / осведомительного сигнала л:,, значение которого анализируется при формировании адреса следующей микрокоманды. Если поле УП = 0, то никакие условия не проверяются и _мк либо берется из адресной части микрокоманды (при принудительной адресации), либо формируется путем прибавления единицы к адресу текущей микрокоманды. Если УП!=0, то _мк = А + х_{. В результате этого осуществляется условный переход: при х_;. - 0 к микрокоманде с адресом _мк =Да при x_t -■ 1 — к микрокоманде с адресом _мк = А + 1. Описанный порядок формирования адреса показан на рис. 6.12 и имеет место в случае принудительной адресации с одним адресом.

Рассмотренный способ позволяет в каждой команде учесть состояние только одного из осведомительных сигналов. Более гибкий подход реализован в ряде ВМ фирмы IBM. В нем адреса микрокоманды разбиваются на две составляющие. Старшие п разрядов обычно остаются неизменными. В процессе выполнения микрокоманды эти разряды просто копируются из адресной части МК в аналогичные позиции РАМ, определяя блок из 2^Лп микрокоманд в памяти микропрограмм. Остальные (младшие) к разрядов РАМ устанавливаются в 1 или 0 в зависимости от того, проверка каких осведомительных сигналов была задана в поле УП и в каком состоянии эти сигналы находятся. Такой метод позволяет в одной микрокоманде сформировать 2^Лк вариантов перехода.

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

Теперь рассмотрим возможные способы реализации принудительной и естественной адресации. Известные подходы сводятся к трем типовым вариантам [75]:

• два адресных поля;

• одно адресное поле;

• переменный формат.

Два первых метода представляют принудительную адресацию, а третий — естественную адресацию микрокоманд.

Простейшим вариантом является включение в микрокоманду двух адресных полей (рис. 6.13).

Рис. 6.13. Логика управления переходом с двумя адресными полями

С помощью мультиплексора в регистр адреса микрокоманды (РАМ) может быть загружен либо адрес, определяемый кодом операции выполняемой команды, либо содержимое одного из адресных полей микрокоманды. Выбор источника адреса осуществляется сигналом «Выбор адреса», вырабатываемым логикой перехода, на основании состояния осведомительных сигналов и поля УП микрокоманды. Если УП = 0 или УП = i, но х. = 0, то в РАМ заносится адрес Л₍либо адрес, полученный из кода операции. В противном случае в РАМ переписывается адрес ₂-

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

Главное достоинство принудительной адресации— высокая универсальность и быстродействие. Здесь изменение участка микропрограммы не затрагивает остальных микрокоманд, а совмещение в одной МК условного перехода с формированием сигналов управления уменьшает общее время выполнения микропрограммы.

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

Основной недостаток принудительной адресации — повышенные требования к емкости памяти для хранения адресов МК:

где Ryij- разрядность поля УП; L — общее количество осведомительных сигналов.

При естественной адресации отпадает необходимость во введении адресной части в каждую МК. Подразумевается, что микрокоманды следуют в естественном порядке и процесс адресации реализуется счетчиком адреса микрокоманды (СЧАМ). Значение СЧ AM увеличивается на единицу после чтения очередной МК.

Однако после выполнения МК с адресом А может потребоваться переход к МК с адресом В + 1. Переход может быть безусловным или зависеть от текущего значения х. (если х = 1, то _мк = А + 1; если х = 0, то _мк = В). Для реализации условных и безусловных переходов используются специальные управляющие микрокоманды, состоящие только из двух полей: адресного поля В и поля УП, вьщеля-ющего номер условия перехода. Алгоритм выполнения управляющей МК:

если УП = 0, то СЧАМ :- В;

если УП !=0, то если х. = 1, то СЧАМ := В, иначе СЧАМ := СЧАМ + 1.

Таким образом, при естественной адресации должны применяться МК двух типов: управляющие и операционные. Операционная микрокоманда содержит только микрооперационную часть и не имеет адресной части. Тип М К задается ее первым разрядом: если МК(1) = 1, то это управляющая микрокоманда.

Структура МПА с естественной адресацией показана на рис. 6.15. Выдача сигналов управления С_г..,С_тстробируется сигналомMK(V),принимающим единичное значение при выполнении операционной МК. Дешифратор условия перехода стробируется сигналом МК(1), который равен 1 при обработке управляющей микрокоманды. Адрес следующей МК образуется на счетчике СЧАМ при выполнении микрооперации +1СЧАМ СЧАМ := СЧАМ + 1 или П₂СЧАМ: СЧАМ := В. Формирование адреса следующей МК описывается микропрограммой на рис. 6.16.

Достоинство естественной адресации — экономия памяти микропрограмм, а основной недостаток состоит в том, что для любого перехода требуется полный тактовый период, в то время как при принудительной адресации переход выпол-

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

няется одновременно с формированием управляющих сигналов без дополнительных обращений к управляющей памяти. Кроме того, при сильно разветвленных микропрограммах требуются большие дополнительные затраты памяти:

Рассмотренные способы адресации аппаратно реализует формирователь адреса микрокоманды ФАМ (см. рис. 6.8). ФАМ является механизмом управления последовательностью выполнения микрокоманд. Возрастание сложности микропрограммного обеспечения современных ВМ предопределяет необходимость расширения функциональных возможностей ФАМ.

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

Набор базовых функций управления, реализуемых ФАМ, включает в себя: ПРИ-PATTTFHHF, ПЕРИОД ВЫЗОВ, ВОЗВРАТ, ЦИКЛ [9, 32]. Функции управления кодируются полем ФУ в составе МК (рис. 6.17) и задают алгоритмы выбора адреса очередной МК.


МО	УП	ФУ	А

Рис. 6.17. Структура микрокоманды с выделенным полем функции управления

Обозначим: ;' — адрес МК, в которой размещена данная функция управления; АМК — адрес следующей МК; СЧЦ — счетчик количества повторений микропрограммы (циклов);^- — значение анализируемого условия; а — адрес возврата к вызывающей микропрограмме. Охарактеризуем каждую функцию управления.

Рис. 6.18. Набор базовых функций управления микрокоманд: а — ПРИРАЩЕНИЕ; б- ПЕРЕХОД; в — ВОЗВРАТ; г— ВЫЗОВ;д - ЦИКЛ

11РИРАШЕНИЕ — обеспечивает переход к МК, записанной по адресу; + 1, ауслов-ная функция ПРИРАЩЕНИЕ — многократное повторение одной и той же МК, записанной по адресу/' (рис. 6.18, а).

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

ПЕРЕХОД — обеспечивает переход к последовательности микрокоманд с начальным адресом АМК. В случае условного перехода управление передается по адресу АМК при единичном значении условия Д/, в противном случае выполняется МК по адресу / + 1 (рис. 6.18, б).

ВЭЗНАТ — позволяет после выполнения микропрограммы автоматически вернуться в ту точку, откуда она была вызвана (рис. 6.18, в). Использование условной функции Β03ΗΆΤ позволяет вернуться к основной микропрограмме из различных точек внешней микропрограммы.

ВЫЗОВ — одна из основных функций, так как позволяет перейти к исполнению другой микропрограммы с начальным адресом АМК (с сохранением адреса точки перехода), как показано на рис. 6.18, г.

ЦИКЛ — передает управление многократно исполняемому участку микропрограммы с начальным адресом АМК (рис. 6.18, д).

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

Организация памяти микропрограмм

Функциональные возможности и структура микропрограммных автоматов в значительной степени зависят от организации памяти для хранения микропрограмм. Основные способы организации памяти микропрограмм можно свести к следующим вариантам [3].

1. Каждое слово ПМП содержит одну микрокоманду. Это наиболее простая организация ПМП. Основной недостаток — в каждом такте работы МПАтребуется обращение к памяти микропрограмм, что приводит к снижению быстродействия МПА.

2. Одно слово ПМП содержит несколько микрокоманд. В результате осуществляется одновременное считывание из ПМП нескольких МК, что позволяет повысить быстродействие УУ.

3. Сегментация ПМП, при которой память разделяется на сегменты, состоящие из 2^Лд соседних слов, при этом адрес слова АМК разделяется на два поля: 5 и Л. Поле 5 определяет адрес сегмента, а поле А — адрес слова в сегменте. Адрес S устанавливается специальной микрокомандой. В последующих микрокомандах указывается только адрес слова А в сегменте. Таким образом, разрядность адресной части МК уменьшается.

4. Двухуровневая память (рис. 6.19). Первый уровень — микропамять, хранящая микрокоманды. Второй уровень — нанопамять, содержащая нанокоманды.

МК выбирается из микропамяти и служит для адресации слова нанопамяти, которое включает в себя необходимые сигналы управления. После выполнения микроопераций из микропамяти выбирается следующая МК. Иначе говоря, нанопамять реализует функцию шифратора управляющих сигналов (см. рис. 6.9, в}. Двухуровневая память рассматривается как способ для уменьшения необходимой емкости ПМП, ее использование целесообразно только при многократном повторении микрокоманд в микропрограмме.

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

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

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

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

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

ПЗУ содержит полный дешифратор с «-разрядным входом (адресом) и 2^Λη выходами. Напротив, ПЛМ имеет неполный дешифратор, количество выходов в котором меньше, чем 2^Λη, поэтому в ПЛМ некоторые адреса вообще не инициируют действий, тогда как другие адреса могут оказаться неразличимыми. Таким образом, возможна выборка одного слова с помощью двух или более адресов или же выборка нескольких слов с помощью одного адреса, что эквивалентно реализации функции «ИЛИ» от выбранных слов.

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

• буфер Б, формирующий парафазные значения а_х„ а_х„...,а_тУ а_т входных переменных а_1Г.,а_я;

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

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

ляющие значения выходных переменных с_х ..., с_п. Матрица адресов содержит 2т входных цепей (горизонтальные линии) и /m-входовых элементов «И», каждый из входов которых (вертикальные линии) может соединяться с входной цепью в точках, обозначенных крестиком. Аналогично строится матрица данных, в которой крестиками обозначены возможные соединения входных цепей матрицы с лу-входовыми элементами «ИЛИ».

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

Рис. 6.20. Структура программируемой логической матрицы Соединения в ПЛМ обеспечивают однонаправленную передачу сигналов: в матрице «И» — из любой горизонтальной цепи в вертикальную, а в матрице «ИЛИ» — из любой вертикальной цепи в горизонтальную. Такие соединения осуществляются за счет диодов или транзисторов.

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

• при выдаче нулевого кода;

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

• при записи одного и того же слова по нескольким адресам.

Чтобы иметь возможность выдать нулевой код из ПЗУ, необходимо обеспечить предварительную запись нуля в определенную ячейку. В ПЛМ для этого достаточно обращения по ^запрограммированному адресу.

Во втором случае в ПЗУ опять должна задействоваться дополнительная ячейка для хранения кода, специально запрограммированного как логическое «ИЛИ»

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

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

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

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

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

Сначала рассмотрим один из возможных подходов, действующих при разбиении линейной микропрограммы на минимальное количество микрокоманд [3].

Обозначим через, — множество операндов микрооперации у.; 0_;. — множество результатов микрооперации^.,. Сигналы управления (СУ) микроопераций у. и у. нельзя объединить в одну микрокоманду, если имеет место один из трех случаев пересечения по данным:

При этом говорят, что у_;. и у. находятся в отношении w_g зависимости по данным: у_;. w у. Графически отношение w_g отображается графом зависимости по данным (ГЗД), вершины которого соответствуют микрооперациям. Дуга (у_;. ,у) в ГЗД показывает, что микрооперации у. и у. находятся в отношении w_g. Пример ГЗД приведен на рис. 6.21.

Если две микрооперации у_;., у. используют один и тот же функциональный узел ВМ, то говорят, что они находятся в отношении структурной несовместимости w_c, то есть у. w_c у. Сигналы управления двух микроопераций можно объединить в одну микрокоманду, если они структурно совместимы и не находятся в отношении зависимости по данным:

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

Пусть между микрооперациямиу_х, ....^рассматриваемого ГЗД существует следующая структурная несовместимость:

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

На первом шаге алгоритма формируется начальное распределение (HP), состоя-, щее из блоков В₁ ..., В_м, где М— длина критического пути ГЗД. Каждый блок Д. является «заготовкой» микрокоманды Υ_{ , в него включаются СУ тех микроопераций, которые могут выполняться не ранее, чем по микрокоманде Y_t.Начальное распределение для нашего примера показано в табл. 6.1.

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


Блок	Распределение МО			Блок	ПКР
Блок	HP	пр	КР	Блок	ПКР
Я.	*У^.УъУ?*	Уг	Уг	δι	Уг
в₂	*УьУь*	УьУ*	Уз	V	Уз
в,	Уа	*Уа>Уч*	Ул	Д>	Уа
в₄	*УьУъ*	*УьУъУъ*	У* У*	в\	У$
				в\	Ул

Так как у_г г/₂,г/₇ независимы по данным от других микроопераций, то они могут выполняться в блоке Β_ν Микрооперация у_ъ зависит по данным от у₂, а у₈ — от у₇, поэтому микрооперацииу₃ну₈могут выполняться не ранее, чем в блоке В₂. Основной принцип построения HP: СУ микрооперации у_п должен помещаться в блок Д, если в блоке Д__; находится СУ такой микрооперации г/_т, что y_mw_gy„. Полученное HP (см. табл. 6.1) содержит четыре блока, что равно длине максимального пути в ГЗД (см. рис. 6.21), и определяет минимально возможное количество МК в микропрограмме.

На втором шаге алгоритма формируется повторное распределение (ПР), определяющее максимальный по номеру блок Д, в котором еще в состоянии выполняться микрооперация^. Если HP формируется прохождением графа сверху вниз, то ПР — проходом по ГЗД снизу вверх. Так, г/₈может выполняться в самом последнем блоке ПР (см. табл. 6.1), поскольку ни одна из микроопераций не зависит по данным оту₈. Длина ПР также равна длине максимального пути в ГЗД.

Исходя из HP и ПР, формируется критическое распределение (КР). В КР входят СУ критических микроопераций, то есть таких, которые находятся в блоках с одинаковыми номерами как в HP, так и в ПР. Так, СУ г/₂находится в блоке Д HP и в блоке Д ПР, следовательно, это критическая микрооперация. К критическим относятся также микрооперации у_ъ, у_р у₅, г/₆(см. табл. 6.1). Кроме того, критическое распределение содержит четыре блока и является основой для формирования набора микрокоманд.

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

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

Блок, содержащий СУ структурно несовместимых микроопераций, «расщепляется»· на подблоки, внутри которых нет структурной несовместимости. Тем самым формируется проверенное критическое распределение (ПКР). В нашем случае существует структурная несовместимость между у₅ и у₆, поэтому блок Β_ψ входящий в КР, необходимо разделить на два подблока В\ иВ* (см. табл. 6.1).

На последнем шаге алгоритма путем размещения оставшихся СУ некритических микроопераций по блокам ПКР формируется окончательный набор микрокоманд (НМК). Каждый блок и подблок ПКР соответствует одной микрокоманде результирующего НМК. В нашем примере нужно распределить СУ микроопераций у^у-цУв- Для этого имеется следующее правило: в ПКР ищется самый первый по номеру блок, в который можно включить СУ микрооперации у^ из последовательности блоков В_и,..., В_к, где В_н— блок HP и В_к —блок ПР, содержащие СУ данной микрооперации. Если размещаемый СУг/„не может быть включен ни в один из этих блоков из-за структурной несовместимости с уже размещенными в них СУ микроопераций, то он помещается в специально формируемый блок В'_к (г = 1,2,...). В табл. 6.2 показано применение этого правила для окончательного формирования НМК. Так, СУ микрооперации y_i должен быть включен в микрокоманду У, или в микрокоманду Y₂. СУ микрооперации у_: включается в МК Υ_ρ так как он структурно совместим с СУ микрооперации у₂ принадлежит Y_r СУ микрооперации у₇должен быть включен в одну из микрокоманд У_1; Y₂, У₃, однако его нельзя включить в из-за структурной несовместимости с СУ микрооперации у₂. Нельзя его поместить и в микрокоманду Υ₂ вследствие структурной несовместимости с у₃. Поэтому СУ у₇ войдет в микрокоманду У₃.

Таблица 6.2. Формирование окончательного НМК


МК	Шаг	выполнения алгоритма
МК	1	г	3
у.	*УиУг*	*Ух<У1*	У«Л
У*	Уз	Уз	Уз
У*	У*	*УьУ?*	**У,Ут***
У*	Уъ	Уа	*Уи.У%*
У,	У*	Уб	Уе

Последней размещается СУ микрооперации г/₈,и сначала может показаться, что он должен быть включен в МК Υ₂, но при этом нарушается ограничение, которое накладывается зависимостью по данным: y₇w_gy₈. Поэтому СУ у_ъ не может войти в МК, предшествующую микрокоманде У₃, которая содержит СУ микрооперации у₇. Для исключения подобных ошибок следует корректировать HP после каждого распределения СУ микрооперации в МК У,. Коррекция заключается в перемещении всех СУ микроопераций у_п, зависящих по данным от распределенного СУ микрооперации, в блок В,· HP, где номер блока равен: i—j+l. Следовательно, СУ микрооперации^после распределенияу₇можно включить только в МК У₄ (см. табл. 6.2).

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

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

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

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

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

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

где |С.| — количество микроопераций в классе несовместимости, а выражение mt^log/n + 1)) определяет минимальную разрядность поля ПМП, необходимую

для кодирования п микроопераций и признака их отсутствия в конкретной МК. папам W_{ - т1(Га£₂(]С^ | +1)) называют ценой класса С,.

Тешение ищется на множестве МКН. Для заданного в табл. 6.3 примера микропрограммы получается следующий набор МКН: C_t - \y_v у·}, у_п}> С_г - (у₂, у₇, у_и},

^ - {У*УтУи>Ь С," &*Ут»Ую)> ^cs " &4>УяЬ Q -&*УьУ«.УиЬ ^С7" &s>УъЬ Q -<3feУ* Таблица б.З, Набор микрокоманд


	Микрокоманд·	СУ микроопераций
	У,	**Уи1ЫЬУ»¥Уб***
	Уг	**Уз>Ут>УУ$***
	у»	**УчУ2>УУ»>У«>***
	У*	**У А, У У U***
	■ ■	У* У*

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

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

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

Уг

Уз

У*

У%

У*

Ут

У·

У»

Ум

Ун

с,

с.

с,

с.

с,

с_ъ

Су

^ίο

С_г

с»

с*.

с,

с_л

*·Ί0

с_е

с₃

с«

с,

c_s

с,

с_я

с.

с»

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

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

Объем вычислений можно сократить путем применения эвристических правил. Так, существенные МКН (или их подклассы) С_и С₂, С^, С₇ (см. табл. 6.4) должны входить в любое решение бета. Далее, если множество МКН в столбце у. является подмножеством множества МКН в столбце y_s то столбец y_s можно удалить из таблицы покрытий, так как микрооперация у. в любом случае покрывается меньшим числом МКН из столбца^ (говорят, что столбец^., доминирует над столбцом у ). Так, в табл. 6.4 столбец у_: доминирует над столбцами г/₇и у_1Р столбец у_г— над столбцом у₁₀, столбец у_ь — над столбцом у₅; следовательно, столбцы у₅, у₇, y_ia,y_nможно удалить из таблицы покрытий.

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


У.	У.	У*
с<	с.	*c_s*
с.	ч»	с*
		t-LO

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

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

Pi ** it'll *Ίι t"s» t'ti t'T» ''lOi· Pj ⁼ ί^Ίι *~Ί> ^3' *-'*> ^7· ^8' Ц)Г> Рз ^— (^It t-2' "3· ^5' ^Ί¹ Ц>1· Pi ⁼ {C-|, C2t Lj, Cj, C7, C(oJ.

Решение 6eTaj может быть избыточным, то есть некоторые микрооперации могут покрываться несколькими МКН C_ff принадлежащее бета j. Для нахождения требуемого mi ного решения необходимо для каждого избыточного решения 6eTaj.

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

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

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

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

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

Цикл выполнения микрокоманды Г_мк можно представить в виде трех этапов:

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

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

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

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

Структура МПА (рис. 6.22, а) с ФАМ и ПМП, связанными непосредственно друг с другом, не допускает совмещения этапов во времени — здесь этап ₊₁ начинается только после выполнения этапа Д(рис. 6.22, б).

Рис. 6.22. Построение МПА без совмещения: а — структурная схема; б— временная диаграмма обработки микрокоманд

В течение цикла Г_мк все узлы заняты обработкой только одной, текущей микрокоманды с номером i, причем последовательный характер обработки МКне позволяет достичь высокого быстродействия:

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