Устройство для решения систем линейных алгебраических уравнений Советский патент 1993 года по МПК G06F15/347 G06F15/324 

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

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

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

0 2. п/2+1); на фиг, 5 - диаграмма работы блока синхронизации для случая п 4.

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

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

00

to

Ю О

со

подключен к шестому входу процессорного элемента 1.0+1), выходы процессорного элемента 1.1 с седьмого по одиннадцатый (i 3,п/2+1), подключены соответственно, ко входам с седьмого по одиннадцатый процессорного элемента 1.(М), одиннадцатый выход процессорного элемента 1.2 подключен к шестому входу процессорного элемента 1.1, шестой выход которого является выходом устройства, вход которого подключен к седьмому входу процессорного элемента 1.1 и к двенадцатым входам остальных процессорных элементов, первый и второй выходы процессорного элемента 1.(п/2+1) подключены к седьмому и восьмому Е одам процессорного элемента 1 .(п/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 подключен ко второму входу первого процессорного элемента, выход

элемента ИЛИ 14 связан со вторым входом элемента И 13. Процессорный элемент 1.1 (i 2, п/2+1) содержит умножитель 16, первый вход которого подключен к выходу первого регистра 17, вход которого подключен к выходу первого коммутатора 18 и ко входу второго регистра 19, выход которого подключен к первым входам первого 18 и второго 20 коммутаторов, вторые входы которых объединены и связаны с выходом третьего коммутатора 21, первый вход которого подключен к выходу четвертого коммутатора 22, первый и второй входы которого являются, соответственно, шестым и один

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

1.1, входы и выходы которого с первого по третий, подключены, соответственно, ко входам и выходам с первого по третий, первого блока элементов задержки 23, второй

0 вход умножителя 16 подключен к выходу пятого коммутатора 24, первый и второй входы которого являются, соответственно, пятым и десятым входами процессорного элемента 1.1 и подключены, соответственно,

5 ко входам второго - 25 и третьего 26, блоков элементов задержки, выходы которых являются соответственно пятым и десятым выходами процессорного элемента 1.1, четвертый и девятый выходы которого под0 ключены к выходам соответственно четвертого 27 и пятого 28 блоков элементов задержки, вход которого является входом процессорного элемента 1.1 и подключен к первому входу шестого коммутатора 29,

5 первый выход которого подключен к управляющим входам коммутаторов 18 и 20, выход коммутатора 20 подключен ко входу шестого блока элементов задержки 30, выход которого связан с первым входом сум0 матора 31, выход которого является шестым и одиннадцатым выходами процессорного элемента 1.1, седьмой и восьмой выходы которого подключены, соответственно, к первому и второму выходам седьмого блока

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

0 27, и к третьему входу коммутатора 28, второй и четвертый входы которого подключены соответственно к восьмому и второму входам процессорного элемента 1.1, второй выход коммутатора 29 является управляю5 щим входом коммутатора 21, второй вход которого подключен к двенадцатому входу процессорного элемента 1.i, управляющий вход коммутатора 22 подключен к седьмому входу процессорного элемента и ко входу инвертора 33, выход которого связан с первым входом элемента ИЛИ 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-входами триггера Збг и 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-триггера 36i, инверсный выход которого подключен ко входам элементов И 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)

или п (все остальные блоки) регистров (блоки 4, 15, 25, 26, 30) или D-триггеров (блоки 12, 27, 28, 54, 55, 35, 11, 23 и 32), вход первого из которых является входом соответствующего блока, а выход последнего выходом блока. Таким образом они формируют задержку сигнала или операнда на п или п-1 тактов. Необходимо отметить, что блоки 11,23 и 32 содержат три независимых цепочки из п D-триггеров и осуществляют

задержку на п тактов сразу трех (блок 32- двух) управляющих сигналов, поступающих на их входы,

Устройство для решения СЛАУ предназначено для решения СЛАУ вида

an xi + ai2 ха + ... + ain xn ai(n-i);

321 Х1+Э22 Х2 + ... + Э2П Xn 32(n-1);

ani xi + аП2 Х2 + ... + ann xn an(n+i),

методом Гаусса-Жордана, который можно записать в рекуррентном виде следующим образом:

i Tjn; j l 1,n ,

iTijj -aji /an ; j i+1, n+i-1;

m(o+i)i 1 /an ;.

