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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных в том числе и систолических устройств, предназначенных для решения задач линейной алгебры. Предложенное устройство позволяет вдвое сократить объем оборудования и повысить точность вычислений по сравнению с прототипом. Устройство содержит (п/2+1) процессорных элементов (где п - четное, порядок матрицы коэффициентов системы) и блок синхронизации. Принцип работы устройства основан на решении системы линей ных алгебраических уравнений вида Ах b методом Жордана - Гаусса с частичным выбором ведущего элемента по столбцу. 5 ил., 1 табл. сл с

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5п5 G 06 F 15/347, 15/324

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ;,;-, О

К АВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ (2 1) 4878784/24 (22) 21.09.90 (46) 23.07,93, Бюл. М 27 (71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции (72) P.Âûæèêîâñêè (PL), Ю,С,Каневский и О,В.Масленников (SU) (56) R, Melhem, Parallel . Gauss — Jordan

elimination for the solution of dense linear

systems. — Parallel Comp. М 4 1987, с.339, М ногофун кциональн ые систолические структуры./Под ред.Дуброва Я.А, Препринт

N 20-89, Львов, 1989, ин-т прикладных проблем механики и математики АН УССР, с.38. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ

УРАВНЕНИЙ

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

Жордана-Гаусса с частичным выбором ведуще го зле ме нта по столб цу.

На фиг. 1 представлена структурная схема устройства для решения СЛАУ; на фиг. 2 — структурная схема первого процессорного элемента; на фиг. 2 — структурная схема возможного варианта построения блока синхронизации; на фиг, 4 — структурная схема i-го процессорного элемента

„„ 4 „„1829043 А1 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных в том числе и систолических устройс в, предназначенных для решения задач линейной алгебры. Предложенное устройство позволяет вдвое сократить объем оборудования и повысить точность вычислений по сравнению с прототипом.

Устройство содержит (и/2+1) процессорных элементов (где и — четное, порядок матрицы коэффициентов системы) и блок синхронизации. Принцип работы устройства основан на решении системы линейных алгебраических уравнений вида Ах = Ь методом Жордана — Гаусса с частичным выбором ведущего элемента по столбцу. 5 ил., 1 табл. (i = 2, и/2+1); на фиг, 5 — диаграмма работы блока синхронизации для случая п = 4.

В тексте приведена таблица, иллюстрирующая работу устройства для случая и = 4.

Устройство для решения СЛАУ содержит процессорные элементы 1.1 — 1,(n/2+1), где n — четное, причем выходы процессорного элемента 1,i с первого по пятый (i = 1,n/2) подключены ко входам, соответственно, с первого по пятый процессорного элемента

1,(i+1), входы процессорного элемента 1,1 с первого по пятый, подключены, соответственно к выходам с первого по пятый блока

2 синхронизации, вход которого является входом запуска устройства, выходы процессорного элемента 1.(n/2+1), с четвертого по шестой подключены, соответственно, к его входам с девятого по одиннадцатый, шестой выход процессорного элемента 1,i (i = 2,п72) 1829043 подключен к шестому входу процессорного элемента 1,(i+1), выходы процессорного элемента 1,i с седьмого по одиннадцатый (i = З,п72ч.1), подключены соответственно, ко входам с седьмого по одиннадцатый процессорного элемента 1,(i-1), одиннадцатый выход процессорного элемента 1.2 подключен к шестому входу процессорного элемента 1.1, шестой выход которого является выходом устройства, вход которого подключен к седьмому входу процессорного эле".ента 1.1 и к двенадцатым входам остальных процессорных элементов, первый и ВтОрОй ВыхОды процессорного элемента 1,(п/2+1) подключены к седьмому и восьмому одам процессорного элемента

1.(n/2+1) соответственно, Процессорный элемент 1,1, содержит блок 3 деления, выход которого подключен ко входу первого блока элементов задержки

4, а первый вход его связан с выходом первого регистра 5, вход которого связан с выходом первого коммутатора 6 и со входом второго регистра 7, выход которого подключен к первым входам схемы 8 сравнения, и первого 6 и второго 9 коммутаторов, вторые входы которых также объединены и подключены к выходу третьего коммутатора 10, первый и второй входы которого являются, соответственно, шестым и седьмым входами первого процессорного элемента, выходы которого, с первого по третий, подключены, соответственно, выходам с первого по третий второго блока элементов задержки 11, входы которого с первого по третий, являются соответственно первым, вторым и пятым входами первого процессорного элемента, пятый и четвертый выходы которого подключены соответственно, к выходам первого 4 и третьего 12 блока элементов задержки, вход которого связан с управляющими входами коммутаторов 6, 9 и с выходом элемента И 13, первый вход которого подключен к третьему входу первого процессорного элемента, четвертый вход которого подключен к первому входу элемента ИЛИ 14, второй вход которого является выходом схемы 8 сравнения, выход коммутатора 9 подключен ко входу четвертого блока элементов задержки 15, выход которого является шестым выходом первого процессорного элемента и подключен ко второму входу блока 3 деления, вход выбора режима которого (деление с обратным знаком или нахождение обратной величины) связан с управляющим входом регистра 5 и является пятым входом первого процессорного элемента, управляющий вход коммутатора 10 подключен ко второму входу первого процессорного элемента, выход

55 элемента ИЛИ 14 связан со вторым входом элемента И 13. Процессорный элемент 1,i (i = 2, n/2+1) содержит умножитель

16, первый вход которого подключен к выходу первого регистра 17, вход которого подключен к выходу первого коммутатора 18 и ко входу второго регистра 19, выход которого подключен к первым входам первого 18 и второго 20 коммутаторов, вторые входы которых объединены и связаны с выходом третьего коммутатора 21, первый вход которого подключен к выходу четвертого коммутатора 22, первый и второй входы которого являются, соответственно, шестым и одиннадцатым входами процессорного элемента

1,i, входы и выходы которого с первого по третий, подключены, соответственно, ко входам и выходам с первого по третий, первого блока элементов задержки 23, второй вход умножителя 16 подключен к выходу пятого коммутатора 24, первый и второй входы которого являются, соответственно, пятым и десятым входами процессорного элемента 1,i и подключены, соответственно, ко входам второго — 25 и третьего 26, блоков элементов задержки, выходы которых являются соответственно пятым и десятым выходами процессорного элемента 1.i, четвертый и девятый выходы которого подключены к выходам соответственно четвертого 27 и пятого 28 блоков элементов задержки, вход которого является входом процессорного элемента 1л и подключен к первому входу шестого коммутатора 29, первый выход которого подключен к управляющим входам коммутаторов 18 и 20, выход коммутатора 20 подключен ко входу шестого блока элементов задержки 30, выход которого связан с первым входом сумматора 31, выход которого является шестым и одиннадцатым выходами процессорного элемента 1,i, седьмой и восьмой выходы которого подключены, соответственно, к первому и второму выходам седьмого блока элементов задержки 32, первый и второй входы которого являются соответственно седьмым и восьмым входами процессорного элемента 1., четвертый вход которого подключен ко входу блока элементов задержки

27, и к третьему входу коммутатора 28, второй и четвертый входы которого подключены соответственно к восьмому и второму входам процессорного элемента 1., второй выход коммутатора 29 является управляющим входом коммутатора 21, второй вход которого подключен к двенадцатому входу процессорного элемента 1л, управляющий вход коммутатора 22 подключен к седьмому входу процессорного элемента и ко входу инвертора 33, выход которого связан с пер1829043 вым входом элемента ИЛИ 34, второй вход которого подключен к первому входу процессорного элемента, третий вход процессорного элемента связан с управляющими входами сумматора 31 (сложение или пропуск операнда) и регистра 17, управляющий вход коммутатора 29 подключен к выходу элемента ИЛИ 34, и ко входу восьмого блока элементов задержки 35, выход которого подключен к управляющему входу коммутатора 24, выход умножителя 16 подключен ко второму входу сумматора 31.

Блок 2 синхронизации может содержать (см. фиг. 3) счетчик 52, выход отрицательного переноса которого является пятым выходом блока 2 и связан со входом элемента

ИЛИ 53, выход которого подключен к J-и к— выходам J-к триггеров 36, и ко входу D-триггера 37, выход которого является четвертым выходом блока 2 и подключен ко входу выбора режима (параллельное занесение значения (и-1) или счет в режиме вычитания) счетчика 52 и к R-входу асинхронного Sтриггера 38, прямой выход которого является вторым выходом блока 2, вход запуска которого связан со входом элемента ИЛИ 53 и со входом D-триггера 39, выход которого связан со входами элементов И 40, 42 и с

S-входами триггера 362 и 38, инверсный выход которого подключен ко входам элементов И 41 и 43, выходы которых подключены, соответственно к синхровходам D-триггеров 44, 46 и 45, 47, а также к синхровходам блоков элементов задержки 54 и 55, выходы которых являются входами коммутатора 48 и подключены ко входам элементов И 49, 56 и 50, 57, входы установки в нуль D-триггеров

44, 45, связаны со входами установки в единицу D-триггеров 46, 47 и триггеров блоков элементов задержки, и подключены к выходам элементов И 40 и 42 соответственно, третий выход блока 2 подключен к выходу коммутатора 48, управляющий вход которого подключен ко входам элементов И 42, 43 и к прямому выходу j-k-триггера 361, инверсный выход которого подключен ко входам элементов И 40, 41, выходы D-триггеров 45 и 44 подключены ко входам элементов И 50 и 49, выходы которых связаны со входами

D-триггеров 47 и 46, выходы которых подключены ко входам элементов И 57 и 56 соответственно, на входы D-триггеров 44, 45 постоянно заводится значение логической единицы. Кроме того, в состав блока синхронизации входит генератор тактовых импульсов 51, выход которого подключен ко входам элементов И 41 и 43, к синхровходам счетчика 52, триггеров 36, 37, 39, а также к синхровходам всех регистров и блоков элементов задержки всех процессорных элементов (на чертежах для простоты эти связи не показаны).

Блоки элементов задержки представляют собой цепочку из и-1 (блок 15, 54, 55, 30)

5 или п (все остальные блоки) регистров (блоки 4, 15, 25, 26, 30) или D-триггеров (блоки

12, 27, 28, 54, 55, 35, 11, 23 и 32), вход первого из которых является входом соответствующего блока, а выход последнего—

10 выходом блока. Таким образом они формируют задержку сигнала или операнда на п или и-1 тактов. Необходимо отметить, что блоки 11, 23 и 32 содержат три независимых цепочки из n D-триггеров и осуществляют

15 задержку на R тактов сразу трех (блок 32двух) управляющих сигналов, поступающих на их входы, Устройство для решения СЛАУ предназначено для решения СЛАУ вида

311 Х1 + 312 X2 + " + a1n Xn = a1(n 1):

321 Х1+ агг X2 + ... + 32n Хл = 32(n-1); ап1 Х1+ ап2 Х2+ ... + апп Xn = ап(п+1) 25 методом Гаусса-Жордана, который можно записать в рекуррентном виде следующим образом:

3 ) =а|;, i=1,n;j=1, п-1; (1)

