На этом уровне ЭВМ можно рассматривать как совокупность операционных устройств, каждое из которых предназначено для выполнения определенного набора операций F={f1, f2, …, fS}. Операции производятся над множеством входных слов A={a1, a2, …, aq} и множеством внутренних (промежуточных) слов R={r1, r2, …, rp}. Результатом выполнения операций является множество выходных слов C={c1, c2, …, сk}, то есть сi = fj (A U R). Операционное устройство (ОУ) можно представить в виде «черного ящика» следующим образом (рис.1.2).
Рис.1.2
Математик Глушков В.М. предложил любое операционное устройство рассматривать в виде композиции двух автоматов: операционного автомата (ОА) и управляющего автомата (УА) (рис.1.3), где: X={x1, x2, …, xn} – множество логических условий, Y={y1, y2, …, ym} – множество микроопераций.
Рис.1.3
Любая операция из множества F может быть реализована последовательностью элементарных операций называемых микрооперациями.
Микрооперация – это элементарное машинное действие, которое не может быть разбито на более простые составляющие и которое выполняется за один машинный такт.
Микрокоманда – это совокупность микроопераций, выполняемых одновременно в одном машинном такте, при выполнении микропрограммы.
Микропрограмма – это алгоритм выполнения машинной операции, описанный в терминах микроопераций и логических условий
УА предназначен для реализации микропрограммы, т.е. для формирования последовательности управляющих сигналов yi, которые инициализируют выполнение одноименных микроопераций в ОА.
ОА предназначен для хранения слов информации (множества A, R, C), выполнения микроопераций над этими словами и формирования значений логических условий xi.
ОА состоит из совокупности операционных элементов (ОЭ), которые объединяются в единую схему с помощью шин, используемых для передачи слов информации и электрических цепей для передачи двоичных сигналов управления. Шина является совокупностью электрически независимых цепей.
Операционные элементы
Каждый из операционных элементов ОЭ описывается:
1) хранимым или вычисляемым словом информации;
2) множеством реализуемых микроопераций;
3) множеством формируемых логических условий.
Основные типы операционных элементов
1. Управляемая шина для реализации микрооперации передачи слова информации. Условное обозначение управляемой шины и ее реализация из логических элементов изображены на рис.1.4. На условном изображении шина изображена в виде широкой стрелки, а цепь управления в виде тонкой стрелки.
Рис.1.4
2. Регистр для реализации микрооперации передачи и хранения слова информации. Регистр – это линейка триггеров, каждый из которых хранит один бит информации (0,1). На условном обозначении регистра (рис.1.5) микрооперация yi производит запись слова A длиной k разрядов в регистр. Значение первого разряда регистра определяет значение логического условия xj
Рис.1.5
3. Сдвигающий регистр служит для хранения слова информации и выполнения микрооперации сдвига над этим словом. На рис.1.6. представлен реверсивный регистр так как по микрооперации yp происходит сдвиг содержимого регистра на 1 разряд влево, а по микрооперации ys - сдвиг содержимого на 1 разряд вправо. Запись в регистр происходит по сигналу yf.
Рис.1.6
4. Счетчик предназначен для хранения слова информации и выполнения над ним микрооперации счета, которая состоит в изменении значения слова (состояния счетчика) на единицу. Счетчик, в котором реализуется микрооперация вида С=С+1 называется суммирующим, а счетчик, реализующий микрооперацию С=С-1 называется вычитающим. Счетчик, в котором реализуются обе микрооперации, называется реверсивным. Двоичный k – разрядный счетчик может находиться в 2k состояний. Значение 2k -1 – это максимальное значение, которое может содержать такой счетчик и называемое ёмкостью счетчика (рис.1.7).
Рис.1.7
Микрооперации: Логическое условие:
1, если СT = 0;
0, если СT ≠ 0.
|
y
o – обнуление СT: = 0;
yp –запись кода CT:= 2k -1; xj =
ya – прямой счет CT:= CT + 1;
yd – обратный счет CT:= CT - 1.
5. Комбинационные схемы, реализующие системы булевых функций. Примером использования типовых комбинационных схем в качестве операционных элементов являются дешифратор и комбинационный сумматор. Дешифратор предназначен для преобразования k-разрядного двоичного кода в n – разрядный двоичный унитарный код, т.е. в код содержащий одну единицу.
На рис.1.8. условное обозначение дешифратора на k входов, n выходов и таблица истинности, задающая полный дешифратор на 2 входа.
k=2
| n=4
| a1
| a2
| c1
| c2
| c3
| c4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.1.8
6. Комбинационный сумматор - это операционный элемент, предназначенный для выполнения микрооперации сложения чисел типа C= A + B (рис.1.9).
C = c1 c2 ... cn;
A = a1 a2 ... an;
B = b1 b2... bn.
p – вход переноса,
q – выход переноса
|
Рис.1.9
Комбинационный сумматор состоит из линейки одноразрядных сумматоров последовательно соединенных цепью переноса из младшего разряда сумматора в старший (рис.1.10).
Рис.1.10
Сложение чисел A и B сводится к поразрядному сложению одноименных разрядов слагаемых, т.е. qi ci = ai + bi + pi, i = 1, 2...n, где:
qi ci – двухразрядное двоичное число;
qi – значение переноса, которое вырабатывается в разряде i и переносится в разряд i – 1;
ci – разряд суммы;
ai и bi – одноименные разряды слагаемых;
pi – перенос из предыдущего младшего разряда т.е. pi = q i + 1, pn = 0.
Рис.1.11
Один разряд комбинационного сумматора можно рассматривать как комбинационную схему с двумя выходами: q, c и тремя входами: a, b, p.
Исходя из правил выполнения двоичного сложения двух целых двоичных чисел, составим таблицу истинности для системы из двух булевых функций q, c, зависящих от трех переменных a, b, p (рис.1.11).
Рис.1.12
Каждой функции q и c соответствуют карты Карно (рис.1.12). После минимизации соответствующих булевых функций, получаются следующие их минимальные дизъюнктивные формы:
q= a p ˅ a b ˅ b p;
c= a ˅ p ˅ a b p ˅ b .
Используя аксиомы и теоремы булевой алгебры можно представить последнею функцию в следующем виде:
c= (a ˅ b ˅ p) ˅ a b p, где: – инверсия q.
На рис.1.13 представлена схема, реализующая эти функции в булевом базисе и являющаяся схемой одного разряда комбинационного сумматора.
Рис.1.13
Накапливающий сумматор - это операционный элемент, предназначенный для выполнения микрооперации сложения чисел типа C=C + A и состоит из регистра и комбинационного сумматора (рис.1.14.).
Рис.1.14
Для описания микропрограмм используются следующие языки:
- язык графической схемы алгоритма (ГСА);
- язык логических схем алгоритма (ЛСА);
- язык матричных схем алгоритма (МСА).
Язык графической схемы алгоритма - это ориентированный граф с вершинами следующих типов:
– начальная операторная вершина, помеченная
символом начальной микрооперации y0;
|
– конечнaя операторная вершина, помеченная
символом конечной микрооперации yк ;
|
– условная вершина, помеченная символом
логического условия xj;
|
– операторная вершина, помеченная символом
микрооперации yi или микрокомандой;
|
Условия корректности ГСА:
- должен существовать путь из начальной вершины в любую другую операторную вершину, т.е. любая вершина должна быть достижима;
- должен существовать путь из любой операторной вершины в конечную вершину, т.е. не должно быть тупиковых вершин.
Достоинством ГСА является их наглядность, а недостатком – громоздкость.
На рис.1.15 приведен пример линейной ГСА, на рис 1.16 – разветвляющейся ГСА, на рис 1.17 – циклической ГСА.
Рис.1.15 Рис.1.16
Рис.1.17
Язык логических схем алгоритма – это строчная запись операторов алгоритма.
Операторы используются следующих типов:
Y0 - начальный оператор;
Yk - конечный оператор;
Yi - исполняемый оператор;
Хj - оператор логического условия, который снабжается открывающей и закрывающей полускобкой с индексом, определяющим соответствие между этими полускобками;
[ k - открывающая полускобка;
k ] - закрывающая полускобка.
Оператор логического условия выполняется следующим образом:
если Хj = 1, то следующим выполняется оператор стоящий после открывающей полускобки, если Хj = 0, то следующим выполняется оператор стоящий после соответствующей закрывающей полускобки.
Хj [ k ... k ]
Для задания безусловного перехода используется тождественно ложный логический оператор:
Oj [ m ... m ]
Запись линейного алгоритма (рис.1.15) на языке ЛСА имеет следующий вид:
Y0 Y1 ... Yк-1Yк.
Запись разветвляющегося алгоритма (рис.1.16) на языке ЛСА имеет вид:
Y0 Y1 X1 [ 2 X2 [ 3 Y4 O1 [ 4 3 ] Y3 O2 [ 5 2 ] Y2 5 ] 4 ] Yк.
Запись циклического алгоритма (рис.1.17) на языке ЛСА имеет вид:
Y0 1 ] Y1 X1 [ 2 Y3 O1 [ 3 . 2 ] Y2 3 ] X2 [ 1 Yк.
Условия корректности ЛСА: баланс открывающих и закрывающих скобок.
Достоинством ЛСА является компактность, а недостатком - отсутствие наглядности.
Язык матричных схем алгоритма - это квадратная матрица, строки которой отмечены индексами операторов от 0 до k – 1, а столбцы индексами от 1 до k. На пересечении i – той строки и j – того столбца записывается условие достижения j – того оператора из i – того оператора.
Запись линейного алгоритма (рис.1.15) на языке МСА представлена в табл. 1.1.
Таблица 1.1
| y1
| y2
| ...
| yk
|
y0
|
|
|
|
|
y1
|
|
|
|
|
.
|
|
|
|
|
yk-1
|
|
|
|
|
Начальная вершина микропрограммы помечена микрооперацией y0.
Безусловный переход из вершины, помеченной микрооперацией у0 в вершину, помеченную микрооперацией y1 определяется значением единицы в соответствующей клетке матрицы.
|
Запись разветвляющегося (рис.1.16) и циклического алгоритма (рис.1.17) представлены на языке МСА в табл. 1.2 и в табл. 1.3 соответственно.
Таблица 1.2 Таблица 1.3
| y1
| y2
| y3
| y4
| yk
|
y0
|
|
|
|
|
|
y1
|
| x1
| x1 x2
| x1 x2
|
|
y2
|
|
|
|
|
|
y3
|
|
|
|
|
|
y4
|
|
|
|
|
|
| y1
| y2
| y3
| yk
|
y0
|
|
|
|
|
y1
|
| x1
| x1
|
|
y2
| x2
|
|
| x2
|
y3
| x2
|
|
| x2
|
Условия корректности МСА:
- отсутствие пустых строк и столбцов;
- в каждой строке значение дизъюнкции конъюнкций логических условий, записанных в клетках этой строки, должна быть тождественно равно единице.
Эти два условия одновременно проверяют достижимость операторных вершин и отсутствие тупиковых вершин.
Достоинство: удобство хранения в памяти компьютера и возможность использования аппарата матричной алгебры.
Недостаток: громоздкость при большом количестве операторов и отсутствие наглядности.