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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 8014050 4 С 06 Р 1532 Си,гдОПИСАНИЕ ИЗОБРЕТгТОРСНОМУ СВИДЕТЕЛЬСТВУ ержвинскии,ова и А.П.Гол ельство СССР15/324, 1979.ьство СССР15/324, 1978,ф Ю ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫПИНЕЙНЫХ, АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ(57) Изобретение относится к вычислительной технике и может быть испальзовано для решения систем линейных алгебраических уравнений. Цельизобретения - повышение быстродейст"вия устройства. Поставленная цельдостигается тем, что устройство содержит блок 1 памяти, первый сумма-.тор 2, регистр 3, блок 4 управления,второй сумматор 5, р мультиплексоров 6, где р - разрядность представления информации, р сдвигавщих регистров 7, р групп по Б блоков 8 памяти,где И - порядок системы уравнений,группу из р сумматоров 9. 1 з.п.лы, 5 ил., 2 табл.1405073 Составитель В.СБобкова Техред И.Дидык орректор В,Пилипен Реда аказ 3107/54 одписное мит отк Производственно-полиграфическое предприя г. Ужгород, ул, Проектная, 4 тие,Тираж 704Государственного коделам изобретений иосква, Ж, Раушска НИИП по 35, та СССРытийб., д, 4/5Изобретение относится к вычислительной технике и может быть исполь зовано для решения систем линейных алгебраических уравненийА%=у; А(С)ФО;е о,т, (1) где А(1)-(п 11 п) - матрица типа теллицевых, составленнаяиз численно определяемых коэффициентов а.И),(1)"аН) а,(1)ао(1)а (1).ае а ееее " Пт 1( 1 ) а Ь 4) ее а О ( " ) А(т,)= 1 а; 11=(2)у(1) - вектор-столбец с заданными компонентамиу;: у 1 И),У 2( ) эрур1 рх(1) - вектор неизвестныхх=Гх,М,хЬ) , ГПредполагается, что .а; 1 и у; 25изменяюгся во времени дискретно, через некоторые промежутки времени 31 ди ВС, причем В(жс,Цель изобретения - довышение быстродействия устройства,ЗО.На Фиг, 1 приведена Функциональная схема устройства; на Фиг. 2 и 3 -схема блока управления 1 на фиг. 4 -состояние сдвигающих регистров в процессе вычисления; на Фнг. 5 - алгоритм работы устройства.Устройство содержит блок 1 памяти, первый сумматор 2, регистр 3,блок 4 управления, второй сумматор 5,р мультиплексоров б, р .сдвигающих регистров 7, р групп по Б блоков 8 памяти, группу из р сумматоров 9. Блок,4 управления содержит первый регистр10, первый 11 и второй 12 счетчики,второй регистр 13, триггер 14, первый 15 и второй 16 дешифраторы, сумматор 17, третий дешифратор 18, первый 19, второй 20, третий 21, четвер тый 22, пятый 23, шестой 24, седьмой25, восьмой 2 б и девятый 27 элементыИ, первый 28, второй 29, третий 30 ичетвертый 31 элементы НЕ, элемент 32задержки, группа из Б элементов И 33,элемент ЧИ-ИЛИ 34.Блок 1 памяти имеет разрядность ри емкость 111 слов, необходимую для55хранения заданного массива значений у,Сумматор 2 служит для формированиярезультата вычислений неизвестных х, Ю 1(3)порядковый номер компонентывектора х (он же порядковыйномер уравнения в системе);индекс суммирования;число уравнений в системе,совпадающее с. размерностьювектора х. как разности между значением у и суммами слагаемых выражений.Регистр 3 представляет р-разрядный регистр для хранения текущего результата вычислений х1Сумматор 5 суммирует числа, представляющие суммы коэффициентов, вычисленные в каждом канале обработки информации.Регистр 7 предназначен для хранения и сдвига вычисляемых и вычисленных ранее компонент вектора и имеет количество разрядов, не меньшее числа коэффициентов а;Блоки 8 памяти предназначены для хранения сумм слагаемых, Его разрядность определяется требуемой точностью вычислений и может быть различной в зависимости от границ области значений коэффициентов а;Адрес ячейки, к которой происходит обращение, определяется кодом, находящимся в соответствующих триггерах регистра 7.Сумматор 9 предназначен для суммирования чисел, считываемых с блоков 8 памяти суммы коэффициентов,Регистр 10 хранит код выполняемой микрооперации. Счетчик 11 формирует . код адреса того блока, в который осуществляется запись сумм коэффициентов. Регистр 13 хранит код требуемого числа циклов вычислений. Триггер 14 формирует признак занятости устройства. Дешифратор 15 Формирует сигнал выполняемой микрооперации. Дешифратор 16 форнирует сигнал набора: блоков 8 памяти при вводе суммы ко фидиентон. Суааатер 17 определяет количество невыполненных циклов итераций. Дешифратор 18 Формирует признак равенства кодов, хранящихся в счетчике циклов и регистре циклов.Решение системы уравнений (1) основано на итерационном методе Гаусса-Зейделя1-1 йИИ 1 7 Г с - Иайа; 1 д 1 - 1 ; 11(7) 30 имеют Ход операции Операции,Мнемоническоеобозначе ние опе 000 СБР Сброс НОП ВКВ ВНП(9) ЗКФ С учетом характера матрицы (2) процесс (3) можно представить в видех (=1,:Б) в двоичном коде имеет видвЕ х=. х 1 2,где р разряднОсть дВоичных чисел 1х, - значение разрядов в двоичном представлении.Обозначив Иц): М+ -, .2 (. Ч, + ф -0 к ЛСлагаемые каждой из двух еумм находящихся в (8), могУт быть сгруппи рованы по Д членов (значение Ы определяется количеством адресных входов 40 в блоках памяти). Общее число таких групп равно Б 1/2, где Б . - число коэффициентов а (Я2 Б). С учетомтого, что Переменные Ч 1 принимают значение 0 при х 1=0 и .а; /а 0 при 45 х =1 может быть вычислена сумма,.1слагаемых для любого из 2 возможных кодов в группе. Вычисления всех 2 сумм в каждой группе производится вне устройства (например, на универ- сальной ЭВМ), а результаты вычислений для всех возможных кодов вводить в блоки 8 памяти сумм коэффициентов.В этОм случае хмОжнО Вычислить как й,М5 в5 Ч)Р(10)р (5-)+1Вычисление х; по формуле (9) реализуется путем считывания кодов Ц,5 из соответствующих ячеек блоков 8 памяти, определяемых кодом текущего при" ближения в сдвигающих регистрах 7, формирования с помощью сумматора 9 сумм Ц 5 в каждом разряде, суммирования в сумматорах 5 значений, полученных в сумматорах 9, считывания вели чин у; /а, и х) с соответствующих блоков памяти и формирования результатов вычисления с помощью сумматора 2.В результате выполнения требуемого количества тактов вычислений, определяемого числом разрядов в регистр 7, в последних записаны результаты вычислений неизвестных х; на И+1)-й итерации, После выполнения необходи-: мого числа итераций, определяемого загруженными в блок 4 управления дан- ными, в регистрах 7 сформирован ре.;:" зультат решения системы уравнений,Таким образом, в устройстве вычисления неизвестных могут быть выполнены в одном такте с помощью та- ких действий, как загрузка, сдвиг выборка по адресу и суммирование,Реализация конкретного алгоритма вычислений основана. На выполнении определенных операций, представленных в табл. 1, и анализе формируемых в устройстве логических условий, приведенных в табл, 2.Т а б л и ц а 1 Ожидание 001Ввод признака окончания вычислений 010 Ввод начального при."ближения 100 Запись коэффициентов 101"Ввод начального приближения", В результате н регистры 7 записываетсяинформация об адресах ячеек блоков 85памяти суммы коэффициентов. При поступлении на входы В 3, В 4 и В 5 кода101 (код операции "Запись коэффициентов") и на вход В 9 импульса занесения код операции записывается вустройство ( блок 4) и производитсядешифрация кода операции 101. Соответственно выбирается в каждом канале только один блок 8 памяти суммыкоэффициентов. При поступлении навход Вб импульса тактовой частоты информация о записываемой сумме коэффициентов с входов В 1,1-В,1 ш заносится в один из выбранных блоков 8памяти суммы коэффициентов, После20 записи информации в выбранную ячеикублоком 4 управления активизируетсядругая цепь и информация с входовВ 1.1-В 1.ш записывается по тому жеадресу, определяемому соответствующим25 кодом регистра 7, но в другой блок 8памяти суммы коэффициентов. Для за.писи суммы коэффициентов в другуюячейку снова выполняется операция"Ввод начального приближения", в ре 30 зультате которой в регистрах 7 записан адрес новой ячейки,"Ввод правой части". Операциясостоит в записи данных в блок 1 памяти, которые поступают на его первый вход, Для этого блок 4 управления формирует стробирующие импульсы,поступающие на вход чтения блока 1памяти,1"Счет". Выполнению операции обыч 40 но предшествует выполнение операций"Запись коэффициентов", "Запись начального приближения" и "Ввод правойчасти". При поступлении кода опера"ции "Счет" на соответствующем выходе48 блока 4 управления формируется импульс, по которому результат, сформированный на выходе сумматора 2, записывается в регистр 3. На выходесумматора 2 при этом формируется раз 50 ность значения правой части, поступающей с блока 1 памяти, и значения,сформированного сумматором 5. Результат на выходе равен сумме слагаемых, считываемых с сумматора 9, ко 5Продолжейие табл,) СЧ Счет Таблица 2 Мнемоничес кое обозна Логическое условие чение СЧИ-М 1 Код счетчика индекса больше или равен М 1СЧИКод счетчика адреса блоков8 памяти суммы коэффициентов равен МЗ СЧЦ-Р 15 ВПЧ , Ввод правой части 110 СЧИ-М 2 . Код счетчика индекса равен М 2 Код счетчика индекса равен 0 Выполненное число цикловвычислений равно числу,записанному в регистреР 13 П р и м е ч а н и е. М 1 - числокоэффициентов а; , М 2 - число разря-дов в регистрах 7, МЗ - число блоков8 памяти суммы коэффициентов, Р 15 -число итерационных циклов, заданноезагружаемыми в регистр 13 данными,На архитектурном уровне содержание операций состоит в следующем."Ввод начального приближения",Операция заключается в записи в регистры 7 данных, додаваемых на входыустройства В 1.1-В 1.ш.1 Ввод признака окончания вычислений. Операция состоит во вводе данных с входов В 1,1-В 1 л в блок 4 управления (количество итераций вычислений)."Запись коэффициентов", Осуществляется после операций Еброс" и торые суммируют числа, поступающиес выходов блоков 8 памяти сумм коэффициентов и определяемые кодом, находящимся в соответствующих регистрах 7.1405 35 Далее информация в регистре 7сдвигается на один разряд а в первый триггер регистра 7 записываетсярезультат, хранящийся в соответствующем триггере регистра 3,5В каждый последующий такт.выпол 1няются аналогичные операции, в первые разряды регистра 7 записываютсяновые вычисленные значения х 1. Послевыполнения М 1 сдвигов блок 4 управления формирует сигнал блокировки записи информации в регистры 7, в результате чего в регистр 7 записывают"ся О. Если выполняемый итерационный 15цикл последний, блок 4 управленияна выводе В 7 формирует признак последнего цикла. В конце последнегоцикла триггер "Работа" переводитсяв нулевое состояние. 20Работа блока 4 управления определяется содержанием операций, приведенных в табл. 1, Выполнение каждойоперации начинается после появленияна выходе В 9 сигнала "Занесение",в результате которого информацйя свходов В 1.1-В 1.ш оказывается занесенной в регистр 10 (фиг. 2). Призаписи в регистр 1 О кодов операции,которые выполняются более чем за один 30такт (коды 100-111), триггер 14 "Работа" устанавливается в "1" с помощью элемента И 27. Далее выполнениеопераций происходит следующим образом."Сброс". Осуществляется сброссчетчика 11 кодом адреса блока 8 памяти счетчика 12 и триггера 14."Ожидание". Импульсы тактовой частоты на выходах элементов 26, 23 и 4032 не формируются, так как блокируются сигналами с выходов элемента 19и дешифратора 15."Ввод начального приближения"При этой микрооперации сигнал с соответствующего выхода дешифратора 15подается на управляющие входы мультиплексоров 6, а сигналы тактовой частоты с выхода элемента 26 подаютсяна вход регистров 7. 50"Запись коэффициентов", На выхо-де элемента 29 формируется сигнал,который подается на блоки 8 памятив качестве признака записи. Записьосуществляется в блок 8, адрес которого определяется кодом в счетчике 11,"Ввод правой части". Сигнал с выхода дешифратора 15 через элемент 073 8НЕ 29 поступает на вход элемента И23, на выходе которого формируетсясигнал записи правой части в блок 1памяти.11Ввод признака окончания вычислений".Информация с входов В 1,1-В 1.шзаписывается в регистр 13."Счет". В каждый период тактовойчастоты на выходе элемента 32 задерж"ки формируется импульс, задержанныйна время установления сигналов насумматорах 5 и 9. При записи в ре 1 гистр 1 О кода операции 111 все блоки8 памяти суммы коэффициентов оказываются выбранными, В каждый периодтактовой частоты формируются такжесигналы на выходе элемента 26, обеспечивающие запись информации из регистра 3 в регистры 7 и увеличивающиемод счетчика 12 на единицу,При формировании в счетчике кодаМ 1 элемент И 22 формирует сигнал бло-,кировки записи информации в регистре7. При поступлении послед(ую(ших тактовых импульсов в регистрах.7 запи, сываются нули. При равенстве значенийкодов счетчика циклов и регистра 13на выходе сумматора 17 формируетсякод, равный О, При этом на нулевомвыходе дешифратора 18 формируетсяпризнак последнего цикла.В нулевом такте регистра 7 находятся начальное приближение и вычисляется первое итерационное приближение х,. В первом такте начальное(приближение сдвигается на один разрядвправо и в первый разряд регистра 7записывается на один разряд вправо,и в первый разряд регистра 7 записы-вается вычисленное значение х,. Ви-м такте в первый разряд ааписывается вычисленное значение х. Итерационный цикл завершается после 2 Б сдви;гов, в результате которых данные вы-числений занимают исходное положениедля выполнения следующей итерации.Состояние устройства в процессе вы"числений может характеризоваться кодами, хранящимися: в триггере "Работа", в счетчике выбранных блокОв памяти суммы коэффициентов, в тригге- ,рах регистров 7, соответствующих раз-,рядам адреса ячейки памяти суммы коэффициентов при выполнении микрооперации "Ввод коэффициентов"Загрузка кодов сумм коэффициентовв блоки 8 памяти и решение системыуравнений иллюстрируется блок-схемой1405073 обозначены следующие действия и логические условия; 35 - "Сброс", в ре-зультате которого блок 4 управленияустанавливается в исходное положение;36 - "Ввод начального приближения",в результате чего в регистры 7 записываются адреса ячеек блоков 8 памяти,суммы коэффициентов(в последующемв эти ячейки записываются коды суммкоэффициентов); 37 - анализ логического условия, "Код счетчика индекса равен М 2"; 38 - "Запись коэффициентов", код с входных шин В 1,1-В 1.шзаписывается в адресуемую регистром7 ячейку, выбранную дешифратором 1 бкода счетчика 11 адреса блоков 8 памяти суммы коэффициентов; 39 - ана-; 20 1. Устройство для решения системылинейных алгебраических уравнений,содержащее блок памяти, первый сумматор, регистр, блок управления, причем первый, второй и третий входыкода операций и вход синхронизацииустройства подключены соответственнок первому, второму, третьему входамрежима и входу синхронизации блокаудравления, вход признака занесения Б кода операции устройства подключенк четвертому входу режима блока уп,равления, с первого по р-.й входы свободных членов устройства, где рразрядность представления информации, О. подключены соответственно к первомупо р-й иьформационным входам блокапамяти, выход которого подключен кпервому информационному входу первогосумматора, выход которого подключенк информационному входу регистра,вход записи которого подключен к первому выходу блока управления, с первого по р-й выходы регистра подключены соответственно к первому по р-й 0 инФормационным выходам устройства,о т л и ч а ю щ е е с я тем, что,сцелью повышения быстродействия устройства,в него введено р мультиплексоров, р сдвигающих регистров, группа из р сумматоров, второй сумматори р групп по Б блоков памяти, гдеБ - порядок системы уравнений, приэтом входы с первого по р-й свободных членов устройства подключенысоответственно к первым информационным входам с первого по р-й мультиплексоров, с первого по р-й выходырегистра подключены соответственнок вторым информационным входамс пер вого по р-й мультиплексоров, выходыкоторых подключены соответственно кинформационным входам с первого пор-й сдвигающих регистров, второй выход блока управления подключен к пер 50 алгоритма работы устройства ( Фиг,5). Цифрами и соответствующей мнемоникой лиз условия "Код счетчика адреса бло ков памяти 8 суммы коэффициентов равен МЗ"; 40 - анализ условия "Код адреса выбранной ячейки равен М 4", где М 4 - максимальное значение адресаячейки в блоке 8 памяти суммы коэффициентов"; 41 - "Ввод признака окончания вычисления", при котором кодтребуемого количества итераций запиывается в соответствуюпдй регистрблока 4 управления; 42 " "Ввод начального приближения", данные начального приближения с входных шин устройства записываются в регистры 7; 43 - анализ логического условия "Код счетчика индексов равен М 2"; 44 -производится "Ввод правой части"(вектор вводится в блок 1 памяти)"45 - анализ логического условия "Код, счетчика индексов равен М 2"; 4 б - "Счет", за один такт осуществляется вычисление одного значения х,. сдвиг содержимого регистров 7 на один разряд и запись вычисленного значенияв освободившийся разряд, 47 - анализ логического условия "Код счетчика индексов больше или равен М 1"; 48 -Формирование признака блокировкимультиплексора, равного 1; 49 - анализ условия "Код счетчика индексаравен М 2"; 50 - формирование признака блокировки мультиплексора, равного 0; 51 - анализ логического условия "Выполненное число итерационныхциклов вычислений равно числу, записанному в Р 15"; 52 - Формирование сигнала "Признак последнего цикла равен 1"; 53 - анализ логического условия "Код счетчика индексов равен 0"; 54 - формирование сигнала "Признак последнего цикла равен 0",При необходимости решения системы(1) для следующего момента времениуказанный процесс повторяется, Вслучае, когда изменяется только правая часть у, а значения а; остаютсяпрежними, необходимость в процедурах вычисления и загрузки коэффициентов отпадает,Формула изобретенияподключен к счетному входу первогосчетчика, выход которого подключен кинформационному входу второго дешифратора выход первого элемента НЕподключен к второму входу элемента4 И-ИЛИ, выход второго элемента НЕподключен к шестому выходу блока управления, выход третьего элемента НЕподключен к третьему входу элемента 104 И-ИЛИ, выход шестого элемента И подключен к четвертому входу элемента4 И-ИЛИ, выходы элементов И с первогопо Б-й группы подключены соответственно к выходам с первого по Б-й 15группы блока управления, входы режима с первого по р-й группы которого подключены к информационным входамсоответственно с первого по р-й второго регистра, выход которого подклн -чен к первому информационному входусумматора, выход которого подключенк входу третьего дешифратора, выходкоторого подключен к восьмому выходублока управления и пятому входу элемента 4 И-ИЛИ, первый и второй выходывторого счетчика подключены соответственно к второму входу четвертогоэлемента И и второму информационномувходу сумматора, третий выход второго счетчика подключен к шестому, седьмому, восьмому и девятому входам элемента 4 И-ИЛИ.