МАТРИЧНЫЙ СПЕЦПРОЦЕССОР Российский патент 1997 года по МПК G06F17/16 

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

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

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

Наиболее близким по технической реализации является устройство для определения модуля трехмерного вектора (авт. свид. СССР N 1205139), реализующее итерационный алгоритм перемещения трехмерного вектора с помощью последовательности из n преобразований отражения до его совпадения с осью абсцисс.

Одним из основных недостатков этого устройства является большое время определения модуля m-мерного вектора, которое равно порядка m/2 циклов по n итераций. Кроме того, при помощи этого устройства невозможно осуществить решение систем линейных алгебраических уравнений с треугольной матрицей (выполнить "обратный ход" для решения систем линейных алгебраических уравнений) и осуществить преобразование матрицы по методу Гаусса или Гаусса-Жордана. Между тем названные операции составляют математическое содержание значительной части практических задач.

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

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

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

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

На фиг. 1 представлена схема матричного спецпроцессора, где 1₁.1_m регистры операндов, 2₁.2_m - дешифраторы знака, 3₁.3_2m-1 сумматоры-вычитатели, 4₁, 4₂, 4₃ сдвигатели, 5 -вход задания двоичного кода номера итерации, 6₁. 6_m-1 схемы ИСКЛЮЧАЮЩЕЕ ИЛИ, 7₁.7_m+3 мультиплексоры, 8 блок умножения, 9 блок изменения знака числа, 10₁.10_m входы операндов, 11 вход синхронизации, 12₁. 12_m выходы спецпроцессора, 13₁.13_m входы анализа знака операнда, 14 вход задания двоичного кода веса обрабатываемого разряда, 15 вход задания двоичного кода режима работы спецпроцессора.

На фиг. 2 представлена схема для преобразования вектора в конвейерном режиме, на котором U₁. U_n устройства, изображенные на фиг. 1, X входной вектор размерности m, Y результирующий вектор той же размерности, X^(j) вектор, обрабатываемый устройством U_j, Z - шина знаков операндов на n итерациях, Z^(j) шина знаков операндов на j-й итерации.

На фиг. 3 представлена схема для триангуляции матрицы A(mxm), столбцы которой поданы на устройства U₁.U_m, каждое из которых является устройством, изображенным на фиг. 2.

На фиг. 4 представлена схема для решения систем линейных алгебраических уравнений с треугольной матрицей, где U₁.U₃ устройства, каждое из которых является устройством, изображенным на фиг. 2, a_ij - элементы матрицы системы до обработки, элементы матрицы системы после обработки, b_i, элементы столбца свободных членов до и после обработки соответственно.

