Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ M-МЕРНОГО ВЕКТОРА

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЭВМ. Устройство содержит m регистров p1...pm, 2m - 1 сумматоров-вычитателей s1...s2m-1, m дешифраторов знака, два сдвигателя 1, 4, блок 2 изменения знака числа, блок 3 умножения на одну из n констант, m входов x1...xm операндов, m входов z1...zm для анализа знака операнда, m выходов y1...ym результата и вход 5 номера итерации. В отличие от известных технических решений в предлагаемом устройстве происходит преобразование компонент вектора в m-мерном пространстве как одна макрооперация за время порядка длительности n операций сложения. Кроме того, результат операции не деформируется (коэффициент удлинения вектора равен единице). Эффективность достигается расширением функциональных возможностей устройства за счет m-мерного преобразования Хаусхолдера при относительно незначительных дополнительных затратах оборудования. 3 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2029356
Класс(ы) патента: G06F7/544
Номер заявки: 5023883/24
Дата подачи заявки: 22.01.1992
Дата публикации: 20.02.1995
Заявитель(и): Духнич Евгений Иванович[RU]
Автор(ы): Духнич Евгений Иванович[RU]
Патентообладатель(и): Духнич Евгений Иванович[RU]
Описание изобретения: Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЭВМ.
Известны специализированные устройства для поворота вектора по алгоритму Волдера, в которых можно вычислять модуль вектора. Устройства содержат сдвигающие регистры, коммутирующие блоки, сумматоры-вычитатели и позволяют решать задачу на порядок быстрее, чем традиционные арифметические устройства (авт. св. СССР 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), столбцы которой поданы на устройства U1...Um, каждое из которых может быть взято из фиг.1 или 2.
Устройство содержит m регистров P1...Pm, 2m-1 сумматоров-вычитателей S1. . .S2m-1, m дешифраторов d1...dm знака, два сдвигателя 1,4, блока 2 изменения знака числа, блок 3 умножения на одну из n констант, m входов х1... хm операндов, m входов z1...zm для анализа знака операнда, m выходов результата y1...ym и вход 5 номера итераций. Входы регистров р1...рm являются входами х1...хm операндов, а выходы подключены к первым входам выходных сумматоров-вычитателей Sm. . .S2m-1соответственно, управляющие входы которых соединены с выходами дешифраторов d1...dm знака, а выходы - с выходами y1.. .ym результатов соответственно. Вход 5 номера итерации подключен к управляющим входам сдвигателей 1,4 и блока 3 умножения. Выход регистра Р1 подключен через сдвигатель 1 и блок 2 изменения знака числа к первому входу сумматора-вычитателя S1, второй вход которого соединен с выходом регистра Р2, управляющий вход - к выходу дешифратора d2 знака, а выход - к первому входу сумматора-вычитателя S2. Сумматоры-вычитатели S1...Sm-1соединены в цепочку, j-й элемент которой первым входом подсоединен к выходу (j-1)-го элемента, вторым - к выходу (j+1)-го регистра, управляющим входом - к выходу дешифратора dj+1 знака, а выходом - к первому входу (j+1)-го элемента. Выход сумматора-вычитателя Sm-1соединен с входом блока 3 умножения, выход которого через сдвигатель 4 подключен к второму входу сумматора-вычитателя Sm и непосредственно к всем вторым входам остальных выходных сумматоров-вычитателей Sm+1...S2m-1. Входы дешифраторов d1...dm знака являются входами z1... zmанализа знака соответственно.
Работу устройства можно описать следующими выражениями:
y1 = x1 - a2bc1;
y2 = x2 - ac2; (1)
y3 = x3 - ac3;
˙˙˙˙˙˙˙˙˙˙˙˙˙
ym = xm - acm, где a = 2(m-1+2-i)-1(2bx1c1+x2c2+...+xmcm);
cj = sgnzj = ±1 (j = 1,2,...,m);
b = -]0,5i[ - целая часть числа, заключенного в скобках (i = 0,1,2,..., n-1).
Алгоритм описывает одно из n преобразований отражения, в результате которых исходный вектор Хо ложится на первую из m осей координат, а остальные координаты вектора равны нулю.
Рассмотрим работу устройства на i-й итерации. Операнды-компоненты вектора Xi заносятся в регистры р1...рm по входам x1...xm и подаются на входы z1. ..zm соответственно. Сдвигатели 1 и 4 служат для сдвига числа на b разрядов, поэтому на выходе блока 2 изменения знака числа получается величина 2bx1sgnz1, к которой на сумматоре-вычитателе S1прибавляется (вычитается) величина x2sgnz2. Таким образом, на выходе сумматора-вычитателя Sm-1 получается выражение (2bx1c1 + x2c2+...+xmcm), которое поступает на вход блока 3 умножения. Блок умножения предназначен для умножения входного числа в зависимости от номера итерации на одну из n констант 2 (m-1+2-i)-1, на его выходе получено значение а. Сумматоры-вычитатели Sm...S2m-1 построчно реализуют вычисления (1), причем для вычисления значения у1 используется сдвигатель 4, который формирует величину а˙ 2b. Дешифраторы знака служат для выработки управления сумматорами-вычитателями по знакам входных операндов z1...zm.
На этом работа в i-й итерации заканчивается. Следующую итерацию можно выполнить в последовательном режиме в этом же устройстве, если предварительно соединить выходы yi с входами xj и zj (j = 1,2,...,m), или в конвейерном режиме с помощью n устройств, как это показано на фиг.2.
Для выполнения быстрого преобразования Хаусхолдера над матрицей А необходимо соединить m устройств по схеме, представленной на фиг.3, где {ajl} - матрица (m x m). В результате одного преобразования Хаусхолдера все элементы первого столбца a1l' = 0 (кроме a11'). После 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-м выходом результата устройства.