i=1,п, mjj = -ау /ajj; j = i+1, j1+i-1;

m(n+j)i = 1/aii, kjk 3 ki - тэ е;к : j = ч1, п н-1:

k = i+1, и+1, i+1,, 1, 3(n+j)k — m(n+i)i ajk k = i+1, П+1.

35

B результате выполнения этого алгоритма определяются искомые элементы xj

Xi = а (n+i)(n+1), = 1,R, С целью повышения численной устойчивости вычислений заявляемое устройство реализует алгоритмы Гаусса-Жордана с час45 тичным выбором ведущего элемента по столбцу. Это означает, что на i-м шаге алгоритма (= 1,п) исключению элементов

akj (k = i+1, j1+i-1) принадлежащих исходной расширенной матрице А = А (при i = 1) или

50 уже частично преобразованной матрице А (при i > 1) предшествует последовательное сравнение элементов ajj (j = i+1,n) с элементом ajj и если очередной элемент lajj I >

l aij l осуществляется перестановка j- u i-й

55 строк. Только после окончания всех (на данном шаге) операций сравнения и перестановок (т,е. процесса выбора ведущего элемента), начи нается и роцесс и рео 6 разования строк с (i+1)-й по (и+1)-ю, выполняемый в соответствии с указанным выше

1829043

