Савельвев А.Я. Основы информатики

Подождите немного. Документ загружается.

Ускорение операции умнолсеиия

Анализ произвольного количества разрядов множителя. Идея ме-

тода состоит в том, что выявляются последовательности нулей или единиц

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

если встречается гругиш вида ...0100...О, то проводится сразу сдвиг на к

разрядов и прибавление множимого в сумматор. Если анализируется груп-

па ...1100...О, то проводится сдвиг на к разрядов и вычитается множимое

из содержимою сумматора. При анализе группы разрядов вида ...0011,.,1

проводится замена ее на новую группу вида ...100... I , что означает вычи-

такие множимого на первом шаге, сдвиг на к разрядов и анализ группы

следующих разрядов, образовавшейся после преобразования. Такой метод

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

обладающего возможностью одновременного сдвига на произвольное ко-

личество разрядов.

Конечтк), если бы числа состояли из достаточно длинного ряда по-

следовательпосгей О или I, то такой метод дал бы высокий эффект в

смысле с()крап;Еения времени на обработку. Однако, как правило, в раз-

рядах чаще чередуются О или I. Это значит, что в подобных случаях

paccMoipcmiMii выше мегод не дает никакого эффекта. Поэтому он мо-

жет бьпь применен только в комбинации с обычными методами после-

довательно! о умножения.

Умножение в cHcietvie счнслення с основанием q

2 .В некоторых

машинах ЕС ЭВМ использовался переход на новое основание системы

счисления вида q = 2 , за счет чего удается существеиио сократить время

выполнения операции умножения.

Пусть ^ = 4 ; это означает, что числа представляются в шестнадцате-

ричнои системе счисления. При этом с помощью приема, аналогичного

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

множителя, можно анализировать сразу тетраду (четыре двоичных разря-

да):

рассмагриваются текущая цифра (тетрада) множителя и его предыду-

щая цифра (тетрада). В зависимости от значений цифры множителя в пре-

дыдущем разряде (равна или больше восьми, т. е. равен или нет единице

ciapnuui рачряд геграды) проводятся разные действия (табл. 5.9). Для реа-

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

А.

увеличивая ею в I, 2, 3 и 6 раз.

131

Умно.исеиие

чисел на двоичных сумматорах

Анализ четырех двоичных разрядов одновременно дает возможность

сразу осуществить сдвиг на четыре двоичных разряда.

Таб л

а а

5,9

Лналшируемая

цифра

(Л)

К)

(Я) 11

(О 12

т 13

(£)14

(Г)15

Анализируемая

течрада

0000

0001

ООН)

ООП

0100

0101

оно

0111

1000

1001

1010

1011

1100

1101

1110

1111

Действия на еуммаюре при значении ирелылу|11сй цифры

+ 1/1

+2.4

+3/1