ajk ajk + mjj aik ; j i+1, n+i-1; k i+1,n+1;

, i+1

a(n+i)k m(n-H)i aik k i+1, n+1.

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

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

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

1ам |

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

алгоритмом. Таким образом, процесс выбора ведущего элемента распространяется только на первых п строк матрицы А.

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

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

Кратко рассмотрим алгоритм работы процессорных элементов. Как уже отмечалось выше, на вход устройства начиная с первого такта последовательно поступают элементы первого столбца матрицы А. При этом коммутатор 10 пропускает их на входы коммутаторов 6, 9 и схемы сравнения 8. Управление коммутаторами 6, 9 организовано таким образом, что элемент аи в первом такте принимается в регистр 7, Во втором такте 321 с выхода коммутатора 10 поступает на вторые входы коммутаторов 6, 9 и схемы 8, на первые входы которых поступает аи и, если Ia2il Ian I, на выходе схемы 8 появляется единица (признак перестановки строк Dai 1 см. алгоритм), который через элементы 13 и 14 поступает на управляющие входы коммутаторов 6, 9, в результате чего 321 записывается в регистр 7, аи - в регистр 1 (Рг 1) блока 15, а 1)21 - в триггер 1 СТр 1) блока 12. Если условие не выполняется, нуль с выхода схемы 8 записывается в Тр 1 блока 12, 321 - в Рг 1 блока 15, аи - перезаписывается в регистр 7. В последующих тактах каждый поступающий элемент aji сравнивается с (j 3,п) максимальным (из регистра 7) аналогично второму такту, заполняя блок 15, а вырабатываемые при- знаки Uji записываются в блок 12, (т.е. осуществляется выбор ведущего элемента). В n-м такте максимальный элемент переписывается в регистр 5. Начиная с (п+1)-го такта на вход устройства поступают элементы

0 второго столбца матрицы А, которые поступают в процессорный элемент 1.2 через коммутатор 21.2. Элементы второго столбца заполняют блок 30.2 и регистр 19.2 под управлением признаков Uji 0 2,п) поступаю5 щих с блока 12 через коммутатор 29.2 на управляющие входы коммутаторов 18.2 и 20.2, т.е. осуществляется перестановка строк с ведущей строкой. В то же время процессорный элемент 1.1 производит вы0 числение коэффициентов rriji, заполняя блок 4. Начиная с (2п+1)-го такта на вход устройства поступают элементы третьего столбца матрицы А, которые поступают в процессорный элемент 1.3 и заполняют

5 блок 30.3 и регистр 19.3 под управлением признаков Uji, поступающими с блока 27.2 через коммутатор 29.3. В это время процессорный элемент 1.2 производит перевычисление элементов второго столбца матрицы

0 aj2 (см. алгоритм), которые с выхода сумматора 31.2 поступают на процессорный элемент 1.1, где происходит выявление максимального (по абсолютной величине) из них аналогично первым п тактам работы, и

5 вновь заполняются блоки 15 и 12. Таким образом начинается второй шаг алгоритма. Далее действия выполняются аналогично (см. фиг. 5).

Рассмотрим работу устройства. Для

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

0 состояние.

Импульс пуска, поступающий на вход запуска устройства (см. фиг. 2 и 6) по заднему фронту тактового импульса устанавливает в единицу триггеры 37, 39, 36. Также

