Устройство для деления

Устройство для деления

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСИОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

«»98762l (61) Дополнительное к авт. свид-ву

t51)M.Ìë з (22) Заявлено 0308В1 (21) 3325347/18-24 с присоединением заявки Йо (23) Приоритет

G Об F 7/52

Государственный комитет

СССР по делам изобретений и открытий (53) YQC б81. 325 (088. 8) Опубликовано 0701ВЗ. Бюллетень М 1

Дата опубликования описания 07.01В3

Н.В. Черкасский, А.А, Мельник, В.М. Крифвпин,, -, Г

И.Г. Грибок 1 (72) Авторы изобретения

Львовский ордена Ленина политехнический институт им. Ленинского комсомола (7t) Заявитель (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ

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

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

Недостаток известного устройства — низкое быстродействие, поскольку цикл вычисления определяется длиной разрядной сетки делимого и делителя и состоит из i=ra шагов, где mразрядность обрабатываемых чисел.

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

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

Цель изобретения — повышение быстродействия.

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

987621 блока стековой памяти, ныход которого соединен с первым входом перемножителя, выход второго входного регистра соединен с информационным входом второго блока стековой памяти и с первым входом первого сумматора, второй вход которого соединен с выходом первого блока постоянной памяти, выход перного сумматора соединен, с информационным входом первого промежуточного регистра, выход которого соединен с входом кнадратора, выход которого соединен с информационным входом второго промежуточного регистра, выход которого соединен с информационным входом сднигателя, выход которого соединен с информационным входом третьего промежуточного регистра, выход которого соединен с первым входом второго сумматора,выход которого соединен с информационным входом четвертого промежуточно- 2О го регистра, выход которого соединен с первым входом перемножителя, второй вход которого соединен с выходом первого блока стековой памяти, первый выход второго блока стековой 25 памяти соединен с входом шнфратора, второй выход второго блока стековой памяти соединен с входом второго блока постоянной памяти, выход которого подключен к второму входу второго 3О сумматора, выход шифратора соединен с управляющим выходом сдвигателя, тактовые входы регистров и блоков стековой памяти соединены с выходом блока управления, первый и второй 35 входы которого соединены с входами задания числа тактов и пуска устройства соответственно, На фиг. 1 показана блок-схема устройства для деления; на фиг. 2 - щ блок-схема управления.

Устройство содержит входные регистры 1 и 2, блок 3 постоянной памяти, сумматор 4, блок 5 стеконой памяти, промежуточный регистр б, блок 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 соединены с выхо- 65 дами соответственно сумматора 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 постоянной памяти служат для хранения констант, которые используются в процессе вычисления частного от деления. Емкость блоков постоянной памяти зависит от требуемой точности вычислений, Адресация к блокам постоянной памяти осуществляется по старшим разрядам знаменателя, Промежуточные регистры б, 9, 13 и 15 предназначены для кратковременного запоминания результатов промежуточных вычислений, а также для обеспечения конвейерного способа обработки данных. Это и-разрядные регистры, где n — количество разрядов, поступающих в устройство операндов.

Блоки 5 и 7 служат для обеспечения конвейерного способа обработки данных, причем блок 5 содержит четыре и-разрядных регистра 22, а блок

7 — три К-разрядных регистра 23, где

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

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

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

Z= (.4+к(к+В)21, !

О где константы A и В выбираются иэ ус1,066846020 -0,9826699700 4

1,492156007 -0,7521023100 8, 2,3894 10 +

0,90096 10

1,106546417 -0,9716439300 4 1 9269 . 10

1,482133024 -0,7549770700 8 1,33762 10

1,136403589 -0,9628535700 4 1,51482 10

1,469190014 -0,7589067900 8

1,72612 10

1,14724 10

2,07396 10

1,158220462 -0,9560561700 4

1,454013604 -0,7637781900 8

1,173458525 -0,9510402100 4 0,81798 10

0,66660 10 5

2,46432 10 5

2,73412 10

2,79580 ° 10

0,13372 10

1,178989988 -0,9491419900 4

-0,7726182435 8

1,428284375

1,419093162.

1,409619374

0,7759432368 8

-0,7794610900 8

0,1001110

1,190029146 -0,9451443100 4

0,1001111

0,1010000

0,1010001 1,189433806 -0,9453892000 4 2,49200 ° 10

0,1010010

0,6250000

0,5156250

0,5234375

0,5312500

0,5390625

0,5468750

0,5546875

0,5652000

0,5703125

0,5781250

0,5859375

0,5937500

0,6014625

0,6093750

0,6171875

0,1000001

0,1000011

0,1000011

0,1000100

0,1000101

0,1000110

0,1000111

0,1001000

0,1001001

0,1001010

0,1001011

0,1001100

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

Границы интервалов выражаются К старшими двоичными разрядами х. Для .

15-разрядных входных чисел использование вышеуказанного алгоритма при разбиении диапазона изменения аргумента на 38 интервалов позволяет достичь точности а „ < 2 (cM. таблицу).

987621 продолжение таблицы

4 5 6

0,1010100

0,1010101

0,6562500

0,6787500

0,1010111

0,1011000

0,68750000

0,10111001

0,1011010

0,70312500

0,71875000

4 4,24974.10

1,1519709810 -0,963380260

0,1011100

0,1011101

0,1011110

0,1011111

0,1100000

1,1385906220 -0,970656190

4 1,21435 10

4 1,27146 10

4 1,32544-10

1,1329329420 -0,973837610

1,1271447110 -0,977161630

0,1100001

0,1100110

0,1101000

2 1,47230 10

2 1,00930. 10

0,9422889630 -1,192299283

0,9385099750 -1,194937359

0,1110000

0,1110100.0,90625000

0,92185000

1 0,56152 .10

1, 0,38832 10

-1,504875380

-1,502449820

0,7447462235

0,7474186795

0,93750000

0,9631250

0,1110000

0,96875000

0,73437500

0,74218750

0,75000000

0,75781250

0,76562500

0,78125000

0,79687500

0,81250000

0,83593750

0,85114625

0,87500000

0,89062500

1,183079078 -0,9481278888 4 4,03658 10 >

0,1010110 1,176830734 -0,9509971428 4 0,82610 ° 10

1,1707044320 -0,95389834 4 3,12842 10

1,1618419590 -0,958280540 4 3,71379 10

1.,1440999200 -0,967620450 4 1,15597 10-5

0,1100100 0,9435546800 -1,191396540 2 0,49520 10

0,1100011

0,1100100 1,1060094110 -0,989846820 4 5,99442- 10

0,9445330210 -1,190811180 2 0,24890.10

0,9332102070 -1,198788339 2 3,08430 10

0,9268987340 -1,203614580 2 1,66780 . 10

0,9211469870 -1,208177340 2 1,89530 - 10

0,9149120320 -1,213298237 2 2,10016 - 10

0,7409356040 -1,508221964 1 0 74950 . 10-5

0,1111100 0,7494896840 -1,500503960 1 0,61020 - 10 5

987621

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

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

В первом такте у и х поступают соответственно на входной регистр 1 и входной регистр 2. Иэ входного регистра 2 х поступает. на сумматор 4, одновременно по адресу, указанному

К старшими разрядами х, из блока

3 постоянной памяти выбирается константа В,.которая также поступает на сумматор 4. В сумматоре 4 производится выработка суммы (х + В). Во вто- 15 ром такте это выражение записывается в промежуточный регистр 6, а содержимое входного регистра 1 и К старших разрядов входного регистра 2 записывается в верхние регистры 22 и 2р

23 соответственно блоков 5 и 7. С каждым последующим тактом информация в блоках 5 и 7 сдвигается на одну ступень вниз. Содержимое промежуточного регистра 6 поступает на вход квадратора 8, в котором формируется выражение (х+В) . В третьем такте это выражение записывается в регистр 9, а из него поступает на сдвигатель 11, где осуществляется сдвиг на W разрядов, т.е. формируется выражение M(x+B) .×èñëî M генерируется шифратором 10 по К старшим разрядам х, поступающим из блока 7. В четвертом такте полученное число M(x+8) записывается в регистр 13, а иэ него поступает на сумматор 14. Одновременно из блока 12 постоянной памяти по адресу, указанному числом иэ блока .

7, считывается константа А, которая также подается на сумматор 14, на вы- 4Е ходе которого получается выражение

A+M(x+8), пятом такте это число записывается в регистр 15 и из него поступает на перемножитель 16, на который одновременно поступает у из блока 5. На выходе перемножителя имеем требуемую функцию

2=У (Л+н(х+ь) )

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

Блок 18 управления работает следу- 55 ющим образом.

Перед началом работы устройства для деления массивов двоичных чисел в счетчик 24 массива загружается по входу 19 код, равный длине массива чисел, которые должны быть разделены, плюс количество ступеней обработки устройства (в данном случае 7), После поступления сигнала "Пуск" по входу 20 на триггер 26 последний 6S устанавливается в "1", сигнал> с его выхода, поступая на элемент И 28, разрешает прохождение через него тактовых импульсов, вырабатываемых генератором 27 тактовых импульсов. Эти тактовые импульсы с элемента И 28 поступают на регистры устройства, построенные на D-триггерах, и при поступлении каждого импульса по его переднему фронту в регистры устройства записывается информация, сформированная в стоящих перед этими регистрами ступенях обработки. С поступлением каждого импульса информация продвигается на одну ступень вниз по конвейеру, т.е. как бы течет от входа к входу. Поскольку в данном устройстве имеется 7 ступеней обработки, то после поступления семи первых импульсов на выходе устройства появится первый результирующий операнд и дальше после поступления каждого последующего импульса на выходе устройства будут появляться новые результаты обработки массива чисел. Вместе с поступлением на регистры устройства тактовые импульсы с элемента И 28 поступают на счетчик 24 массива и с поступлением каждого импульса из содержимого счетчика вычитается единица, т.е. в счетчике подсчитывается количество обработанных операндов.

Как только содержимое счетчика 24 массива станет равным нулю, т.е. весь массив чисел обработан, дешифратором 25 нуля вырабатываетоя управляющий сигнал, который поступает на триггер 26 пуска и останова и сбрасывает его в "0" ° Сигнал с выхода этого триггера запрещает прохождение тактовых импульсов из генератора 27 тактовых импульсов через элемент И 28 на регистры устройства, тем самым пре кращается работа устройства. При необходимости обработки нового массива в счетчик 24 массива загружается его длина и при поступлении сигнала

"Пуск" начинается новая обработка. (Пример. Пусть в первом такте на входные регистры поступают нормализованные 15-разрядные числа x =

0,62571; у = 0,727.

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

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

12,ветствующая данному интервалу (В =

-0,94538) . На сумматоре 4 формируется выражение х+В, равное -0,31967.

Во втором такте это число записывается в промежуточный регистр б, у иэ входного регистра 1 поступает в 5 блок 5, а старшие семь разрядов х— в блок 7. В квадраторе 8 число из регистра 6 возводится в квадрат и становится равным (х+В ) = 0,10219 °

В третьем такте это число записи- 1О вается в регистр 9 и сдвигается на сдвигателе 11 на величину W, которая генерируется шифратором 10 (W 4), т.е". на сдвигателе 11 осуществляется сдвиг на два двоичных разряда влево. 15 . В четвертом такте число M(x+B)

0,40875 поступает на регистр 13, а из него на сумматор 14, куда также поступает число A = 1,18943 из . блока 12 постоянной памяти. На сумма- Zg торе получаем число A + W(x +8)

1,59818; В пятом такте это число записывается в промежуточный регистр

15 и поступает на перемножитель 16, в котором это число умножается на у, поступивший из блока 5. На выходе перемножителя получаем требуемый результат y(A+W(x+B) 3= 1,16188 = у/х, который в шестом такте записывается в выходной регистр 17 и иэ негр поступает на выход.

Данное устройство работает по конвейерному принципу. В каждом такте в него можно вводить новые операнды.

Такт конвейерной обработки массива данных определяется по задержке, вносимой наиболее времяемким узлом. Та ким узлом в данном устройстве является перемножитель, поэтому такт равен времени умножения двух чисел Тл =

40 — Это и есть быстродействие . устройства при обработке массива данных.

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

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

9 305475, кл. G 06 F 7/52, 1971 (про у тотип).

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

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

1. Авторское свидетельство СССР

Р 367421, кл. G 06 F 7/54, 1973.

2. Авторское свидетельство СССР

987621

Составитель В.Березкин

Редактор A. Лежнина Техред Ж.Кастелевич Корректор, М.Коста

Заказ 10304/37 Тираж 704 Подписное

ВИИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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