Арифметическое устройство Советский патент 1981 года по МПК G06F7/38 

(54) АРИФМЕТИЧЕСКОЕ УСТГОЙСТВО

Изобретение относится к вычислительной технике и может быг.. использовано при по строении щ фровых вычислительных машин. Известно арифметическое устройство, содержащее арифметико-логический блок, входные буферные регистры, регистры общего назначення, схемы утфавления 1. Однако известное устройство обладает низким быстродействием. Наиболее близким к предлагаемому является арифметическое устройство, содержащее ариф метико-логический блок, умножитель, нормализатор (сдвигате)1ь), блок деления, две группы регистров общего назначения, мультиплексор, три буферных регистра, причем выход первого буферного регистра соединен со входами первой и второй группы регистров общего назначения, выходы которых соединены соответствен но с первыми входами второго и третьего буферных регистров, выход второго буферного регистра сое;1ииен с первыми информационными входами арифметико-логического блока, умножителя, блока деления и нормализатора, вторые входы которых соединены с выходом мультиiDiieKCopa, а выходы - с первым информационным входом первого и вторьпми информационными входами второго и третьего фуберных; регистров, выход -фетьего буферного регистра соединен с первым информационным входом мультиплексора, управляющие входы арифме-. тшсо-логического блока, умножителя, блока , деления, нормализатора и мультиплексора соедитны с соответствующими управляющими шинами устройства 2 . Недостатком )гказанного устройства является то, что для быстрого вьшолнения с его помощью операций абпеяия необходнм специальный блок деления, который имеет достаточно больШой объем оборудования и тем самымyBiejbniffiaeT общий объем арифметического устройства. Цель изобретения - уменьшение оборудования арифметического устройства. Для достижеиия поставленной цели арифметическое устройство, содержащее арифметикологический блок, умножитель, нормализатор, две группы регистров общего назначения, мультивибратор, трн буферных регистра, причем выход первого буферного регистра соединен со входами

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

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

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

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

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

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

X нормировано, т. е. . Знаменатель X представим в виде

X а + Ь,(1)

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

Л. Лv,

a4b - (2)

Числа а и b выбираются таким образом.

чтобы выполнялось условие

/а-Ч/ 2-4

(3)

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

Z а b

U