15

25

55 алгоритмом. Таким образом, процесс выбора ведущего элемента распространяется только на первых и строк матрицы А, Вычислительный процесс в устройстве организован таким образом, что одна матрица СЛАУ обрабатывается 2n(n+1) тактов, однако одновременно происходит обработка двух различных матриц, моменты начала поступления на вход устройства которых разнесены на n(n+1) тактов, Т.е., если элементы матрицы А первой СЛАУ начинают поступать на вход устройства с первого такта его работы, то элементы матрицы В следующей СЛАУ начинают поступать с

n(n+1)+1-го такта, и период работы устройства в реж ме поточной обработки, т.о., составляет n(n+i) тактов (см. фиг, 5, где С 1 элементы матрицы С той СЛАУ, которая начала обрабатываться за п(п+1) такт до начала обработки матрицы А. Вследствие этого в блок синхронизации устройства входит два одинаковых блока триггеров, элементов

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

Поступление исходных данных организовано следующим образом (см. фиг, 5). На вход устройства начиная с первого такта каждый такт последовательно поступают элементы матрицы А исходной системы по столбцам, начиная с элемента а1 и заканчивая аьч (i = 1, n+1), т.е. первые п тактов поступают элементы первого столбца матрицы А, вторые и тактов — элементы второго столбца и т.д, Кратко рассмотрим алгоритм работы процессорных элементов. Как уже отмечалось выше, на вход устройства начиная с первого такта последовательно поступают элементы первого столбца матрицы А, При этом коммутатор 10 пропускает их на входы коммутаторов 6, 9 и схемы сравнения 8. Управление коммутаторами 6, 9 организовано таким образом, что элемент а в первом такте принимается в регистр 7, Во втором такте а21 с выхода коммутатора 10 поступает на вторые входы коммутаторов 6, 9 и схемы

8, на первые входы которых поступает а11 и, если а 1! > I а111, на выходе схемы 8 появляется единица (признак перестановки строк 021 = 1 см. алгоритм), который через элементы 13 и 14 поступает на управляющие входы коммутаторов 6, 9, в результате чего ад записывается в регистр 7, а11 — в регистр 1 (Рг 1) блока 15, à LJz — в триггер 1 (Тр 1) блока 12. Если условие не выполняется, нуль с выхода схемы 8 записывается в

Тр 1 блока 12, az> — в Pr 1 блока 15, а — перезаписывается в регистр 7. В последующих тактах каждый поступающий элемент

a1< сравнивается с (j = З,n) максимальным (из регистра 7) аналогично второму такту, заполняя блок 15, а вырабатываемые признаки 011 записываются в блок 12, (т.е, осуществляется выбор ведущего элемента). В и-м такте максимальный элемент переписывается в регистр 5. Начиная с (n+1)-ro такта на вход устройства поступают элементы второго столбца матрицы А, которые поступают в процессорный элемент 1.2 через коммутатор 21.2. Элементы второго столбца заполняют блок 30,2 и регистр 19,2 под управлением признаков Ui> (j = 2,n) поступающих с блока 12 через коммутатор 29.2 на управляющие входы коммутаторов 18.2 и

20.2, т.е. осуществляется перестановка строк с ведущей строкой. В то же время процессорный элемент 1.1 производит вычисление коэффициентов mi>, заполняя блок 4. Начиная с (2n+1)-го такта на вход устройства поступают элементы третьего столбца матрицы А, которые поступают в процессорный элемент 1.3 и заполняют блок 30.3 и регистр 19.3 под управлением признаков Uj<, поступающими с блока 27,2 через коммутатор 29,3, В это время процессорный элемент 1.2 производит перевычисление элементов второго столбца матрицы ар (см, алгоритм), которые с выхода сум,г матора 31,2 поступают на процессорный элемент 1.1, где происходит выявление максимального (по абсолютной величине) из них аналогично первым и тактам работы, и вновь заполняются блоки 15 и 12, Таким образом начинается второй шаг алгоритма, Далее действия выполняются аналогично (см, фиг, 5).

Рассмотрим работу устройства. Для простоты описания и без потери общности положим n = 4, Условимся, что прием информации в триггеры 44 — 47, блоки 11, 23, 32, 35, 54, 55 и счетчик 52 осуществляется по переднему фронту тактового импульса, т,е. в начале такта, а во все регистры, блоки 4, 15, 12, 25 — 28, 30, триггеры 36, 37 и 39 — по заднему фронту тактового импульса. Пусть перед началом вычислений триггер 36 и триггеры блоков 11, 23, 32, 35 установлены в нулевое состояние.

Импульс пуска, поступающий на вход запуска устройства (см. фиг. 2 и 6) по заднему фронту тактового импульса устанавливает в единицу триггеры 37, 39, 36. Также устанавливаются в единицу S-триггер 38, триггер 47, блок 55, а в нуль — триггер 45, Коммутатор 48 пропускает единицу с выхода блока 55 на третий выход блока 2. В следующем, первом такте в счетчик 52 по переднему фронту тактового импульса за1829043

10 писывается значение (и-1) = 3 в двоичном коде, на выходе отрицательного переноса счетчика находится нуль, по заднему фронту тактового импульса триггеры 37 и 39 сбрасываются в нуль, а« = а«поступает со

1 входа на седьмой вход процессорного элемента 1.1, и пройдя через коммутаторы 10 и

6 (на их управляющих входах единицы), записывается по заднему фронту тактового импульса в регистр 7, а единица с четвертого входа процессорного элемента 1.1 — в

Тр 1 блока 12. Во втором такте a21 = az1 со

1 входа устройства поступает через коммутатор 10 на второй вход схемы сравнения 8, на первый вход которой подается а« . Пусть

Iаг1 I I a«1, Тогда нуль с выхода схемы

8 записывается в Тр 1 блока 12 (U21 = О), единица переписывается в Тр 2 блока 11, а21 записывается в Рг 1 блока 15, а«пере1 1 записывается в регистр 7, содержимое счетчика 52 уменьшается на единицу. В третьем такте аз1 = аз1 поступает со входа устройст1 ва в процессорный элемент 1.1, где аналогично второму такту сравнивается с а« .

Пусть 1аз1 I 1 à11 I . .Тогда нуль с выхо1 1 да схемы 8 записывается в Тр 1 блока 12 (0з1 = О), аз1 записывается в Р 1 блока

15, az1 — в Р, 2 блока 15, содержимое

1 счетчика 52 уменьшается на единицу, Uz1 переписывается в Тр 2 блока 12, В четвертом такте содержимое счетчика 52 становится равным нулю, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в нуль триггер 36, в единицу триггер 37, а он, в свою очередь, сбрасывает в нуль триггер 38, a41 = a41 по1 ступает на вход процессорного элемента 1.1 и сравнивается с а11 аналогично второму и

1 третьему такту. Пусть а«1< I a41 I. Тогда единица с выхода схемы 8 (041 = 1) записывается в Тр 1 блока 12, а«записывается в

Рг 1 блока 15. а а41 — в регистр 5 (a41 ведущий элемент, следовательно, ведущей строкой на первом шаге алгоритма стала четвертая строка матрицы А). На инверсном выходе триггера 38 появляется единица, которая разрешает прохождение тактовых импульсов через элемент И 14, Кроме того, нуль с выхода этого триггера поступает на управляющий вход коммутатора 10, и он передает на свой выход значения с первого своего входа, Параллельно с этим, в первых четырех тактах в процессорном элементе

1,2 идет вычисление Ip матрицы С.

В пятом такте на вход устройства поступает а12 = а12, которое пройдя через комму1 татары 21.2 и 18,2 записывается в регистр

19.2, поскольку коммутатор 29.2 пропускает на свои выходы информацию со своего четвертого и третьего входов, В этом же такте в счетчик 52 вновь записывается значение (n-1) = 3 в двоичном коде, а 1 с выхода

1 блока 15 поступает на вход блока 3, на другой вход которого подается а41, и ре1 зул ьтат m21 = -аг1 /a41 по заднему фронту

1 тактового импульса записывается в Рг 1 блока 4.

В шестом такте на вход устройства поступает а22 = агг, которое пройдя через

1 коммутаторы 21.2 и 20.2 записывается в Рг

1 блока 30.2, поскольку на управляющие входы коммутаторов 20.2 и 18,2 поступает

Uz1 = 0 с первого выхода (и третьего входа) коммутатора 29.2, а перезаписывается в регистр 19.2. В этом же такте аз1 с выхода

1 блока 15 поступает на вход блока 3, и результат п1з1 = -аз1 /а41 записывается в Рг 1

1 блока 4, а mz1 переписывается в Рг 2 блока

4, 0г1 записывается в Тр 1 блока 27, а единица перезаписывается в Тр 2 блока 27, счетчик 52 уменьшает свое значение на единицу.

В седьмом такте азг = азг со входа уст1 ройства поступает в процессорный элемент

1.2, и записывается в Рг 1 блока 30.2, 0з1 = О переписывается в Тр 1 блока 27,2, Uz1 — в

Тр 2 блока 27.2, единица — в Тр 3 блока

27.2, a1z переписывается в регистр 19.2, 1 а«с выхода блока 15 поступает на вход блока 3, с выхода которого результат m41 = а« /а41 записывается в Рг 1

1 1 блока 4, счетчик 52 уменьшает свое значение на единицу.

В восьмом такте содержимое счетчика

52 становится равным нулю, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в единицу триггеры

37 и 36, и таким образом разрешается прохождение тактовых импульсов через элемент И 43. В этом же такте a4z = a42 со входа

1 устройства поступает и записывается в регистры 19.2 и 17,2, à a1z из регистра 19.2 переписывается в Рг 1 блока 30.2, 041 = 1 переписывается в Тр 1 блока 27.2, на вход выбора режима блока 3 поступает единица, и значение 1/а41 = п1у записывается в Рр 1

1 блока 4. Параллельно с этим, во вторых четырех тактах идет выбор ведущего элемента матрицы C(i = 4) в процессорном элементе

1.1, и перевычисление в процессорных элемвнтах1,2 и 1.3 С14 и С5 (См. фиг.5), КрсмЕ того, на управляющем входе коммутатора

21.2 появляется нуль, и он начинает передавать на свой выход информацию с выхода коммутатора 22.2.

1829043

В девятом такте нуль с выхода триггера

45 записывается в триггер 47, единица записывается в триггер 45, (n-1) = 3 записывается в счетчик 52, а1з = а1з поступает со входа устройства в процессорный элемент

1.3, и пройдя через коммутатор 21.3 и 18.3 записывается в регистр 19.3, поскольку коммутатор 29.3 пропускает на свои выходы информацию со своего третьего и четвертого входов. В этом же такте из блока 4 через коммутатор 24,2 (на его управляющем входе появляется единица, которая будет присутствовать и = 4 такта) на вход умножителя

16.2 поступает mz1, на другой вход его поступает а4; из регистра 17.2, и результат

mz1a4z потупает на вход сумматора 31.2, 1 на другой вход которого подается azz с вы1 хода блока 30.2. С выхода сумматора 31,2 результат а22 + m21 a42 = а22 поступает

2 через коммутатор 10 в процессорный элемент 1.1, и записывается в регистр 7 (аналогично первому такту).

В десятом такте счетчик 52 уменьшает свое состояние на единицу, нуль из триггера

47 переписывается в Тр 1 блока 55, а2з = а2з

1 поступает со входа устройства в процессорный элемент 1,3, и пройдя через коммутаторы 21.3 и 20,3 записывается в Рг 1 блока

30.3, Uz1 = 0 переписывается в Тр 1 блока

27.3, а а, переписывается в регистр 19.3.

В этом же такте из блока 4 на вход умножителя 16,2 поступает гпз1, с выхода которого тз1/а42 поступает на вход сумматора 31.2, 1 на другой вход которого подается аз2 с вы1 хода блока 30.2. С выхода сумматора 31.2 результат аз21 + п1з1a4z1 = аз2 поступает

1 через коммутатор 10 в процессорный элемент 1.1, где сравнивается с а22 аналогич2 но второму такту, Пусть 1аз2 I> lazz !.

2 2

Тогда единица с выхода схемы 8 сравнения (U32 = 1) записывается в Тр 1 блока 12, а также поступает на управляющие входы коммутаторов 6 и 9, в результате чего аз2 г появляется в регистре 7, а а22 записывается

2 в Рг 1 блока 15.

В одиннадцатом такте счетчик 52 уменьшает свое состояние на единицу, нуль переписывается в Тр 2 блока 55, азз = азз

1 поступает со входа устройства в процессорный блок 1.3 и записывается в Р, 1 блока

30.3, Оз1 = 0 переписывается в Тр 1 блока

27.3, а1з перезаписывается в регистр 19.3.

В этом же такте из блока 4 на вход умножителя 16.2 поступает m41, с его выхода

m41 а42 поступает на сумматор, с выхода

1 которого результат а12 + а42 — m41 = à42

1,1 2 поступает в процессорный элемент 1,1, где

55 сравнивается с аз2, Пусть (а42 I < 1 a32

2 2

Тогда нуль с выхода схемы 8 (U4z = О) записывается в Тр 1 блока 12, а также управляет работой коммутаторов 6 и 9 так что a4z записывается в Рг 1 блока 15, а аз2 остается

1 в регистре 7, В двенадцатом такте счетчик 52 уменьшает свое значение до нуля, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в нуль триггер 36, а в единицу — 37, нуль переписывается в Тр 3 блока 55 и появляется на его выходе и на выходе коммутатора 48 (в течение интервала от начала такта до заднего фронта тактового импульса), а4з = а4з поступает со

1 входа устройства в процессорный элемент

1.3 и записывается в регистры 19.3 и 17,3, U41 = 1 переписывается в Тр 1 блока 27,3, а1з записывается в Рг 1 блока 30,3. В этом

1 же такте из блока 4 нэ вход умножителя 16,2 поступает m51, с его выхода m51 a4z посту1 пает на сумматор 31.2, который осуществляет пропуск операнда (на его управляющем входе единица) и результат гп51 а42 = э52 с

1 выхода сумматора поступает в процессорный элемент 1.1, где без операции сравнения (на выходе элемента 13 нуль) записывается в Рг 1 блока 15, а в Тр 1 блока

12 записывается в нуль, Параллельно с этим, с девятого по двенадцатый такт в процессорном элементе 1.1 идет вычисление коэффициентов 114 матрицы С, в процессорных элементах 1.2 и 1.3 — перестановка элементов С15 и вычисление элементов С5, 4, 4 соответственно.

В тринадцатом такте в счетчик 52 записывается значение (и-1) = 3, на вход устройства поступает а14 = а14, которое пройдя

1 через коммутатор 21.3 (на его управляющем входе остается единица, хотя коммутатор

29,3 уже передает на свои выходы информацию с первого и второго своих входов) и коммутатор 18.3, записывается в регистр

19.3. В этом же такте mz1 через коммутатор

24.3 поступает на вход умножителя 16.3, на другой его вход поступает а4з из реги1 стра 17.3, и результат mz1 а4з поступает

1 на вход сумматора 31,3, на другой вход которого подается агз с выхода блока 1

30,3. С выхода сумматора результат а2з1+

+ m21 à4ç = a232 поступает через коммута1 торы 22,2 и 21.2 в процессорный элемент

1.2, где записывается в регистр 19,2. В этом же такте az2 с выхода блока 15 посту2 пает на блок 3, который выполняет деление, и результат взг = -а22 /a32 принимается в

2 2

Рг 1 блока 4.

1829043

14

В четырнадцатом такте счетчик 52 уменьшает свое значение на единицу, на вход устройства поступает az4 = 824, кото1 рое записывается в Pr 1 блока 30,3, U21 = О переписывается в Тр 1 блока 28.3, m31 через коммутатор 24.3 поступает на вход умножителя 16.3, с выхода которого m31 а4з посту1 пает на сумматор 31.3, с выхода которого результат 833 + m31 843 = 833 поступает в

1 . 1 2 процессорный элемент 1.2, где записывается в регистр 19,2 (U32 = 1), а а2з записыва2 ется в Рг 1 блока 30.2, В этом же такте 842

2 с выхода блока 15 поступает на блок 3, с выхода которого m42=-842 /832 принимает2 ся в Рг 1 блока 4, m31 записывается в Рг 1 блока 25.3, а mz1 переписывается в Pr 2 блока 25.3.

В пятнадцатом такте счетчик 52 уменьшает свое значение на единицу на вход устройства поступает a34 = a34, которое

1 записывается в Рг 1 блока 30.3, U31 = О переписывается в Тр 1 блока 28.3, п141 поступает на вход умножителя 16.3, с выхода которого m41 а43 поступает на

1 сумматор 31.3, с выхода которого результат 813 + m41843 = а4з поступает в

1 процессорный элемент 1,2, где записывается в Рг 1 блока 30.2 (U4z = О), а азз остается

2 в регистре 19.2, U4z переписывается в Тр 1 блока 27,2, U3z — в Тр 2 блока 27.2, B этом же такте agz с выхода блока 15 поступает на блок 3, с выхода которого п152 = -852 /а32

2 2 принимается в Рг 1 блока 4.

В шестнадцатом такте содержимое счетчика 52 становится равным нулю, на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в единицу триггеры 37 и 36, нэ вход устройства поступает a44 = а44, которое записывается в ре1 гистры 17,3 и 19,3, а14 записывается в Рг 1

1 блока 30.3, 041 = 1 переписывается в Тр 1 блока 28.3, гпу поступает на вход умножителя 16.3 с выхода которого п151 843 посту1 пает на сумматор 31.3, который осуществляет поопуск операнда, и результат п151 843 =853 с выхода сумматора посту1 пает в процессорный элемент 1.2, где записывается в Рг 1 блока 30.2. В этом же такте значение 1/а32 = m62 записывается в г

Рг 1 блока 4 (на входе выбора режима блока

3 — единица).

В семнадцатом такте в счетчик 52 записывается значение (и-1) = 3, mz1 поступает с выхода блока 25,3 через коммутатор

24,3 нэ умножитель 16.3 (на управляющем входе коммутатора 24.3 нуль), на другой вход которого поступает а44, с вы1 хода умножителя 16,3 m21 à44 поступает

1 на сумматор 31.3, с выхода которого ре5

55 зультат 824 + п121 844 = 824 поступает нд

1 . 1 2 коммутатор 22,3, с выхода которого проходит через коммутаторы 21.3 и 18.3, и принимается в регистр 19.3. Кроме того, в этом такте на вход устройства поступает а15, которое поступает в процессорный элемент

1,2 и пройдя через коммутаторы 21.2 и 18.2 записывается в регистр 19.2. В этом же такте т32 с выхода блока 4 поступает ía axon умножителя 16.2, с выхода которого m3z а33 поступает на вход сумматора 31.2, на другой вход которого поступает az3 с выхода блока 30.2 и результат 823 + m32 азз = азз

2 . 2 3 с выхода сумматора поступает в процессорный элемент 1,1, где принимается в регистр 7.

В восемнадцатом такте счетчик 52 уменьшает свое значение на единицу, m31 поступает на умножитель 16.3, с выхода которого m31 à44 поступает на сумматор 31.3, 1 с выхода которого результат а34 + m31 а44 =

1 . 1

= аз4 проходит через коммутаторы 22.3 и

21.3 и записывается в регистр 19.3, а а24 записывается в Рг 1 блока 30 3, Кроме того, в этом же такте на вход устройства поступает 82ь, которое пройдя через коммута1 торы 21.2 и 20.2 записывается в регистр

Рг 1 блока 30,2 (U21 = О), m4z с выхода блока 4 поступает на умножитель 16.2, с выхода KQTopol п142 833 поступает На вход сумматора 31.2, с выхода которого результат 843 + п142 а33 = а43 поступает в г процессорный элемент 1.1, где сравнивается с азз из регистра 7. Пусть 1833 I < 1843 I . Тогда единица с выхода схемы 8 сравнения (043 = 1) записывается в Тр 1 блока 12, а33 записывается в Р 1 блока 15, а а43 — в

3 регистр 7, В девятнадцатом такте счетчик 52 уменьшает свое значение на единицу, m41 поступает на умножитель 16.3, с выхода которого m41 а44 поступает на сумма1 тор 31.3, с выхоуа которого результат

814 + m41 à44 = а44 проходит через комму1 татары 22,3 и 21.3 и записывается в Pr 1 блока 30,3. Кроме того, в этом такте на вход устройства поступает 83, которое пройдя

1 через коммутаторы 21.2 и 20.2 записывается

В Рг 1 бЛОКа 30,2 (031 = О), тГ2 С ВЫХОда бЛОКа

4 поступает на умножитель 16,2, с выхода которого msz а33 поступает на вход сум2 матора 31.2, с выхода которого результат

as3 + mgz а33 =абаз поступает в процессор2 . 2 3 ный элемент 1,1, где без сзоавнения записывается в Рг 1 блока 15, 833 переписывается в Рг 2 блока 15.

В двадцатом такте счетчик 52 уменьшает свое значение до нуля, и на его выходе отрицательного переноса появляется единица, ms1 поступает на умножитель 16,3, с

1829043

Выхода которого т5 a44 поступает на сум1 матор 31,1, который пропускает это значение на ВыхОд, и результат п151 д44 = а54 г. поступает в Рг 1 блока 30,3, Кроме того, в этом такте на вход устройства поступает 5 а45 = а45, которое пройдя через коммута1 торы 21.2 и 18.2, записывается в регистры

19.2 и 17,2 (U41 = 1), а а15 переписывается в

Pr 1 блока 30.2, п 52 с выхода блока 4 поступает на умножитель 16.2, с выхода которого 10

m52 а33 поступает на сумматор 31.2 с выхог да которого результат а33 m5$ = а53 (на упг. равляющем входе сумматора единица) принимается в Pr 1 блока 15, пройдя через

20 а 44, 36 — в нуль.

35 коммутаторы 10 и 9, Кроме того, в этом такте на вход запуска устройства поступает импульс пуска, который по заднему фронту тактового сигнала устанавливает триггеры

39, 37, 38, 46 и триггеры блока 54 в единицу, В двадцать первом такте аналогично первому такту, в счетчик 52 записывается значение (n-1) = 3, первый элемент Ь11 = Ь11

1 очередной обрабатываемой матрицы В поступает на вход устройства, и пройдя через коммутаторы 10 и 6 записывается в регистр

7, а единица — в Тр 1 блока 12. Параллельно с этим продолжается обработка матрицы А аналогично тому, как это было с матрицей С (см. фиг. 5).

Далее работа устройства продолжается аналогично. Как видно из таблицы, вывод результатов х обработки матрицы А происходит с 37 по 40-й такт работы устройства, а вывод результатов у> обработки матрицы

С вЂ” с 17 по 20-й такт работы устройства.

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

Устройство для решения систем линейных алгебраических уравнений, содержащее n/2+1 процессорных элементов (n — четное число), блок синхронизации, о т л и ч а ю щ е е с я тем, что, с целью повышения точности и снижения аппаратурных затрат, выходы -го процессорного элемента с первого по пятый (i = 1, п/2) подключены к входам соответственно с первого по пятый (i+1)-го процессорного элемента, входы первого процессорного элемента с первого по пятый подключены соответственно к выходам с первого по пятый блока синхронизации, вход которого является входом запуска устройства, шестой выход i-го процессорного элемента (i = 2, n/2) подключен к шестому входу (i+1)-го процессорного; элемента, выходы i-го процессорного элемента с седьмого по одиннадцатый (i = 3, п/2+1) подключены соответственно к входам с седьмого по один40

55 надцатый (i-1)-го процессорного элемента, первый и второй выходы (и/2+1) процессорного элемента подключены к седьмому и восьмому входам (n/2+1)-го процессорного элемента соответственно, выходы (n/2+1)-го процессорного элемента с четвертого по шестой подключены соответственно к его входам с девятого по одиннадцатый, одиннадцатый выход второго процессорного элемента подключен к шестому входу первого процессорного элемента, шестой выход которого является выходом устройства, вход которого подключен к седьмому входу первого процессорного элемента и к двенадцатым входам остальных процессорных элементов, причем первый процессорный элемент содержит блок деления, выход которого подключен к входу первого блока элементов задержки первого процессорного элемента, а первый вход его соединен с выходом первого регистра первого процессорного элемента, вход которого связан с выходом первого коммутатора первого процессорного элемента и с входом второго регистра первого процессорного элемента, выход которого подключен к первым входам схемы сравнения, первого и второго коммутаторов первого процессорного элемента, вторые входы которых также объединены и подключены к выходу третьего коммутатора первого процессорного элемента, первый и второй входы которого являются соответстВЕННО ШЕСТЫМ И СЕДЬМЫМ ВХОДаМи ПЕРВОГО процессорного элемента, выходы процессорного элемента с первого по третий подключены соответственно к выходам с первого по третий второго блока элементов задержки, входы которого с первого по третий являются соответственно первым, вторым и пятым входами первого процессорного элемента, пятый и четвертый выходы которого подключены соответственно к выходам первого и третьего блока элементов задержки, вход которого связан с управляющими входами первого и второго коммутаторов и с выходом элемента И первого процессорного элемента, первый вход которого подключен к третьему входу первого процессорного элемента, четвертый вход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом схемы сравнения, выход второго коммутатора подключен к входу четвертого блока элементов задержки, выход которого является шестым выходом первого процессорного элемента и подключен к второму входу блока деления, выход выбора режима которого соединен с управляющим входом первого регистра и является пятым входом первого процессорного эле1829043

45

55 мента, управляющий вход третьего коммутатора подключен к второму входу первого процессорного элемента, выход элемента

ИЛИ соединен с вторым входом элемента И первого процессорного элемента, причем

i-й процессорный элемент (i = 2, n/2-1) содержит умножитель, первый вход которого подключен к выходу первого регистра i-ro процессорного элемента, вход которого соединен с выходом первого коммутатора и входом второго регистра i-ro процессорного элемента, выход которого подключен к первым информационным входам первого и второго коммутаторов i-ro процессорного элемента, вторые входы которых объединены и связаны с выходом третьего коммутатора, первый информационный вход которого подключен к выходу четвертого коммутатора, первый и второй информацио н н ы и входы которого я вл я ются соответственно шестым и одиннадцатым входами i-го процессорного элемента, входы и выходы которого с первого по третий подключены соответственно к входам и выходам с первого по третий первого блока элементов задержки. второй вход умножителя подключен к выходу пятого коммутатора, первый и второй входы которого являются соответственно пятым и десятым входами

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

10 выходы i-ro процессорного элемента подключены соответственно к первому и второму выходам седьмого блока элементов задержки, первый и второй входы которого являются соответственно седьмыми и вось15 мыми входами i-го процессорного элемента, четвертый вход которого подключен к входу четвертого блока элементов задержки и к третьему входу шестого коммутатора, второй и четвертый входы которого подключе20 ны соответственно к восьмому и второму входам i-го процессорного элемента, второй выход шестого коммутатора является управляющим входом третьего коммутатора, второй вход которого подключен к

25 двенадцатому входу i-го процессорного элемента, управляющий вход четвертого коммутатора подключен к седьмому входу i-го процессорного элемента и к входу элемента

НЕ, выход которого соединен с первым вхо30 дом элемента ИЛИ, второй вход которого подключен к первому входу -го процессорного элемента, третий вход i-го процессорного элемента соединен с управляющими входами первого регистра и сумматора, уп35 равляющий вход шестого коммутатора подключен к выходу элемента ИЛИ и к входу восьмого блока элементов задержки, выход которого подключен к управляющему входу пятого коммутатора. выход

40 умножителя подключен к второму входу сумматора.

1829043 оз j .2

ОЗ 1.1

Такты

2 гб

/с )

1,5 / з с

1.43 (с ) 163 л ==аз и < сг =

45 сбб

54

161 п)1== аЗ/

) сбб C

