Операционные устройства вычислительных машин (стр. 1 )

Глава 7.

Операционные устройства вычислительных машин

В классической фон-неймановской ВМ функция арифметической и логической обработки данных возлагается на арифметико-логическое устройство (АЛУ). Учи­тывая разнообразие выполняемых операций и типов обрабатываемых данных, ре­ально можно говорить не о едином устройстве, а о комплексе специализирован­ных операционных устройств (ОПУ), каждое из которых реализует определенное подмножество арифметических или логических операций, предусмотренных сис­темой команд ВМ. С этих позиций следует выделить:

- ОПУ целочисленной арифметики;

- ОПУ для реализации логических операций;

- ОПУ десятичной арифметики;

- ОПУ для чисел с плавающей запятой.

На практике две первых группы обычно объединяются в рамках одного операци­онного устройства. Специализированные ОПУ десятичной арифметики в совре­менных ВМ встречаются достаточно редко, поскольку обработку чисел, представ­ленных в двоично-десятичной форме, можно достаточно эффективно организовать на базе средств целочисленной двоичной арифметики. Таким образом, будем счи­тать, что АЛУ образуют два вида операционных устройств: целочисленное ОПУ и ОПУ для обработки чисел в формате с плавающей запятой (ПЗ).

В минимальном варианте АЛУ должно содержать аппаратуру для реализации лишь основных логических операций, сдвигов, а также сложения и вычитания чисел в форме с фиксированной запятой (ФЗ). Опираясь на этот набор, можно программным способом обеспечить выполнение остальных арифметических и логических операций как для чисел с фиксированной запятой, так и для других форм представления информации. Следует, однако, учитывать, что подобный вариант не позволяет добиться высокой скорости вычислений, поэтому по мере расширения технологических возможностей доля аппаратных средств в составе АЛУ постоянно возрастает.

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

По форме записи оператор этапа — это оператор присваивания, в котором:

- слева от знака присваивания указывается наименование результата действий, выполненных на этапе;

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

Исходной информацией для первого этапа служит хранящийся в счетчике ко­манд адрес Аki, текущей команды Кi. Процесс выборки команды отображается опе­ратором первого этапа: Кi:= BK(AKj).

Адрес Аki, обеспечивает также второй этап, результатом которого является адрес следующей команды Аki+1, поэтому оператор второго этапа имеет вид: AKi+1 := ФАСК(Аki). В качестве исходных данных для третьего этапа машинного цикла выступают содержащиеся в коде текущей команды способ адресации CAi (он определяет конк­ретную модификацию ЦФ-ФИАО) и код адресной части Аi. Результатом стано­вится исполнительный адрес операнда Аисп := ФИА(САi, Аi).

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

Оi :=ВО(Аисп).

Результат исполнения операции P0j, получаемый на пятом этапе машинного цик­ла, зависит от кода операции 2-й команды K0ni (определяет модификацию ЦФ-ИО), кода первого операнда Oi и кода второго операнда — результата предыдущей (i-1)-й операции РОi-1: РОi := ИО(Копi, Оi, РОi-1).

В соответствии со структурой граф-схемы этапов все команды ВМ можно раз­делить на три типа:

- команды типа «Сложение» (Сл);

- команды типа «Запись» (Зп);

- команды типа «Условный переход» (УП).

Типовые граф - схемы этапов представлены на рис. 6.1.

Видно, что количество этапов в командах типа «Сл» (см. рис. 6.1, а) колеблется от трех (для непосредственной адресации НА) до пяти. При непосредственной адресации второй операнд записан в адресной части команды, поэтому нет необходимости в реализации устройством управления целевых функций ЦФ-ФИ А, ЦФ-ВО. Количество этапов для команд типа «Зп» постоянно и равно четырем (см. рис. 6.1, б) здесь отсутствует необходимость в ЦФ-ВО. Машинный цикл команд типа «УП» состоит из трех этапов (см. рис. 6.1, в), поскольку здесь, помимо выборки операнда, можно исключить и этап ФАСК — действия, обычно выполняемые на этом этапе, фактически реализуются на этапе ИО.

