Устройство для деления Советский патент 1983 года по МПК G06F7/52 

(54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ Изобретение относится к вычислительной технике и предназначено -для построения специализированных и универсальных быстродействуницих устройств , обрабатывающих большие масси вы данных. Известно цифровое устройство для ускоренного деления, содержащее матричную схему умножения, накопительный сумматор, схему расширения, пре образователь дополнительногокода, схему сравнения, распределитель такгтовых импульсов и вентили tl3. Недостаток известного устройства - низкое быстродействие, поскольку цикл вычисления определяется длиной разрядной сетки делимого и делителя и состоит из шагов, где mразрядность обрабатываемых чисел. Наиболее близким к предлагаемому по тexничec Joй сущности является уст ройство для деления, содержащее вход ной регистр делителя, входной регистр делимого, два выходных регистра, блок управления,, блок для формирования и суммирования частичных про изведений с входами для сомножителей и с дополнительными входами дпя корректирующего слагаемого, блок для хранения таблицы начального приближе ния к обратной величине ; елителя и клапаны на входах блока для формирования и суммирования частичных произведений 21. Недостаток устройства заключается в низком быстродействии, поскольку деление выполняется итерационным методом при помощи умножений, причем в каждой итерации выполняется по два умножения. Цель изобретения - повышение быстродействия. Указанная цель достигается тем, что в устройство для деления, содержащее первый и второй входные регистры, первый блок постоянной памяти, перемножитель, выходной регистр, блок управления, причем выход йторого входного регистра соединен с входом первого блока постоянной памяти, выход перемножителя соединен с информационным входом выходного регистра, выход которого является выходом устройства, дополнительно введены два сумматора, два блока стековой памяти, четыре промежуточных регистра, шифратор, квадратор, сдвигатель, второй блок постоянной памяти, причем выход первого входного регистра соединен с информационным входс м первого блока стековой памяти, выход которого соединен с первым входом перемно жителя, выход BTdporo входного регистра соединен с информационным входом второго блока стековой памяти и с первым входом первого сумматора второй вход которого соединен с выхо дом первого блока постоянной памяти выход первого сумматора соединен, с информационным входом первого промежуточного регистра, выход которого соединен с входом квадратора, выход которого соединен с информационным входом второго промежуточного регист ра , выход которого соединен с информационным входом сдвйгателя, выход .которого соединен с информационным входом третьего промежуточного регистра, выход которого соединен с первым входом второго сумматора,вы ход которого соединен с информацион HEIM входом четвертого промежуточного регистра, ВЕЛХОД которого соединен с первым входомперемножителя, второ вход которого соединен с выходом первого блока стековой памяти, первый выход второго блока стековой памяти соединен с входом шифратора, второй выход второго блока стековой памяти соединен с входом второго бло ка постоянной памяти, выход которого подключен к второму входу второго сумматора, выход шифратора соединен с управляющим выходом сдвйгателя, тактовые входы регистров и блоков стековой памяти соединены с выходом блока управления, первый и второй входы которого соединены с входами задания числа тактов и пуска устройства соответственно. На фиг. 1 показана блок-схема устройства для деления; на фиг. 2 блок-схема управления. Устройство содержит входные регистры 1 и 2, блок 3 постоянной памя ти , сумматор 4, блок 5 стековой памяти, промежуточный регистр 6, блок 7 стековой памяти, квадратор 8, промежуточный регистр 9, шифратор 10, сдвигатель 11, блок 12 постоянной памяти, промежуточный регистр 13, сумматор 14, промежуточный регистр 15,перемножитель 16, выходной регистр 17, блок 18 управления, вход 19 задания числа тактов, вход 20 пуска, выход 21 блока управления. Блок 5 содержит последователь но соединенные регистры 22. В блок 7 входят последовательно соединенные регистры 23. Выход регистра 1 соединен с инфор мационным входом блока 5, а выход регистра 2-е информационным входом блока 7 и с входом блока 3 постоянной памяти. Входы сумматора 4 подключены к выходам регистра 2 и блока 3. Информационные входы регистров . 6, 9, 13, 15 и 17 соединены с выходами соответственно сумматора 4, квадратора 8, сдвйгателя 11, сумматора 14, перемножителя 16, а выходы - соответственно с входами квадратора 8, сдвйгателя 11, сумматора 14, перемножителя 16,. Первый выход блока 7 соединен с входом шифратора 10, а второй - с входом блока 12 постоянной памяти. Выход шифратора 10 соединен с управляющим входом сдвйгателя 11, а выход блока 12 - с входом сумматора 14. Выход блока 5 подключен к входу перемножителя 16. Выход 21 блока 18 управления соединен.с тактовыми входами регистров 1, 2, б, 9, 13, 15 и 17 и блоков5 и 7. Блок 18 управления (фиг. 2) содержит счетчик 24 массива, дешифратор 25 нуля, .триггер 26 пуска и останова, генератор 27 тактовых импульсов, элемент И 28, причем первый вход счетчика 24 массива соединен с входом 19, а выход счетчика 24 массива - с входом -дешифратора 25 нуля, выход которого подключен к первому входу триггера 26 пуска и .останова. Второй вход триггера 26 соединен с входом 20, а выход - с первым входом элемента И 28, второй вход которого подключен к выходу генератора 27 тактовых импульсов , а выход - к второму входу счетчика 24 массивов и к выходу 21 блока 18 управления. Блоки 3 и 12 постоянной памяти служат для хранения констант, которые используются в процессе вычисления частного от деления. Емкость блоков постоянной памяти зависит от требуемой точности вычислений. Адресация к блокам постоянной памяти осуществляется по старшим разрядам знаменателя. Промежуточные регистры 6, 9, 13 и 15 предназначены для кратковременного запоминания результатов промежуточных вычислений, а также для обеспечения конвейерного способа обработки данных. Это п-раэрядные регистры, где п - количество разрядов, поступающих в устройство операндов. Блоки 5 и 7 служат для обеспечения конвейерного способа обработки данных, причем блок 5 содержит четыре п-разрядных регистра 22, а блок 7 - три К-разрядных регистра 23, где К - количество старших разрядов х, по которым осуществляется адресация к блокам постоянной памяти, причем выход второго регистра 23 блока 7 является первым его выходом и соединен с входом шифратора 10, а выход третьего регистра 23 блока 7 - его вторым входом и соединен с входом блока 12 постоянной памяти. Устройство предназначено для о&работки нормализованных данных, представленных в формате с фиксированной запятой. Вычисление функЦии Z « у/х осуществляется на основе метода сегментной аппроксимации, в соответствии с которым диапазон изменения аргумента 1/2, 1 разбивается на интервалы,количество которых определяется требуемой точностью. На каждом интервсше функция Z определяется выражением

2 Л + У(Х+В)2,

где константы А и В выбираются из УСЛОВИЯ минимизации абсолютной погрешности, а константа W выбирается равной степени числа 2, что позволя ет заменить операцию умножения операцией сдвига.На разных интервалах константы имеют различные значения. Границы интервалов выражгиотся К старшими двоичными разрядами х. Для 15-разрядных входных чисел использование вышеуказанного алхюритма при разбиении диапазона изменения аргумента на 38 интервалов позволяет достичь точности д„ 2(см. таблицу)

0,1000000 0,1000001 ОД000011 0,1000011 0 1000100 0,1000101 0,1000110

0,1000111 0,1001000 0,1001001 0,1001010

. 0,1001011 0,1001100 0,1001101 0,1001110 0,1001111 0,1010000 0,1010001 0,1010010

1,499083746 -0,7502367800 8 1,13144-10 5

2,3894 10

-0,98266997004 0,90096-10-0,75210231008. 1,9269 10-0,97164393004 1,33762-Ю

-0,75497707008 1,51482-Ю-З

-0,96285357004 1,72612-10-0,75890679008 1,14724-10

-0,95605617004 2,07396-Ю

-0,76377819008 0,81798-10-0,95104021004 0,6666q-105

-0,94914199004 2,4643210-5

-0,77261824358

2,73412-10-

- 0,77594323688 2, 7958010-

-0,77946109008 0,13372-10-0,94514431004

1,189433806 -0,9453892000 4 2,49200-10- 0,968750000,1111100 .0,7494896840

Продолжение таблицы -1,500503960 1 0,61020-10-5

Константы В хранятся в блоке 3 постоянной памяти, константы А - в блоке 12 постоянной памяти, константы W генерируются шифратором 10.

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

В первом такте у и х поступают соответственно на входной регистр 1 и входной регистр 2. Из входного регистра 2 х поступаетна сумматор 4 одновременно по адресу, указанному К старшими разрядами х, из блока 3 постоянной памяти выбирается константа В,.которая также поступает на сумматор 4. В сумматоре 4 производится выработка суммы (х + В). Во втором такте это выражение записывается в промежуточный регистр 6, а содержимое входного регистра 1 и К старших разрядов входного регистра 2 записывается в верхние регистры 22 и 23 соответственно блоков 5 и 7. С каждым последующим тактом информация в блоках 5 и 7 сдвигается на одну ступень вниз. Содержимое промежуточного регистра 6 поступает на вход квадратора 8, в котором формируется выражение (х+В). в третьем такте это выражение записывается в регистр 9 , а из него поступает на сдвигатель 11, где осуществляется сдвиг на W разрядов, т.е. формируется выражение W(x+B).Число W генерируется шифратором 10 по К старшим разрядам X, поступающим из блока 7. В четвертом такте полученное число W(x+B)2 записывается в регистр 13, а из него .поступает на сумматор 14. Одновременно из блока 12 постоянной памяти по адресу, указанному числом из блок 7, считывается константа А, которая также подается на сумматор 14, на выходе которого получается выражение A+W(x+B) .В пятом такте это число записывается в регистр 15 и из него поступает на перемножитель 16, на который одновременно поступает у из блока 5. На выходе перемножителя требуемую функцию

2 :/f/j+w(x+B)

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

Блок 18 управления работает следу

ющим образом.

Перед началом работы устройства для деления массивов двоичных чисел в счетчик 24 массива загружается по входу 19 код, равный длине массива чисел, которые должны быть разделены, плюс количество ступеней обработки устройства (в данном случае 7),

После поступления сигнала Пуск по входу 20 на триггер 26 последний

устанавливается в 1, с его выхода, поступая на элемент И 28, разрешает прохождение через него тактовых импульсов, вырабатываемых генератором 27 тактовых импульсов. Эти тактовые импульсы с элемента И 28 поступают на регистры устройства, построенные на О-триггерах, и при поступлении каждого импульса по его переднему фронту в регистры устройст,ва записывается информация, сформированная в стоящих перед этими регистрами ступенях обработки. С поступлением каждого импульса информация продвигается на одну, ступень в.низ по конвейеру, т.е. как бы течет от входа к входу. Поскольку в данном устройстве имеется 7 ступеней обработки, то после поступления семи первых импульсов на выходе устройства появится первый результирующий операнд и дальше после поступления каждого последующего импульса на выходе устройства будут ПОЯВЛЯТЬСЯ новые результаты обработки массива чисел. Вместе с поступлением на регистры устройства тактовые импульсы с элемента И 28 поступают на счетчик 24 массива и с поступлением каждого импульса из содержимого счетчика вычитается единица, т.е. в счетчике подсчитывается количество обработанных операндов. Как только содержимое счетчика 24 массива станет равным нулю, т.е. весь массив чисел обработан, дешифратором 25 нуля вырабатывается управляющий сигнал, который поступает на триггер 26 пуска и останова и сбрасывает его и О. Сигнал с выхода этого триггера запрещает прохождение тактовых импульсов из генератора 27 тактовых импульсов через элемент И 28 на регистры устройства, тем самым пре кращается работа устройства. При необходимости обработки нового массива в счетчик 24 массива загружается его длина и при поступлении сигнала Пуск начинается новая обработка.

П р и м е.р. Пусть в первом такте на входные регистры поступают нормализованные 15-разрядные числа х 0,62571,; у 0,727.

В таблице приведены вариант разбиения диапазона изменения х С 1/2,1 на 38 интервалов, что обеспечивает максимальную точность для 15-разрядных чисел, т.е. ошибка не превыаает, , и значения констант А, В, и W для каждого интервала, а также максимальная ошибка, приближения в каждом интервале.

Как видно из таблицы, каждый интервал отличается от другого по семи старшим разрядам х. Поэтому в первом такте по адресу, указанному этими разрядс1ми, из блока 3 постоянной па-, мяти считывается константа В, соот

ветствующая данному интервалу (В -0,94538J.На сумматоре 4 формируется выражение Х4В, равное -0,31967. Во втором такте это число записывается в промежуточный регистр 6, у из входного регистра 1 поступает в блок 5 а старшие семь разрядов к в блок 7. В квадраторе 8 число из регистра 6 возводится в квадрат и становится равным ( 0,10219.

В третьем такте это число записывается в регистр 9 и сдвигается на сдвигателе 11 на величину W, которая генерируется шифратором 10 (W t) , т.е на сдвигателе 11 осуществляется сдвиг на два двЬичных разряда влево.

В четвертом такте число W(x+B) 0,40875 поступает на регистр 13, а из него на сумматор 14, куда также поступает число А 1,18943 из блока 12 постоянной памяти. На сумматоре получаем число А + W(x+B) 1,59818. В пятом такте это число записывается в промежуточный регистр 15 и поступает на перемножитель 16, в котором это число умножается на у, поступивший из блока 5. На выходе перемножителя получаем требуемый результат (x+B) 1Д6188 у/х, оторый в шестом такте записывается а выходной регистр 17 и из него пос-упает на выход.

Данное устройство работает по конвейерному принципу. В каждом такте а него можно вводить новые операнды. Такт конвейерной обработки массива анных определяется по задержке, вносимой наиболее времяемким узлом. Таким узлом в данном устройстве является перемножитель, поэтому такт равен времени умножения двух чисел Т-, t,;n,v,. Это и есть быстродействие устройства при обработке массива данных.

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

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

Устройс1 о для деления, содержащее первый и второй входные регистры, первый блок постоянной памяти, .перемножитель, выходной регистр.

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

o памяти, четыре промежуточных регистра, шифратор, квадратор, сдвигатель, второй блок постоянной памяти, причем выход первого входного регистра соединен с информационным входом пер5 вого блока стековой памяти, выход которого соединен с пepвы 1 входом перемножителя, выход второго входного регистра соединен с информационным входом второго блока стековой памяти

0 и с первым входом первого сумматора, второй вход которого соединен с выходом первого блока постоянной памяти, выход первого сумматора соединен с информационным входом первого про5 межуточного регистра, выход которого соединен с входом квадратора, выход которого соединен с информационным входом второго промежуточного регистра, выход которого соединен с инфор« мационным входом сдвигателя, выход которого соединен с информационным входом третьего промежуточного регистра, выход которого соединен с первым входом второго сумматора, выход которого соединен с информационным входом четвертого промежуточного регистра, выход которого соединен с первым входом перемножителя, второй вход которого соединен с выходом первого блока стековой памяти, первый

выход второго блока стековой памяти соединен с входом шифратора, второй выход второго блока стековой памяти соединен с входом второго блока постоянной памяти, выход которого под5 ключен к второму входу второго сумматора, выход шифратора соединен с управляющим выходом сдвигателя, тактовые входы регистров и блоков стековой памяти соединены с выходом

0 блока управления, первый и второй входы которого (соединены с входами; задания числа тактов и пуска устройства соответственно.

Источники информации,

5 принятые во внимание при экспертизе

30S475, кл. G 06 F 7/52, 1971 (про0 тотип).