УСТРОЙСТВО ДЕЛЕНИЯ И ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ Российский патент 2014 года по МПК G06F7/535 G06F7/552 

Область техники

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

Уровень техники

Известно устройство для вычисления квадратного корня $$\left(\sqrt{x}\right)$$ [1], в котором вычисление функции производится за n циклов (n - число разрядов двоичного кода значения квадратного корня) с вычислением за каждый цикл одной значащей цифры результата путем выполнения в каждом цикле трех операций с разрядной цифрой а_i результата.

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

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

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

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

Известно устройство для извлечения квадратного корня [3], содержащее блок умножения, блок деления, первый блок памяти, регистр результата. Недостатком такого устройства является сложность реализации, обусловленная необходимостью использования блока памяти большой емкости, что связано с применением метода литейной интерполяции для вычисления значений функции между опорными точками. Так для описываемого устройства, имеющего длину разрядной сетки входного и выходного слова, равную (n+1), включая знаковый разряд, требуется запоминающее устройство емкостью Q₀=(n+1)·2^n-4 бит. Устройство также не позволяет производить операции деления над входными числами.

Известно устройство для деления [4], содержащее два регистра остатка, регистр делителя, регистр частного, сумматор принудительного округления, узел вычисления обратной величины, два сумматора, два блока умножения, первый коммутатор, селектор, вычитатель, элемент НЕ и блок микропрограммного управления, причем вход данных устройства соединен с информационным входом регистра делителя и с первым информационным входом первого коммутатора, выход которого соединен с информационном входом первого регистра остатка, выход первого сумматора является выходом результата устройства и соединен с входом уменьшаемого вычитателя, входы вычитаемого и заема которого соединены с выходами первой и второй групп первого блока умножения соответственно, выходы разности и заема вычитателя соединены с вторым информационным входом первого коммутатора и информационным входом второго регистра остатка соответственно, выходы старших разрядов первого и второго регистров остатка соединены с первым и вторым информационными входами второго сумматора соответственно, выход младших разрядов которого соединен с первым информационным входом второго блока умножения, второй информационный вход которого соединен с выходом узла вычисления обратной величины, вход которого соединен с выходом сумматора принудительного округления, информационный вход которого соединен с выходом старших разрядов регистра делителя, выход которого соединен с первым информационным входом первого блока умножения, второй информационный вход которого соединен с информационным входом младших разрядов регистра частного и выходом селектора, информационный вход которого соединен с выходом второго блока умножения, вход переноса сумматора принудительного округления является входом логической единицы устройства, выход старшего разряда второго сумматора соединен с входом элемента НЕ, выход которого соединен с управляющим входом селектора, вход синхронизации устройства соединен с синхровходами первого и второго регистров остатка, регистра делителя, регистра частного и блока микропрограммного управления, первый выход которого соединен с первым управляющим входом первого коммутатора и входом установки в "О" второго регистра остатка, второй выход блока микропрограммного управления соединен с вторым управляющим входом первого коммутатора и входами разрешения записи второго регистра остатка и регистра частного, третий и четвертый выходы блока микропрограммного управления соединены с входами разрешения записи первого регистра остатка и регистра делителя соответственно, пятый выход блока микропрограммного управления является выходом признака окончания деления устройства, отличающееся тем, что в устройство введены второй и третий коммутаторы, причем выход первого регистра остатка соединен с первым информационным входом второго коммутатора, второй информационный вход которого соединен с первым выходом регистра частного, выход второго регистра остатка соединен с первым информационным входом третьего коммутатора, второй информационный вход которого соединен с вторым выходом регистра частного, выход второго коммутатора соединен с первым информационным входом первого сумматора, второй информационный вход которого соединен с выходом третьего коммутатора, первые управляющие входы второго и третьего коммутаторов соединены с вторым выходом блока микропрограммного управления, шестой выход которого соединен с вторыми управляющими входами второго и третьего коммутаторов.

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

