Жмакин А.П. Архитектура ЭВМ (2006) (1186252), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Итак, процесс разработки OA можно представить состоящим из следующих этапов:

1. Определение форматов входных и выходных данных (слов).

2. Разработка ГСА выполняемых операций.

3. Разработка структуры OA — выбор элементов и организация связей.

4. Определения множества {у} микроопераций, выполняемых в OA.

5. Определения множества {х} логических условий, формируемых в OA.

4.3.1. Пример проектирования операционного автомата АЛУ

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

Определение форматов данных

Будем считать, что в арифметической операции деления участвуют операн­ды А — делимое и В — делитель. Результат операции С — частное. Кроме того, устройство должно формировать признаки результата — двоичные пе­ременные:

□ Z — признак нулевого результата;

□ S — признак отрицательного результата;

□ OV — признак переполнения.

Алгоритм операции алгебраического деления разрабатываются для 16-раз­рядных двоичных чисел с фиксированной запятой, представленных в прямом коде. Знак числа кодируется в старшем (нулевом) разряде числа, запятая фик­сирована после знакового разряда, таким образом, все числа могут быть только дробными (рис. 4.2).

Итак, в операциях участвуют следующие переменные:

□ А = a₀a_]a₂...a_l5 —первый операнд (делимое);

□ В = b_Qb\b₂—b\s — второй операнд (делитель);

□ С = с₀с_хс₂...с₁₅ — результат операции (частное), в процессе выполнения алгоритма переменная С используется для хранения остатка;

□ D = d_Qd_xd₂...d_X5 — переменная, в которой в процессе деления накаплива­ются цифры частного;

□ a₀, Ь₀, с₀ —знаковые разряды.

Разработка алгоритма деления

В прямых кодах удобнее делить модули чисел. Знак результата не зависит от соотношения модулей делимого и делителя и определяется по выраже­нию (4.1).

с₀ = a_Qb_Q v а₀Ь₀. (4.1)

Деление чисел с фиксированной запятой в заданном формате невозможно, если модуль делимого не меньше модуля делителя. Поэтому сначала следует проверить соотношение операндов путем вычитания делителя из делимого. Если разность окажется положительной, то можно формировать признак пе­реполнения OV = 1 и завершать операцию. В противном случае модуль част­ного оказывается меньше 1, т.е. переполнение отсутствует и деление воз­можно.

Алгоритмы деления с восстановлением остатка и без восстановления ос­татка подробно рассмотрены в разд. 3.9. Учитывая приведенный там срав­нительный анализ алгоритмов, выберем метод деления без восстановления остатка.

ГСА деления без восстановления остатка представлена на рис. 4.3. Алго­ритм предусматривает формирование знака результата согласно формуле (4.1) и сохранение его временно в переменной s. После этого производится деление модулей чисел (знаки операндов обнуляются).

Сначала производится пробное вычитание делителя из делимого. Поскольку чнаки операндов — 0, то появление 1 в знаковом разряде разности означает, что А < В, и можно продолжать деление (целая часть частного равна 0).

При с₀ = 0 деление невозможно — формируется признак переполнения.

13 процессе получения цифр частного значение очередного остатка принимает переменная С. Независимо от знака остатка она копируется в переменную А, которая затем увеличивается вдвое путем сдвига влево на один разряд. В зависимости от знака переменной С (знака остатка) формируется очеред­ная цифра переменной D (частного) и принимается решение о действии на следующем шаге — добавлять или вычитать делитель из сдвинутого остатка. После арифметической операции выполняется сдвиг влево частного D (ос­вобождается место для очередной цифры частного), изменяется счетчик цифр частного и проверяется условие выхода из цикла — получение шестнадцати цифр частного, включая самую первую цифру — "0 целых", на место которой копируется знак частного из переменной s .

Разработка структуры операционного автомата

Анализ алгоритма деления (см. рис. 4.3) позволяет разработать структуру операционного автомата. Учитывая действия, которые требуется выполнить для реализации алгоритма, включим в состав операционного автомата сле­дующие элементы:

□ два шестнадцатиразрядных регистра Рг А и Рг В для хранения входных операндов и промежуточных результатов, причем регистр ?гА должен обеспечить возможность сдвига своего содержимого влево;

□ шестнадцатиразрядный регистр Рг С для размещения результата арифме­тической операции сложения или вычитания (в нашем случае в этом реги­стре формируется остаток): в конце операции в нем будет размещен ре­зультат — частное;

□ шестнадцатиразрядный регистр Рг D с возможностью левого сдвига кода для размещения частного в процессе его формирования;

□ шестнадцатиразрядный двоичный параллельный сумматор/вычитатель Сум/Выч;

□ четырехразрядный вычитающий счетчик Сч п по модулю 16 для подсчета цифр частного;

□ триггер переполнения Тг OF для хранения признака переполнения разряд­ной сетки;

□ триггер знака Тг s для временного хранения знака частного;

□ схема сравнения на "равно" знаковых разрядов исходных операндов;

□ дешифратор DC "О" нулевой комбинации в разрядах С[1 : 15], формирую­щий признак нулевого результата Z.

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

Таблица 4.1. Список микроопераций и логических условий

Таблица 4.1 (окончание)

Внимательно посмотрим на рис. 4.4. Очевидно, любые действия, обозначен­ные в операторных вершинах алгоритма, приведенного на рис. 4.3, могут быть реализованы на разработанной нами структуре (см. рис. 4.4).

Теперь определим, какая последовательность микроопераций должна быть реализована в разработанной структуре, чтобы выполнилась операция деле­ния, предусмотренная алгоритмом рис. 4.3. Простейшее решение— сохра­нить топологию графа алгоритма и заменить содержимое его операторных вершин на соответствующие микрооперации, а содержимое условных вер­шин — на соответствующие логические условия.

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

