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

 

Изобретение относится к вычислительной технике и предназначено для построения на его основе специальных ЭВМ. Устройство содержит дешифраторы знака (I₁-I_m), первую группу сумматоров-выситателей (2₁-2_m-1), вторую группу сумматоров-вычитателей (3₁-3_m), сдвигатели (4₁-4₃, блок изменения знака числа (5), регистры (6₁-6_m), группу сумматоров (7₁-7_m), группу сдвигателей (8₁-8_m). В устройстве производится преобразование компонент вектора в m-мерном пространстве как одна макрооперация путем ортогональных преобразований отражения без использования "длинной" операции умножения. Это приводит к увеличению быстродействия на время порядка n сложений на одной итерации и на время порядка n² сложений при конвейерной обработке с использованием n последовательно включенных устройств. 3 ил.

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

Известны специализированные устройства, выполняющие триангуляцию матрицы (патент РФ N 1800463), решение систем линейных алгебраических уравнений (патент РФ N 1832301) и другие.

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

Наиболее близким по технической реализации является "Устройство для вычисления модуля m мерного вектора" (патент РФ N 2029356). Это устройство позволяет привести путем ортогональных преобразований исходную матрицу к верхнетреугольной или двухдиагонльной формам, что необходимо для решения систем линейных алгебраических уравнений и проблемы собственных значений. Однако алгоритм, на базе которого реализовано данное устройство, требует выполнения "длинной" операции умножения, что приводит к понижению быстродействия.

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

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

На фиг. 1 представлена схема устройства для вычисления модуля m-мерного вектора, где: 1₁.1_m-дешифраторы знака; 2₁.2_m-1-первая группа сумматоров-вычитателей; 3₁.3_m-вторая группа сумматоров-вычитателей; 4₁.4₃-сдвигатели; 5 блок изменения знака числа; 6₁.6_m-регистры; 7₁.7_m-группы сумматоров; 8₁.8_m-группа сдвигателей; 9₁.9_m-входы операндов;
10₁.10_m-входы анализа знаков операндов;
11₁.11_m-выходы результатов;
12 вход номера итерации.

На фиг. 2 представлена схема для преобразования вектора в конвейерном режиме, на которой 13₁.13_n-устройства, изображенные на фиг. 1, 14 умножитель.

На фиг. 3 представлена схема для триангуляции матрицы A(m x m), столбцы которой поданы на устройства 13₁.13_m, каждое из которых может быть взято из фиг. 1 или фиг. 2.

Устройство содержит m дешифраторов знака 1₁.1_m, первую группу из (m-1) сумматоров вычитателей 2₁.2_m-1, вторую группу из m сумматоров вычитателей 3₁.3_m, три сдвигателя 4₁.4₃, блок изменения знака числа 5, m регистров 6₁. 6_m, группу из m сумматоров 7₁.7_m, группу из m сдвигателей 8₁.8_m, m входов операндов 9₁.9_m, m входов анализа знака операндов 10₁.10_m, m выходов результата 11₁.11_m, вход номера итерации 12, причем входы регистров 6₁.6_m являются входами операндов 9₁.9_m, а выходы подключены ко входам сдвигателей группы 8₁.8_m и к первым входам сумматоров группы 7₁.7_m соответственно вторые входы сумматоров группы 7₁.7_m подключены к выходам сдвигателей группы 8₁.8_m соответственно, управляющие входы сдвигателей группы 8₁.8_m подключены ко входу номера итерации 12, входы дешифраторов знака 1₁.1_m являются соответственно входами анализа знаков операндов 10₁.10_m, выходы дешифраторов знака 1₁.1_m соединены с управляющими входами сумматоров-вычитателей второй группы 3₁.3_m соответственно, выход первого дешифратора знака 1₁ подключен к управляющему входу блока изменения знака числа 5, а выходы дешифраторов знака, начиная со второго, 1₂.1_m подключены к управляющим входам сумматоров-вычитателей первой группы 2₁.2_m-1 соответственно, выход первого регистра 6₁ подключен к информационному входу первого сдвигателя 4₁, соединенного выходом с информационным входом блока изменения знака числа 5, подключенного выходом к первому входу первого сумматора-вычитателя первой группы 2₁, второй вход которого соединен с выходом регистра 6₂, управляющий вход сдвигателя 4₁ соединен со входом номера итерации 12, а выход первого сумматора-вычитателя первой группы 2₁ соединен с первым входом второго сумматора-вычитателя первой группы 2₂; сумматоры-вычитатели первой группы 2₁.2_m-1 соединены в цепочку, в которой первый вход каждого последующего сумматора вычитателя соединен с выходом предыдущего сумматора-вычитателя, а второй вход j-го сумматора-вычитателя первой группы, где j 1, 2, m-1, соединен с выходом (j+1)-го регистра; выход последнего сумматора-вычитателя первой группы 2_m-1 соединен со входом третьего сдвигателя 4₃, подключенного выходом к первым входам сумматоров-вычитателей второй группы, начиная со второго, 3₂.3_m; выход сдвигателя 4₃ соединен со входом сдвигателя 4₂, подключенного выходом к первому входу первого сумматора-вычитателя второй группы 3₁, управляющий вход сдвигателя 4₂ соединен со входом номера итерации 12; вторые входы сумматоров-вычитателей второй группы 3₁.3_m подключены к выходам сумматоров группы 7₁.7_m соответственно, а выходы сумматоров вычитателей второй группы 3₁.3_m являются выходами устройства 11₁.11_m соответственно.

Работу устройства можно описать следующими выражениями:

где p 1+2^-(2i+k);
a 2(-2^-iX₁C₁+X₂C₂+X₃C₃+.+X _mC_m);
C_j sgn Z_j ±1 ( j 1, 2, m);
i 0, 1, 2,n-1;
m 2^k+1;
n число точных двоичных цифр результата.

Алгоритм описывает одно из n преобразований отражения, в результате которых исходный вектор X₀ ложится на первую из m осей координат, а остальные координаты вектора будут равны нулю. В результате преобразования вектор претерпевает деформацию на величину

поэтому для сохранения ортогональности преобразования после выполнения последней итерации, необходимо производить масштабирование путем умножения элементов вектора на величину, обратную r (2) в умножителе Y так, как показано на фиг. 2.

Рассмотрим работу устройства на i-ой итерации. Операнды компоненты входного вектора заносятся в регистры 6₁.6_m по входам 9₁.9_m и подаются на входы 10₁.10_m соответственно. Группа сдвигателей 8₁.8_m и группа сумматоров 7₁.7_m служит для формирования величин X_j(1+2^-(2i+k)). Группа сдвигателей 8₁. 8_m служит для сдвига числа на 2i+k разрядов вправо. На сумматорах группы 7₁. 7_m производится суммирование величин X_j и X_j2^-(2i+k) (j 1, 2,m). Сдвигатели 4₁ и 4₂ служат для сдвига числа на i разрядов вправо, поэтому на выходе блока изменения знака числа 5 получится величина -2^-iX₁sgn Z₁, к которой на первом сумматоре вычитателе первой группы 2₁ прибавится (вычтется) величина X₂sgn Z₂. Таким образом, на выходе последнего сумматора-вычитателя первой группы 2_m-1 получится выражение (-2^-iX₁ C₁+X₂C₂+.+X_mC _m), которое поступит на вход сдвигателя 4₃. Сдвигатель 4₃ предназначен для умножения числа на 2 (сдвига влево на 1 разряд), и на его выходе будет получено значение a. Сумматоры-вычитатели второй группы 3₁.3_m построчно реализуют вычисления (1), причем для вычисления значения первой величины результирующего вектора используется сдвигатель 4₂, который формирует величину 2^-ia. Дешифраторы знака служат для выработки сигналов управления сумматорами-вычитателями по знакам входных операндов 10₁.10_m.

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

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

В отличие от прототипа в предлагаемом устройстве не реализуется операция умножения и заменяется сдвигом, что уменьшает время преобразования на время порядка n сложений (время реализации операции умножения). Таким образом, при обработке вектора в конвейерном режиме, как показано на фиг. 2, время преобразования уменьшается на время порядка n x n (n²) операций сложения. Для сохранения ортогональности преобразования, после выполнения n итераций, необходимо произвести операцию масштабирования путем умножения элементов вектора на величину, обратную r (2) в умножителе 14, как показано на фиг. 2.

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

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

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

РИСУНКИ

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