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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 51104 Р 15/3 лирования вский ордеени инсти- авиации с етельство СССР Р 15/324,1976. етельство СССР Г 15/324, 1974. кимов В,Ф., но-аналоговые емы. М.: Сов. р ГОСУДАРСТВЕННЫЙ НОМИТЕТ ССС ПО ДЕЛАМ ИЗОбРЕТЕНИЙ И ОТКРЫ ОПИСАНИЕ ИЗОБ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Институт проблем модв энергетике АН УССР и Кина Трудового Красного Знамтут инженеров гражданскойим. 60-летия СССР(57) Изобретение относится к области вычислительной техники и можетбыть использовано для оперативногоразложения квадратной симметричнойматрицы на две треугольные, решениясистем алгебраических уравнений, вычисления определителей матриц. Цельизобретения - увеличение быстродействия. Устройство содержит и треугольных матриц вычислительных ячеек.ОдноАазная структура имеет параллельную организацию, благодаря чему время решения равно задержке сигналамежду входом и выходом структуры,4 ил.)ээ з.=3 1=444 В соответствии с развернутымри 1=12,3,4, орьного вычисления угольная ма тельную яче бой паралле треугольные вой по (ительную ячейку бой параллельнь тельные ячейки входы 4, выходь ства, параллел представл ганизацию элементов де и груп группа ур параллел1 з можно преДп уравнений, Павнений имеета, а)э11э 11 ставить в вири п=4 перваявид представляющую селитель, вычислиинформационные=Гац и 14 зультата устр ножитель 6,7 одноразряд)Е У модуг два, выходы О и ля, вторые 11 и раллельного дел элемент ИЛИ 14, влекателя, вход О ДЕЛИТЕ ды п 13,С) 1 э 114 Втораяителя, эле выходы 15 ы 16 корне менты НЕ корнеиэизвлекат 14 4 5 гр па уравнений имеет ля.+1Эз ээ гэ Работа однорструктуры для в нижней треуголь руемой из элеме матрицы А как А понированная по нои выч лительноилементов ени 1гэ 2424 г 4 матриць ичн тов симм1,Ь, гдеотношению трансматрибратвертая группы у ретья и в и имеют ца, осуществлязом,ледую 1 С 2) Э 4 1 яСг) 25Изобретение Относится к вычислительной технике и может быть ислоль"овано для оперативного разложения квадратно)1 симметричной матрицы на две треугольные, решения систем алгебраических уравнений, Вычисления определителей матриц,Цель изобретения - увеличение быстродействия.На фиг. 1 приведена схема одно О родной вычислительной структуры для случая, когда число и треугольных матриц вычислительных ячеек равно четырем (п=4), на фиг. 2 - схема вычислительных ячеек, начиная с второй 5 строки каждой треугольной матрицы устройства На фиг. 3 - введена схема вычислительных ячеек первой строки, начиная с второго столбца каждой треугольной матрицы, представляющие 20 собой параллельный делитель, нафиг, 4 - схема вычислительных ячеек первой строки первого столбца каждой треугольной матрицы устройства, представляющие собой параллельный корнеизвлекатель.Однородная вычислительная структура содержит п треугольных матриц Вычислительных ячеек, каждая третрица содержит вычислийку 1, представляющую сольный корнеизвлекатель, матрицы, начиная с иер)-ю, содержатвычислиычисление элементов матрицы Ьизуется методом квадратного корня по следующим рекуррентным выражениям Г1 =а - 1; 3.,=кгКс где 1; - элементы матрицы Ь;а. - элементы матрицы А.для п=4 выражения 1, 11 11; в развернутом виде при 1.=1,213,4будут иметь вид аа,э1 =1)а1 = --1 = --я я1 1 24 12 14 24 ЭЭ Э Э ЭЭ-4 .4404 4мости вида л=- Й определяется на основании выраженияГруппы уравнений являются основой для определения элементов 1 ц с помо 5 щью операций деления и извлечения корня.Частное Х от деления делимого Е на делитель У реализуется по выраже;.; (о нию Е-УХ=О пведставленному в разряд-чч чной формеЕ-УХ=Я, где Х=ХХ Е=Ч,К, 0=00 - разрядные векторы, представляющие собой разрядные изображения Х, Е и 0 соответственно,У= у у у - разрядная матрица,у у представляющая собойэу изображение делителя 20при п=ЗПроцесс определения 1 с-го (1 с=,2п) разряда искомого вектораХ реализуется на основании зависимости вида25(хгде Езначение переноса из старшего разряда вектора Е , ЗОопределяемого по выражению(х)2 при Е =О.В качестве примера рассмотримвычисление выражения Е/У, где У==0,96875, Е=0,4296875, Запишем У,Е, Х в разрядной формеч ч ЧУ 1011; Е=01111110; Х=1010;ч Ф)1 с=1 Е =01101; 1 с=2 Е =00101;Е"=РООО; Е(=1010;гч х ч(4) х =Ок=3 Е =10101; 1 с=4 Е =00000;50У"=1001;Е =00000; Е -1001;х: хФТаким образом, решение равноХ=1010.(Х=0,625).55Параллельный корнеизвлекатель работает следующим образом, Старший1 чразряд Х искомого вектора Х зависиДалее каждый последующий разрядХ=-1,2п искомого вектора Х определяется по выражениюпри Е, =1;(1 )Р при Е =О,где Е - значение переноса из старшего разряда вектора У.(",определяемого на основании выраженияч (1 ) ч (1) ) ч й"(1) ", (1Х"=(Х )(Х Х ),В качестве примера рассмотрим вычисление выражения ЧУ , где У=Х =/хЫ = (010о 11);У =(0000000) (Х=0,65625).х=(Однородная вычислительная структура работает следующим образом, На инфор,мационные входы 4,4,4,4,ячеек 1 2 пер-,вой строки первой матрицы подаютсясоответственно значенияа, а,а а,на унформационные входы 4,4,4 ячеек 3Ы 1 Ъф 24Фвторой строки первой матрицы подаютсяисходные значения а, а,а,далее на вхо 22 2 2ды 4,4 . ячеек З,третьей строки первойматрйцы подаются значения а а ,на входф 4 ф4 ячейки 3 последней строки первой матрицы подается значение а После зтого в схеме устройства протекает переходной процесс, по окончании которого на выходе ячейки 1( перьойстроки первой матрицы образуетсязначениеэлемента искомой матри 1251104цы Ь, которое поступает на выход5 п и на входы ячеек 2 первой строкипервой матрицы. В ячейках 2 первойстроки первой матрицы образуются значения элементов первой строки ,1, искомой матрицы Ь, которые поступают соответственно на выходы 55, 5,), на входы ячеек 3, столбцапервой матрицы и входы ячеек 3, вто- Орой,третьей и четвертой строк первойматрицы. В ячейках 3, второй,третьей и четвертой строк певой матрицы образуются значения: 1 1,1 (вторая строка) 1 , 1" (третья 5(оэ 91 поступают на входы ячеек 3 второй строки и 3 третьей строки второй матрипь). На выходах ячеек 12 первой строки второй матрицы образуются значения элементов1 второй строки искомой матрицы, 25которые5 и на соответствующие входы ячеек3 второй и третьей строк второй матрицы. На выходах ячеек 3 второй итретьей строк второй матрицы образу- З 021, 1 э,) поступают на входы ячеек(и1 , 2 первой строки третьей матри(22цйю а значение 141 - на вход ячейки 35Зз второй строки третьей матрицы.На выходах ячеек 1 э, 2 э первой строки третьей матрицы образуются элементы 1 , 1 третьей строки искомойматрицы, которые подаются на выходы5 , 5 и на соответствующие входыячеек 3 последующих строк третьейматрицы. В ячейке Зэ второй строкитетьей матрицы формируется значениеО)14 , которое подается на вход ячейки1 первой строки четвертой матрицы,в которой образуется значение 1 последней строки матрицы Ь, котороепоступает на выход 54 . Управлениеработой однородйой вычислительнойструктуры осуществляется с помощьюсинхросигналов, поступающих на, всевычислительные ячейки.Однородная вычислительная структура имеет параллельную организа цию, благодаря чему время решения равно задержке сигнала между входом и выходом структуры, т,е, вычисление элементов матрицы Ь и соответст% венно представления А=ЬЬ происходит за время переходного процесса в схеме. Это позволяет использоватьоднородную вычислительную структуру в качестве спецпроцессора для организации вычислительного процесса в реальном масштабе времени.Формула изобретенияОднородная вычислительная структура, содержащая первую верхнюю треугольную матрицу иэ п(п+1)/2 вычислительных ячеек, о т л и ч а ю -щ а я с я тем, что, с целью повьппения быстродействия, в нее введеныс второй по и-ю треугольные матрицывычислительных ячеек, первые информационные входы вычислительных ячеек первой треугольной матрицы подключены к информационным входам устройства, первые информационные вхо" ды вычислительных ячеек 1-й строки 3-го столбца-й треугольной матри" цы (п)=2п; =1,2п-ш-+2) подключены к выходам вычислительной ячейки ).-й строки 1-го столбца (ш)-Й треугольной матрицы, выход вычислительной ячейки первой строки первого столбца г-Й (г=1,п) треугольной матрицы подключен к вторым информационным входам вычислительных ячеек первой строки с второго по (и-г+1)-й столбец г-й треугольной матрицы, выходы вычислительных ячеек первой строки 1"го (1= =2п) столбца Е-Й треугольной матрицы подключены к вторым информационным входам вычислительных ячеек столбцов с (1-)-го по первый соответственно строк с второй по (и-юи к вторым ийформационньм входам ячеек 1-й строки 1(-треугольной матрицы, выход вычислительной ячейки (и(+1)-го столбца первой строки 1-й треугольной матрицы подключен к третьим информационным входам вычислительных ячеек (и-(-2.+2)-го столбца с второй по (пю строк и к второму информационному входу вычислительной ячейки первого столбца последней строки 1-й треугольной матрицы, выходы вычислительных ячеек первых строк треугольных матриц подключенык выходам результата уст ройства, при этом вычислительные ячейки, начиная с второй строки каж1251 10 дой треугольной,матрицы, содержат сумматор и умножитель, первый и второй входь умножителя подключены соответственно к второму и третьему информационным входам вычислитель ных ячеек, начиная с второй строки каждой треугольной матрицы, первый .и вто ой входы сумматора подключены соответственно к выходу умйожителя и к первому информационному входу вычислительной ячейки, начиная с второй строки каждой треугольной матрицы, выход сумматора подключен к выходу вычислительной ячейки, начиная с второй строки каждой тре угольной матрицы, причем вычислительные ячейкипервой строки, начиная с второго столбца каждой треугольной матрицы, содержат И групп (где И - разрядность поступающих операндов) 20 по И+1 сумматоров и И групп по И сумматоров по модулю два, с первого по М-й разряды первого входа вычислительной ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, являются входами делимого и подключены к первым входам сумматоров соответственно с первого по И-й первой группы, с (И+1)-го по 2 Иразряды первого входа вь 1 чис- ЗО лительной ячейки первой строки, начиная с второго столбца каждой треугольной матриЦы, подключены также к третьим входам (И+1)-х сумматоров групп с первой по И-ю, вторые входы 9"га разряда (=1И) второго входа вычислительной ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, являют ся входами делителя и подключены к перВым входам-го сумматора пс модулю два групп с первой по И-ю, выход 1-го сумматора по модулю дна-й группы (=1И) подключен к второму входу (+1)-го сумматорац -й группы, второй вход первого сумматорапервые входы (И+1)-х сумматоров первой группы, вторые входы сумматоров па модулю два первой группы подключены к шине единичного сигнала устройства, выход переноса (+1)-го сумматора р-й группы подключен к третьему входу 1 -го сумматора р -й группы, выходы переноса первых сумматоров Г-й группы (К=1И) подклю чены соответственно к вторым входам первых сумматоров, первым входам (И+1)-х сумматоров и к вторым входам 104 8сумматоров по модулю два (Г+1)-й группы, выход з-го (з=.2 И+1) сумматора -й группы подключен к первому входу (з)-го сумматора (С+ +1)-й группы, вьгхады переносов первых сумматоров групп с первой по И-ю подключены к выходам вычислительных ячеек первой строки, начиная с второго столбца каждой треугольной матрицы причем вычислительные ячейкиопервой строки первого столбца каждой треугольной матрицы содержат элемент ИЛИ, И групп сумматоров, при этом р-я (р=1И) группа сумматоров содержит р+2 сумматора, Игруппу сумматоров по модулю два, при этом .а-я группа (с 1=1И) сумматоров по модулю два содержит с сумматоров по модулю два, И элементов НЕ, первый разряд входа вычислительной ячейки первой строки первого столбца каждой треугольной матриць 1 подключен к первому входу элемента ИЛИ и к первому входу первого сумматора первой группы, второй разряд входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключен к второму входу элемента ИЛИ и к второму входу второго сумматора первой группы, (2 р+1)-е разряды входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключены к первым входам последнего сумматора р-й группы, (2 р+2)-е разряды входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключены к вторым входам последнего сумматора р-й группы и к входу (р+1)-го элемента НЕ, выход элемента ИЛИ подключен к входу первого элемента НЕ и к первым входам первых сумматоров по модулю два групп, выход переноса первого сумматора р-й группЫ подключен к первому входу первого сумматора (р+1)-й группы, к второму входу сумматоров пс модулю два р-й группы, к первому входу последнего сумматора пс модулю два (р+1) - й группы и к первому входу второго сумматора по модулю два третьей группы, третич вход второго сумматора и третьи нходы последних сумматоров групп подключены к шине нулевогс потенциала устройства выход первого элемента НЕ подключен к второму входу первого сумматора первой группы, 9 1 выходы переноса (р+2)-х сумматоров р-й группы подключены к первым входам (р 1)-х сумматоров р-й группы, выходы переноса ч-х сумматоров (ч 2. . .р 1) р-й группы подключены к третьим входам (у)-х сумматоров, выходы и-х сумматоров (ц 2.,р+2) р-й группы подключены к вторым входам (и)-х сумматоров (р 1)-й группы, выходы -х элементов НЕ (й=2 251104 1 Ор) подключены к вторым входам (р+1)-х сумматоров 1-й группы, выходые-х сумматоров по модулю два (р=1,Ч) о-й группы подключены к первым входам (41)-х сумматоров (ц 1)-йгруппы, выходы переноса первых сумматоров групп подключены к выходамвычислительной ячейки первой строки первого столбца каждой треуголь ной матрицы.1251104 актор И,Рыбчен Корректор С.Чер акаэ 4413/47 енного ко енин и о Раушск производственно-полиграфическое предприятие, г, ужгород, ул, Проектн сия 4Составитель В.СмирнТехред М.Ходанич Тираж 6 НИИПИ Государст по делам иэобре 35,.Москва, ЖПодписнотета СССРытийнаб д. 4/5