ass= ) с 55 с

2 сз

64 ам== aI I сз

/с /

/,с

/а, /

1 71 = (с„г)

1с-,,С сз

22) 2137= з

55= (а 32) Ш 41

7 сз

65 с

1c6s(з (! 47) 4161 =

/" 72 /

45

22

/атз / (агз) 7 гг== 732

)c, 3

„2 " 32

75

164

1О

2 аэ. = "42

2 асг=

)с,з(с4

6s (а зз) 2 зазгс

1! . 2,4

7S! 2

134 = (a„7) 5

2 =

1З

/агб /

"t1 Э

5 с65 (I17 ) а2

74 ) 16!.142 =

1 75 (5

7S.

7 а43 (a„ ) (а, ) 15

53,z

)абэ(Вб с сб =

36 (аб,, ) эб

6 1 4"

7 агз

2 а 24

/а / (а „ i

/6 15/

25) ВЫВОД "7

17 аз

43 эг

1Е (a4 ) . з,.

53 а

49 (a3S) з

/а / з

54 f.

7 54 "45

ЗО

25

/ат /

/ 3 /

2=

/ь,„ /

21 сз

35 35 (аг ) Ь11 == bzl

7 45 аз

aax == Ь„.

m63

55

Iax == Ьа„

64

/аз/

4 44 (а .) 24 п!73

/ас /

/a 337 /,з

635

/Ь)2 /

