Арифметическое устройство

 

(.= "- .-.-----.

И. Г. Грибков, Н. В. Илющечкин, В. П. Коше)тев и Т. Л. Степукова (72) Авторы изобретения (71) Заявитель (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО

Изобретение относится к вычислительной технике и может быт использовано при построении цифровых вычислительных машин.

Известно арифметическое устройство, содержащее арифметико.логический блок, входные буферные регистры, регистры общего - назначения, схемы управления (11.

Однако известное устройство обладает низким быстродействием.

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

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

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

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

На фиг. 1 показана структурная схема арифметического устройства; на фиг. 2 - порядок хранения необхадимых констант в блоке постоянной памяти; на фиг. 3 — блок-схема алгоритма деления чисел.

Устройство содержит арифметико-логический блок 1, умножитель 2, нормализатор (сдвигатель) 3, первая и вторая группы 4 и 5 регис. тров общего назначения, первый, второй и третий буферные регистры б, 7 и 8, мультиплексор 9, блок 10 постоянной памяти, блок 11 формирования адреса, вспомогательный регистр 12, информационную шину 13 и управляющие шины 14 — 23.

- Снижение количества оборудования арифметичеекого устройства удается обеспечить эа счет реализации в устройстве алгоритма деления на основе полиномияльной аппроксимации функции 1/х, цри этом конструируется: полипом с минимальным числом Операций умножения.

Равномерно загружая умножитель 2, нормалнзатор 3 и арифметико-логический блок 1 при реализации этого алгоритма удается путем введения некоторого дЬполнительиого оборудования, которое значительно меньше оборудования специального делителя, выполнять деление за время меньшее, чем на специальном последовательно параллельном делителе.

Рассмотрим обоснование алгоритма деления на основе полиноминальной аппроксимации.

Требуется вычислить частное у/х, где число х нормировано, т. е. 2 «» х(1. Знаменатель

1 х представим в виде хр а+ Ь при этом частное у/х можно вычислить по формуле

Х О,Ь а 4 -Ь (2)

Числа а и Ь выбираются таким образом, чтобы выполнялось условие

/а Ь/»2 (3)

При этом число а принимает лишь конечгО ное число значений в зависимости от х, а все значения а " занесены в блок постоянной памяти. Ниже будет показано,.как по х выбирать разбиение (1). А теперь, считая, что разбиение (1) уже выбрано и выполняется условие (3), покажем. как вычислить, частное у/х по формуле (2) Очевидно, основная трудность состоит в вычислении выражения (1+z), где г=а Ь

Ц

Построим при / г/ 2 многочлен шестой степени М6 (z), приближающий функцию (1+2 ° для этОГО положим

М (Х)-С02. + 1g +C g +С +(: +

+СЕХ+С6 (И7 где с.; (1= О, 1,- 6) и à — неизвестные пока числа;

7y —.Многочлен Чебышева, т. е.

-г (,,6), 7,/,,12 в щь

Тогда соотношения (4) трансформируются в систему линейных уравнений: с =-2 4

О со+ с1 0

24 с +с=7 2 "Г

2 с + с = 0

И

)+С4 с, + с .= 0 с . + с = 7" 2 C

50 ся = 1 ° из которой легко находим (2 Ь4 "7 2я4+7 2:"в -7 24)-"

Сот -С = 2 4 (2 4-7.224+7 g.45 7 24)-М

Х, если Х C 2

Х+2,если Х > 2

5 С4 = -С6 = (2 -7 Я,а4+7 gpss)(g +

1.7:2 Ю 7,24)-1 Сь = 4.

Тем самым приближаюший многочлен M6(z). полностью найден.. Теперь оценим погрешность укаэанного приблюкения. Так как (1 + z) (1 + z) = 1, то из соотношений (4) следует, что

0+2.)ЕЙ+7.) -М6(ХЦ = ГТУ(7/2 4), откуда при )z) <2 (4+Х) "-М (Е)/ - - - и (4+2 " ) (5)

С точки зрения зкономии вычислений нас не совсем устраивает многочлен Мб(), так как его старший коэффициент с 1. о

Поэтому пусть

Ь ="-Со "- "7 (2 4-2 " 24)(; ь4-7-2.z+

+ 7.2 16-7 ) ..

Положим, R<() =/ (Ы)+ Х. ЬГ6 (У/2-4)

Тогда получим f;t>i "Z +Cf<2 +O2Х +С1 Х+О, + + +5 f6р где 0,=С„; О =С -Ь 2 Д;Ц =С3;

-2O

Ц4 =Cg® g 5;agf =C> Я6=С 2 ТААД