Построим при / z/ 2 многочлен шестой степени M(z), приближающий функцию (1+zT; Для этого положим

Mj,(l)eoZ -fC Z -C2Z4-eCj2 C4Z

где (i О, 1,...,6) и С- неизвестные пока числа;

tj -.многочлен Чебышева, т. е.

Tj (ад) г 64 (ii -ff 2се/ +560; -тш

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

С-. + Су О

° 24

с + С2 7 2 С;

,5сJ + с -7.2 Т

с л О 4 S Л ITC

Сб 1.

из которой легко находим (2 М.7. 2.- -7-2 V -- 2 (2 -7-2 4+7- .. C(2H7.2){217-2

.Г - (.224 7-215;( .24;- , Тем самым приближающий многочлен M полностью нацаен. Теперь оценим погреш указанного приближения. Так как (1 + Z)(l + 2) 1, ТО из соотношений (4) следует, что (их)га+тг-л 6(2)3 TT-jd/i -4 Jz/-2откуда при M.-Vf /С ч-хН-Ал (z:}/ точки зрения экономии вычислений не совсем устраивает многочлен M(z), как его старший коэффициент c lПоэтому пусть |Д -l-Co -7(.24Д2И-7.l2 4-7-2 5.72;9 Положим , Яба)«б(2) (. Тогда получим RU.) ,r %Z«36, а2 Сд -5-2Л/03 3; С5;аб СбОчевидно,, JR6(2;-%fz;/«2-25/A/ 2- Из неравенств (5) и (6) следует, что /(;-«-z;tR Cz / i 142-i2- ; 2 в десятичной записи с погреишостью лее 0,5 10 коэффициенты а./ имеют ,006869460106 а,. 1,000026814111 а -0,999986563406 0 999999947603 ,000000006564 Qe-it Можно проверить, что многочлен R представим в виде Rg{2)((z -bpz4-9(z+r;+e) «г((( где р .-1.003434725929; ,: 1,000007502170; -0,000000004124; 0,000001699858; -0,999992490377; 1,000001695721. Очеэидно, что есян числа р , q, г, заранее занести в блок постоянной пам (то вычисление f(z) при произвольном может бьггь. произведено по формулам f ,+t;Vl9 l% ig/ Очевидно, что Ri(2) п. и что во всей (8) присутстоследовательности вычислений уют три умножения и семь сложенш. Таким бразом, для вьпшсления значения R-(z) при аданном z достаточно трех умгюжений и семи ложений, что меньше нежели при реализации олинома по схеме Горнера. Если формулу (2) переписать в виде Rfi (), то становится очевидным, что для вычисления астного достаточно шести умножений и нескольих сложений, включая выбор разбиения (1). Осталось показать, каким образом следует ыбирать числа а и Ь в формуле (1). Для этого знаменатель х представим в виде X к+ I где X - первые 4 разряда х; х - остальные разряды. Определим сначала числа of- я Р таким образом: ( х , если х Z 4xVi1 если X 5S 5 если v е РЧх-kl если Очевидно, что о может принимать только значения вида ct П2,где п О, 1 8 всего 9 значений. Теперь покажем, как по уже найденным и i определять а и Ь. Прежде всего заметим, что должно вьшолняться соотношение а + Ь ot.+ р, которое можно переписать в виде ь где О а-а. Очевидно, что если мы по данному значению 0 независимо от А будем единственньпл образом выбирать а, то величиш а и будут принимать по 9 значений каждая. В памяти должны содержаться значения а и (Г. Так как может принимать значения от -2 до 2, то условие (3) дает такое ограничение на выбор а J a-(( 2,(10) Приведем значения а в зависимости от об: 12 .13 . 14 / t / 16 16 16 1 - 1 - 1I Q 6,57,5116,234,2ll6,58,9h6.17 Непос1)едствеш1О можно проверить, что для приведенных значений а и вьтояняется овие (10). Преимущество f разбиения х а + b ред разбиением х oL Н./ состоит в том что величины имеют очень простую д ичную запись длиной не более байта, вследствие чего умножение любого числа на а может быть произведено быстрее, чем на п норазрядное 32-разрядное число. Таким обр зом, для вычисления частного по формуле (9) достаточно четырех полноразрядньЬс умножений, двух умножений на байтовые м жители и нескольких сложений. Вычислительный .процесс (8) можно еще много упростить, если перейти к переменно Iff- Z + г. Очевидно, RgM) Кб(Св;(№Чрш+С)) П tt Чр а )« + 3 - Р t f О-Ж 1 где р pf - 2 г; Р q q к м I t И-5 - q. Или, в десятичной записи р -1,003434717681 q 1,000007498032 t -2,000001692405 Очевидно, что если числа р, q, в, t, и заранее занесены в блок 10 постоянной пам то вычисление R(tt/) при произвольной может быть произведено по формулам п со-ь р W п п n,j,+ q Пд о) n g . 5 3 n, ng+ t r 7 Очевидно, что R ((S)) n и что для в ления R(W) по схеме (12) достаточно тр умножений и шести сложений. Для того, чтобы получать величину и) в то величины Z без дополнительных арифм ческих операций, следует держать-в блоке постоянной памяти вместо значений (Г зна чения сГ о + аг и вычислять величину b по формуле b р + cf Очевидно, что тогда d- b - а - (}ъ 4 сГ-на Г) Приведенное обоснование и полученные формулы показывают возможность реализа операции деления на умножителях и сумма рах-вычитателях. Для практического выполнения приведенного алгоритма деления имеет смысл произвести его масштабирование. Прежде всего, в блоке 10 постоянной памядолжны содержаться ти вместо величин а „-2 -( величины 2 а , а вместо величин р, q U - соответственно величины 2 р, 2 q , f. Поскольку результаты всех арифметических операций не должны превосходить по абсолютной величине единицу, то промасштабированньгаал горитм (12) вьп-лядит следующим образом: , 2(i}+ 2 р 2-. 2:n, Пл п,i 2 -2 -i 2 п 2 П2:+ 2q 2-V 2.f1l,-r%, 2-% 2- + 2 n, + , 2 t 2-пв 2.2%2Л, 4- A- 2 По 2Г ng+ 2 и После выполнения алгоритма (13) промасштабированное частное 2 у/х вычисляется . по формулеi . - 2 п Все операнды для любой операции в арифметическом yctpoHCTBe хранятся в регистрах, входящих в группы регистров 4 и 3 общего назначения и в трех буферных регистрах 6, 7 и 8. Кроме того ,однобайтовый операнд может храниться в дополнительном регистре 12 и также использоваться в операциях. Арифметико-логический блок 1 умножитель 2 и нормализатор 3 представляют из себя комбинационные схемы. Выход каждого комбинационного блока представляет собой трёхстабильный выход, позволяющий все выходы соединить между собой. Управление работой устройства осуществляется по системе шин 14 - 23. Устройство работает следующим образом. Выполнение арифметических и логических операций. Эти операции выполняются блоком 1. Операция начинается с записи в регистры 7 и 8 исходных операндов. В регистры 7 и 8 операнды могут быть записаны либо из любых двух регистров группьг 5 или 4, для чего по управляющим шинам 19 или 17 подаются соответствующие номера регистров, либо с выходов блока 1 или умножителя 2, или нормализатора 3, или со входа 13 устройства. Одновременно по управляющей шине 16 подается код операции, например операции суммирования. Через такт работы устройства на выходе блока 1 устанавливается значение суммы. Этот результат может быть выбран по шине 13 из устройства либо записан в регистр группы 4 или 5. Для записи в группу 4 или 5 регистров результат сначала записьшается в регистр 6, а затем в нужный регистр группы 4 или 5, номер регистра и сигнал записи подаются по управляющим шинам 19 или 17... Вьшолнение операции умножения. Одиниз сомножителей подается на умножитель 2 из регистра 7, другой либо из вспомогательного регис тра 12, либо по байтам из регистра 8 через мультиплексор 9. Для этого по шине 23 подается код, обеспечивающий нужное подключение муль типлексора к регистру 8 или к вспомогательному регистру 12. Умножитель 2 обеспечивает на вы ходе старшие 32 разряда произведения. Результат произведения на бдит можно через такт pa6oTbf устройства как и предьщущем случае считать с выхода умножителя 2. Для использовашш улшожителя 2 дляг получения произведения Двух 32-разрядных чисел требуется четыре такта работы, промежуточные произведения на байты последовательно суммиру)отся и хранятся во внутреннем регистре умножителя 2. Перед новьш обращением к умножителю 2 внутренйий регистр оввуллеая соответствующим сетналом. Вьшолнение операции сдвига. Сдвиг осуществляется ньрма;пюатором 3 над я1«фаядом, записаинь1м в регистре 7. Число двонтаых сдви гов пода:ется либо по шине 14, либо с выхоща мультиплексора 9, т. е. число сдвигов может определять любой байт операнда регистра 8 йот байт вспомогательного регистра 12. Место поступления числа двоичных сдвшгс (яфеделяется сигналом, поступающим по шинам 14 япя 23. Результат сдвига получается на выходе нормализатора 3 через такт работы устрсяства. Вьшолнение операции нормализации. Операция выполняется нормализатором 3, при этомпо поше 14 поступает соответствующий код операции. Нормализуемый оператор поступает из одного регистра 7 или 8. Мантисса яормада зованного числа получается на выходе нормализатора 3 через такт, после чего ее можно считать, еще через такт можно считывать порядок иормализованного числа. Выполнение операции деления. Операция деления выполняется на основе метода полиномиальной аппроксимации и опирается на приведенные вьпце операции: суммирование, вычитание, сдвиг, нормализация, умножение. Кроме того, дополнительно на введенном оборудовани выполняются операции формирования адреса.и обращения к блоку 10 постоянной памяти за необходимыми константами алгоритма деления. Опишем кратко всю операцию делашя. Исходные операнды, делимое и делитель, хранятся в любых регистрах групп 4 и 5. Делитель по.10 сьшается в регистр 7 и нормализуется в нормализаторе 3, после чего помещается в регистры . 6 и 7 и в одну из групп 4 или 5. Помещение в регистр 6 нормализова1шого дешггеля обеспечивает на входах блока 11 соответств)аощие разряды делителя. После этого начинается этап получения обргаяай Величшпл от делителя. На первом и нулевом тактах работы устрой- ства по реализации получения обратной функции во вспомотатепьный регистр 12 помещаются числа +5, -4, обеспечивающие с помощью нормалнзат( 3 и двух сдвигов в нем выделение нз делителя разрядов с двадцать седьмого по первый, что означает поотчеюю 2. После этого фо{ шруется адрес oi, который подается в блок 10 постоянной тамятя иобеспечивает считывание величины 2 эшшсью её во вспомогателмый fecactp 12 и считывание | величины 2(Г+ 2 га в регистр 6. Величнш 2(Гт 2 га подписывается в регистр группы Л а опуда в penicip 8, после чего выполняется суммирование в бпоке 1. Результат сумм1фования ломоцается в ретмстр 7. Далее выполняется операция умножения суммы на величину 2 краяямую во вспомогательном регистре 12, что о6есае1вшае1ся умяожнтелем 2. Последунниие нытсяааю выйолвяются в соответствии с блспсСхоюб алгорита, приведеяного иа фиг. 3. Вя Иротяжеит всей 11оследуюа|ей работ устройства блок И генерирует ядресл К+Г. ТС+2,.... что обеспечивает носл юатьяую подачу в р гистр 6 констант fip, Тц, 2 5, , f u и нослеД(ателю)по подачу масштабных велиЧ1Ш, указываювпх чясяо сдвигов при работе нормализатсфа 3. На двадцать пятом laicie работы устройсюа спить прснюхопкг абряаяеяяе к блоку 10 пос таяшмй пшияти по адресу лС Этту печиваегся вторичное стаылаияк константы 2 а. Посяе получения величины 2 1/х происходит умножение иа нее делимсн-о, выбирается из oiEtHoro регистра группы 4. Результат последило умножёяня с выхода умиожителя 2 есть резулыва операат деясяяя, когорыб поступает на ши 13 к может бып загаюан в ретистры б, 7 и 8. На этом работа ус1ф(ства при выиояиении («ерация делогая заканчивается. Блок 11 формирования адреса рабопет еле дующим образом. На стадии . такта работы арифметического устройства на вход блока II поступают тридцатый ,. даадцать девятый, двадцап восьмой и даадцать седьмой двоятаые разряды X, по котсфым определяется блока 10 постоянной памяти в ирепешш О-в, т. е. реалнзуетсяeiapec x-q5« 2, . 11 где ,lJ- двадцать седьмой двоичный разряд числа X. Выработкой адреса достигается доступ к блоку 10 постоянной памяти для выборки 2 а и 2сГ+ 2 га 2cf. Предварительно в нулевом и первом цикле, в которых производится подготовка к операции деления, устанавливается по выходу блока 11 адрес К 10, что позволяет на вспомогатель ном регистре 12 иметь число +5, определяющее число логических сдвигов влево делителя X. В первом цикле это число +5 подается через мультиплексор 9 на вход нормализатора 3. Таким образом, в первом цикле обеспечивается сдвиг делителя х на пять разрядов влево, чем достигается вычисление |5 в маштабе 2 Параллельно сдвигу влево на 5.разрядов в блок 11 подается 1, которая добавляется к К, после чего по адресу К+Г, выбирается на вспомогательный регистр 12 число 4, которое во втором цикле через мультшшексор 9 обеспечивает арифметический сдвиг числа 2 на 4 разряда вправо, после чего на выходе нормализатора 3 получаем 2/5. Оборудование, которое введено в арифметическое устройство вместо специального блока делителя, требует 16 интегральных микросхем, что меньше как по числу, так и по потребляемой мощности оборудования специального блока делителя. Кроме того, введенное оборудование позволяет обходиться простыми методами контроля и диагностики, например побайтовым контролем по четности. Специальный блок деления, будучи устройством, производящим арифметические операции и сдвиги (при последовательно-параллельном способе деления на основе вычитания) требует контроля арифметических операций. Контрольное оборудование в зтом смысле значительно увеличивает общее оборудование как при дублировании вычитателя, так и при сверт ке по модулю три. В последнем случае может увеличиваться время Цикла при выполнении деления. В специальном блоке делителя требуется 3 такт вычитания - сдвиг при делении и при нахождении обратной величины.В предлагаемом арифметическом устройстве деление выпол- i няется за 30 тактов, а выполнение обратной величш{ы за 26 тактов. Таким образом, в предлагаемом арифметическом устройстве операция деления выполняется за то же время, что и в известном, опера Щ1Я вычисления обратной величины - за время на 10% меньше, чем в известном, при этом количество оборудования , обеспечивающего one рацшо деления и вычибления обратной величины по крайней мере на 50% меньше, чем количество оборудования деления в известном устройстве (без учета управления специального делителя). Формула изоб ре т е н и я Арифметическое устройство, содержащее арифметико-логический блок, умножитель, нормализатор, две группы регистров общего Назначения, мультиплексор, три буферных регистра, причем выход первого буферного регистра соединен со входами первой и второй группы регистров общего Назначения, выходы ч которых соединены с первыми инофрмационными входами соответственно второго и третьего буферных регистров, выход второго буферного регистра соединен с первыми информационными входами арифметико-логического блока, умножителя и нормализатора, вторые информационные входы которых соединены с выходом мультиплексора, а выходы соедцнены с информащюнной шиной устройства, котор&й соединена с первым информационным входом первого буферного регистра и вторыми информационными входами второго и третьего буферных регистров, выход третьего буферного регистра соединен с первым информационш м входом мультиплексора, управляюише входы арифметики- логического блока, умножителя, нормализатора, мультиплексора, и буферных регистров соединены « соответствующими управляющими шииами устройства, о т л и ч а ю ш е е с я тем, что, с целью сокращения количества оборудования, оно содержит блок постоянной памяти, вспсжогательный ре гистр и блок формирования адреса, информационный вход которого соединен с выходом первого буферното регистра, управляющий вход блока формирования адреса соединен с соответствующей управляющей шиной устройства, а выход подключен ко входу блока постоянной памяти, первый выход которого соединен со вторым информационным входом первого буферного регистра, а второй выход со входом вспомогательного регистра, выход которого поключеи ко второму информациоиному-входу мультиплексора. Источники информации, принятые во внимание при экспертизе 1.Каган Б. М. Электронные вычислительные машины и системы. М.,.Энергия, 1979, 2.Экспресс-информация. Сер. ВТ. 1976, № 2, с. 6-11 (прототип).

Адрес.