5 устанавливаются в единицу S-триггер 38, триггер 47, блок 55, а в нуль - триггер 45. Коммутатор 48 пропускает единицу с выхода блока 55 на третий выход блока 2. В следующем, первом такте в счетчик 52 по переднему фронту тактового импульса записывается значение (п-1) 3 в двоичном коде, на выходе отрицательного переноса счетчика находится нуль, по заднему фронту тактового импульса триггеры 37 и 39 сбрасываются в нуль, an an поступает со входа на седьмой вход процессорного элемента 1.1, и пройдя через коммутаторы 10 и б (на их управляющих входах единицы), записывается по заднему фронту тактового импульса в регистр 7, а единица с четвертого входа процессорного элемента 1.1 - в Тр 1 блока 12. Во втором такте 321 Э211 со входа устройства поступает через коммутатор 10 на второй вход схемы сравнения 8, на первый вход которой подается аи . Пусть |а21 I Ian I. Тогда нуль с выхода схемы 8 записывается в Тр 1 блока 12 (U21 0), единица переписывается в Тр 2 блока 11, 321 записывается в Рг 1 блока 15, аи перезаписывается в регистр 7, содержимое счетчика 52 уменьшается на единицу. В третьем такте аз1 аз11 поступает со входа устройства в процессорный элемент 1.1, где аналогично второму такту сравнивается с аи . Пусть |аз1 I :Ј Ian I. Тогда нуль с выхода схемы 8 записывается в Тр 1 блока 12 (Кз1 0), asi1 записывается в Рг 1 блока 15, 321 - в Рг 2 блока 15, содержимое счетчика 52 уменьшается на единицу, Dai переписывается в Тр 2 блока 12. В четвертом такте содержимое счетчика 52 становит- ся равным нулю, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в нуль триггер 36, в единицу триггер 37, а он, в свою очередь, сбрасывает в нуль триггер 38, 341 3411 поступает на вход процессорного элемента 1.1 и сравнивается с аи1 аналогично второму и третьему такту. Пусть 1ац1| 1а4111. Тогда единица с выхода схемы 8 (U41 1) записывается в Тр 1 блока 12, аи1 записывается в Рг 1 блока 15, а Э411- в регистр 5 (а411 - ведущий элемент, следовательно, ведущей строкой на первом шаге алгоритма стала четвертая строка матрицы А). На инверсном выходе триггера 38 появляется единица, которая разрешает прохождение тактовых импульсов через элемент И 14. Кроме того, нуль с выхода этого триггера поступает на управляющий вход коммутатора 10, и он передает на свой выход значения с первого своего входа. Параллельно с этим, в первых четырех тактах в процессорном элементе 1.2 идет вычисление Ij3 матрицы С.

В пятом такте на вход устройства поступает ai2 ai2 , которое пройдя через коммутаторы 21.2 и 18.2 записывается в регистр

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

(п-1) 3 в двоичном коде, Э211 с выхода блока 15 поступает на вход блока 3, на другой вход которого подается 341 , и результат гп21 -321 /Э411 по зэднему фронту тактового импульса записывэется в Рг 1

блока 4.

В шестом такте на вход устройства поступает 322 322 , которое пройдя через коммутаторы 21.2 и 20.2 записывэется в Рг 1 блока 30.2, поскольку на управляющие

входы коммутаторов 20.2 и 18.2 поступает 1)21 0 с первого выхода (и третьего входа) коммутатора 29.2, а перезаписывается в регистр 19.2. В этом же такте азт с выходэ блока 15 поступает на вход блока 3, и результат тэт -аз11/Э411 записывается в Рг 1 блока 4, а ггш переписывается в Рг 2 блока 4, U21 записывается в Тр 1 блока 27, а еди- ницэ перезэписывается в Тр 2 блока 27, счетчик 52 уменьшает свое знэчение на единицу.

В седьмом такте аз2 аз2 со входа устройства поступает в процессорный элемент 1.2, и записывается в Рг 1 блока 30.2, IJ31 О переписывается в Тр 1 блока 27,2, U21 - в

Тр 2 блока 27.2, единица - в Тр 3 блока 27.2, ai2 переписывается в регистр 19.2, аи с выхода блока 15 поступает на вход блока 3, с выхода которого результат ГП41 аи /341 записывается в Рг 1

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

В восьмом такте содержимое счетчика 52 становится равным нулю, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанэвливает в единицу триггеры 37 и 36, и тэким образом разрешается прохождение тэктовых импульсов через элемент И 43. В этом же такте 342 Э421 со входа

устройства поступает и записывается в регистры 19.2 и 17.2, a ai21 из регистра 19.2 переписывается в Рг 1 блока 30.2, LMi 1 переписывается в Тр 1 блока 27.2, на вход выбора режима блока 3 поступает единица,

и значение 1/Э41 msi записывается в Рг 1 блока 4. Параллельно с этим, во вторых четырех тактах идет выбор ведущего элемента матрицы C (i 4) в процессорном элементе 1.1, и перевычисление в процессорных элементах 1.2 и 1.3 Cj44 и Cjs3 (см. фиг. 5). Кроме того, на упрэвляющем входе коммутатора 21.2 появляется нуль, ион начинает передэ- вать на свой выход информацию с выхода коммутатора 22.2.