Очевидно,, JR Ã2)-М (ХЦ Е 2-29/6/ с2 >ь. (6)

Из неравенств .(5) н (6) следует, что

/(4+2T- g(z)f«< 1+2 +2 ) 2

В десятичной записи с погрешностью не бо лее 0,5 ° 10 коэффициенты а имеют вид

-42 а = -1,006869460106 а = 1,000026814111 а =-0,999986563406

a4=: 0,999999947603 а = -1,000000006564

О6="

Можно проверить, vro многочлен К (z) представим в виде

Q 0Р)=((У. +Р 2+g )(Х 1 )ч9)"

„((>+ g (y+y)+y Z +g )+(f (7) где р =,-1,003434725929;

q . 1 000007502170;

r = -0,000000004124; а = 0,000001699858;

= -0,999992490377;

u = 1 000001695721.

Очевидно, что если числа р, р, r,, t,,Q. эЩЮиее занести блок постоянкои памяти, (то вычисление 8. (я) при произвольном z может быть. произведено по формулам

><"-2+P Q""2 1 ч И Ф + (И =Х+), (Ир 81+8, Ny--QNg (И д --l1y 44

Очевидно, что R<(z) = п и что во всей

<о» последовательности вычислений (8) присутствуют три умножения и семь сложений. Таким образом, для вычисления значения и (z) при

6„

5 заданном z достаточно трех умйожений и семи сложений, что меньше нежели при реализации полинома по схеме Горнера.

Если формулу (2) иерепнсать в виде у/х= уа В 6. (а b), (9) то становится очевидным, что для вычисления частного достаточно шести умножений и нескольких сложений, включая выбор разбиения (1).

Осталось показать, каким образом следует выбирать числа а и b в формуле (1). Для этого знаменатель х представим в виде х =х +х °

I где х — первые 4 разряда х;

f/ х — остальные разряды. щ Определим сначала числа оС и Ь таким образом:

«(х" Х"

1= —, 7 Х" 2+если )(> Й

Очевидно, что о может принимать только значения видаñf=2+ п 2, где и О, 1,..., 8— всего 9 значений.

Теперь покажем, как по уже найденным 011. 1т

Р определять а и b. Прежде всего заметим, что должно выполняться соотношение в+ b = d-+f3 которое можно переписать в виде

Зз, b = Pad", где д =d-a.

Очевидно, что если мы по данному значению независимо от Р будем единственным об40 разом выбирать а, то величины а и g будут принимать по 9 значений каждая. В памяти должны содержаться значения а 1 и ц . Так как

Р может принимать значения от -2 э до

Я

2, то условие (3) дает такое ограничение на выбор а а (2 +/(У /7 2 (10) (а

Приведем значения а и ц в зависимости от g(,: (8 9 10,11. 12,13 14 15 16

$0 g g g / / / /, 16 19 16 16 16 16 16 16 16 я К 0 — :-1-. -.- -; --;;- - -1- 0

16,5718,51 16,23 4,21 16,5 8 9 16,17

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

885993 (13) Или, в десятичной записи

Преимущество 1, разбиения х = а + Ь перед разбиением x = Д.+P - состоит в том, что величины а 1 имеют очень простую двоичную запись длиной не более байта, вследствие чего умножение любого числа на а

-rf может быть произведено быстрее, чем на полноразрядное 32-разрядное число. Таким образом, для вычисления частного по формуле (9) достаточно четырех полноразрядных умножений, двух умножений на байтовые множители и нескольких сложений.

Вычислительный .йроцесс (8) можно еще немного упростить, если перейти к переменной

09= z+ r.

Очевидно, () 1 ®) (((Ю +РЩ+ф )Э +Я) r (1 1)

"Г(® +РСи+с})В+ +(В2-+ре+с )+Ь +ц, гдер=р)- 2r;

g t» — pr+q

Ф

t=t — s -q. р -1,003434717681

q = 1,000007498032

- 2,000001692405

Очевидно, что если числа р, q, s, t, u заранее занесены в блок 10 постоянной памяти, то вычисление Й6(Ш) при ронзвольной может быть произведено по формулам и Ф+р

2 пз и+q (12)

5 4 п п + пэ пт = п6+ па nS п7

n9= ng +u

Очевидно, что R< (N) n9 и что для BbPIHcления R6(uv) но схеме (12) достаточно трех умножений и шести сложений.

Для того, чтобы получать величину Ж вместо величины z без дополнительных арифметических операций, следует держать в блоке 10 постоянной памяти вместо значений д знаРФ чения Cf =о + ar и вычислять величину Ь по о ле ф рму

Ь= P+д

Очевидно, что тогда а- Ь =СГ" (P+ СГ +а1-) = .+ =Ю

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

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

Прежде всего, в блоке 10 постоянной памяS ти вместо величин а должны содержаться

-я л величины 2 а, а вместо величин р, q, s, t, u — соответственно величины 2 р, 2 q, 2 S, 2 t, 2 и.

Поскольку результаты всех арифметических

> и операций не должны превосходить по абсолютной величине единицу, то промасштабированный ал горитм (12) выглядит следующим образом:

2 M)= 2 +2b

-) -4 -)

2 п)=2Ж+2р

1S 2 и = 2 "и 2 <)) 2 «а " -2

2 n=2 пя+2ц

-2

2 и= 22®2 пу

2 п=2 и +Г S

-з.

2 и-=-2 и +2 п3 аь з.

2 п2 и+2

-а

2 п9 2 2 п2 и .4 г п=2 пВ+2и зч Посла выполнения алгоритма (13) промас-я штабированное частное 2 у/х вычисляется . по формуле

2 у/х — 2-2 а у 2 и>

Все операнды для любой операции в арифметическом устройстве хранятся в регистрах, входящих в группы регистров 4 и 5 общего назначения и в трех буферных регистрах 6, 7 и 8. Кроме того, однобайтовый операнд может храниться в дополнительном регистре 12 и также использоваться в операциях.

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

23.

Устройство работает следующим образом.

Выполнение арифметических и логических операций. Эти операции выполняются блоком 1.

Операция начинается с записи в регистры 7 и

8 исходных операндов. В регистры 7 и 8 операнды могут быль записаны либо из.любых двух регистров группы 5 или 4, дшг чего по управляющим шинам 19 или 17 подаются соответствующие номера регистров, либо с выходов блока 1 или умножителя 2, или нормализатора 3, или со входа 13 устройства.

Одновременно по управляющей шине16 подается код операции, например операции суммирования.

Через такт работы устройства на выходе блока 1 устанавливается значение суммы. Этот

8859 результат может быть выбран по шине 13 из устройства либо записан в регистр группы 4 или 5. Для записи в группу 4 или 5 регистров результат сначала записывается в регистр 6, а затем в нужный регистр группы 4 или 5 з 5 номер регистра и сигнал записи подаются по управляющим шинам 19 или 17.

Выполнение операции умножения. Один из сомножителей подается на умножитель 2 нэ . регистра 7, другой либо из вспомогательного регис. е тра 12, либо по байтам из регистра 8 через мультиплексор 9. Для этого по шине 23 подается код, обеспечивающий нужное подключение мультиплексора к регистру 8 или к вспомогательному регистру 12. Умножитель 2 обеспечивает на выходе старшие 32 разряда произведения. Результат произведения на байт можно через такт работь1 устройства как и предыдущем случае считать с выхода умножителя 2.

Для использования умножнтеля 2 для получения произведения двух 32-разрядных чисел требуется четыре такта работы, промежуточные произведения на байты последовательно суммиру1отся и хранятся во внутреннем регистре умножителя 2. Перед новым обращением к умножителю 2 внутренний регистр обнуляется 23 соответствующим сш налом.

Выполнение операции сдвига; Сдвиг осуществляется нормализатором 3 над операндом, записанным в регистре 7. Число двоичных сдвигов подается либо по шине 14, либо с выхода .ЗЭ мультиплексора 9, т, е. число сдвигов может определять любой байт операнда рвгистра 8 или баит вспомогательного регистра 12. Место поступления числа двоичных сдвигов определяется сигналом, поступающим по шинам 14 ипн

23. Результат сдвига получается на выходе нормалиэатора 3 через такт работы устройства.

Выполнение операции нормализации. Операция выполняется нормализатором 3, при этом по шине 14 поступает соответствующий код оце- аб рации. Нормализуемый оператор поступает из одного регистра 7 или.8. Мштисса-нормализованного числа получается на выходе нормализатора 3 через такт, после чего ее можно считать, еще через такт можно считывать порядок 4$ нормализованного числа.

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

Опишем кратко всю операцию деления. Исходные операнды, делимое и делитель, хранятся в любых регистрах групп 4 и 5. llemneJn no93 10 сылается в регистр 7 и нормализуется в нормализаторе 3, после чего помещается в регистры

6 и 7 и в одну из групп 4 или 5. Помещение в регистр 6 нормализованного дешпеля обеспечивает на входах блока 11 соответствующие разряды делителя. После этого начинается этап получения обратной величины от делителя.

На первом и нулевом тактах работы устрой- . ства по реализации получения обратной функции во вспомогательный регистр 12 помещаются числа "+5", "-4", обеспечивающие с помощью нормализатора 3 и двух сдвигов в нем выде.ление иэ делителя разрядов с двадцать седьмого по первый, что означает получение 2P. После этого формируется адрес af, который подается в блок 10 постоянной а мяти и обеспечивает считывание величины 2 à е записью ее во вспомогательный регистр 12 и считывание, велипшы 2d + 2 гв в регистр б.

Величина 2d + 2 га переписывается в регистр группы 4, а огтуда в регистр 8, после чего вывыполияеуя операцйя умножения сумьш на величину 2 а . хранимую во вспомогательном

Последующие вычисления выНоамются в соответствии с блок-схемой алгоритма, приве-: денного на фиг. 3. На npotn tnn всей последующей рабоаы ущюйства блок 11 генерирует адреса "К+1". "К+2",..., "К+15 что обеспечивает послед ную подачу в регистр б констант. р, 2(1, 2 8, F+t, 2 и и последовательную nag% масштабных величин, указывающих чжло сдвигов при работе иормалнзатора 3.

На двадцать пятом satrte работы устройсвва опять проиехойнг обращаем к блоку 10 постоянной памяти по адресуа Этим o5jnpgiaezея вторичное oettatnatnte константы а .

После получения величины 2" 1/х происходит yamexcenne aa nee делимого, который выбирается as одного peritcqta группы 4. Результат последнего умножения с выхода умножителя 2 есть результат оперании genennn, который пмтупает па шпву 13 к может быть записан в регистры 6, 7 н 8. На этом рабата устройства при выполнении операции делапгя заканчивается. . Блок 11 формирования адреса работает еле дующим образом.

На стадии второго. такта работы арифметического устройства на вход блока 11 поступают тридцатый, двадцать девятый, двадцать восьмой и двадцать седьмой двои шые разряды х, по которым определяется айрес блока 10 постоянной памяти в прщиенах 0-8, z. e, реалиэуется формула а =адРЕС =Х->5t.2 1ч, 885993

$O

$$ где m = 0,1 — двадцать седьмой двоичный разряд числа х, Выработкой адреса достигается. доступ к блоку 10 постоянной памяти для выборки 2 а" и2д+2га=2д.

Предварительно в нулевом и первом цикле, в которых производится подготовка к операции . деления, устанавливается по выходу блока 11 адрес "К" = 10, что позволяет на вспомогательном регистре 12 иметь число "+5", определяю- щее число логических сдвигов влево делителя х. В первом цикле это число "+5" подается через мультиплексор 9 на вход нормализатора 3.

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

Параллельно сдвигу влево на 5.разрядов в блок 11 подается "1", которая добавляется к

"К", после чего по адресу "К+1", выбирается на вспомогательный регистр 12 число "4", которое во втором цикле через мультиплексор 9 обеспечивает арифметический сдвиг числа 2 3 на 4 разряда вправо, после чего на выходе нормализатора 3 получаем 2P.

Оборудование, которое введено в арифме. тическое устройство вместо специального блока делителя, требует 16 интегральных микросхем, что меньше как по числу, так и по потребляемой MoIIlBocTH оборудования специального блока делителя, Кроме того, введенное оборудование позволяет обходиться простыми методами контроля и диагностики, например побайтовым контролем по четности. Специальный блок деления. будучи устройством, производящим арифметические операции и сдвиги (при последовательно-параллельном способе деления на основе вычитания), требует контроля арифметических операций.

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

В специальном блоке делителя требуется 31 такт вычитания — сдвиг при делении и при нахождении обратной величины. В предлагаемом арифметическом устройстве деление выпол-, няется за 30 тактов, а выполнение обратной величины эа 26 тактов.

Таким образом, в предлагаемом арифметическом устройстве операция деления выполняется за то же время, что и в известном, опера ция вычисления обратной величины — за время на 10 o меньше, чем в известном, при этом количество оборудования, обеспечивающего операцию деления и вычисления обратной велнчи12 ны по крайней мере на 50% меньше, чем количество оборудования деления в известном устройстве (без учета управления специального делителя) .

Формула изобрeтения

Арифметическое устройство, содержащее

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

Источники информации, принятые во внимание при экспертизе

1. Каган Б. М, Электронные вычислительные машины и системы. М, "Энергия", 1979, с. 235.

2. Экспресс-информация. Сер. ВТ. 1976, и 2, с. 6 — 11 (прототнп).

885993

Жабер такИ

ВНИИПИ Заказ 10544l70 Тираж 748 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4