Спецпроцессор содержит m регистров 1₁.1_m, 2m-1 сумматоров-вычитателей 3₁.3_2m-1, m дешифраторов знака 2₁.2_m, m-1 схему ИСКЛЮЧАЮЩЕЕ ИЛИ 6₁.6_m-1, m+3 мультиплексора 7₁.7_m+3, три сдвигателя 4₁, 4₂, 4₃, блок изменения знака числа 9, блок умножения 8 на одну из n констант, m входов операндов 10₁.10_m, m входов анализа знака операнда 13₁.13_m, выходов 12₁.12_m, вход задания двоичного кода номера итерации 5, вход задания двоичного кода режима работы 15, вход задания двоичного кода веса обрабатываемого разряда 14, причем входы регистров 1₁.1_m являются входами операндов 10₁.10_m, а выходы подключены к входам первого слагаемого (уменьшаемого) выходных сумматоров-вычитателей 3_m. 3_2m-1 соответственно, входы дешифраторов знака 2₁.2_m являются соответственно входами анализа знака операнда 13₁.13_m, выходы дешифраторов знака 2₂.2_m соединены с вторыми входами схем ИСКЛЮЧАЮЩЕЕ ИЛИ 6₁.6_m-1 соответственно, первые входы этих схем подключены к выходу дешифратора знака 2₁, а выходы соединены с первыми информационными входами мультиплексоров 7₁.7_m-1 соответственно, вторые информационные входы этих мультиплексоров соединены с выходами дешифраторов знака 2₂.2_m соответственно, вход задания двоичного кода номера итерации 5 подключен к управляющим входам сдвигателей 4₁, 4₂, 4₃ и блока умножения 8, выход регистра 1₁ подключен через сдвигатель 4₁ и блок изменения знака числа 9 к входу первого слагаемого (уменьшаемого) сумматора-вычитателя 3₁, вход второго слагаемого (вычитаемого) которого соединен с выходом регистра 2₂, управляющий вход с выходом мультиплексора 7₁, а выход с входом первого слагаемого (уменьшаемого) сумматора-вычитателя 3₂, сумматоры-вычитатели 3₁.3_m-1 соединены в цепочку, j-й элемент которой входом первого слагаемого (уменьшаемого) подсоединен к выходу (j-1)-го элемента, входом второго слагаемого (вычитаемого) к выходу (j+1)-го регистра, управляющим входом к выходу мультиплексора 7_j, а входом к входу первого слагаемого (уменьшаемого) (j+1)-го элемента, выход сумматора-вичитателя 3_m-1 соединен с информационным входом блока умножения 8, выход которого через сдвигатель 4₂ подключен к входу второго слагаемого (вычитаемого) сумматора-вычитателя 3_m и непосредственно к первому информационному входу мультиплексора 7_m, выход сумматор-вычислителя 7_m подключен к второму информационному входу мультиплексора 7_m+3, первый информационный вход которого соединен с выходом первого регистра, а выход с первым выходом спецпроцессора 12₁, второй информационный вход мультиплексора 7_m соединен через сдвигатель 4₃ с выходом регистра 1₁, а выход подключен к первому информационному входу мультиплексора 7_m+1 и к входам второго слагаемого (вычитаемого) сумматоров-вычитателей 3_m+2.3_2m-1, второй информационный вход мультиплексора 7_m+1 подключен к входу задания двоичного кода веса обрабатываемого разряда 14, а выход к входу второго слагаемого (вычитаемого) сумматора-вычитателя 3_m+1, управляющие входы сумматоров-вычитателей 3_m+2.3_2m-1 подключены к выходам мультиплексоров 7₂.7_m-1 соответственно, а управляющий вход сумматора-вычитателя 3_m+1 подключен к выходу мультиплексора 7_m+2, первый информационный вход которого соединен с выходом мультиплексора 7₁, а второй с выходом мультиплексора 7₂, управляющие входы всех мультиплексоров соединены с входом задания двоичного кода режима работы спецпроцессора 15, выходы сумматоров-вычитателей 3_m+1.3_2m-1 являются выходами спецпроцессора 10₂.10_m соответственно, выход дешифратора знака 2₁ соединен с управляющим входом блока изменения знака числа 9 и управляющим входом сумматора-вычитателя 3_m, входы синхронизации регистров 1₁.1_m соединены с входом синхронизации спецпроцессора 11.

Спецпроцессор может работать в одном из трех режимов.

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

где i номер итерации.

Значения величин a и с_j определяются режимом работы спецпроцессора.

В режиме 1

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

В режиме 2