В девятом такте нуль с выхода триггера 45 записывается в триггер 47, единица записывается в триггер 45, (п-11 3 записывается в счетчик 52, aia ais поступает со входа устройства в процессорный элемент 1.3, и пройдя через коммутатор 21.3 и 18.3 записывается в регистр 19.3, поскольку коммутатор 29.3 пропускает на свои выходы информацию со своего третьего и четвертого входов. В этом же такте из блока 4 через коммутатор 24.2 (на его управляющем входе появляется единица, которая будет присутствовать п 4 такта) на вход умножителя 16.2 поступает тат, на другой вход его поступает Э4г1 из регистра 17.2, и результат гп21 Э421 поступает на вход сумматора 31.2, на другой вход которого подается 322 с выхода блока 30.2. С выхода сумматора 31.2 результат 322 + гп21 Э42 322 поступает через коммутатор 10 в процессорный элемент 1.1, и записывается в регистр 7 (аналогично первому такту).

В десятом такте счетчик 52 уменьшает свое состояние на единицу, нуль из триггера 47 переписывается в Тр 1 блока 55, 323 3231 поступает со входа устройства в процессорный элемент 1.3, и пройдя через коммутаторы 21.3 и 20.3 записывается в Рг 1 блока 30.3, 1)21 0 переписывается в Тр 1 блока 27.3, а а,.1 переписывается в регистр 19.3. В этом же такте из блока 4 на вход умножителя 16,2 поступает тэт, с выхода которого тз1/Э421 поступает на вход сумматора 31.2, на другой вход которого подается аз2 с выхода блока 30.2. С выхода сумматора 31.2 результат аз21 + глз1 а421 аз21 поступает через коммутатор 10 в процессорный элемент 1.1, где сравнивается с 322 аналогично второму такту. Пусть |аз2 1а22 I. Тогда единица с выхода схемы 8 сравнения (U32 1) записывается в Тр 1 блока 12, а также поступает на управляющие входы коммутаторов 6 и 9, в результате чего аз22 появляется в регистре 7, а Э222 записывается в Рг 1 блока 15.

В одиннадцатом такте счетчик 52 уменьшает свое состояние на единицу, нуль переписывается в Тр 2 блока 55, азз азз1 поступает со входа устройства в процессорный блок 1.3 и записывается в Рг 1 блока 30.3, Usi 0 переписывается в Тр 1 блока 27.3, ais1 перезаписывается в регистр 19.3. В этом же такте из блока 4 на вход умножителя 16.2 поступает гп41, с его выхода гп41 Э421 поступает на сумматор, с выхода которого результат ai21 + Э421 - Го41 Э422 поступает в процессорный элемент 1.1, где

сравнивается с аз22. Пусть |a422l 1аз22 I. Тогда нуль с выхода схемы 8 (U42 0) записывается в Тр 1 блока 12, а также управляет работой коммутаторов 6 и 9 так, что Э422

записывается в Рг 1 блока 15, а аз2 остается в регистре 7.

В двенадцатом такте счетчик 52 уменьшает свое значение до нуля, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в нуль триггер 36, а в единицу - 37, нуль переписывается в Тр 3 блока 55 и появляется на его выходе и на выходе коммутатора 48 (в течение интервала от начала такта до заднего фронта тактового импульса), 343 а431 поступает со входа устройства в процессорный элемент 1.3 и записывается в регистры 19.3 и 17.3, U41 1 переписывается в Тр 1 блока 27.3,

ais1 записывается в Рг 1 блока 30.3. В этом же такте из блока 4 на вход умножителя 16.2 поступает msi, с его выхода msi a42 поступает на сумматор 31.2, который осуществляет пропуск операнда (на его управляющем

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

12 записывается в нуль. Параллельно с этим, с девятого по двенадцатый такт в процессорном элементе 1.1 идет вычисление коэффициентов Ij4 матрицы С, в процессорных элементах 1.2 и 1.3 - перестановка элементов Cj5 , и вычисление элементов Cjs4 соответственно.

В тринадцатом такте в счетчик 52 записывается значение (п-1) 3, на вход устройства поступает аи аи , которое пройдя через коммутатор 21.3 (на его управляющем входе остается единица, хотя коммутатор 29.3 уже передает на свои выходы информацию с первого и второго своих входов) и

коммутатор 18.3, записывается в регистр 19.3. В этом же такте гт)21 через коммутатор 24.3 поступает на вход умножителя 16.3, на другой его вход поступает Э431 из регистра 17.3, и результат Ш21 а43 поступает

