УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА Российский патент 1997 года по МПК G06F7/544 

Описание патента на изобретение RU2080650C1

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

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

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

где p 1+2-(2i+k);
a 2(-2-iX1C1+X2C2+X3C3+.+X mCm);
Cj sgn Zj ±1 ( j 1, 2, m);
i 0, 1, 2,n-1;
m 2k+1;
n число точных двоичных цифр результата.

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

поэтому для сохранения ортогональности преобразования после выполнения последней итерации, необходимо производить масштабирование путем умножения элементов вектора на величину, обратную 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.

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

Похожие патенты RU2080650C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА 1992
  • Духнич Евгений Иванович[Ru]
RU2029356C1
МАТРИЧНЫЙ СПЕЦПРОЦЕССОР 1994
  • Духнич Евгений Иванович
  • Деревенсков Сергей Олегович
RU2079879C1
Устройство для определения модуля трехмерного вектора 1983
  • Духнич Евгений Иванович
SU1142830A1
Устройство для определения модуля трехмерного вектора 1984
  • Духнич Евгений Иванович
  • Духнич Олег Евгеньевич
SU1205139A1
Устройство для преобразования сферическихКООРдиНАТ B пРяМОугОльНыЕ 1978
  • Духнич Евгений Иванович
  • Митраков Виталий Алексеевич
SU805308A1
Устройство для поворота вектора с коррекцией 1980
  • Денисов Виктор Маевич
  • Духнич Евгений Иванович
SU951299A1
Арифметическое устройство 1979
  • Духнич Евгений Иванович
  • Митраков Виталий Алексеевич
  • Денисов Виктор Маевич
SU826344A1
Вычислительное устройство 1986
  • Бартошевский Валерий Дмитриевич
  • Владимиров Виктор Владимирович
  • Духнич Евгений Иванович
  • Орлов Борис Константинович
SU1361546A1
Вычислительное устройство 1981
  • Владимиров Виктор Владимирович
  • Духнич Евгений Иванович
  • Заярный Петр Пантелеевич
  • Митраков Виталий Алексеевич
  • Орлов Борис Константинович
SU1136147A1
Вычислительное устройство 1983
  • Синенко Владимир Николаевич
  • Духнич Евгений Иванович
  • Бартошевский Валерий Дмитриевич
  • Владимиров Виктор Владимирович
  • Орлов Борис Константинович
SU1167604A1

Иллюстрации к изобретению RU 2 080 650 C1

Реферат патента 1997 года УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА

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

Формула изобретения RU 2 080 650 C1

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

Документы, цитированные в отчете о поиске Патент 1997 года RU2080650C1

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА 1992
  • Духнич Евгений Иванович[Ru]
RU2029356C1
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1

RU 2 080 650 C1

Авторы

Духнич Евгений Иванович

Егунов Виталий Алексеевич

Даты

1997-05-27Публикация

1995-03-01Подача