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

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

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

Часто это соотношение записывают так:

ᾳ≡ A (mod р) .

Для представления чисел в СОК необходимо выбрать т. н. систему основа­ний— множество целых чисел р^, р₂,р_п. Тогда любое число А может быть представлено в СОК следующим образом:

А = (а_х,а₂,...,а_п), (3.35)

где а = A (mod р). Обозначим произведение

Можно показать [1], что если все основания p_t — взаимно-простые числа, то между числами 0, 1, 2,(Р-\) и числами, представленными в СОК соглас­но (3.35), имеет место взаимно-однозначное соответствие.

Пример 3.30

Пусть р_х = 3, Pi = 5, рз = 7 — взаимно-простые числа. р = 3-5-7 = 105.

Представим в СОК несколько десятичных чисел:

Заметим, что при выходе за пределы диапазона [0, (P-l)] нарушается взаим­но-однозначное соответствие между представлением чисел в позиционной системе счисления и СОК. Действительно.

0 = 105 = 210 = ... = (mod 3), (mod 5), (mod 7);

1 = 106 = 211 = ... = (mod3), (mod 5), (mod 7)

и т. д. Очевидно, для расширения диапазона представления чисел в СОК сле­дует увеличить число и/или значения оснований.

3.12.2. Арифметические операции с положительными числами

Рассмотрим правила выполнения операций сложения и умножения в СОК в случае, если оба операнда и результат операции находятся в диапазоне

[о,р).

Пусть

при этом в качестве цифры результата берется наименьший остаток

Действительно, на основании (3.33) можно написать

Из представления А к В следует, что

где kj и /, — целые неотрицательные числа. Тогда

Учитывая (3.39), получим

Следовательно

что и доказывает (3.38).

Рассмотрим несколько примеров, иллюстрирующих приведенные выше пра­вила.

Пример 3.31

Выполним сложение чисел, представленных в СОК. Результат— на рис. 3.39.

Обратите внимание, если результат выходит за пределы допустимого диапа­зона (А + В>Р), то в СОК он неотличим от А + В-Р (путем весьма слож­ных ухищрений можно обнаружить переполнение суммы в СОК [1]).

Пример 3.32

Выполним умножение чисел, представленных в СОК. Результат— на рис. 3.40.

Операция вычитания в общем случае в СОК не определена, т. к. в СОК от­сутствуют отрицательные числа. Однако в частных случаях, когда А, В, (А-В) в [О, Р), можно записать

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

Пример 3.33

Рассмотрим вычитание А-В для случаев А>В. Результат— на рис. 3.41.

3.12.3. Арифметические операции с отрицательными числами

Если необходимо оперировать отрицательными числами, можно ввести т. н. искусственные формы представления чисел в СОК. Выражение (3.36) опре­деляет диапазон представления чисел в СОК с основаниями р\, р₂,р„. Пусть одно из оснований системы равно 2, например, для определенности А = 2.

Обозначим через h величину

Будем оперировать числами, лежащими в диапазоне 0 < |7V| < h.

Примем в качестве нуля число h и будем представлять положительные числа N = |V| в виде N' = h + \N\, а отрицательные числа N = -\N\ в виде

N' = h-\N\. Тогда при алгебраическом суммировании получим следующий вид представления положительных и отрицательных чисел:

N' = h + N.

Это означает, что в принятом представлении мы всегда будем иметь дело с положительными числами, однако числа в искусственной форме N' в интер­вале [О, й) будут отображать отрицательные числа, а в интервале [h, Р) — положительные.

ГЛАВА 4

Организация устройств ЭВМ

4.1. Принцип микропрограммного управления

Для выполнения операций над информацией используются операцшш ные устройства— арифметико-логические, управления, контролл! ;ры ВУ и т. п. Функцией операционного устройства является выполнение заданного множества операций F = {/j, /₂,/_к} над входными сла­вами из множества D_x с целью вычисления выходных слов из мно­жества D₀, представляющих результаты операций D_Q-f_k(l\), * = 1,

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

принципе микропрограммного управления, который состоит в следующем [7|:

1. Любая операция f_k, реализуемая устройством, рассматривается как слож

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

2. Для управления порядком следования микроопераций используются логи ческие условия, которые, в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "истина" или "ложь" (1 или 0).

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

4. Микропрограмма используется как форма представления функции устрой­ства, на основе которой определяются структура и порядок функциониро­вания устройства во времени.

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

4.2. Концепция операционного и управляющего автоматов

В функциональном и структурном отношении операционное устройство, входящее в состав ЭВМ, удобно представить разделенным на две части: опе­рационный и управляющий автоматы (рис. 4.1).

Операционный автомат (OA) служит для хранения слов информации, вы­полнения набора микроопераций и вычисления значений логических усло­вий, т. е. операционный автомат является структурой, организованной для выполнения действий над информацией. На вход OA подаются входные дан­ные D_l, которые в соответствии с алгоритмом операции преобразуются в выходные данные D_Q. Кроме того, OA вырабатывает множество {х} осведо­мительных сигналов (логических условий) для управляющего автомата. Управляющий автомат (УА) генерирует последовательность управляющих сигналов {у}, обеспечивающую выполнение в операционном автомате задан­ной последовательности элементарных действий, которая реализует алгоритм выполняемой операции. Управляющая последовательность генерируется в соответствии с заданным алгоритмом и с учетом значений логических усло­вий х, формируемых OA.

Часто операционное устройство может выполнять несколько различных опе­раций (например, арифметико-логическое устройство может выполнять четыре арифметических действия и несколько логических операций над вход­ными словами). В этом случае на вход УА поступает команда С, опреде­ляющая тип выполняемой операции. Кроме того, поскольку различные опе­рации над различными данными выполняются за разное время, УА формиру­ет сигнал g, отмечающий окончание операции и готовность выходных данных.

Таким образом, любое операционное устройство— процессор (который обычно, в свою очередь, представляют состоящим из двух операционных устройств: АЛУ — арифметико-логического устройства и ЦУУ — централь­ного устройства управления), канал ввода/вывода, контроллер внешнего уст­ройства — можно представить как композицию операционного и управляю­щего автоматов. Операционный автомат, реализуя действия над словами информации, является исполнительной частью устройства, работу которого организует управляющий автомат, генерирующий необходимые последова­тельности управляющих сигналов.

Такой подход позволяет разработать эффективные процедуры синтеза OA и УА, формализовать эти процедуры и, в некоторых случаях, автоматизировать процесс синтеза цифровых устройств.

4.3. Операционный автомат

Исходным для разработки структуры операционного автомата (OA) явля­ются:

□ описание входных и выходных слов OA (множеств D_l и D₀);

□ список множества операций из F, которые должны выполняться над словами.

Процесс разработки OA, таким образом, следует начинать с определения форматов входных и выходных слов и разработки алгоритмов выполнения операций в терминах слов и стандартных действий над словами (сложение, копирование, инверсия, сдвиг и т. д.). Разработанные алгоритмы удобно представить в форме граф-схемы алгоритма (ГСА).

Далее необходимо разработать структуру OA. Операционный автомат стро­ится на базе операционных и логических элементов. Предложенные процеду­ры формального синтеза OA [7] не получили широкого распространения; обычно используют т. н. "содержательный" метод синтеза.

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

чтобы обеспечить реализацию всех действий, предусмотренных в оператор­ных вершинах ГСА.

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

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

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

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