на вход сумматора 31.3, на другой вход которого подается 323 с выхода блока 30.3. С выхода сумматора результат а231 + + Ш21 а431 Э232 поступает через коммутаторы 22.2 и 21.2 в процессорный элемент

1.2, где записывается в регистр 19.2. В этом же такте 322 с выхода блока 15 поступает на блокЗ, который выполняет деление, и результат г Рг 1 блока 4.

и результат тз2 -322 /аза принимается в

В четырнадцатом такте счетчик 52 уменьшает свое значение на единицу, на вход устройства поступает 324 Э241, которое записывается в Рг 1 блока 30.3, U21 О переписывается в Тр 1 блока 28.3, тэт через коммутатор 24.3 поступает на вход умножителя 16.3, с выхода которого тзч азз1 поступает на сумматор 31.3, с выхода которого результат азз + азз поступает в процессорный элемент 1.2, где записывается в регистр 19.2 (Us2 1), а 323 записывается в Рг 1 блока 30.2. В этом же такте Э422 с выхода блока 15 поступает на блок 3, с выхода которого т42 -а422/аз22 принимается в Рг 1 блока 4, nisi записывается в Рг 1 блока 25.3, a mai переписывается в Рг 2 блока 25.3.

В пятнадцатом такте счетчик 52 уменьшает свое значение на единицу на вход устройства поступает аз4 аз41, которое записывается в Рг 1 блока 30.3, Usi О переписывается в Тр 1 блока 28.3, т41 поступает на вход умножителя 16.3, с выхода КОТОРОГО ГП41 а43

сумматор 31.3, с

поступает на ре

выхода которого

зультат ai31 + гп41 а431 Э432 поступает в процессорный элемент 1.2, где записывается в Рг 1 блока 30.2 (U42 0), а азз2 остается в регистре 19.2, U42 переписывается в Тр 1 блока 27.2, - в Тр 2 блока 27.2. В этом же такте as2 с выхода блока 15 поступает на блок 3, с выхода которого ms2 -352 /аз2 принимается в Рг 1 блока 4.

В шестнадцатом такте содержимое счетчика 52 становится равным нулю, на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в единицу триггеры 37 и 36, на вход устройства посту

пает 344 Э441, которое записывэется в ре- гистры 17,3 и 19.3, ai41 записывается в Рг 1 блока 30.3, U41 1 переписывается в Тр 1 блока 28.3, ГП51 поступает на вход умножителя 16.3 с выхода которого поступает на сумматор 31.3, который осуществляет пропуск операнда, и результат msi a43 353 с выхода сумматора поступает в процессорный элемент 1.2, где записывается в Рг 1 блока 30.2. В этом же такте значение 1/аз2 тб2 записывается в Рг 1 блока 4 (на входе выбора режима блока 3 - единица).

В семнадцатом такте в счетчик 52 записывается значение (п-1) 3, mai поступает с выхода блока 25.3 через коммутатор 24.3 нз умножитель 16.3 (на управляющем входе коммутатора 24.3 нуль), на другой вход которого поступает 344 , с выхода умножителя 16.3 т21 Э44 поступает на сумматор 31.3, с выхода которого ре

0

зультат Э241 + гп21 а441 3242 поступает на коммутатор 22.3, с выхода которого проходит через коммутаторы 21.3 и 18.3, и принимается в регистр 19.3. Кроме того, в этом такте на вход устройства поступает ais, которое поступает в процессорный элемент 1,2 и пройдя через коммутаторы 21.2 и 18.2 записывается в регистр 19.2. В этом же такте тз2 с выхода блока 4 поступает на вход умножителя 16.2, с выхода которого гтш азз поступает на вход сумматора 31.2, на другой вход которого поступает Э232 с выхода блока 30.2 и результат 323 + глз2 азз азз с выхода сумматора поступает в процессорный элемент 1.1, где принимается в регистр 7.

