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

Классы МПК:G06F7/544 для нахождения значений функций путем вычислений
Автор(ы):,
Патентообладатель(и):Духнич Евгений Иванович,
Егунов Виталий Алексеевич
Приоритеты:
подача заявки:
1995-03-01
публикация патента:

Изобретение относится к вычислительной технике и предназначено для построения на его основе специальных ЭВМ. Устройство содержит дешифраторы знака (I1-Im), первую группу сумматоров-выситателей (21-2m-1), вторую группу сумматоров-вычитателей (31-3m), сдвигатели (41-43, блок изменения знака числа (5), регистры (61-6m), группу сумматоров (71-7m), группу сдвигателей (81-8m). В устройстве производится преобразование компонент вектора в m-мерном пространстве как одна макрооперация путем ортогональных преобразований отражения без использования "длинной" операции умножения. Это приводит к увеличению быстродействия на время порядка n сложений на одной итерации и на время порядка n2 сложений при конвейерной обработке с использованием n последовательно включенных устройств. 3 ил.
Рисунок 1, Рисунок 2, Рисунок 3

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

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

Описание изобретения к патенту

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

Известны специализированные устройства, выполняющие триангуляцию матрицы (патент РФ 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-мерного вектора, где:

11.1m-дешифраторы знака;

21.2m-1-первая группа сумматоров-вычитателей;

31.3m-вторая группа сумматоров-вычитателей;

41.43-сдвигатели;

5 блок изменения знака числа;

61.6m-регистры;

71.7m-группы сумматоров;

81.8m-группа сдвигателей;

91.9m-входы операндов;

101.10m-входы анализа знаков операндов;

111.11m-выходы результатов;

12 вход номера итерации.

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

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

Устройство содержит m дешифраторов знака 11.1m, первую группу из (m-1) сумматоров вычитателей 21.2m-1, вторую группу из m сумматоров вычитателей 31.3m, три сдвигателя 41.43, блок изменения знака числа 5, m регистров 61. 6m, группу из m сумматоров 71.7m, группу из m сдвигателей 81.8m, m входов операндов 91.9m, m входов анализа знака операндов 101.10m, m выходов результата 111.11m, вход номера итерации 12, причем входы регистров 61.6m являются входами операндов 91.9m, а выходы подключены ко входам сдвигателей группы 81.8m и к первым входам сумматоров группы 71.7m соответственно вторые входы сумматоров группы 71.7m подключены к выходам сдвигателей группы 81.8m соответственно, управляющие входы сдвигателей группы 81.8m подключены ко входу номера итерации 12, входы дешифраторов знака 11.1m являются соответственно входами анализа знаков операндов 101.10m, выходы дешифраторов знака 11.1m соединены с управляющими входами сумматоров-вычитателей второй группы 31.3m соответственно, выход первого дешифратора знака 11 подключен к управляющему входу блока изменения знака числа 5, а выходы дешифраторов знака, начиная со второго, 12.1m подключены к управляющим входам сумматоров-вычитателей первой группы 21.2m-1 соответственно, выход первого регистра 61 подключен к информационному входу первого сдвигателя 41, соединенного выходом с информационным входом блока изменения знака числа 5, подключенного выходом к первому входу первого сумматора-вычитателя первой группы 21, второй вход которого соединен с выходом регистра 62, управляющий вход сдвигателя 41 соединен со входом номера итерации 12, а выход первого сумматора-вычитателя первой группы 21 соединен с первым входом второго сумматора-вычитателя первой группы 22; сумматоры-вычитатели первой группы 21.2m-1 соединены в цепочку, в которой первый вход каждого последующего сумматора вычитателя соединен с выходом предыдущего сумматора-вычитателя, а второй вход j-го сумматора-вычитателя первой группы, где j 1, 2, m-1, соединен с выходом (j+1)-го регистра; выход последнего сумматора-вычитателя первой группы 2m-1 соединен со входом третьего сдвигателя 43, подключенного выходом к первым входам сумматоров-вычитателей второй группы, начиная со второго, 32.3m; выход сдвигателя 43 соединен со входом сдвигателя 42, подключенного выходом к первому входу первого сумматора-вычитателя второй группы 31, управляющий вход сдвигателя 42 соединен со входом номера итерации 12; вторые входы сумматоров-вычитателей второй группы 31.3m подключены к выходам сумматоров группы 71.7m соответственно, а выходы сумматоров вычитателей второй группы 31.3m являются выходами устройства 111.11m соответственно.

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

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

где p 1+2-(2i+k);

a 2(-2-iX1C1+X2C2+X3C3+.+X mCm);

Cj sgn Zj устройство для вычисления модуля m-мерного вектора, патент № 20806501 ( j 1, 2, m);

i 0, 1, 2,n-1;

m 2k+1;

n число точных двоичных цифр результата.

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

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

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

Рассмотрим работу устройства на i-ой итерации. Операнды компоненты входного вектора заносятся в регистры 61.6m по входам 91.9m и подаются на входы 101.10m соответственно. Группа сдвигателей 81.8m и группа сумматоров 71.7m служит для формирования величин Xj(1+2-(2i+k)). Группа сдвигателей 81. 8m служит для сдвига числа на 2i+k разрядов вправо. На сумматорах группы 71. 7m производится суммирование величин Xj и Xj2-(2i+k) (j 1, 2,m). Сдвигатели 41 и 42 служат для сдвига числа на i разрядов вправо, поэтому на выходе блока изменения знака числа 5 получится величина -2-iX1sgn Z1, к которой на первом сумматоре вычитателе первой группы 21 прибавится (вычтется) величина X2sgn Z2. Таким образом, на выходе последнего сумматора-вычитателя первой группы 2m-1 получится выражение (-2-iX1 C1+X2C2+.+XmC m), которое поступит на вход сдвигателя 43. Сдвигатель 43 предназначен для умножения числа на 2 (сдвига влево на 1 разряд), и на его выходе будет получено значение a. Сумматоры-вычитатели второй группы 31.3m построчно реализуют вычисления (1), причем для вычисления значения первой величины результирующего вектора используется сдвигатель 42, который формирует величину 2-ia. Дешифраторы знака служат для выработки сигналов управления сумматорами-вычитателями по знакам входных операндов 101.10m.

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

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

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

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

Класс G06F7/544 для нахождения значений функций путем вычислений

способ создания представления результата вычисления, линейно зависимого от квадрата значения -  патент 2375743 (10.12.2009)
арифметическое устройство -  патент 2268482 (20.01.2006)
арифметические операции в системе обработки данных -  патент 2225638 (10.03.2004)
устройство для вычисления собственных значений матриц -  патент 2168760 (10.06.2001)
времяимпульсный квадратичный преобразователь -  патент 2149449 (20.05.2000)
кодирующий времяимпульсный преобразователь -  патент 2141721 (20.11.1999)
устройство для вычисления функции близости текущих и эталонных признаков объектов с адаптацией к условиям обстановки -  патент 2112271 (27.05.1998)
устройство для определения модуля трехмерного вектора -  патент 2040039 (20.07.1995)
устройство для вычисления модуля m-мерного вектора -  патент 2029356 (20.02.1995)
устройство для приведения функций к мультипликативному алгоритму вычислений -  патент 2028659 (09.02.1995)
Наверх