+(2/( + 2/0

ЩА+2А}

+6/1

+(6/i+l/()

+(6,4 + 2/1)

-(1/1 + 6/1)

-6/1

-(3/( + J/l)

-(2/1 + 2Л)

-3.4

-2/1

-Ы

+ Ы

+2.4

+3/1

+(2.4 + 2/1)

+(2/1+ ЗЛ)

+ЬЛ

+(6Л+1.4)

+(6/1+2/1)

-(6/1+1/1)

-6Л

-(3,4*2,1)

-(2.4 + 2,4)

-3,1

-J4

-1.4

Так как при операции умножения необходимо складывать и вычитагь

коды,

то потребуется сумматор дополнительного или обратного кода.

Пример

5.9.

Умножить

два

числа /) =

0,0001101

В~0.О000МК)

олнонремепным

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

Решение,

Для

умножения потребуются числа: Л =

О.СЮОО!

101,

2А=

О.ОООНОШ.

зл^о.ооюот.

6/1

0.01001110.

Множитель Представляется в дополнительном коде [Я|д

1,1 И ЮОШ,

^^-^

Шаг

Анализ первой цифры множителя для

2^ (прелылушая цифра равна иулк»)-

6з=0010 —на основании таблицы 5.9 надо вызвать множимое

+2/1

0,00011010

nairpa-

вить его в сумматор. Содержимое сумматора станет

0,0001

iOiO.

!32

Матричные методы умножения

Hi ii

2 Лпали! вюрой цифры множителя (предыдущая цифра меньше восьми):

/?^

= Т i ! I - - на основании таблицы 5,9 надо вызвать множимое -

/1,

= i.ti i

iOO!

I . сдвинуть

ею на че1ырс разряда влево и направить в сумматор, где проволшсн следующее дейс(вис-

0,00011010

1.00110000

Ответ /I/? = -0,101 iOi 10.

5.8. Матричные методы умножения

Сущее

гиует

ряд методов умножения, основанных на суммировании фупп

часгных произведений с последующим объединением сумм вместе с пер^нсюа-

ми ты получения произведения. Например, четные произведения фуппируюг-

ся по три и подаются па входы цепочки сумматоров. Выходы цепочки суммато-

ров подключаются к регистрам, запоминающим отдельно получившиеся сумму

и переносы в

дру1

ие группы. Выходы этих регистров объединяются в группы по

1ри и !юдключа10тся уже к другим сумматорам. В конце цепочки складываиэтся

голько сумма и пе}>еносы Д1!я слагаемых. Такая раздельная обработка промежу-

точных сумм и перепсюов требует так называемого «дерева сумматоров». По-

доГ)И1,п1

мсюдумпожсиня использован в вымислпгельпых машинах IBM-360.

tymeciRyior пжже ускоренные методы умножения, основанные на ис-

нолыоиапии м;прип (громсжуточных результатов. Рассмотрим схему ум-

можеиия пл примере двух пятиразрядных чисел:

А - a5«4"3"2^i

a^h^a^h^a^h^ajh^ciyh^

С = с,.

')гу схему умножения можно представить также в виде матрицы

(lafui. 5.10).

Каждый элемент э'юй матрицы равен О или 1. Произведение двух чисел

можно HOjryiHrb, если суммировать элементы матрицы в следующем порядке:

a^h, а,Ь, a,hi

а.Ь,

a.h,

133

—

л,

л.

1>1

Л.

5 Умнп

и^

аф,

о, 6;

о,*,

а А

аф.

жение чисел на

двоичных сумматорах

а,

а^

оА

^^2

a,h,

"Л

а,)\

а^

а,Ь,

")*1

аф.

а,Ь,

аг^\

a^bj

"2^3

а,Ь,

аф.

а б

.1 и

ц 3

аф.

аф,

"!^

аф.

"!*,

5.10

Так как при суммировании но столбцам складываются только О и I,

операнию сложения можно выполнить с помощью счегяиков. Однако при

значигельном числе разрядов сомножителей потребуются счетчики с боль-

шим количес7вом входов и выходов, что существенно увеличивает время

суммирования. Но этот принцип умножения можно реализовать таким об-

разом,

что количество входов счетчиков на каждом этапе будет не больше

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

полусумматоры и сумматоры.

Наиболее известны среди матричных алгоритмов умножения алго-

ритмы Дадда, Уоллеса, матричный и ajuopnTM с сохранением перено-

сов.

На рис. 5.4 представлена структурная схема множительного уст-

ройства для реализации матричного алгоритма, а на рнс. 5.5 — схема, с

noMouibio которой может быть реализован алгоритм Дадда. Как видно

из рисунков, алгоритмы отличаются друг от друга не только i руппи-

ровкон частных произведений, но и количеством ступеней преобразо-

вания:

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

равно четырем, т. е, на единицу меньше числа разрядов сомножи1елен,

а для алгоритма Дадда — трем. Но с другой стороны, группировка раз-

рядов но методу Дадда требует более сложного устройства управления

операцией умножения.

Реализация матричных методов выполнения операции умножения тре-

буег большего количества оборудования, чем методов последовательного

анализа разрядов или групп разрядов множителя и дает больший выигрыш

во времени. Однако в связи с широким развитием микроэлектронных и

особенно больших интегральных схем (БИС) ограничения но количеству

оборудования становятся все менее строгими, поэтому рассмотренные вы-

ше методы применяют на практике.

134

5.8 Матричные методы

умио.жения

a^bf agb,

Ojbg

О/^Ь,

а^Ь^

a^b, a,bf a,b, a,b,

гВ

FLffJ f~Gi] rtO

1-1SM Pp-ISMli

I-

riHrr&

Сумматор

III

I i I