В восемнадцатом такте счетчик 52 уменьшает свое значение на единицу, тзт поступает на умножитель 16.3, с выхода которого тзта441 поступает на сумматор 31.3, с выхода которого результат аз41 + тз1 а441 аз42 проходит через коммутаторы 22.3 и 21.3 и записывается в регистр 19.3, а Э242 записывается в Рг 1 блока 30,3, Кроме того, 5 в этом же такте на вход устройства поступает 325 , которое пройдя через коммутаторы 21.2 и 20.2 записывается в регистр Рг 1 блока 30,2 (U21 0), гги2 с выхода блока 4 поступает на умножитель 16.2, с выхода которого т42 азз2 поступает на

0

5

0

5

0 5

0

5

вход сумматора 31.2, с выхода которого результат Э432 + гп42 азз2 Э433 поступает в процессорный элемент 1.1, где сравнивается с азз3 из регистра 7. Пусть I азз31 134331 . Тогда единица с выхода схемы 8 сравнения (U43 1) записывэется в Тр 1 блока 12, азз3 записывается в Рг 1 блока 15, а Э433 - в регистр 7.

В девятнадцатом такте счетчик 52 уменьшает свое значение на единицу, гг)41 поступает на умножитель 16.3, с выхода которого гп41 а441 поступает на сумматор 31.3, с выхода которого результат 3141 + гп41 а441 344 проходит через коммутаторы 22.3 и 21.3 и записывается в Рг 1 блока 30.3. Кроме того, в этом такте на вход устройства поступает аз5 , которое пройдя через коммутаторы 21.2 и 20.2 записывается в Рг 1 блока 30.2 (Usi 0), ms2 с выхода блока 4 поступает на умножитель 16.2, с выхода которого гп52 азз поступает на вход сумматора 31.2, с выхода которого результат ass + гп52 азз 353 поступает в процессорный элемент 1.1, где без сравнения записывается в Рг 1 блока 15, азз переписывается в Рг 2 блока 15.

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

выхода которого m5i a44 поступает на сумматор 31.1, который пропускает это значение на выход, и результат msi a44 354 поступает в Рг 1 блока 30,3. Кроме того, в этом такте на вход устройства поступает 345 Э451, которое пройдя через коммутаторы 21.2 и 18.2, записывается в регистры 19.2 и 17.2 (U41 1), a ais1 переписывается в Рг 1 блока 30.2, ГП62 с выхода блока 4 поступает на умножитель 16.2, с выхода которого глб2 азз2 поступает на сумматор 31.2, с выхода которого результат азз2 тб2 аез (на управляющем входе сумматора единица) принимается в Рг 1 блока 15, пройдя через коммутаторы 10 и 9. Кроме того, в этом такте на вход запуска устройства поступает импульс пуска, который по заднему фронту тактового сигнала устанавливает триггеры 39, 37, 38,46 и триггеры блока 54 в единицу, а 44, 36-в нуль.

В двадцать первом такте аналогично первому такту, в счетчик 52 записывается значение (п-1) 3, первый элемент Ьп bn очередной обрабатываемой матрицы В по- ступает на вход устройства, и пройдя через коммутаторы 10 и 6 записывается в регистр 7, а единица - в Тр 1 блока 12. Параллельно с этим продолжается обработка матрицы А аналогично тому, как это было с матрицей С (см. фиг. 5).

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

