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

(57) Изобретение относится к в тельной технике, предназначено решения систем линейных алгебр ких уравнений и может быть исп но при построении специализир устройств, функционирующих в р масштабе времени, Целью изобре является увеличение быстродейс Цель достигается тем, что устр содержит матрицу размером Мх(И операционных блоков 1, где И - док решаемой системы линейных раических уравнений, 6 ил.,Чеб твия, ойство +1) поря- алгебРЕШЕНИЯ СИСТЕМ КИХ УРАВНЕНИЙ СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ ССС ОПИСАНИЕ ИН АВТОРСКОМУ СВИ 4488133/24-2428,09,8807,06.90. БюлА.П.Царев, И.Ии А,.Г.Шенешеуцкий(54) УСТРОЙСТВО ДЛЯЛИНЕЙНЫХ АЛГЕБРАИЧ детельство СССРР 15/32, 1979.тельство СССР6 Р 15/32, 1986 р=1, И, 3 =1, И+1-и аз Изобретение относится к вычислительной технике и м)эжет быть использовано при построении специализированных вычислительных систем функционирующих в реальном масштабе времени,Цель изобретения - увеличение быстродействия,На фиг.1 представлена схема устройства; на фиг.2 - схема операционного блока первого столбца матрицы,на Фиг,З - схема операционного блокапервой строки с второго по И-й столбцов матрицы на фиг.4 - схема операционного блока первой строки (И+1)го столбца матрицы;.на фиг.5 - схемаоперационного блока с второго по И-йстолбцов и с второй по И-ю строк матрицы; на фиг.б - схема операционного, блока (,И+1)-го столбца и с второй поИ-ю строк матрицы (И - порядок решаемой системы линейных алгебраическихуравнений).Устройство содержит матрицу размером И(И+1) операционных блоков 1,вход 2 режима устройства, вход 3 синхронизации устройства, вход 4 коэффициентов устройства, выходы 5 операции.зх блоког матрицы, выходы 6-6(:.стройства, Каждый операционный блок1 первого столбца матрицы содержитмупьтиппексор 7 и регистр 8, Каждыйоперационный блок 1 первой строки с(о)На И-й итерации матрица С),(вы рождается в вектор-столбец С я, С С ,С ),являющийся ре(,( ,ффшением системы линейных алгебраичес(М)ких уравнений, т,е. Х=С ,.Устройство работает следующн обС синхровхода 3 на входь; записи- чтения регистров 8 поступает первый тактовый импульс, а на вход 2 устройства подается единица, откуда она поступает на управляющий вход мультиплексора 7 операционного блока 1,: гце ).1=1,И и, таким образом, с инфармациочного входа 4, на выход мультилексора 7 поступает информаци второго по И-й столбцов матрицы содержит мультиплексор 7, регистр 8 иделитель 9,Каждый операционный бЛок 1 с вто" рого. по И-й столбцов и с в"орого по И-ю строк матрицы содержит мультиплексор 7, регистр 8, умножитель 1 О, сумматор 11. Каждьй операционный блок 1 (И+1)-го столбца с второй по И-ю строк матрицы содержит регистр 8, умножитель О и сумматор 11. Устройство осуществляет решение системы из И линейных алгебраическихо уравнений вида АХ=В, где А=( а матрица коэффициентов Х= Х ( Х ц - вектор-столбец неизвестных,- ТВ=ЬЬ- вектор-столбец свободных членов, на основе метода исключения. Решение системы из И линейных алгебраических уравнений с И неизвестными происходит за И итераций, На каждой итерации вычисляется новая )(о)С , поступает на одни инфсрмационные входы делителей .9 операционных блоков 1( , где 1=2 И+1 на другие информационные входы которых нэ регистров 8 поступают соответствующие элементы С , НЯ (3 ыход де)бетеля 9 Операционно(о блока 1, поступает частное,2ный вход умножителя 1 О операционногО Затем элементы столбца С;, Сблока 1; , где 1 щ 2,Я, и на выход 531 ф ф Ч где =1,И, поступают на информационо 1 5 ные выходы ; устройства, являющиесяционного блока 1 элемент С г, с,1 " решением системы тпнейных алгебраитупает на информационный вход умножи- ческих уравнений,теля 10 операционного блока 1. Свыхода умножителя 10 операционногоблока 1 произведение С(1 С 1 /Споступает на один йнформационный вход Устройство для решения систем лисумматора 11, на другой информационный нейных алгебраических уравнений, совход которого с выхода регистра. 9 держащее матрицу размером Мх(И+1)поступает элемент С(о . На выход сум-операционных блоков, где И - порядокматора 11 операционйого блока 1, и 15 Решаемой системылинейных алгебраи,1далее на выход 6,поступает элемент ческих уравнений, при этом вход синхфЗ (о),)(о 1дам синхронизации всех операционныхС блоков матрицы, вход режима устройНа втором такте на вход 12 подает- ства подкдочен к управляющим входамоперационных блоков строк с первойся ноль, который позволяет пропуститьпо М-ю, столбцов с первого по И-йна выход мультиплексора 7 операционноматрицы, выход операционного блокаго блока 1 , где 1=1,0-1 т=1 И первого столбца 1-й строки матрицыЭ 9 9 9чнформацию с информационного выхода (где 1=1, ,Х) подключен к первому5, операционных волоков и на вы- информационному входу операционногоход мультиплексора 7 операционного блока второго столбца 1-й строки матблока 1.Иинформацию с информацион" рицы, входы с первого по Х-й первойного выхода 5, , операционных блоков., группы коэффициентов устройства подНа последующих тактах на выход муль ключены соответственно к первому интиплексора 7 информация пропускается формационному входу операционноготолько с информационных выходов 5 блока первой строки первого столбцаС выхода мультиплексора 7 информацйя матрицы и к вторым информационньвз.исывается в регистр 8, Таким обра- входам операционных блоков первойзом, в регистрах 8 операционных бло- З 5 строки со второго по И-й столбцов матков 1; , где 1,1=1,3, записаны элефА ирицы, первый выход операционного бло=менты. Далее устройство работает ка первой строки 1-го столбца матрицыачалогичйо первому такту, В конце (где =2И+ 1) подключен к третьетакта на информационные выходы 5 му информационному входу операционногде 1=.2,И, 1=2,Ипоступают элементы л го блока второй строки т-го столбцаС. и на информационные выходыматрицы, о т л и ч а ю щ е е с я тем,р 1 что, с целью. увеличения быстродейст 5,1, поступают элементы Си вия, выход о пе рацион но го блок а перНа и-м такте в регистры 8 операци- вого столбца д-й строки матрицы подонного блока 1, ,где 1=1,И, 1=1,И+1-п, 45 ключен к первым информационным входам(о записываются элементы С; . Далее операционных блоков с третьего поустройство работает аналогично преды- (И+1)-й столбцов -й строки матрицы1дущим тактам, В конце и-го такта на первые входы коэффициентов групп синформационные выходы 5 где 1=2,И, второй по И-ю устройства подключены1=2,М 1-п,поступают элементы С ,5(1 соответственно к первым информацион - 2 +фд (р 1и на информационные выходы 5 посту- ным входам операционных блоков перво(о 1пают элементы С го столбца строк с второй по М-юНа М-м такте в регистры 8 операци- матрицы, т-й вход коэффициентов к-йонного блока 1; , где 1=1 И, =1.2, группы (где (с=2 .И) устройства:Изаписываются элементы С; После подключен к второму информационному4аналогичнь 1 х действий, как на предыду-. входу операционного блока к-й строкиих тактах, в конце такта на информа-го столбца матрицы, первый выходционные выходы 5, , где =2,К посту- операционного блока первой строки9 Элают элементы С( и на информациои- т-го столбца матрицы подключен к тре 1569846тьнм информационным входам операционных блоков 1 го столбца с третьей по М-ю строк матрицы, третий информационный вход операционного блока первой строки Е-го столбца матрицы подключен5 к выходу операционного блока второй строки %+1)-го столбца матрицы,3 четвертый информационный вход операционного блока -го столбца 1-й10 строки (где 1=2 Н) матрицы подключен к выходу операционного блока (1+1)-й строки В+1)-го столбца мат.- рицы, второй выход операционного блока первой строки сп-го столбца (где щ= 15 .:3,; И+1) подключен к четвертому информационному входу операционного блока Ю-й строки (в)-го столбца матрицы, выход операционного блока второго столбца В-й строки матрицы 20 подключен к второму информационному входу операционного блока первого столбцаЬ)-й строки матрицы и к Ос)-му выходу устройства, второй выход операционного блока первой строки второго столбца матрицы подключен .к второму информационному входу операционного блока первого столбца И-й ;троки матрицы и к Б-му выходу устройства, при этом каждый операционный 30 блок первого столбца матрицы содержит мультиплексор и регистр, причем в каждом операционном блоке первого столбца матрицы управляющий вход, вход синхронизации, первый и второй инфор- З 5 мационные входы операционного блока первого столбца матрицы подключены соответственно к управляющему входу мультиплексора, к входу записи-чтения регистра, к первому и втоРому инфор" 40 мационным входам мультиплексора, выХод которого подключен к информационному входу регистра, выход которого подключен к выходу операционного блока первого столбца матрицы, при этом каждый операционный блок первой строки с второго по И-й столбцов матрицы содержит мультиплексор, регистр и делитель, причем в каждом операционном .блоке первой строки с второго по И-й столбцов матрицы первый, второй и третий информационные входы, вход синхронизации и управляющий вход операционных блоков первой строки с второго по В-й столбцов матрицы подклю 55 чены соответственно к первому информационному входу делителя, к первому и второму информационным входам мультиплексора, к входу записи-чтения регистра и к управляющему входу мультиплексора, выход которого подключен к информационному входу регистра, выход которого подключен к второму информационному входу делителя, выход которого подключен к первому и второму выходам операционных блоков первой строки со второго по И-й столбцов матрицы, йри этом операционный блок . первой строки (И+1)-го столбца матрицы содержйт регистр и делитель, причем в операционном блоке первой строки ,(0+1)-го столбца матрицы первый и второй информационные входы и вход синхронизации операционного блока первой строки (И+1)-го столбца матрицы подключены соответственно к первому информационному входу делителя, к информационному входу регистра и к входу записи-чтения регистра, выход которого подключен к второму информационному входу делителя, выход которого подключен к первому и второму выходам операционного блока первой строки (3+1)-го столбца матрицы, причем каждый операционный блок с второго по М-й столбцов и с второй по И-ю строк матрицы содержит мультиплексор, регистр, сумматор и умножитель, причем в каждом операционном блоке с второго по И-й столбцов и с второй по М-ю строк матрицы первый, второй, третий и четвертый информационные входы, вход синхронизации и управляющий вход операционного блока с второго по Б-й столбцов и с второй по И-ю строк матрицы подключены соответственно к первым и вторым информационным входам умножителя и мультиплексора, к входу записи-чтения регистра и к управляющему входу мультиплексора, выход которого подключен к информационному входу регистра, выходы регистра и умножителя подключены к первому и , второму информационным входам сумматора, выход которого подключен к выходу операционного блока с второго по М-й столбцов и с второй по М-ю строк матрицы, причем каждый операционный блок (И+1)-гс столбца с второй по И-ю строк матрицы содержит регистр, умножитель и сумматор, причем в операционном блоке (И+1)-го столбца с второй по И-ю строк матрицы первый, второй и третий информационные входы и вход синхронизации операционного блока,(И+1)-го столбца с второй по Б-ю строк матрицы подключены соответ9 15698461 Оственио к первому информационномуственно к первому и второму информавходу умножителя, к информационному ционным входам сумматора, выход кото- входу регистра, к второму информа- рого подключен к выходу операционного ционному входу умнощителя и к входу блока (И+1)-го столбца с второй по5записи-чтения регистра, выходы реги" И-ю строк матрицы.стра и умножителя подключены соответСоставитель В.СмирновБланар Техред М,Ходданнч . Корректор Л.Патай едакто Заказ 145 1 Тираж 569 ,Подписно ВБППИ Государственного. комитета по изобретениям и о 113035, Москва, Ж, Раушская наб.,ьгтням при ГКНТ ССС 4/5 венно-издательский комбинат "Пате Ужгород, ул. Гагарин, 101 Произ