P^/V fi ^ Pe Pi

Рис. 5.4. C"i рук1ур11ая схема матричного умножителя

a,i,

a fig

дЖ

Oj'j

a,i.

ff,6,

Ofis

Рис. 5.5.

1'гр>к!урпая

схема М1Гожи1ельмого

\с1роиства

laiioMHiiamieM переносов

135

\мн(}.ж-€ние

чисел иа двоичных сумматорах

5.9. Методы параллельного умножения с нснользованнем

итеративных структур

Время,

затрачиваемое на выполнение операции умножения, можно су-

щественно уменьшить, воспользовавшись методами параллельного умноже-

ния.

Конечно, методы последовательного выполнения операции обеспечива-

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

множество задач, для решения которых отводится весьма мало времени. Э^го

задачи,

выполняемые с использованием метода быстрого преобразования

Фурье, матричные задачи и другие задачи, решаемые в реальном масштабе

времени.

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

сложнее и дороже устройств, построенных на традиционных методах умно-

жения,

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

структур'. При этом очень широко используются так называемые ячеистые

(cetUilar) или итеративные элементы. По сун^еству, с помоп1ью итсроишных

элементов гшраллельно образуются несколько частных произведений с соог-

вегствующими весовыми коэффициентами, которые тут же суммир) югся, и

определяется полное произведение.

Типовой итеративный элеменг (ТИЭ) представлен на рис. 5.6*. Функ-

ционально ТИЭ может состоять из схемы U и полного сумматора SM с со-

ответствующими входами для множимого А, множителя В, нредыдун(С1о

частного произведения

S^_^

и переноса из младшею разряда С, ((', пе-

ренос в старший разряд).

Таким образом, на ТИЭ реализуются следуюгцие операции:

' -' ' ' ' (3,15)

Параллельный умножитель для четырехразрядных двоичных чисел

представлен на рис. 5.7. Каждый ТИЭ, представленный в cipyKiype на

рис. 5.7, служит для получения одного частного произведения, к которому

прибавляются частные произведения, имеющие одинаковый с ним весовой

коэффициент. Полученная сумма 5, подается на следующий элемент того

же веса, а перенос С, — на соседний слева элемент.

В первой советской ЭВМ «Стрела» было реализовано г1араллелыюе миожигельпое >с!-

ройстио. осгговапиое па комбиианиоипых схемах, что по

ICM

прсмеиам являлос!, ncpwioni.iM

ретепием.

Наибольший вклад в создание и разработку итеративных crp>Kiyp внесли американ-

ские специалисты Дж, Спришер. И. Алфке. Д. Лграваль и др.

136

5 9 Методы параллельного

умно.ж-е/шя

с использованием итеративных структур

S'i.f Ay

с,

Рис. 5.6. Схема типового итеративного элемента

Рис. 5.7. i 1араллельный умножитель \

Достоинство игератив1гых лот ических струтстур состоит и в том, что они

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

Основттая TTpoGjTCMa, решаемая при проектировании итеративных

структур с ттомощьто технологии интегральных схем, состоит в том, сколь-

ко функциоиа1тьных элементов можно разместить на одноти кристалле. По-

этому первьте итеративттые структуры были реализованы на кристаллах,

вмещавших 4x2 двоичттых разряда (бита). Развитие технологии производ-

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

кр11с1а1тле структуры тта 16x16 битов и более.

137

Умиож'ение

чисел на двоичных сумматорам

5.10. Систолический метод вычислении

Сущность систолического метода вычислений состоит в том, что в

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

через параллельные магистрали подобно тому, как сердце перекачивает

кровь но системе кровообращения»'. В традиционных процессорах и ите-

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

ственный процессорный элемент. Систолические процессоры содержат

динамические перестраиваемые матрицы элементов, которые принимают

потоки данных и пропускают каждый поток через определеннуго магист-

раль,

содержащую отдельные процессоры. Изменять информационные

магистрали в систолических процессорах значительно проще, чем в дру-

гих параллельных структурах.

'itti,

Г%'п)

Ml!)

ЧгДг

1^11

'oj/A»)

4l/V

'02,

Ьг,)

Рис.

5.8. Схема систолических вычислений

Рассмотрим работу систолического метода на примере перемножения

двух двумерных матриц 3x2 и 2x2. Необходимая для этого гфимера сис-

