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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСИОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(23 Приоритет 6 Об Р 7/52 Государственный комитет СССР ло дедам изобретений и открытий(72 Авторы изобретения Львовский ордена Ленина политехнический инститУт.": им. Ленинского комсомола(54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ Изобретение относится к вычислительной технике и предназначено для построения специализированных и универсальных быстродействующих устройств, обрабатывающих большие массивы данных.Известно цифровое устройство для ускоренного деления, содержащее матричную схему умножения, накопительный сумматор, схему расширения, преобразователь дополнительного кода, схему сравнения, распределитель так. - товых импульсов и вентили 1 3.Недостаток известного устройства - низкое быстродействие, поскольку цикл вычисления определяется длиной разрядной сетки делимого и делителя и состоит из 1=ю шагов, где п- разрядность обрабатываемых чисел.Наиболее близким к предлагаемому по техничес(юй сущности является устройство для деления, содержащее входной регистр делителя, входной регистр делимого, два выходных регист- . ра, блок управления блок для формирования и суммирования частичных произведений с.входами для сомножителей и с дополнительными входами для корректирующего слагаемого, блок для хранения таблицы начального приближе ния к обратной величине делителя иклапаны на входах блока для формирования и суммирования частичных произведений 2 3.Недостаток устройства заключаетсяв низком быстродействии, посколькуделение выполняется итерационным методом при помощи умножений, причем вкаждой итерации выполняется по дваумножения,Цель изобретения - повышение быстродействия.Указанная цель достигается тем,что в устройство для деления, содержащее первый и второй входные регистры, первый блок постоянной памяти,перемножитель, выходной регистр, блокуправления, причем выход второго входного регистра соединен с входом первого блока постоянной памяти, выходперемножителя соединен с информационным входом выходного регистра, выходкоторого является выходом устройства, дополнительно введены два сумма 2 З тора, два блока стековой памяти, четыре промежуточных регистра, шифратор, квадратор, сдвигатель, второйблок постоянной памяти, причем выход первого входного регистра соедиЗО нен с информационным входом первогоблока стековой памяти, ныход которого соединен с первым входом перемножителя, выход второго входного регистра соединен с информационнымвходом второго блока стековой памятии с первым входом первого сумматора,второй вход которого соединен с выходом первого блока постоянной памяти,выход перного сумматора соединен, синформационным входом первого промежуточного регистра, выход которогосоединен с входом кнадратора, выходкоторого соединен с информационнымвходом второго промежуточного регистра, выход которого соединен с информационным входом сднигателя, выходкоторого соединен с информационнымвходом третьего промежуточного регистра, выход которого соединен спервым входом второго сумматора,выход которого соединен с информационным входом четвертого промежуточного регистра, выход которого соединенс первым входом перемножителя, второйвход которого соединен с выходомпервого блока стековой памяти, первый выход второго блока стековой 25памяти соединен с входом шнфратора,второй выход второго блока стековойпамяти соединен с входом второго блока постоянной памяти, выход которогоподключен к второму входу второго 30сумматора, выход шифратора соединенс управляющим выходом сдвигателя,тактовые входы регистров и блоковстековой памяти соединены с выходомблока управления, первый и второй 35входы которого соединены с входамизадания числа тактов и пуска устройства соответственно,На фиг. 1 показана блок-схемаустройства для деления; на фиг, 2 - 4 Облок-схема управления.Устройство содержит. входные регистры 1 и 2, блок 3 постоянной памяти, сумматор 4, блок 5 стеконойпамяти, промежуточный регистр б,блок 7 стековой памяти, квадратор8, промежуточный регистр 9, шифратор 10, сдвигатель 11, блок 12 постоянной памяти, промежуточный регистр 13, сумматор 14, промежуточный регистр 15,перемножитель 16, выходной регистр 17, блок 18 управления, вход 19 задания числа тактов,вход 20 пуска, выход 21 блока управления, Блок 5 содержит последовательно соединенные регистры 22. В блок 557 входят последовательно соединенныерегистры 23.Выход регистра 1 соединен с информационным входом блока 5, а выходрегистра 2 - с информационным входом боблока 7 и с входом блока 3 постоянной памяти, Входы сумматора 4 подключены к выходам регистра 2 и блока3. Информационные входы регистровб, 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 постоянной памятислужат для хранения констант, которыеиспользуются в процессе вычисления частного от деления, Емкость блоков постоянной памяти зависит от требуемой точности вычислений, Адресация к блокам постоянной памяти осуществляется по старшим разрядам знаменателя,Промежуточные регистры б, 9, 13 и 15 предназначены для кратковременного запоминания результатов промежуточных вычислений, а также для обеспечения конвейерного способа обработки данных. Это и-разрядные регистры, где и - количество разрядов, поступающих в устройство операндов,Блоки 5 и 7 служат для обеспечения конвейерного способа обработки данных, причем блок 5 содержит четыре и-разрядных регистра 22, а блок7 - три К-разрядных регистра 23, гдек - количество старших разрядов х,по которым осуществляется адресацияк блокам постоянной памяти, причемвыход второго регистра 23 блока 7 является первым его выходом и соединенс входом шифратора 10, а выход третьего регистра 23 блока 7 - его вторым входом и соединен с входом блока 12 постоянной памяти.Устройство предназначено для обработки нормализованных данных, пред987621 ловия минимизации абсолютной погрешности, а константа Я выбираетсяравной степени числа 2, что позволяет заменитьоперацию умножения операцией сдвига, На разных интервалахконстанты имеют различные значения,Границы интервалов выражаются Кстаршими двоичными разрядами х. Для .15-разрядных входных чисел использование вышеуказанного алгоритма приразбиении диапазона изменения аргумента на 38 интервалов позволяет достичь точности а2 (см, таблицу). ставленных в Формате с Фиксированной. запятой. Вычисление ФункцииЕ щ у/х осушествляется на основе метода сегментной аппроксимации, в соответствии с которым диапазон изменения аргумента 1/2, 1 3 разбивается наинтервалы, количество которых определяется требуемой точностью. На каждом интервале Функция 2 определяется выражением2 з з А+% х+В)21О где константы А и В выбираются иэ ус 00000Константы В хранятся в блоке 3 постоянной памяти, константы А - в блоке 12 постоянной памяти, константы И генерируются шифратором 10.Устройство работает следующим образом.В первом такте у и х поступают соответственно на входной регистр 1 и входной регистр 2. Иэ входного регистра 2 х поступает на сумматор 4, одновременно по адресу, указанному 10 К старшими разрядами х, из блока 3 постоянной памяти выбирается константа В,.которая также поступает на сумматор 4. В сумматоре 4 производится выработка суммы (х + В), Во вто ром такте это выражение записывается в промежуточный регистр 6, а содержимое входного регистра 1 и К старших разрядов входного регистра 2 записывается в верхние регистры 22 и 2 р 23 соответственно блоков 5 и 7. С каждым последующим тактом информация в блоках 5 и 7 сдвигается на одну ступень вниз. Содержимое промежуточного регистра 6 поступает на вход квадратора 8, в котором формируется выражение (х+В). В третьем такте это выражение записывается в регистр 9, а из него поступает на сдвигатель 11, где осуществляется сдвиг на И разрядов, т,е. формируется выражение И(х+В) .Число Я генерируется шифратором 10 по К старшим разрядам х, поступающим из блока 7. В четвертом такте полученное число У(х+8) записывается в регистр 13, а иэ него поступает на сумматор 14. Одновременно из блока 12 постоянной памяти по адресу, указанному числом иэ блока .7, считывается константа А, которая также подается на сумматор 14, на вы Е ходе которого получается выражение А+И(х+В),В пятом такте это число записывается в регистр 15 и из него поступает на перемножитель 16, на который одновременно поступает у из 45 блока 5. На выходе перемножителя имеем требуемую функцию2=у К+н(х+ь)Ц.В шестом такте полученное число 50поступает на выходной регистр 17 ииэ него на выход устройства. Выработка тактовых сигналов производится вблоке 18 управления.Блок 18 управления работает следующим образом,Перед началом работы устройствадля деления массивов двоичных чиселв счетчик 24 массива загружается повходу 19 код, равный длине массива . фчисел, которые должны быть разделены, плюс количество ступеней обработки устройства (в данном случае 7),После поступления сигнала "Пуск"по входу 20 на триггер 26 последний 6 устанавливается в "1", сигнал с его выхода, поступая на элемент И 28, разрешает прохождение через него тактовых импульсов, вырабатываемых генератором 27 тактовых импульсов. Эти тактовые импульсы с элемента И 28 поступают на регистры устройства, построенные на О-триггерах, и при поступлении каждого импульса по его переднему фронту в регистры устройства записывается информация, сформированная в стоящих перед этими регистрами ступенях обработки. С поступлением каждого импульса информация продвигается на одну ступень вниз по конвейеру, т.е. как бы течет от входа к входу. Поскольку в данном устройстве имеется 7 ступеней обработки, то после поступления семи первых импульсов на выходе устройства появится первый результирующий операнд и дальше после поступления каждого последующего импульса на выходе устройства будут появляться новые результаты обработки массива чисел. Вместе с поступлением на регистры устройства тактовые импульсы с элемента И 28 поступают на счетчик 24 массива и с поступлением каждого импульса из содержимого счетчика вычитается единица, т.е. в счетчике подсчитываетсяколичество обработанных операндов, Как только содержимое счетчика 24 массива станет равным нулю, т,е. весь массив чисел обработан, дешифратором 25 нуля вырабатываетоя управляющий сигнал, который поступает на триггер 26 пуска и останова и сбрасывает его в "0"Сигнал с выхода этого триггера запрещает прохождение тактовых импульсов из генератора 27 тактовых импульсов через элемент И 28 на регистры устройства, тем самым пре кращается работа устройства. При необходимости обработки нового массива в счетчик 24 массива загружается его длина и при поступлении сигнала "Пуск" начинается новая обработка.3П р и м е р. Пусть в первом такте на входные регистры поступают нормализованные 15-разрядные числа х =0,62571; у = 0,727.В таблице приведены вариант разбиения диапазона изменения х1/2,13 на 38 интервалов, что обеспечивает максимальную точность для 15-разрядных чисел, т.е. ошибка не превяаает, 2, и значения констант А, В, и У для кажцого интервала, а также максимальная ошибка, приближения в каждом интервале.Как видно из таблицы, каждый интервал отличается от другого по семи старшим разрядам х. Поэтому в первом такте по адресу, укаэанному этими разрядами, иэ блока 3 постоянной па-, мяти считывается константа В, соот-,-0,94538).На сумматоре 4 формируется выражение х+В, равное -0,31967. Во втором такте это число записывается в промежуточный регистр б, у иэ входного регистра 1 поступает в 5 блок 5, а старшие семь разрядов х - в блок 7. В квадраторе 8 число из регистра 6 возводится в квадрат и становится равным х+В ) = 0,10219В третьем такте это число записи вается в регистр 9 и сдвигается на сдвигателе 11 на величину Ч, которая генерируется шифратором 10 (Ч4), т.е", на сдвигателе 11 осуществляется сдвиг на два двоичных разряда влево. 15. В четвертом такте число Ч(х+В)0,40875 поступает на регистр 13, а из него на сумматор 14, куда также поступает число А = 1,18943 из . блока 12 постоянной памяти. На сумма- щ торе получаем число А + Ч(х +В)21,59818; В пятом такте это число записывается в промежуточный регистр 15 и поступает на перемножитель 16, в котором это число умножается на у, поступивший из блока 5. На выходе перемножителя получаем требуемый результат уАЧ(х+В) )= 1,16188 = у/х, который в шестом такте записывается в выходной регистр 17 и иэ негр поступает на выход.Данное устройство работает по конвейерному принципу. В каждом такте в него можно вводить новые операнды, Такт конвейерной обработки массива данных определяется по задержке, вносимой наиболее времяемким узлом. Та ким узлом в данном устройстве является перемножитель, поэтому такт равен времени умножения двух чисел Т 1 =40 - Это и есть быстродействие устройства при обработке массива данных.Быстродействие предлагаемого устройства по сравнению с прототипом выше в 10 раз, поскольку в прототипе 45 деление осуществляется с помощью итерации, причем в каждой итерации осуществляется по два умножения, а дЛя достижения требуемой точности потребуется минимум пять итераций, 50 т.е. нужно выполнить десять умножений. Р 305475, кл. 6 06 Г 7/52, 1971 (про 0 тотип). Формула изобретения Устройсро для деления, содержащее первый и второй входные регистры, первый блок постоянной памяти, ,перемножитель, выходной регистр,блок управления, причем выход второго входного регистра соединен с входом первого блока постоянной памяти,выход перемножителя соединен с информационным входом выходного регистра,выход которого является выходом уст-,ройства, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, в него дополнительно введены два сумматора, два блока стековой памяти, четыре промежуточных регистра, шифратор, квадратор, сдвигатель,второй блок постоянной памяти, причем выход первого входного регистра соединен с информационным входом первого блока стековой памяти, выход которого.соединен с первым входом перемножителя, выход второго входногорегистра соединен с информационным входом второго блока стековой памяти и с первым входом первого сумматора, второй вход которого соединен с выходом первого блока постоянной памяти, выход первого сумматора соединен с информационным входом первого промежуточного регистра, выход которогосоединен с входом квадратора, выходкоторого соединен с информационным входом второго промежуточного регистра, выход которого соединен с информационным входом сдвигателя, выходкоторого соединен с информационнымвходом третьего промежуточного регистра, выход которого соединен с первым входом второго сумматора, выходкоторого соединен с информационнымвходом четвертого промежуточного регистра, выход которого соединен спервым входом перемножителя, второй вход которого соединен с выходом первого блЬка стековой памяти, первыйвыход второго блока стековой памятисоединен с входом шифратора, второйвыход второго блока стековой памятисоединен с входом второго блока постоянной памяти, выход которого подключен к второму входу второго сумматора, выход шифратора соединенс управляющим выходом сдвигателя,тактовые входы регистров и блоковстековой памяти соединены с выходомблока управления, первый и второйвхбды которого соединены с входами;задания числа тактов и пуска устройства соответственно,Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССРР 367421, кл. 6 06 Г 7/54, 1973,2. Авторское свидетельство СССРКорректор,М.Кос Редак одписноеР 04/37 Тираж 704ВИИИПИ Государственного комитета Спо делам изобретений и открытий 113035, Москва, Ж, Рауюская наб Заказ илиал ППП Патент", г, Ужгород, Ул. Проектная, 4