Рис 7.1 • Динамика изменения соотношения между аппаратной и программной реализациями

функций АЛ У

На рис. 7.1 показана динамика изменения соотношения между аппаратной и программной реализациями функций АЛУ по мере развития элементной базы вычислительной техники. Здесь подразумевается, что по вертикальной оси откла­дывается календарное время.

Структуры операционных устройств

Набор элементов, на основе которых строятся структуры различных ОПУ, назы­вается структурным базисом. Структурный базис ОПУ включает в себя:

- регистры, обеспечивающие кратковременное хранение слов данных;

- управляемые шины, предназначенные для передачи слов данных;

- комбинационные схемы, реализующие вычисление функций микроопераций

и логических условий по управляющим сигналам от устройства управления.

Используя методику, изложенную в [21], можно синтезировать ОПУ с так на­зываемой канонической структурой, являющуюся основополагающей для синте­за других структур. Такая структура образуется путем замены каждого элемента реализуемой функции соответствующим элементом структурного базиса. Кано­ническая структура имеет максимальную производительность по сравнению с дру­гими вариантами структур, однако по затратам оборудования является избыточной. С практических позиций больший интерес представляют два иных вида структур ОПУ: жесткая и магистральная.

Операционные устройства с жесткой структурой

В ОПУ с жесткой структурой комбинационные схемы жестко распределены между всеми регистрами. К каждому регистру относится свой набор комбинационных схем, позволяющих реализовать определенные микрооперации. Пример ОПУ Жесткой структурой, обеспечивающего выполнение операций типа «сложение», приведен на рис. 7.2.

В состав ОПУ входят три регистра со своими логическими схемами:

- регистр первого слагаемого РСл1 и схема ЛРСл1;

- регистр второго слагаемого РСл2 и схема ЛРСл2;

- регистр суммы РСм и схема комбинационного сумматора См.

Рис. 7.2. Операционное устройство с жесткой структурой

Логическая схема Л РСл2 реализует микрооперации передачи второго слагаемого из РСл2 на левый вход сумматора:

- прямым кодом ЛСм := РСл2 (по сигналу управления ВхРСл2);

- инверсным кодом ЛСм := ->РСл2 (по сигналу управления В1-РСлЗ);

- со сдвигом на один разряд влево ЛСм := 1Л(РСл2 • 0) (по сигналу управлений

L1PCл2)

Логическая схема ЛРСл1 обеспечивает передачу результата из регистра РСм

в регистр РСл1:

- прямым кодом РСл1 := РСм (по сигналу управления ПгРСл1);

- со сдвигом на один разряд влево РСл1 :=L1(РСм.0) (по сигналу управления L1РСм)

- со сдвигом на два разряда вправо РСл1 := R2(s • s • РСм) (по сигналу управления R1PCм).

Комбинационный сумматор См предназначен для суммирования (обычного или

по модулю 2) операндов, поступивших на его левый (ЛСм) и правый (ПСм) входы.

Результат суммирования заносится в регистр РСм: РСм := ЛСм + ПСм (по сигналу

управления П2РСм) или РСм := ЛСм © ПСм (по сигналу управления П2М2РСм).

Моделью ОПУ с жесткой структурой является так называемый I-автомат,

с особенностями синтеза которого можно ознакомиться в [21, 25].

Аппаратные затраты па ОПУ с жесткой структурой Сж можно оценить по вы-

ражению

где N — количество внутренних слов ОПУ; n1.....пN — длины слов; n = (n1+ ...nN)

— средняя длима слова; kij. — количество микроопераций типа j =1,2,...К (сложе

ние, сдвиг, передача и т. п.), используемых для вычислений слов с номерами

i=1,2,…,N; Ст — цена триггера; Cj — цена одноразрядной схемы для реализации микрооперации j-ro типа.

В приведенном выражении первое слагаемое определяет затраты на хранен

n-разрядных слов, второе — на связи регистров с комбинационными схемами,

331

а третье - суммарную стоимость комбинационных схем, реализующих микрооперации К типов над N словами.

