Разметка граф-схемы алгоритма

Цель разметки — распределение микрокоманд микропрограммы по ячейкам памяти. При разметке каждой вершине граф-схемы алгоритма (см. рис. 4.27) операции умножения двоичных чисел за исключением начальной поставим в соответствие микрокоманду. Микрокоманды МК1, МК2, МК3,… будем хранить в ячейках управляющей памяти. Для обращения к ячейкам воспользуемся естественной адресацией, при которой различают операционные и управляющие микрокоманды. Тип микрокоманды зависит от значения одноразрядного поля признака П: значению П = 0 соответствует операционная микрокоманда, значению П = 1 — управляющая микрокоманда. Операционная микрокоманда выполняется операционным автоматом под управлением сигналов {уА} или микрокоманд У, У2, У3. Управляющая микрокоманда предназначена для реализации условных переходов в соответствии со значениями проверяемых условий X, Х2. При разметке граф-схемы алгоритма в каждую вершину вносится следующая информация: • записываются одна из микрокоманд микропрограммы и ее адресный код. Номер микрокоманды и соответствующий ему адрес ячейки памяти проставляются согласно алгоритмической последовательности выполнения операции умножения;

• • фиксируется состояние операционного автомата (ОА). В операторных вершинах проставляется операционная микрокоманда (У, У2 или У3), которую выполняет ОА. В условных вершинах ОА не выполняет микрокоманд, поэтому ставится прочерк «-» ;
• • фиксируется состояние управляющего автомата (УА), определяемое блоком микропрограммного управления (БМУ). В операторной вершине выполняется безусловный переход (БП), в условной вершине — условный переход (УП), поэтому делаются соответствующие записи и указывается, по какому условию Хх или Х2 выполняется управляющая команда.

Основная трудность распределения адресов ячеек памяти обусловлена наличием условных переходов. Для упрощения схемной реализации БМУ будем исходить из того, что при условном переходе альтернативные микрокоманды располагаются в двух соседних ячейках памяти, причем если логическое условие Xi = 0, то выполняется микрокоманда с адресом А, указанным в поле адреса; если логическое условие А?'. = 1, то выполняется микрокоманда с адресом А + 1.

Размеченные по указанному правилу граф-схемы алгоритмов приведены на рис. 4.30. Рассмотрим принципы составления микропрограммы и построения схем управляющей памяти и БМУ управляющего автомата.

Составление микропрограммы. Микропрограмма составляется в соответствии с размеченной граф-схемой алгоритма (рис. 4.30) и представляется в виде таблицы (табл. 4.14).

Таблица 4.14

Алгоритм.

Адрес ячейки памяти.

Микрокоманда микропрограммы.

№МК.

поле адреса.

поле условий перехода.

поле управляющих сигналов.

Ф.

Ф.

МК1.

Ф.

Ф.

мкз.

Ф.

Ф.

МК4.

МК5.

МК2.

Окончание операции умножения.

МК6.

Ф.

Ф.

МК1.

МК2.

МКЗ.

Окончание операции умножения.

МК4.

Ф.

Ф.

МК5.

Ф.

Ф.

МК6.

Проиллюстрируем на примере алгоритма 2 принципы составления микропрограммы.

В ячейку с адресом 000 помещаем МК1, которая в О, А выполняет загрузку, предусмотренную управляющими сигналами уv у2 (или микрокомандой Yx), а в БМУ управляющего автомата (УА) — безусловный переход (БП) к ячейке с адресом 001 (см. рис. 4.30, алгоритм 2).

В ячейке 001 располагаем МК2, которая в ОА не предусматривает никаких действий, а в УА определяет условный переход по условию Х2: при Х2 = 0 переход в следующую ячейку с адресом 0010, при Х2 = 1 — к ячейке 011, где хранится МК4 для продолжения программы после выполнения операции умножения.

Микрокоманда МКЗ в ячейке 010 также не предусматривает действий в ОА и предназначена для осуществления перехода по условию X: при X, = 0 переход к ячейке 100, при X, = 1 — к ячейке с адресом 0101, где соответственно хранятся МК5 и МК6.

Микрокоманда МК5 выполняет в ОА действия, предусмотренные управляющими сигналами у~ yv, а в БМУ — безусловный переход к ячейке с адресом 001.

Микрокоманда МК6 предусматривает в ОА действия У2, а в БМУ — безусловный переход к ячейке 100 (МК5).

При отсутствии проверки логических условий П = 0 значения ПХ2 и nXj могут быть любыми (Ф = 0 или 1).

Для наглядности на рис. 4.31, а показано размещение микрокоманд микропрограммы в ячейках памяти с адресами в десятичной системе счисления. Возможны.

Рис. 4.30. Размеченные граф-схемы алгоритмов умножения двоичных чисел для составления микропрограммы.

другие размещения микрокоманд в памяти (см., например, рис. 4.31, б). Важно, чтобы пары микрокоманд Х2, К (Конец) и У3, Y2 располагались в соседних ячейках.