Наиболее близким по технической сути к предложенному техническому решению является устройство для деления [5], содержащее регистр делимого, регистр делителя, сумматор частного, сумматор принудительного округления делителя, блок деления усеченных чисел, регистр цифр частного, три коммутатора и блок управления, причем выходы делителя и делимого через шину данных устройства соединены с информационными входами регистра делителя и информационными входами первой группы первого коммутатора соответственно, выходы первого коммутатора соединены с информационными входами регистра делимого, информационные входы первой группы второго коммутатора соединены с выходами старших разрядов делимого через шину данных устройства, выход старших разрядов регистра делителя соединен с информационными входами первой группы третьего коммутатора, информационные входы второй группы которого соединены с выходами старших разрядов делителя через шину данных устройства, выходы третьего коммутатора соединены с информационными входами сумматора принудительного округления делителя, вход переноса которого соединен с входом логической единицы устройства, выходы сумматора принудительного округления соединены с входами делителя блока деления усеченных чисел, входы делимого которого соединены с выходами второго коммутатора, выходы блока деления усеченных чисел соединены с информационными входами регистра цифр частного, выходы которого соединены с входами младших разрядов сумматора частного, вход синхронизации устройства соединен - с синхровходами регистров делимого и делителя, сумматора частного, регистра цифр частного и блока управления, первый выход блока управления соединен с входом разрешения записи регистра делителя и входом установки в "О" сумматора частного, а также с первыми управляющими входами первого, второго и третьего коммутаторов, второй выход блока управления соединен с вторыми управляющими входами первого, второго и третьего коммутаторов и входом разрешения записи сумматора частного, третий выход блока управления соединен с входом разрешения записи регистра делимого и регистра цифр частного, четвертый выход блока управления является выходом признака окончания деления устройства, выходы сумматора частного являются выходом частного устройства, отличающееся тем, что устройство содержит формирователь частичных произведений, блок суммирования, два сумматора и элемент ИЛИ - НЕ, причем выход регистра делителя соединен с первым информационным входом формирователя частичных произведений, второй информационный вход которого соединен с выходом регистра цифр частного, выход регистра делимого соединен с первым информационным входом блока суммирования, второй информационный вход блока суммирования соединен с выходом формирователя частичных произведений, выходы сумм и переносов блока суммирования соединены с входами первого и второго слагаемых первого сумматора соответственно, выходы старших разрядов сумм и переносов блока суммирования соединены с входами первого й второго слагаемых второго сумматора соответственно, выход второго сумматора соединен с информационными входами второй группы второго коммутатора, выход первого сумматора соединен с информационными входами второй группы первого коммутатора, выход старшего разряда первого сумматора соединен с первым входом элемента ИЛИ - НЕ, выход которого соединен с входом установки в "О" регистра цифр частного, первый выход блока управления соединен с вторым входом элемента ИЛИ - НЕ.

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

Раскрытие изобретения

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

Заявленное устройство для деления и извлечения квадратного корня позволяет производить вычисление в формате плавающей точки в соответствии со стандартом стандарт IEEE 754 с одинарной (результат представлен 32-битным двоичным числом) и двойной (результат представлен 64-битным двоичным числом) точностью, причем входные операнды могут быть представлены в формате плавающей точки как одинарной, так и двойной точности.

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

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

Краткое описание чертежей

Признаки и сущность заявленного изобретения поясняются в последующем детальном описании, иллюстрируемом чертежами, где показано следующее:

На фиг.1 - структурная схема заявленного устройства деления и извлечения квадратного корня, где:

1 - блок выделения степени и мантиссы входных операндов;

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

3 - блок входных регистров;

4 - схема управления блока сумматора и блока умножителей;

5 - блок умножителей;

6 - блок сумматоров;

7 - блок формирования результатов вычисления.

Осуществление изобретения

Деление и извлечение квадратного корня происходит на одних и тех же элементах устройства с целью повышения быстродействия 3- ступенчатый конвейер позволяет загружать исходные данные и передавать на последующую обработку из любой ступени, ориентируясь загрузкой блоков умножителей и сумматоров, блоки умножителей и сумматоров совместно с регистрами конвейера производят вычисление по алгоритму деления «с сохранением остатка», а извлечения квадратного корня «без сохранения остатка» с целью унификации связей блоков умножителей и сумматоров для операций деления и извлечения квадратного корня, результат каждой итерации определяется из условия: $$\min \left(P-f\left(A_{i-1}+B_{i,j}\right)\right)>0(1)$$ , где P - делимое или число, из которого извлекается квадратный корень, A_i-1 - промежуточный результат, полученный на предыдущей итерации, B_i,j - вектор приближений текущей операции, f(A_i-1+B_i,j) - арифметическая операция, обратная вычисляемой, для операции деления - умножение на делитель, для операции извлечения квадратного корня - возведение в степень, при этом результатом i итерации является число $$A_i=A_{i-1}+B_{i,k}(2)$$ , где B_i,k - значение приближения из вектора B_i,j, удовлетворяющее условию (1), одна итерация вычисления содержит операцию умножения и операцию вычитания промежуточных результатов, отличающиеся тем, что с целью повышения быстродействия операция извлечения квадратного корня может выполняться одновременно над двумя независимыми входными числами, результат и входные данные, флаги выполнения операций соответствуют стандарту IEEE 754 для чисел в формате плавающей точки одинарной и двойной точностей.

Блок выделения степени и мантиссы входных операндов 1 производит разбор поступивших на вход двоичных чисел в формате плавающей точки. Производит выделение из них степени и мантиссы из входных операндов, определяет признаки результата, такие как деление на ноль, признак нулевого результата и др. Данные с выхода блока выделения степени и мантиссы входных операндов 1 поступают в одну из ступеней конвейера регистров блока входных регистров 3, свободную от вычисления. В случае заполнения всех ступеней конвейера 3 схема управления 3-ступенчатым конвейером блока входных регистров 2 формирует сигнал «занят» препятствующий дальнейшему поступлению чисел на вход блока разбора и подготовки входных данных. Сигнал «занят» снимается сразу после завершения первой выполняемой операции. Каждый блок входных регистров 3 содержит защелки делителя, делимого или числа, из которого извлекается квадратный корень, степени результата, знак результата, признаки результата, а также номер цикла итерации и промежуточное значение результата.