Затраты времени на выполнение операций типа «сложение» в ОПУ с жесткой структурой равны

где tв— длительность микрооперации выдачи операндов из регистров; tс — продолжительность микрооперации «сложение»; tп — длительность микрооперации приема результата в регистр.

Достоинством ОПУ с жесткой структурой является высокое быстродействие, недостатком — малая регулярность структуры, что затрудняет реализацию таких ОПУ в виде больших интегральных схем.

Операционные устройства с магистральной структурой

В ОПУ с магистральной структурой все внутренние регистры объединены в отдельный узел регистров общего назначения (РОН)', а все комбинационные схемы— в операционный блок (ОПБ), который зачастую ассоциируют с термином

«арифметико-логическое устройство».

Операционный блок и узел регистров сообщаются между собой с помощью

магистралей — отсюда и название «магистральное ОПУ».

Пример магистрального ОПУ представлен на рис. 7.3.

Рис. 7.3. Магистральное операционное устройство

В состав узла РОН здесь входят N регистров общего назначения, подключаемых к магистралям А и В через мультиплексоры MUX А и MUX В. Каждый из мультиплексоров является управляемым коммутатором, соединяющим выход одного из РОН с соответствующей магистралью. Номер подключаемого регистра определяется адресом а или Ь, подаваемым на адресные входы мультиплексора из устройства управления.

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

По магистралям А к В операнды поступают на входы операционного блоки, к которым подключается комбинационная схема, реализующая требуемую микрооперацию (по сигналу управления из УУ). Таким образом, любая микрооперация ОПБ может быть выполнена над содержимым любых регистров ОПУ. Результат микрооперации по магистрали С заносится через демультпплексор DMX С и конкретный регистр узла РОН. Демультиплексор представляет собой управляемый коммутатор, имеющий один информационный вход и N информационных выходов.

Вход подключается к выходу с заданным адресом с, который поступает на адресные входы DMX С из УУ.

Моделью 0ПУ с магистральной структурой является М-автомат. М-автоматом

называется модель ОПУ, построенная па основе принципа объединения комбинационных схем и реализующая а каждом такте только одну микрооперацию. Синтез М-автоматов рассматривается и [22].

Используя обозначения, введенные в предыдущем разделе, выражение для оценки аппаратных затрат на магистральное ОПУ можно записать в следующем виде:

где первое слагаемое определяет затраты на N регистров, второе — затраты на связи узла РОН и ОПБ, а третье — суммарную цену ОПБ.

Из сопоставления выражении для затрат следует, что магистральная структура экономичнее жесткой структуры, если

где

— количество микроопераций, реализуемых ОПУ с жесткой структурой.

С учетом последнего неравенства можно сформулировать следующее сильней

условие экономичности магистральных структур:

M>N + K.

Затраты времени на сложение в магистральных ОПУ больше, чем в ОПУ с жесткой структурой:

где tмих – задержка на подключение операндов из РОН к ОПБ; tDMX — задержи

на подключение результата к РОН.

Основным достоинством магистральных ОПУ является высокая универсальность и регулярность структуры, что облегчает их реализацию на кристаллах ИС. Вообще говоря, магистральная структура ОПУ в современных ВМ является превалирующей.

Классификация операционных устройств с магистральной структурой

Магистральные ОПУ классифицируют по виду и количеству магистралей, организации узла РОН, типу ОПБ.

Магистрали ОПУ могут быть однонаправленными и двунаправленными, соответственно обеспечивающими передачу данных в одном или двух различных направлениях. Типичным режимом работы магистрали является разделение времени,

при котором магистраль используется для передачи функционально разнотипных

данных в различные моменты времени.

По функциональному назначению выделяют:

- магистрали «внешних связей, соединяющих ОПУ с памятью и каналами ввода/

вывода ВМ;

- внутренние магистрали ОПУ, отвечающие за связь между узлом РОН и операционным блоком.

Количество магистралей внешних связей зависит от архитектуры конкретной ВМ и обычно не превышает двух для внешних связей и трех — для внутренних.