Формула изобретения Устройство для решения систем ли- нейных алгебраических уравнений, содержащее п/2+1 процессорных элементов (п - четное число), блок синхронизации, отл ичающееся тем, что, с целью повышения точности и снижения аппара- турных затрат, выходы i-ro процессорного элемента с первого по пятый 0 1, п/2) подключены к входам соответственное первого по пятый (i+1)-ro процессорного элемента, входы первого процессорного элемента с первого по пятый подключены соответственно к выходам с первого по пятый блока синхронизации,вход которого является входом запуска устройства, шестой выход i-ro процессорного элемента (i 2, п/2) подключен к шестому входу (i+1)-ro процессорное элемента, выходы i-ro процес- сорного элемента с седьмого по одиннадцатый (i 3, п/2+1) подключены соответственно к входам с седьмого по одиннадцатый (И)-го процессорного элемента, первый и второй выходы (п/2+1) процессорного элемента подключены к седьмому и восьмому входам (п/2+1)то процессорного элемента соответственно, выходы (п/2+1)-го процессорного элемента с четвертого по шестой подключены соответственно к его входам с девятого по одиннадцатый, одиннадцатый выход второго процессорного элемента подключен к шестому входу первого процессорного элемента, шестой выход которого является выходом устройства, вход которого подключен к седьмому входу первого процессорного элемента и к двенадцатым входам остальных процессорных элементов, причем первый процессорный элемент содержит блок деления, выход которого подключен к входу первого блока элементов задержки первого процессорного элемента, а первый вход его соединен с выходом первого регистра первого процессорного элемента, вход которого связан с выходом первого коммутатора первого процессорного элемента и с входом второго регистра первого процессорного элемента, выход которого подключен к первым входам схемы сравнения, первого и второго коммутаторов первого процессорного элемента, вторые входы которых также объединены и подключены к выходу третьего коммутатора первого процессорного элемента, первый и второй входы которого являются соответственно шестым и седьмым входами первого процессорного элемента, выходы процессорного элемента с первого по третий под- ключены соответственно к выходам с первого по третий второго блока элементов задержки, входы которого с первого по третий являются соответственно первым, вторым и пятым входами первого процессорного элемента, пятый и четвертый выходы которого подключены соответственно к выходам первого и третьего блока элементов задержки, вход которого связан с управляющими входами первого и второго коммутаторов и с выходом элемента И первого процессорного элемента, первый вход которого подключен к третьему входу первого процессорного элемента, четвертый вход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом схемы сравнения, выход второго коммутатора подключен к входу четвертого блока элементов задержки, выход которого является шестым выходом первого процессорного элемента и подключен к второму входу блока деления, выход выбора режима которого соединен с управляющим входом первого регистра и является пятым входом первого процессорного элемента, управляющий вход третьего коммутатора подключен к второму входу первого процессорного элемента, выход элемента ИЛИ соединен с вторым входом элемента И первого процессорного элемента, причем i-й процессорный элемент (i 2, п/2-1) содержит умножитель, первый вход которого подключен к выходу первого регистра 1-го процессорного элемента, вход которого соединен с выходом первого коммутатора и входом второго регистра i-ro процессорного элемента, выход которого подключен к первым информационным входам первого и второго коммутаторов i-ro процессорного элемента, вторые входы которых объедине- ны и связаны с выходом третьего коммутатора, первый информационный вход которого подключен к выходу четвертого коммутатора, первый и второй информационный входы которого являются соответст- вен но шестым и одиннадцатым входами i-ro процессорного элемента, входы и выходы которого с первого по третий подключены соответственно к входам и выходам с первого по третий первого блока элементов за- держки. второй вход умножителя подключен к выходу пятого коммутатора, первый и второй входы которого являются соответственно пятым и десятым входами i-ro процессорного элемента и подключены соответственно к входам второго и третьего блоков элементов задержки, выходы которых являются соответственно пятым и десятым выходами i-ro процессорного элемента, четвертый и девятый выходы i-ro процессорного элемента подключены к выходам соответственно четвертого и пятого блоков элементов задержки, вход которого является девятым входом i-ro процессорного элемента и подключен к пер- вому информационному входу шестого коммутатора, первый выход которого подключен к управляющим входам первого и второго коммутатора i-ro процессорного элемента, выход которого подключен к входу шестого блока элементов задержки, выход которого соединен с первым входом сумматора, выход которого соединен с шестым и одиннадцатым выходами i-ro процессорного элемента, седьмой и восьмой выходы i-ro процессорного элемента подключены соответственно к первому и второму выходам седьмого блока элементов задержки, первый и второй входы которого являются соответственно седьмыми и восьмыми входами i-ro процессорного элемента, четвертый вход которого подключен к входу четвертого блока элементов задержки и к третьему входу шестого коммутатора, второй и четвертый входы которого подключены соответственно к восьмому и второму входам i-ro процессорного элемента, второй выход шестого коммутатора является управляющим входом третьего коммутатора, второй вход которого подключен к двенадцатому входу i-ro процессорного элемента, управляющий вход четвертого коммутатора подключен к седьмому входу i-ro процессорного элемента и к входу элемента НЕ, выход которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к первому входу i-ro процессорного элемента, третий вход i-ro процессорного элемента соединен с управляющими входами первого регистра и сумматора, управляющий вход шестого коммутатора подключен к выходу элемента ИЛИ и к входу восьмого блока элементов задержки, выход которого подключен к управляющему входу пятого коммутатора, выход умножителя подключен к второму входу сумматора.

Фцг.1

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

Фиг.1

t

(V

ewezei

4,

et706Z8L