толическая структура представлена на рис. 5.8, «, б. Элементы матрицы Л

поступают слева сверху, а матрицы В — справа сверху. Стрелками покача-

ны направления движения информации. Обработка матриц осуществляется

несколькими последовательными шагами. Все ячейки этой структуры рабо-

тают одновременно. На рис. 5.8, а показан третий шаг процесса перемно-

жения матриц. На этом шаге получено произведение «,, -бц (нижняя час1ь

верхнего элемента), оно будет сложено с произведением «,2

•/'21'

элементы

Название метода дано его создателем проф

MejfJiOHa(Cl-UA).

X. Т. Куном из Универси!е1а KopneiH-

138

Задание для самоконтроля

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

получила никакой информации. На рис, 5.8, б показан четвертый шаг, в ре-

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

риц С|| =а^2 •/'21 +'^11 '^i\-

В^*^**

процесс занимает шесть шагов. Сложение и

перемножение символов матриц продолжается до тех пор, пока все симво-

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

символы матрицы-результата.

Задание для самоконтроля

иеремпожи1ь на сумматоре прямого кода числа Л = -0,1100011

В=:-0,ШП10К

Псремиожигь в обратном и дополнительном кодах числа

А =

-0,1

i и

-0,1 i

11ра)браюнаи. мпожигель

-0,11001 П

01011

в избьпочпую двоичную систему

(О,

Перемножить

но

способу одновременного анализа двух разрядов множителя числа

/1 = 0,1100011101

и 5

--0,110010001

а) начиная

младших разрядов;

б)

начиная

со

старших разрядов.

Перемножит!, комбинированным методом

одновременным анализом произвольного

количесгиа разрядов множителя числа Л

--0,100000001

0,011001110.

6. 11еремножи1ь числа

=0,11001101

В = 0,1(КЮ1100, использовав промежуточную

систему счисления

с q -

2'*

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

Персмножигь числа /1=0,110П01

В = 0,1000111, используя формулу АВ = 2АВ/2,

если

В -

четное;

АВ-

2А{В-\)/2

если В— нечетное.

8. Умножигь числа

= O.fOOiOl• 2^

В =0,110001-2"', если задана разрядность: семь

двоичных разрядов

со

знаком для мантиссы

четыре двоичных разряда

со

знаком

для по-

рядка

139

6. ВЫПОЛНЕНИЕ ОПЕРАЦИИ ДЕЛЕНИЯ ЧИСЕЛ

НА ДВОИЧНЫХ СУММАТОРАХ

6.1,

Методы деления двоичных чисел

Деление двоичных чисел во многом аналогично делению десжичнььч

чисел. Процесс деления состоит в том, что последовательно разряд за разря-

дом отыскиваются цифры чш;тного путем подбора с последующим умноже-

нием этой цифры на делитель и вычитанием

это!

о произведения из делимого.

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

рим наиболее распространенные.

Прюжде всего это — «школьный» алгоритм деления,

заключаюН;ЕИЙСЯ

том,

что делитель на каждом шаге вычитается столько раз из делимого (начи-

ная со старших разрядов), сколько это возможно для гюлучения наименьшегчз

пoлoжи^eJtьиoro остатка. Тогда в очередной разряд частного записывается

цифра, равная числу делителей, содержащихся в делимом па данном uiai е. Та-

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

сдви1

а.

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

делимого на обратную величину делителя. Здесь возникает новая опера-

ция — вычисление обратной величины, осуществляемое но ичвесрным

приближенным формулам (например, разложением в биномиальный ряд

Ньютона и г. II.). В этом случае в состав команд машины должна входи !ь

спеш'альная операция нахождения обратной величины.

К наиболее распроС1раненнь1м методам выполнения операции деления

относится также метод, заключающийся в использовании приближенной

формулы для нахождений частного от деления двух величии. Ог мего/va

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

частное определяется по некоторой формуле, которая сводился к выполне-

нию операций сложения, вычитания и умножения.

Фактически два последних метода пригодны для использования в спе-

циализированных машинах, в которых операция деления встречаегся но

часто и ее целесообразно реализовать программным путем.

В универсальных вычислительных машинах, как правило, рсализуекя

разновидность «школьного» алгоритма деления.

140