В этом режиме алгоритм (1) описывает одно из n преобразований вектора по методу Гаусса (или Гаусса-Жордана), в результате которых исходных исходный вектор X₀(x(0)1

, x(0)2, ..., x(0)m преобразуется в вектор Y(x(0)1, 0, ..., 0).
Режим 3 является вспомогательным и предназначен для выполнения операции деления на этом же устройстве, что необходимо для решения систем линейных алгебраических уравнений с треугольной матрицей.

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

где

В этом режиме исходный вектор X₀(x(0)1

, 0, x(0)3) преобразуется в вектор Y(x(0)1, x(0)3/x(0)1, 0). Остальные координаты входного и выходного вектора в этом режиме не используются и могут быть произвольными.

Рассмотрим работу спецпроцессора на i-ой итерации. Операнды-компоненты вектора X_i заносятся в регистры 1₁.1_m по входам 10₁.10_m соответственно и фиксируются в этих регистрах по сигналу синхронизации, поступающему по входу 11 спецпроцессора. На входы 13₁.13_m подаются операнды, по знакам которых дешифраторы знака 2₁.2_m и схемы ИСКЛЮЧАЮЩЕЕ ИЛИ 6₁.6_m-1 вырабатывают сигналы управления сумматорами-вычитателями согласно соотношениям (2), (3), (5).

Мультиплексоры 7₁.7_m-1 и 7_m+2 служат для коммутации выработанных сигналов управления сумматорами-вычитателями в соответствии с режимом, двоичный код которого задается по входу 15. Сдвигатели 4₁ и 4₂ служат для сдвига числа на i разрядов, поэтому на выходе блока изменения знака числа 9 получится величина -2^-i•x₁•C₁, к которой на сумматоре-вычитателе 3₁ прибавится (вычтется) величина x₂•c₂. Таким образом, на выходе сумматора-вычитателя 3_m-1 получится выражение -2^-i•x₁•c₁+x₂•c₂ + + x_m•c_m, которое поступит на вход блока умножения 8. Блок умножения предназначен для умножения входного числа в зависимости от номера инерции на одну из n констант -2•(m-1+2^-i)^-1. На выходе блока умножения будет получено значение a, которое через сдвигатель 4₂, формирующий значение a•2^-i, подается на сумматор-вычитатель 3_m. Полученное таким образом значение a соответствует режиму 1. Для режимов 2 и 3 значение a, равное x₁•2^-i, формируется на выходе сдвигателя 4₃. Мультиплексор 7_m выбирает одно из этих значений в зависимости от режима. С выхода мультиплексора 7_m значение a поступает на входы второго слагаемого (вычитаемого) сумматоров-вычитателей 7_m+2.7_2m-1 непосредственно, a на соответствующий вход сумматора-вычитателя 3_m+1 через мультиплексор 7_m+1, на второй информационный вход которого подается значение d с входа задания двоичного кода веса обрабатываемого разряда 14. Мультиплексор 7_m+1 в режимах 1 и 2 подключает на вход второго слагаемого (вычитаемого) сумматора-вычитателя 3_m+1 значение a, а в режиме 3 значение d согласно (4). В режимах 1 и 2 сумматоры-вычитателя 3_m.3_2m-1 построчно реализуют соотношения (1), а в режиме 3 сумматоры-вычитатели 3_m.3_m+2 построчно реализуют соотношения (4). Значения Y₂. Y_m, получаемые на выходах сумматоров-вычислителей 3_m+1.3_2m-1 соответственно, подаются непосредственно на выходы спецпроцессора, а значение Y₁ поступает на выход спецпроцессора через мультиплексор 7_m+3, который соединяет соответствующий выход с выходом сумматора-вычитателя 3_m в режиме 1 и с выходом регистра 1₁ в режимах 2 и 3. Все мультиплексоры управляются от входа задания двоичного кода режима работы спецпроцессора 15.

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

В режимах 1 и 2 при обработке главного столбца входы 13₁.13_m j-го устройства соединяются с входами 10₁10_m этого устройства соответственно, а при обработке зависимого столбца с входами 10₁.10_m устройства, обрабатывающего главный столбец. В режиме 3 входы 13₁ и 13₃ j-го устройства соединяются соответственно с входами 10₁ и 10₃ этого устройства. Сигналы, подаваемые на входы 13₁.13_m j-го устройства образуют шины Z^(j) и общую шину Z, показанные на фиг.2.

На фиг. 3 представлена схема соединения m устройств, каждое из которых представляет собой устройство, показанное на фиг.2. Эта схема предназначена для приведения матрицы A ({a_ij}) размерности (mxm) к верхнетреугольному виду путем ортогональных преобразований отражения (в режиме 1) или путем разложения матрицы на треугольные множители по методу Гаусса (в режиме 2). При этом устройство U₁ обрабатывает главный столбец, а устройства U₂.U_m зависимые столбцы матрицы. Входы Z каждого устройства соединены по описанным выше правилам и образуют шину Z на фиг.3. В результате преобразования все элементы первого столбца матрицы, кроме , будут равны нулю, а элемент будет равен модулю вектора (в режиме 1) или a₁₁ (в режиме 2). После исключения (обнуления) поддиагональных элементов первого столбца та же процедура проводится с матрицей порядка (m-1) для исключения поддиагональных элементов второго столбца.

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

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

Для триангуляции матрицы при решении систем линейных алгебраических уравнений необходимо добавить устройство U_m+1, обрабатывающее зависимый столбец в выбранном режиме, для обработки столбца свободных членов аналогично столбцам матрицы.

На фиг. 4 представлена схема для выполнения "обратного хода" (получения решения из треугольной или диагональной матрицы) при решении систем линейных алгебраических уравнений. Устройства U₁, U₂, U₃ представляют собой устройства, показанные на фиг.2. Устройство U₁ работает в режиме 3, на его вход X подается вектор (а_mm, O, b_m), где a_mm элемент матрицы системы, b_m элемент столбца свободных членов, на выходе Y устройства получается вектор, первым элементом которого является значение элемента вектора решения x_m=b_m/a_mm. В случае диагональной матрицы для получения вектора решения достаточно проделать m подобных операций. В случае треугольной матрицы после получения x_m необходимо перейти к матрице размерности (m-1), преобразовав при этом вектор свободных членов. Для этого служат устройство U₂, обрабатывающее зависимый столбец-вектор (x_m, b₁, b_m-1), и устройство U₃, обрабатывающее главный столбец-вектор (1, а_1m, a_m-1m). В результате на выводах устройства U₂ получается вектор Y (x_m, b₁-a_1mx_m, b_m-1-a_m-1mx_m).

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

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

Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЭВМ. Целью изобретения является расширение класса решаемых задач. Поставленная цель достигается тем, что матричный спецпроцессор содержит m регистров, m дешифраторов знака, 2m-1 сумматоров-вычитателей, m-1 схем ИСКЛЮЧАЮЩЕЕ ИЛИ, три сдвигателя, m+3 мультиплексора (m - размерность обрабатываемой матрицы). 4 ил.

Матричный спецпроцессор, содержащий три регистра, три дешифратора знака, шесть сумматоров-вычитателей, три сдвигателя, причем управляющие входы сдвигателей соединены с входом задания двоичного кода номера итерации спецпроцессора, выход первого регистра соединен с информационным входом первого сдвигателя, отличающийся тем, что в него введены m-3 регистров, m-3 дешифраторов знака, 2m-7 сумматоров-вычитателей, m-1 схем исключающее или, m+3 мультиплексоров, где m размерность обрабатываемой матрицы, блок умножения, блок изменения знака числа, причем информационные входы всех регистров являются входами операндов спецпроцессора, входы синхронизации всех регистров соединены с входом синхронизации спецпроцессора, управляющий вход блока умножения подключен к входу задания двоичного кода номера итерации спецпроцессора, выход первого сдвигателя через блок изменения знака числа, управляющий вход которого соединен с выходом первого дешифратора знака, подключен к первому входу цепочки сумматоров-вычитателей, у которой вход первого слагаемого (уменьшаемого) j-го элемента (j=1,2,m-1) соединен с выходом (j-1)-го элемента, а вход второго слагаемого (вычитаемого) с выходом (j+1)-го регистра, выход последнего элемента цепочки подключен к информационному входу блока умножения, выход которого соединен с информационным входом второго сдвигателя, вход второго слагаемого (вычитаемого) первого выходного сумматора-вычитателя соединен с выходом второго сдвигателя, вход первого слагаемого (уменьшаемого) i-го выходного сумматора-вычитателя (j 1, 2, m) соединен с выходом i-го регистра, выход i-го выходного сумматора вычитателя, кроме первого, подключен к i-му выходу спецпроцессора, вход i-го дешифратора знака является i-м входом анализа знака операнда спецпроцессора, выход первого дешифратора знака подключен к управляющему входу первого выходного сумматора-вычитателя, выход первого регистра через третий сдвигатель соединен с первым информационным входом m-го мультиплексора, второй информационный вход которого соединен с выходом блока умножения, а выход с входами второго слагаемого (вычитаемого) каждого выходного сумматора-вычитателя, кроме первого и второго, выход первого выходного сумматора-вычитателя соединен с вторым информационным входом (m + 3)-го мультиплексора, первый информационный вход которого соединен с выходом первого регистра, а выход с первым выходом спецпроцессора, выход j-го дешифратора знака (j 2,3,m) соединен с вторым входом (j 1)-й схемы ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которой соединен с выходом первого дешифратора знака, выход (j 1)-й схемы ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к первому информационному входу (j 1)-го мультиплексора, второй информационный вход которого соединен с выходом j-го дешифратора знака, выход j-го мультиплексора (j 1,2,m 1) подключен к управляющему входу j-го сумматора-вычитателя в цепочке и к управляющему входу (j + 1)-го выходного сумматора-вычитателя, кроме первого и второго, выход второго мультиплексора подключен к второму информационному входу (m + 2)-го мультиплексора, первый информационный вход которого соединен с выходом первого мультиплексора, а выход с управляющим входом второго выходного сумматора-вычитателя, первый информационный вход (m + 1)-го мультиплексора соединен с выходом m-го мультиплексора, второй информационный вход с входом задания двоичного кода веса обрабатываемого разряда спецпроцессора, а выход с входом второго слагаемого (вычитаемого) второго выходного сумматора-вычитателя, управляющие входы всех мультиплексоров соединены с входом задания двоичного режима работы спецпроцессора.