Устройство для вычисления модуля m-мерного вектора

 

Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЭВМ. Устройство содержит m регистров p₁...p_m, 2m - 1 сумматоров-вычитателей s₁...s_2m-1, m дешифраторов знака, два сдвигателя 1, 4, блок 2 изменения знака числа, блок 3 умножения на одну из n констант, m входов x₁...x_m операндов, m входов z₁...z_m для анализа знака операнда, m выходов y₁...y_m результата и вход 5 номера итерации. В отличие от известных технических решений в предлагаемом устройстве происходит преобразование компонент вектора в m-мерном пространстве как одна макрооперация за время порядка длительности n операций сложения. Кроме того, результат операции не деформируется (коэффициент удлинения вектора равен единице). Эффективность достигается расширением функциональных возможностей устройства за счет m-мерного преобразования Хаусхолдера при относительно незначительных дополнительных затратах оборудования. 3 ил.

Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЭВМ.

Известны специализированные устройства для поворота вектора по алгоритму Волдера, в которых можно вычислять модуль вектора. Устройства содержат сдвигающие регистры, коммутирующие блоки, сумматоры-вычитатели и позволяют решать задачу на порядок быстрее, чем традиционные арифметические устройства (авт. св. СССР N 445042, кл. G 06 f 7/38, 1974).

Однако они работают с двумерными векторами и для вычисления модуля m-мерного вектора требуют выполнения последовательности из m-1 операций.

Наиболее близким по технической реализации к изобретению является устройство для определения модуля трехмерного вектора (авт. св. СССР N 1205139, кл. G 06 f 7/544, 1986). Это устройство содержит три регистра аргументов, три сдвигателя, вычитатель, шесть сумматоров-вычитателей, три дешифратора знака и реализует итерационный алгоритм "цифра за цифрой" перемещения трехмерного вектора с помощью последовательности из n преобразований отражения до его совпадения с осью абсцисс. Такое линейное преобразование вектора носит название преобразования Хаусхолдера (Ортега Дж. Введение в параллельные и векторные методы решения линейных систем, М.: Мир, 1991, с. 92).

Недостатками таких устройств являются большое время определения модуля m-мерного вектора, которое равно ≈ m/2 циклов по n итераций, а также деформация модуля в каждом цикле.

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

Цель достигается тем, что в устройство, содержащее три дешифратора знака, три регистра, два сдвигателя, шесть сумматоров-вычитателей, причем управляющие входы сдвигателей соединены с входом номера итерации устройства, выход первого регистра соединен с входом первого сдвигателя, введены m-3 регистров, m-3 дешифраторов знака, 2m-7 сумматоров-вычитателей, блок умножения и блок изменения знака числа, причем входы всех регистров подключены к m входам операндов устройства, управляющий вход блока умножения подключен к входу номера итерации устройства, выход первого сдвигателя через блок изменения знака числа, управляющий вход которого соединен к выходу первого дешифратора знака, подключен к первому входу цепочки сумматоров-вычитателей, у которой управляющий вход j-го элемента (j = 1,2,..., m-1) подключен к выходу (j+1)-го дешифратора знака, первый вход соединен с выходом (j-1)-го элемента, а второй - с выходом (j+1)-го регистра, выход последнего элемента цепочки подключен к входу блока умножения, выход которого соединен с вторыми входами m выходных сумматоров-вычитателей (кроме первого), второй вход первого выходного сумматора-вычитателя соединен с выходом второго сдвигателя, вход которого подключен к выходу блока умножения, первый вход каждого l-го выходного сумматора-вычитателя соединен с выходом l-го регистра, его управляющий вход подключен к выходу l-го дешифратора знака, а выход - к l-му выходу устройства, вход l-го дешифратора знака соединен с l-м входом анализа знака операнда (l = 1,2,...,m).

На фиг.1 представлена схема устройства для вычисления модуля m-мерного вектора; на фиг.2 - схема устройства в конвейерном режиме; на фиг.3 - схема устройства для выполнения преобразования Хаусхолдера над матрицей А(m x m), столбцы которой поданы на устройства U₁...U_m, каждое из которых может быть взято из фиг.1 или 2.

Устройство содержит m регистров P₁...P_m, 2m-1 сумматоров-вычитателей S₁. . .S_2m-1, m дешифраторов d₁...d_m знака, два сдвигателя 1,4, блока 2 изменения знака числа, блок 3 умножения на одну из n констант, m входов х₁... х_m операндов, m входов z₁...z_m для анализа знака операнда, m выходов результата y₁...y_m и вход 5 номера итераций. Входы регистров р₁...р_m являются входами х₁...х_m операндов, а выходы подключены к первым входам выходных сумматоров-вычитателей S_m. . .S_2m-1соответственно, управляющие входы которых соединены с выходами дешифраторов d₁...d_m знака, а выходы - с выходами y₁.. .y_m результатов соответственно. Вход 5 номера итерации подключен к управляющим входам сдвигателей 1,4 и блока 3 умножения. Выход регистра Р₁ подключен через сдвигатель 1 и блок 2 изменения знака числа к первому входу сумматора-вычитателя S₁, второй вход которого соединен с выходом регистра Р₂, управляющий вход - к выходу дешифратора d₂ знака, а выход - к первому входу сумматора-вычитателя S₂. Сумматоры-вычитатели S₁...S_m-1соединены в цепочку, j-й элемент которой первым входом подсоединен к выходу (j-1)-го элемента, вторым - к выходу (j+1)-го регистра, управляющим входом - к выходу дешифратора d_j+1 знака, а выходом - к первому входу (j+1)-го элемента. Выход сумматора-вычитателя S_m-1соединен с входом блока 3 умножения, выход которого через сдвигатель 4 подключен к второму входу сумматора-вычитателя S_m и непосредственно к всем вторым входам остальных выходных сумматоров-вычитателей S_m+1...S_2m-1. Входы дешифраторов d₁...d_m знака являются входами z₁... z_mанализа знака соответственно.