Данные с входа/выхода одного из блоков входных регистров 3 через схему управления 3-ступенчатым конвейером блока входных регистров 2 и схемы управления блока сумматора и блока умножителей 4 поступают на вычисление промежуточного результата деления или извлечения квадратного корня. На основании номера цикла итерации и промежуточного значение результата полученного с предыдущего цикла схема управления блоком сумматоров и блоком умножителей 4 формирует вектор возможных результатов текущего цикла путем поразрядного слияния промежуточного значение результата, полученного с предыдущего цикла, и набора констант приближения. Константы приближения являются членами ряда 0, 1,…2^K - 1, где K - количество бит результата, определяемых за одну итерацию. Позицию для слияния определяет схема управления блоком сумматоров и блоком умножителей 4 на основе номера цикла итерации. Данные с выхода схемы управления блока сумматоров и блока умножителей 4 поступают на вход блока умножителя 5, где в случае деления двух чисел происходит умножение делителя и вектора возможных результатов текущего цикла, а в случае извлечения корня производится возведение в квадрат векторов возможных результатов текущего цикла. Результат фиксируется в схеме управления блоком сумматоров и блоком умножителей 4 в первом такте итерации. Во втором такте итерации производится пробное вычитание и определение промежуточного значение результата как элемента вектора возможных результатов, обеспечивающего минимальный положительный остаток от вычитания. В случае деления из делимого вычитаются результат умножения, а в случае извлечения квадратного корня вычитание производится из числа, из которого извлекается квадратный корень. Минимальный положительный остаток от вычитания определяется схемой управления блоком сумматоров и блоком умножителей 4 по смене знака результата разности с помощью логической комбинационной схемы, входящей в схему управления блоком сумматоров и блоком умножителей. Блоки сумматора 6 и блоки умножителей 5 для выполнения деления на первом и втором тактах вычисления выполняют операции, входящие в текущий и следующий цикл итерации, а в случае извлечения квадратного корня внутри одного цикла итерации на первом и втором тактах операции выполняются последовательно. Для ускорения цикла извлечение квадратного корня блоки 5 и 6 имеют возможность производить извлечение квадратного корня из 2 чисел одновременно, при этом числа на вход блоков умножителей 5 и блоков сумматоров 6 поступают по очереди для каждого такта вычисления. Вычисление частного производится за 11 циклов для получения результата двойной точности (общая разрядность операндов 64, мантисса - 53 разряда), при этом общий цикл деления составляет 15 тактов. Вычисление квадратного корня из одного числа составляет также 11 тактов с общей длительностью 24 такта, при вычислении квадратного корня из двух чисел одновременно среднее время вычисления равно 12 тактам.

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

Примеры реализации

Заявленное устройство для деления и извлечения квадратного корня было применено в сопроцессоре плавающей точки процессора SPARC V8, результаты сравнения с аналогичными устройствами [6] представлены в таблице 1.

Табл.1 Блоки деления Операция Извлечение Преимущество Преимущество умножения различных сопроцессоров плавающей точки (FPU) деление, такты (операция двойной точности) квадратного корня (операция двойной точности) по быстродействию при делении при извлечении квадратного корня GRFPU 16 (16) 23 (24) 6,66% 0/100%* ARM VFP9-S 28 (31) Нет данных 86.66% - ARMVFP11 29 (33) Нет данных 93.33% - AMD K7 17(20) Нет данных 13.33% - MEIKO 50 Нет данных 233.33% - Заявленное 15 (15) 24/12 (12)* Объект сравнения устройство      

* - для группового извлечения квадратного корня

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

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

Список используемой литературы

1. А.с. СССР №842806. Устройство для вычисления квадратного корня / В.В.Чекушкин. - Опубл. 1981. Бюл. №24.

2. А.с. СССР №611208, кл. G 06 F7/38 1978 г. Устройство для вычисления квадратного корня.

3. А.с. СССР №656055, кл. G 06 F7/38 1979 г. Устройство для вычисления квадратного корня.

4. Сафонова Э.М., Шостак А.А «УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ», Патент №2018933, кл. G06F7/52, дата публикации 30.08.1994.

5. Сафонова Э.М., Шостак А.А «УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ», Патент №2018934, кл. G06F7/52, дата публикации 30.08.1994.

6. Edvin Catovic «GRFPU - High Performance IEEE- 754. Floating- Point Unit» Gaisler Research, Första Långgatan 19, SE-413 27 Göteborg, Sweden edvin@gaisler. Com,

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

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