Структура трехмагистрального ОПУ представлена на рис. 7.4, а), а соответствующая ему микропрограмма выполнения операции типа «сложение» — на рис. 7.4, б).

Рис. 7.4. Трехмагистральное ОПУ: а — структура; б — микропрограмма сложения

Данный вариант характеризуется наибольшим быстродействием: выборка операндов из РОН, выполнение микрооперации суммирования и запись результата

в РОН — все эти действия производятся за один такт. Основной недостаток трех-

магистральной организации — большая площадь, занимаемая магистралями на кристалле БИС (от 0,16 до 0,22 от площади кристалла).

Двухмагистральная организация при меньшей площади, покрываемой магистралями (от 0,06 до 0,19 от площади кристалла), требует введения как минимум одного буферного регистра (БР), предназначенного для временного хранения одного из операндов (рис. 7.5, а), при этом операция сложения будет выполняться уже за два такта (рис. 7.5, б):

- Такт 1: загрузка БР одним из операндов.

- Такт 2: выполнение микрооперации в ОПБ над содержимым БР и одного из

РOH; запись результата в РОН.

Наконец, организация ОПУ на основе только одной магистрали (рис. 7.6, а)

минимизирует расходы площади (от 0,03 до 0,09 от площади кристалла).

В одномагистральном ОПУ, вместе с тем, возникает необходимость введения не менее двух буферных регистров БР1. БР2. и длительность операции возрастает

до трех тактов (рис. 7.6, б):

Рис, 7.5. Двухмагистральное ОПУ: а — структура; б — микропрограмма сложения

Рис. 7.6. Одномагистральное ОПУ: а — структура; б — микропрограмма сложения

- Такт 1: загрузка БР1 одним из операндов.

- Такт 2: загрузка БР2 вторым операндом.

- Такт З: выполнение микрооперации в ОГЩ над содержимым БР1 и БР2; запись результата в один из РОН.

Организация узла РОН магистрального операционного устройства

Количество регистров в узле РОН магистрального ОПУ обычно превышает тот минимум, который необходим для реализации универсальной системы операций. Избыток регистров используется:

- для хранения составных частей адреса (индекса, базы);

- в качестве буферной, сверхоперативной памяти для повышения производительности ВМ за счет уменьшения требуемых пересылок между основной памятью и ОПУ.

Количество регистров колеблется в среднем от 8 до 16, иногда может достигав 32-64. В процессорах с сокращенным набором команд количество РОН доходит до нескольких сотен. 1

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

В входу узла подключается один демультиплексор, а к выходу — один мультиплексор. Во втором случае доступ осуществляется с помощью двух демулътиплексоров и (или) двух мультиплексоров. Двухканальный доступ повышает быстродействие 0ПУ - так как позволяет обратиться параллельно к двум регистрам.

Организация операционного блока магистрального операционного устройства

Тип операционного блока (ОПБ) определяется способом обработки данных. Различают ОПБ последовательного и параллельного типа.

В последовательном операционном блоке (рис. 7.7) операции выполняются побитово, разряд за разрядом.

Рис. 7,7. Последовательный операционный блок

Бит переноса, возникающий при обработке 1-го разряда операндов, подается на вход ОПБ и учитывается при обработке (i+1)-го разряда операндов. Результат побитово заносится в выходной регистр, предыдущее содержимое которого перед этим сдвигается па один разряд. Таким образом, после n циклов в выходном регистре формируется слово результата, где каждый разряд занимает предназначенную для него позицию.

При параллельной организации операционного блока (рис. 7.8) всё разряды операндов обрабатываются одновременно. Внутренние переносы обеспечиваются схемой ОПБ. Более подробно возможности организации переносов рассматриваются позже.

Рис. 7.8. Параллельный операционный блок

Микрооперация Пi обеспечивает передачу результата на магистраль С без сдвига. Пo ходу микрооперации R, результат сдвигается на один разряд вправо, при этом в освобождающийся старший разряд заносится значение с внешнего контакта SL, а выдвигаемый (младший) разряд сумматора посылается внешний контакт 5R.