25 I 54

/а". / (аз ) аз =

"з!

2б аз

75 оьзг ) 27

14 41

/а /

74

За з

Ьгг=

22

"45, 4 1

/ь„/

29 л1 51

1,2 г

77 32

) а."5(7 зг ас

ss (ь„) 64,2 баах == Ь42

2 ь„,=

4 65

3" 7s ( (ь„) 31

" 74 =

75

)Ьбгб

b7 бг (b„, )

"гэ

ЗЗ

134

5 55

65 ("зз ) /ass/ бб

/074 /

)с зг= (b74 ) Ьг =

33 з" (Ь43 )

/б/

35/

75 .. 5 авб (ь ) 35

kS2=

I 62=

Ь7 =

43 ьз

53 (ь „) Зб

b33=

Ьгс =

) 1133 /

rs/

З7

Ь

3 бз

b53 =

34 ь, -=ь т

33 13 э

)0631

1 г -) (ь, „) ьг=

4I1 э

) ЬбэС

Э 54(ьз. =

63 ьг

34 (Ь45 ) 4О

/ / - прием в регистр 7 или 191 () - приен в регистр 19 или БЭЗ 30 (в эависиности от (" прием в 533 12 или 30; max — текущий макс. элемент (иэ регистра 7);

= = - сравнение элементов "33

3 азз == а43

/ »/ вь!вод \ нвод 33 вывод ТЕ сыссд х

=4!ЭОГ, х сод рсгаод х

1829043

Фиг. 2

1829043

iuzsona

1829043

Составитель О. Масленников

Техред М.Моргентал Корректор Л. Филь

Редактор Т. Иванова

Производственно-издательский комбинат "Патент", r. Ужгород, ул,Гагарина, 101

Заказ 2476 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5