При проектировании цифровых устройств обычно стремятся достичь макси­мальной скорости их работы. Один из путей достижения этой цели — парал­лельное (во времени) выполнение некоторых операций. Поэтому при преоб­разовании графа алгоритма в граф микропрограммы следует объединять в одной операторной вершине те микрооперации, которые могут быть в данной структуре выполнены одновременно с учетом реализуемого алгоритма. Со­вокупность микроопераций, выполняемых одновременно в один такт дис­кретного времени, называется микрокомандой.

Например, анализируя ГСА рис. 4.3, можно отметить, что операторы а₀ := 0; Ь₀ := 0 можно выполнить в структуре, изображенной на рис. 4.4, одновре­менно. То же можно сказать о паре операторов D := L\(D); п:=п-\ и неко­торых других. В то же время, операторы А :- С, А:= L\(A) нельзя выполнять

одновременно. (Для ускорения этой процедуры можно передавать информа­цию из С в А со сдвигом: C:=L\(A), но это уже будет другая структу­ра OA.)

Проанализировав с этой точки зрения исходный алгоритм, получим микро­программу, приведенную на рис. 4.5. Микропрограмма определяет, в какой последовательности и в зависимости от каких условий должны выдаваться микрокоманды, чтобы реализовалась операция деления на разработанной структуре (см. рис. 4.4) операционного автомата.

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

4.4. Управляющий автомат

Исходным для проектирования управляющего автомата (УА) является мик­ропрограмма, представленная, например, в форме ГСА.

Различают два класса управляющих автоматов [2, 7]:

□ с "жесткой" логикой:

• автомат Мура;

• автомат Мили;

• С-автомат;

□ с программируемой логикой.

4.4.1. Управляющий автомат с "жесткой" логикой

Автоматы с "жесткой" логикой проектируются как обычные конечные струк­турные автоматы [2, 7, 8].

Сначала необходимо перейти от ГСА микропрограммы к графу автомата, для чего следует:

1. Разметить исходную микропрограмму.

2. Построить по размеченной микропрограмме граф автомата.

Далее реализуются стандартные процедуры синтеза структурного автомата, заданного графом:

□ кодирование алфавита входных и выходных символов автомата двоичны­ми кодами;

□ кодирование внутренних состояний автомата;

□ выбор элемента памяти (типа триггера);

□ построение автоматной таблицы переходов;

□ синтез комбинационной схемы, реализующей функцию переходов КСх 1;

□ синтез комбинационной схемы, реализующей функцию выходов КСх 2.

Процедура разметки микропрограммы ставит в соответствие символам со­стояний автомата (а₁, а₂,..., а_м) некоторые объекты микропрограммы.

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

Для автомата Мура разметка выполняется по следующим правилам [2]: П символом а, отмечается начальная и конечная вершина ГСА;

□ различные операторные вершины отмечаются разными символами со­стояний;

□ все операторные вершины должны быть отмечены.

Для автомата Мили разметка выполняется по следующим правилам [2]:

□ символом а_х отмечается вход вершины, следующей за начальной, а также вход конечной вершины;

□ входы всех вершин, следующих за операторными, должны быть отмечены символами состояний;

□ если вход вершины отмечается, то лишь одним символом;

□ входы различных вершин, за исключением конечной, отмечаются различ­ными символами.

Пример проектирования УАЖЛ

Рассмотрим пример построения управляющего автомата Мура для устрой­ства, реализующего операцию деления. Операционный автомат (см. рис. 4.4) и ГСА микропрограммы (см. рис. 4.5) этого устройства были построены ранее.

Шаг 1. Выполним разметку микропрограммы. Для этого сопоставим каждой операторной вершине ГСА в произвольном порядке (например, слева напра­во и сверху вниз) символ состояния автомата из множества {а₂,а^,а₁₄). Начальную и конечную вершины сопоставим с начальным состоянием авто­мата а_х. Такая разметка показана на рис. 4.5.

Шаг 2. Построим граф автомата, заданного размеченной микропрограм­мой, которую получили на предыдущем шаге. Для этого вершины графа со­поставим с состояниями автомата iah &2 »•••> °14- Соединим ориентирован­ными ребрами те пары вершин графа, между которыми на ГСА микропрограммы существуют переходы, причем пометим ребра графа соответствую­щими условиями перехода. Если переход между двумя операторными вер­шинами микропрограммы осуществляется безусловно, то условие перехода па ребре графа — константа 1.

Построив таким образом граф, мы фактически задаем алфавиты внутренних состояний и входных символов и определяем функцию переходов. Для зада­ния алфавита выходных символов и функции выходов (для автомата Мура функция выходов зависит только от его состояний) следует сопоставить каж­дой вершине автомата в качестве выходного символа содержимое соответст­вующей операторной вершины ГСА микропрограммы. Таким образом, полу­чим граф микропрограммного автомата, который приведен на рис. 4.6.

Шаг 3. Кодирование алфавитов входных и выходных символов автомата дво­ичными кодами. Алфавит входных символов составляет множество двоичных переменных X = {х_],х₂,х^}, поэтому проблема кодирования входных симво­лов двоичными переменными здесь не стоит. Что касается кодирования сим­волов выходного алфавита, то отложим обсуждение этого вопроса до шага 8.

Шаг 4. В процессе кодирования внутренних состояний автомата могут ре­шаться проблемы исключения гонок в автомате, проблемы минимизации комбинационной схемы, обеспечивающей функцию переходов автомата. Для решения этих задач разработаны достаточно сложные алгоритмы, которые описаны в литературе, например, [2, 5]. Здесь мы не будем касаться этой сто­роны процедуры синтеза автомата.

Характеристики

Список файлов книги