В микрооперации L, результат сдвигается на один разряд влево. Здесь в освобождающийся младший разряд заносится значение с внешнего контакта SR, а выдвигаемый (старший) разряд См передается на внешний контакт SL.

Базис целочисленных операционных устройств

Для большинства современных ВМ общепринятым является такой формат с фиксированной запятой (ФЗ), когда запятая фиксируется справа от младшего разряда кода числа. По этой причине соответствующие операционные устройства называют целочисленными ОПУ. В форме с ФЗ могут быть представлены как числа без знака, когда все n позиций числа отводятся под значащие цифры, так и со знаком. В последнем случае старшим (n-1)-й разряд числа занимает знак числа (0 —плюс, 1 — минус), а под значащие цифры отведены разряды с (n - 2)-го по 0-й.

При записи отрицательных чисел используется дополнительный код, который для числа N получается по следующей формуле:

Если исключить логические операции, которые рассматриваются отдельно, целочисленное ОПУ должно обеспечивать выполнение следующих арифметических

операций над числами без знака и со знаком:

- сложение/вычитание;

- умножение;

- деление.

Сложение и вычитание

На рис. 7.10 приводятся примеры сложения целых чисел, представленных в дополнительном коде (напомним, что при сложении в дополнительном коде знаковый разряд участвует в операции наравне с цифровыми).

Рис. 7,10. Примеры выполнения операции сложения в дополнительном коде:

а, б, в, г — сложение без возникновения переполнения;

д, е — сложение с переполнением

При сложении - разрядных двоичных чисел (бит знака и n-1 значащих цифр)

возможен результат, содержащий n значащих цифр. Эта ситуация известна как переполнение. «Лишний» бит занимает позицию знака, что приводит к некорректности результата. Естественно, что ОПУ должно обнаруживать факт переполнения и сигнализировать о нем. Для этого используется следующее правило: ее»-

суммируются два числа и они оба - положительные или оба отрицательные, Переполнение имеет место тогда и только тогда, когда знак результата противоположен знаку слагаемых. Рисунки 7.10,3 и 7.10, е показывают примеры переполнения, Обратим внимание, что переполнение не всегда сопровождается переносов

из знакового разряда.

Рис. 7.11. Примеры выполнения операции вычитаний в дополнительном коде: а, б, s, г — вычитание без возникновения переполнения; д, е — вычитание с переполнением J

Вычитание выполняется в соответствии с правилом: для вычитания одного числа (вычитаемого) из другого (уменьшаемого) необходимо взять дополнение вычитаемого и прибавить его к уменьшаемому. Под дополнением здесь понимается вычитаемое с противоположным знаком, представленное в дополнительном коде.

Вычитание иллюстрируется примерами (рис. 7.11). Два последних примера (см. рис. 7.11,д и 7.11,е) демонстрируют ранее рассмотренное правило обнаружения переполнения.

Чтобы упростить обнаружение ситуации переполнения, часто применяется так

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

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

Рис. 7.12. Примеры выполнения операции сложения в модифицированном дополнительном коде: а, б — переполнения нет; в, г — возникло переполнение

На рис. 7.13 показана возможная структура операционного блока для сложения и вычитания чисел со знаком в формате с фиксированной запятой. Центральным звеном устройства является n-разрядный двоичный сумматор. Операнд А поступает на вход сумматора без изменений. Операнд В предварительно пропускается через схемы сложения по модулю 2, поэтому вид кода В, поступающего на другой вход сумматора, зависит от выполняемой операции. Если задана операция сложения (управляющий код 0), то результат на выходе ОПБ определяется выражением S=A+B. При операции вычитания (управляющий код 1) на вход сумматора подаются инверсные значения всех разрядов В, и, кроме того, на вход переноса в младший разряд сумматора СIN поступает 1. В итоге на выходе ОПБ будет S= A + B + 1,что соответствует прибавлению к А числа В с противоположным знаком, то есть вычитанию.

Рис. 7.13. Структура операционного блока для сложения и вычитания