Работу устройства можно описать следующими выражениями: y₁ = x₁ - a2^bc₁; y₂ = x₂ - ac₂; (1) y₃ = x₃ - ac₃; ˙˙˙˙˙˙˙˙˙˙˙˙˙ y_m = x_m - ac_m, где a = 2(m-1+2^-i)^-1(2^bx₁c₁+x₂c₂+...+x_mc_m); c_j = sgnz_j = ±1 (j = 1,2,...,m); b = -]0,5i[ - целая часть числа, заключенного в скобках (i = 0,1,2,..., n-1).

Алгоритм описывает одно из n преобразований отражения, в результате которых исходный вектор Х_о ложится на первую из m осей координат, а остальные координаты вектора равны нулю.

Рассмотрим работу устройства на i-й итерации. Операнды-компоненты вектора X_i заносятся в регистры р₁...р_m по входам x₁...x_m и подаются на входы z₁. ..z_m соответственно. Сдвигатели 1 и 4 служат для сдвига числа на b разрядов, поэтому на выходе блока 2 изменения знака числа получается величина 2^bx₁sgnz₁, к которой на сумматоре-вычитателе S₁прибавляется (вычитается) величина x₂sgnz₂. Таким образом, на выходе сумматора-вычитателя S_m-1 получается выражение (2^bx₁c₁ + x₂c₂+...+x_mc_m), которое поступает на вход блока 3 умножения. Блок умножения предназначен для умножения входного числа в зависимости от номера итерации на одну из n констант 2 (m-1+2^-i)^-1, на его выходе получено значение а. Сумматоры-вычитатели S_m...S_2m-1 построчно реализуют вычисления (1), причем для вычисления значения у₁ используется сдвигатель 4, который формирует величину а˙ 2^b. Дешифраторы знака служат для выработки управления сумматорами-вычитателями по знакам входных операндов z₁...z_m.

На этом работа в i-й итерации заканчивается. Следующую итерацию можно выполнить в последовательном режиме в этом же устройстве, если предварительно соединить выходы y_i с входами x_j и z_j (j = 1,2,...,m), или в конвейерном режиме с помощью n устройств, как это показано на фиг.2.

Для выполнения быстрого преобразования Хаусхолдера над матрицей А необходимо соединить m устройств по схеме, представленной на фиг.3, где {a_jl} - матрица (m x m). В результате одного преобразования Хаусхолдера все элементы первого столбца a_1l^' = 0 (кроме a₁₁^'). После m-1 таких преобразований в последовательном или конвейерном режиме матрица A^'будет верхнетреугольной, а после подобных манипуляций со строками матрицы-двухдиагональной, что необходимо для решения систем линейных алгебраических уравнений, проблемы собственных значений или других задач линейной алгебры.

В отличие от известных технических решений в предлагаемом устройстве происходит преобразование компонент вектора в m-мерном пространстве как одна макрооперация за время порядка длительности n операций сложения. Кроме того, в отличие от прототипа результат операции не деформируется (коэффициент удлинения вектора равен единице).

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

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА, содержащее три регистра, два сдвигателя, шесть сумматоров-вычитателей и три дешифратора знака, причем вход номера итерации устройства соединен с управляющими входами сдвигателей, информационный вход первого из которых соединен с выходом первого регистра, выход второго регистра соединен с первым информационным входом первого сумматора-вычислителя, управляющий вход и выход которого соединены соответственно с выходом первого дешифратора знака и первым информационным входом второго сумматора-вычитателя, второй информационный и управляющий входы которого соединены с выходами третьего регистра и второго дешифратора знака соответственно, выход второго сумматора-вычитателя соединен с первым информационным входом третьего сумматора-вычислителя, управляющий вход которого соединен с выходом третьего дешифратора знака, отличающееся тем, что в него введено m - 3 регистров, m - 3 дешифраторов знака, 2 m-7 сумматоров-вычитателей, блок умножения на константу и блок изменения знака чисел, причем i-й вход операнда устройства (i = 1, m) соединен с входом i-го регистра, первый информационный вход k-го сумматора-вычитателя (k = 4, m - 1) - с выходом (k-1)-го сумматора-вычитателя, выход j-го регистра (j = 4, m) - с вторым информационным входом (j-1)-го сумматора-вычитателя, управляющий вход j-го сумматора-вычитателя - с выходом дешифратора знака, выход первого сдвигателя - с информационным входом блока изменения знака, управляющий вход и выход которого соединен с выходом m-го дешифратора знака и вторым информационным входом первого сумматора-вычитателя, вход i-го дешифратора знака - с i-м входом анализа знака операнда устройства, выход (m-1)-го сумматора-вычитателя - с информационным входом блока умножения на константу, выход которого соединен с первыми информационными входами с (m+1)-го по (2m-1)-й сумматоров-вычитателей и информационным входом второго сдвигателя, выход которого соединен с первым информационным входом m-го сумматора-вычитателя, второй информационный вход l-го сумматора-вычитателя (l = m, 2m - 1) - с выходом i-го регистра, управляющий вход n-го сумматора-вычитателя (n = m+1, 2m-1) - с выходом p-го дешифратора знака (p=1, m-1), выход l-го сумматора-вычитателя является i-м выходом результата устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3