Однородная вычислительная структура для разложения матриц

,ЯО 124953 504006 Г 15/ ОПИСАНИЕ ИЗОБРЕТЕН ас ж в СС 56) С. Численньс. 324-33 идетельство 06 Г 15/32 детельство 06 Р 15/32 Бахвалов Н аука, 1975торское св 687, кл. С торское св 987, кл. С е методы. О. СССР 1979 СССР 1979ИИСЛИТЕЛ ЖЕНИЯ ИА СТРУК ОДНОРОДНАЯДЛЯ 1 Л 3-РАЗЛМ ОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ АВТОРСКОМУ СВИДЕТЕЛ(71) Киевский ордена Трудовоного Знамени институт инженеданской авиации им. 60-летия(57) Изобретение относится к вычислительной техйике и может быть использовано автономно или в комплексес ЦВИ для разложения квадратной матрицы на две треугольные, Цель изобретения - увеличение быстродействия.Это достигается тем, что устройствосодержит (и) матриц из и вычислительных ячеек, реализующих операциивида а+1 о и аЛ. Разложение исходнойматрицы в устройстве осуществляетсяна основе рекуррентных соотношений.Увеличение быстродействия достигается за счет параллельной организациилогической структуры при реализациирекуррентных соотношений. Время формирования решения в устройстве определяется временем переходного процессав схеме. 3 ил, 6 табл.1249531 Во втором слое производятся вычисления:(к 1) 1 с, при Г =1 Х= В третьем слое производятся следующие вычисления 15 где Г ) - значение (кч) переноса изора Ежению Е стар щего разрядделяемогок)- в е опр е ч(Кв еличина принимающая зна 2, при й =1 ния В четв ующие вычскЕ том слое оизводятся слесления:=0,6 ной1,м з)5 5 сс й 5 66 0 1 0 10 1 0 1 О Реализаци производится ществления о гебраическим вычисления в слоях осу ал- ения а с умми) ри реалное ХУ реаставле за я х= 1 0 х)=0чател елен изуе дели1 Х=Ое 0 номуЕ-МХ= и К=Э и К=4 0 1 0 0,,2 , 2г, гсоответств Таким етствуе Однор для 1 Л)-рельная систем риц работает 2 дующиВ и нии на входные 3 2,1 1 фгс э 21 ьуг енно значения зл ау нто.,а определения К-гозряда искомого век на основании зави 3) фисход 5 сф 5 бего в схеф ЗЗИ 1ой матрицы,Процесс 2. и) рекает пер мос После окончания са ерычислит ель ч 1 Ягде Х=Х, Х,.ч 1 2 2 л0=0,00,разрядные вексобой разрядисоответственн м параллельногций умножения срованием и делоперации деледелимого Е напо выражению 2разрядной форм разрядная матрица, представляющая собой изоб ражение делителя у при и=3.,а 5после чодной процессереходного пр1 О 20 о строки и первого столбца первой матрицы по выражению образук)тся значения элементовпервой строки и столбца искомых элементов матриц ЬН, которые поступают на выходные шины 3 3, 33, соответственно. Далее во всех остальных ячейках 1 , начиная с второй строки и второго столбца, образуются промежуточные значенияр) )Н,1 Н, 1 1, ,которые поступают на вторые входы соответст-. вующих ячеек 1 второй матрицы. На выходах ячеек 1, первой строки и,первого столбца второй матрицы образуются искомые значения Н,Ь),Н 5 иК, поступающие на выход соответственно.На выходах ячеек 1, первого и второго столбцов, второй, третьей и четвертой строк второй матрицы обра)7) Т) 9) зук)тся значения Н. 13) и 1., 11, которые подаются на первые входы соответствующих ячеек 1, третьей матрицы.На выходах ячеек 1, первой строки и первого столбца третьей матрицы образуются, искомые значения Н ,У и . 1, третьей строки и столбца элементов матриц Ь и Б, которые поступают на выходные шины 3 3,. и 3 3, соответственно. На всех остальных ячейках 1, третьей матрицы образуются промежуточные значения): з)Н , которые. поступают на вторые входы ячеек 1 четвертой матрицы Наконец, на выходах двух последних ячеек 1 четвертой матрицы образуются искомые значения Н, и элементов матриц Ь и Н, которые поступают на выхоцные шины 3 и 3,. соответственно. Таким образом, за время, равное,цлительности переходного процесса в схеме, на выходных шинах 3, устройства образуются искомые значения элементов ЬП матриц,Однородная вычислительная структура для ЬН-разложения матриц является однородной и глобально параллельной. Время вычисления элементов Ф и 1 Я, на ней равно задержке сигнала между входом и выходом элементов схемы. Процесс вычисления элементов 1, , ), представлен в виде слоев с пельк) распараллеливания вычислений д) уровня двух типов 25 30 35 10 45 50 55 операций; а+10 и деления. Это позволяет строить вычислительную структуру из существующих интегральных схем ограниченной номенклатуры илив виде отдельной СБИС. Благодаря организации логической структуры вычислителя в виде однородных слоев,она является параллельной (комбинационной), вычислительный процессв ней начинается с момента подачи исходных данных на входные шины,результат вычислений снимается извыходных шин после окончания переходного процесса в схеме, который длится, например, 4 мкс, если каждая из идентичных ячеек 1 выполненана базе одного типа интегральныхсхем К 155 ИПЗ серии 155 при п=10и гп=16.Формула из обретения Однородная вычислительная структура для 1 Л-разложения матриц, содержащая первую матрицу из и вычислительных ячеек, о т л и ч а ю щ а я с я тем, что, с целью увеличения быстродействия, в устройство введены с второй по (и)-ю матрицы вычислительных ячеек, при этом Е-я матрица (1 с=1,2,п) содержит (и+1-1 с) строк и (ис) столбцов, первые информационные входы вычислительных ячеек 1-й строки (д=1,2,п) первой матрицы подключены соответственно к информационным входам элементов первого столбца 1-й строки разлагаемой матрицы устройства, вторые информационные входы вычислительных ячеек 1-й строки 1-го столца (3=1,2 п) матрицы вычислительных ячеек подключены соответственно к входам записи элементов разлагаемой матрицы устройства, выходы вычислительных ячеек первой строки -го столбца (1=1, 2пс) 1 с-й матрицы подключены к выходам считывания элементов 1 с-й строки Н-матрицы результата и к третьим информационным входам вычислительных ячеек 1-го столбца с-й матрицы, выходы вычислительных ячеек первого столбца Я-й строки (5=2,3 ис+1) 1 с-й матрицы подключены к выходам считывания элементов )с-го столбца Ь-матрицы матрицы результата и к первым информационным входам вычислительных ячеек (Б)-й строки с)1)-йматрицы, выходы вычислитель 12 ч 9331(р=2, Зп+1-1 с, Ч=2,3 ис)1 с-матрицы подключены к вторым информационным входам соответствующих вычислительных ячеек (р)-й строки(1 - 1) - го столбца (Е+1)-й матрицы,при этом вычислительная ячейка р-й,строки о-го столбца 1-й матрицы содержит умножитель и сумматор, первыйи второй информационные входы вычислительной ячейки р-й строки о-гостолбца 1-матрицы являются информационными входами первых операндовумножителя и сумматора соответственно, а третий информационный вход вычислительной ячейки р-й строки о-гостолбца 1-й матрицы - информационным входом второго операнда умножителя, выход которого подключен к информационному входу второго операндасумматора, выход которого являетсявыходом вычислительной ячейки вы"числительная ячейка первой строкиМ-й матрицы содержит щ групп одноразрядных сумматоров по (щ+1) сумматорув каждой из щ групп сумматоров помодулю два по щ сумматоров в каждой,где щ - разрядность представления информации, первый информационный входг-го разряда (г=1,2щ) делителяячейки первой строки 1-й матрицы подключен к первым информационным входамг-х сумматоров по модулю два с первой по щ-ю группы, вторые информационные входы сумматоров по модулю двапервой группы, первый информационныйвход. первого одноразрядного сумматора первой группы и третий информаци 5 90онный вход (щ+1) -го одноразрядного сумматора первой группы подключены к шике единичного сигнала устройства, информационные выходы г-х сумматоров по модулю два Ч=й группы (Ч= 1,2щ) подключены к первым информационным входам (г+1)-х одноразрядных сумматоров Ч-й группы, второй информационный вход г-горазряда делимого ячейки первой строки Е-й матрицы подключен к вторым информационным входам г-го одноразрядного сумматора первой группы, а второй информационный вход Г-го разряда делимого (Г=г+12 г) ячейки первой строки Е-й матрицы подключен к вторым информационным входам(щ+1)-х одноразрядных сумматоров20 г-й группы, выходы переноса первыходноразрядных сумматоров 9 -й группы(4 =1щ) подключены к первомуинформационному входу первого одноразрядного сумматора, к третьему инФормационному входу (щ+1)-го одноразрядного сумматора, к вторым информационным входам сумматоров по модулю два (1+1)-й группы и соответственно к выходу г-гр разряда результата,информационный выход-го (Р=2щ+1) одноразрядного сумматора 1 -йгруппы подключен к второму информационному входу (Р)-го сумматора(1+1)-йгруппы, выход переноса р -гооднообразного сумматора Ч-й группы подключен к третьему информационному входу Р + 1) - гоодноразрядного сумматора Ч-йгруппы.1249531Составитель В.Смирнов Редактор С.Патрушева. Техред О.Гортвай Корректор О.Луговая Заказ 4326/50 7 йраж б 71 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4