Ответы на вопросы экз

41. Содержательные и закодированные гса

Граф-схемой алгоритма (ГСА) называют ориентированный связанный граф, содержащий одну начальную вершину (А₀), одну конечную (А_k) и произвольное конечное множество операторных (A = {a₁, ..., a_k-1}) и условных (P = {p₁, ..., p_f}) вершин. Данные вершины изображены на рисунке 5.4 под буквами а, б, в и г соответственно.

Рисунок 5.4 – Типы вершин ГСА

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет, как и показано на рисунке. Начальная и операторная вершины имеют только по одному выходу, а условная - два выхода, помеченных символами 1 и 0. Конечная вершина выходов не имеет.

При построении ГСА должна удовлетворять следующим условиям:

1. Входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода к входу;

2. Каждый выход соединен точно с одним входом;

3. Любой вход соединяется, по крайней мере, с одним выходом;

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

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

6. В каждой условной вершине записывается один из элементов множества X = {x₁, ..., x_L}, называемого множеством логических условий. Запись одинаковых элементов множества X в различных условных вершин разрешается;

7. В каждой операторной вершине записывается оператор (микрокоманда) Y_t - подмножество множества Y = {y₁, ..., x_N}, называемого множеством микроопераций. Y = {y_t1, ..., y_tu, ..., y_tU}; y_tU  Y, u = 1, ..., U_t. При U_t = 0 Y_t = , Разрешается также запись в различных операторных вершинах одинаковых подмножеств множества операций.

Оператор или микрокоманда – совокупность микроопераций, выполняемых одновременно за один такт. Микрооперации, выполняемые совместно (одновременно) в течении одного такта называются совместимыми микрооперациями.

Микрокоманду, состоящую из пустого множества микроопераций обозначают символом Y₀. Реализация такой микрокоманды равносильна отсутствию выполнения каких-либо элементарных операций. В случае синхронных дискретных устройств микрокоманду Y₀ удобно интерпретировать как пропуск как пропуск такта, когда не поступают никакие сигналы от устройства управления к операционному устройству.

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

Для записи функциональных микропрограмм используется язык функционального микропрограммирования (Ф - язык).

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

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

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

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

Основным элементом информации, с которым оперирует Ф – микропрограмма, является слово. Наименование и формат слова задаются в следующем виде C(П₁:П₂), где С – идентификатор; П₁ и П₂ – номера старшего и младшего двоичных разрядов слова. Разряды слова номеруются направо неотрицательными целыми числами n₁>0, n₂>0, n₁<n₂. Одноразрядное слово состоит только из идентификатора С.

Совокупность слов, имеющих одинаковую длину, может объединятся в массив. Массив описывается в следующем виде: M[m₁:m₂](n₁:n₂), где M – идентификатор массива; m₁,m₂ – границы номеров слов, составляющих массивов, причем m₁<m₂; n₁,n₂ – номера старшего и младшего разрядов слова.

В зависимости от способа использования значений выделяют следующие типы слов:

Входные слова – значения присваиваются вне микропрограммы и используются внутри микропрограммы.
Внутренние – значения присваиваются и используются только внутри микропрограммы.
Вспомогательные – значения присваиваются и используются только внутри микропрограммы, но существуют не постоянно, а только в течении такта автоматного времени (типа А).
Выходные – значения присваиваются в микропрограмме и используются вне ее (типа О).

Двоичное выражение определяет правило вычисления двоичного значения путем выполнения операций над первичными двоичными значениями. Константы записываются в следующем виде 1100₂, 14₈, 12₁₀, С₁₆.

Первичные двоичные значения, слова и поля – объединяются в двоичное выражение с помощью двоичных операций, к которым относятся обычно следующие операции:  - инверсия,  конкатенация,  - конъюнкция, -дизъюнкция, + - сложение, - - вычитание,  - сложение по модулю 2.

Примерами двоичных выражений являются следующие конструкции:

А; В(0);  А; С+1; С+А(1:15); С+11₂ А(1:15)+1.

Последнее выражение вычисляется в следующем порядке – вначале инвертируются разряды 1-15 слова А  А(1:15); затем формируется составляющее значение 11₀ А(1:15); выполняется сложение с С составным значением С+11₂ А(1:15); и последняя сумма складывается с 1.

В синтаксическом смысле микрооперация – это оператор присваивания, посредством которого слову присваивается значение двоичного выражения. Микрооперация состоит из левой части, знака присваивания (:=) и двоичного выражения в правой части.

Все микрооперации подразделяются на семь классов:

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

Микрооперация передачи – обеспечивает присваивание слову значение другого слова (А:=В). Микрооперация сдвига служит для изменения положения разрядов слова по отношению к начальному пути перемещения каждого разряда на k позиций влево или вправо. Операции сдвига обозначаются следующим образом:

Rh(A) – удаление из двоичного выражения А k младших правых разрядов, то есть сдвиг на k разрядов вправо.

Lk(A) – удаление из двоичного выражения A k старших левых разрядов, то есть сдвиг на k разрядов влево.

Бинарные логические микрооперации присваивают слову значение, получаемое поразрядным применением микроопераций , ,  к парам соответствующих разрядов слагаемых. Например, С:=АВ.

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

Функция операционного автомата сводится к вводу – выводу и хранению слов информации, выполнению микроопераций и вычислению логических условий. Набор элементов, на основе которых могут строиться структуры с определенным свойствами, называется структурным базисом. Структурный базис операционных автоматов должен содержать элементы, обеспечивающие передачу и хранение слов информации и вычисление значений функций, на основе которых строятся микрооперации и логические условия. Для этих целей наиболее широко используем следующий набор элементов:

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

Рассмотрим в качестве примера содержательную ГСА, описывающую устройство сложения двоичных чисел с использованием обратного кода. Sm=A+B (рис. 2.5).

После построения содержательной ГСА логические условия и микрооперации кодируются символами x₁, ..., x_L и y₁, ..., y_N соответственно.

Условия переходов (из условных вершин).

x₁: signSm;

x₂: signRg;

x₃:переполнение?.

Микрооперации (из операторных вершин):

y₁: Sm:=A;

y₂: Rg:=B;

y₃: Sm:=[Sm]_обр;

y₄: Sm:=Sm+[Rg]_обр;

y₅: Sm:=Sm+Rg;

y₆: PP:=1.

Микрокоманды и соответствующие им микрооперации:

Y₁={ y₁, y₂};

Y₂={ y₃};

Y₃={ y₄};

Y₄={ y₅};

Y₅={ y₆}.

Затем строится закодированная ГСА, в которой микрооперации и условия заменены идентификаторами (рис.5.6).

Рисунок 5.5 – Содержательная ГСА

Рисунок 5.6 – Закодированная ГСА

Содержание