На рис. 7.13 не показана схема формирования признака переполнения V, который согласно описанным ранее правилам определяется логическим выражением

Целочисленное умножение

По сравнению со сложением и вычитанием, умножение — более сложная операция, как при программном, так и при аппаратном воплощении. В ВМ применяются различные алгоритмы реализации операции умножения и, соответственно, несколько схем построения операционных блоков, обеспечивающих выполнение операции умножения.

Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения Р двух

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

ЧП упрощается — если цифра множителя bi, равна 0, то Wi тоже равно 0, а при Ьi=1 частичное произведение равно множимому (Wi = А). Перемножение двух n-разрядных двоичных чисел Р=АхВ приводит к получению результата, содержащего

2n битов. Таким образом, алгоритм умножения предполагает последовательное

выполнение двух операций — сложения и сдвига (рис. 7.14). Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Согласно данной схеме, устройство умножения предполагает наличие регистров множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига, если операция сдвига не реализована иным способом, например за счет «косой» передачи данных между узлами умножителя.

Рис. 7.14. Общая схема умножения со сдвигом суммы частичных произведений влево или вправо

В зависимости от способа получения суммы частичных произведений (СЧП),

возможны четыре варианта реализации «традиционной» схемы умножения [10|:

1. Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведении вправо п при неподвижном множимом.

2. Умножение, начиная со старших разрядов множителя, при сдвиге суммы частичных произведений влево и неподвижном множимом.

3. Умножение, начиная с младших разрядов множителя, при сдвиге множимого влево и неподвижной сумме частичных произведении.

4. Умножение, начиная со старших разрядов множителя, со сдвигом множимого вправо и при неподвижной сумме частичных произведений.

Варианты со сдвигом множимого на практике не используются, поскольку для их реализации регистр множимого, регистр СЧП и сумматор должны иметь разрядность 2n, поэтому остановимся на вариантах 1 и 2. Первый из них назовем алгоритмом сдвига вправо, а второй — алгоритмом сдвига влево.

Умножение чисел без знака

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

Алгоритм сдвига вправо

Алгоритм сводится к следующим шагам:

1. Исходное значение суммы частичных произведений принимается равным нулю.

2. Анализируется очередная цифра множителя (анализ начинается с младшей

цифры). Если она равна единице, то к СЧП прибавляется множимое, в противном случае (цифра равна нулю) прибавление не производится.

3. Выполняется сдвиг суммы частичных произведений вправо па один разряд.

4. Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя.

Процедура умножения иллюстрируется примером вычисления произведения

10x 11 (рис 7.15).

Рис. 7.15. Пример умножения со сдвигом суммы частичных произведений вправо

Алгоритм может быть реализован с помощью схемы, показанной на рис. 7.16.

Рис. 7.16. Схема устройства умножения по алгоритму правого сдвига

Первоначально множимое и множитель заносятся в n-разрядные регистры множимого (РМн) и множителя (РМт) соответственно, а все разряды 2n-разрядного

регистра суммы частичных произведений (РЧП) устанавливаются в 0. Умножение происходит за n шагов. На каждом шаге, в зависимости от состояния младшего

Разряда регистра множителя, управляющего мультиплексором, на один из входов n-разрядного сумматора подается либо множимое, либо 0. На второй вход поступает содержимое n старших разрядов РЧП. Новое частичное произведение из сумматора пересылается в старшие разряды РЧП. Далее содержимое РЧП сдвигается на один разряд вправо, причем в освободившийся старший разряд регистра заносится значение переноса из старшего разряда сумматора. Поскольку мультиплексор управляется младшим разрядом РМт, то содержимое этого регистра также сдвигается на один разряд вправо. Описанная последовательность повторяется n раз. Более экономичным в плане аппаратуры является иное решение, когда вместо двух регистров — n-разрядного РМт и 2/7-разрядного РЧП — используется один комбинированный 2n-разрядный регистр (показан на рис 7.16 справа). Множитель первоначально заносится в младшие n разрядов этого регистра, а старшие разряды обнуляются. По мере сдвигов вправо младшие, уже проанализированные разряду множителя выталкиваются из регистра, освобождая место для очередной цифры СЧП. Обычно такой регистр строится из двух n-разрядных регистров, объединенных цепями сдвига. Дополнительно отметим, что если очередная цифра множителя равна 1, то для вычисления суммы ЧП требуются операции сложения и сдвига, а при нулевой цифре множителя в принципе можно обойтись без сложения, ограничившись только сдвигом. Это, естественно, требует некоторого видоизменения схемы.

Алгоритм сдвига влево

Процедура традиционного умножения со сдвигом влево включает в себя следующие шаги:

1. Исходное значение суммы частичных произведений принимается равным нулю.

2. Анализируется очередная цифра множителя (анализ начинается со старшей цифры). Если она равна единице, то к СЧП прибавляется множимое, в противном случае (цифра равна нулю) прибавление не производится.

3. Выполняется сдвиг суммы частичных произведений влево на одни разряд.

4. Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя.

На рис. 7.17 приведен пример умножения со сдвигом влево (10 х 11).

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

К преимуществу алгоритма сдвига влево следует отнести то, что он позволяет совмещать во времени операции сложения и сдвига. Однако, по сравнению с алгоритмом сдвига вправо, он имеет и ряд недостатков. В первую очередь, СЧП и множитель не могут совместно использовать один и тот же регистр. Для реализации алгоритма требуется 2n-разрядный сумматор. Кроме того, схема со сдвигом влево неудобна при выполнении умножения над числами с разными знаками.

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

Рис. 7.17. Пример умножения со сдвигом суммы частичных произведений влево

Рис, 7.18. Схема устройства умножения по алгоритму левого сдвига

Умножение чисел со знаком

Несколько сложнее обстоит дело с умножением чисел со знаком, когда n-разрядные сомножители содержат знак (в старшем разряде слова) ия-1 значащую цифру. В дальнейшем условимся отделять знаковый разряд точкой, не забывая, однако, что знаковый разряд участвует в операции наряду с цифровыми разрядами.

Наиболее очевидная мысль — получить абсолютные значения операндов и перемножить их как числа без знака. Справедливость такого решения видна из примера, приведенного на рис. 7.19, где показан процесс умножения чисел +13 и +10.

Во всех ВМ общепринято представлять числа со знаком в форме с фиксированной запятой в дополнительном коде. Положительные числа в этом представлении не отличаются от записи в прямом коде, а отрицательные записываются в виде

2n -х, где x — фактическое значение числа. В двоичной системе запись отрица
тельного числа в дополнительном коде сводится к инвертированию всех цифровых разрядов числа, представленного в прямом коде, и прибавлению единицы к младшему разряду получившегося после инвертирования обратного кода. По этой причине более предпочтительны варианты, не требующие преобразования сомножителей и обеспечивающие вычисления непосредственно в дополнительном коде.

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

Множимое произвольного знака,

множитель положительный

Пример для положительных сомножителей (А > О, В > 0) уже был рассмотрен.

В случае отрицательного множимого процедура умножения протекает аналогично, с учетом сделанного замечания об арифметическом сдвиге СЧП, что подтверждает пример, приведенный на рис. 7.20.

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

Множимое произвольного знака,

множитель отрицательный

Так как множитель отрицателен, он записывается в дополнительном коде:

[В]д = 2n – |В|, и в цифровых разрядах кода будет представлено число 2n-1-|В|.

При типовом умножении (как и случае В > 0) получим Р = А х (2n-1 - |В|)=

= -|В|х A+ A х 2n-1. Псевдопроизведение Р больше истинного произведения P

Рис. 7.20. Умножение чисел при отрицательном множимом и положительном множителе

на величину А х 2n-1, что и необходимо учитывать при формировании окончательного результата. Для этого перед последним сдвигом из полученного псевдопроизведения необходимо вычесть избыточный член. На рис. 7.21 и 7.22 приведены примеры умножения положительного и отрицательного множимого на отрицательный множитель, в которых видна упомянутая коррекция результата.