Устройство для обращения плотных ( @ х @ ) матриц

 

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. Целью изобретения является повышение быстродействия. Устройство содержит п операционных блоков (ОБ). РК-й ОБ () содержит умножитель , сумматор, три регистра, четыре триггера, два элемента И и группу элементов И. РК-й ОБ () содержит умножитель , узел вычисления обратной величины , два регистра, четыре триггера, два элемента И, две группы элементов И, элемент ИЛИ-НЕ, группу элементов ИЛИ. РК-й ОБ () содержит умножитель, сумматор, пять регистров, восемь триггеров, группу элементов И, два элемента И. Поставленная цель достигается за счет алгоритмических и структурных решений, реализованных в устройстве. 3 з.п. ф-лы, 5 ил. с (О (Л

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (50 4 б 06 F 15/347

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

С

ОПИСАНИЕ ИЗОБРЕТЕНИЯ „"

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ йЪ;„;,,„. (21) 4143350/24-24 (22) 31.10.86 (46) 07.04.88. Бюл. № 13 (72) В. П. Якуш, С. Г. Седухин, В. А. Мищенко и Л. Б. Авгуль (53) 681.32 (088.8) (56) Авторское свидетельство СССР № 1211754, кл. G 06 F 15/347, 1984.

Hwang.Ê., Cheng Y. Н. VLSI computing

structures for solving large — scale lineas system of eguations. — Proc. Int. Conf. Patal1еl Proc. New York, Н. Y., 1980, р. 217 — 227. (54) УСТРОЙСТВО ДЛЯ ОБРАШЕНИЯ

ПЛОТНЫХ (N x N) МАТРИЦ (57) Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычисÄÄSUÄÄ 1387013 А1 лительных машинах и устройствах обработки данных. Целью изобретения является повышение быстродействия. Устройство содержит n операционных блоков (ОБ). РК-й ОБ (Р)К) содержит умножитель, сумматор, три регистра, четыре триггера, два элемента И и группу элементов И. РК-й ОБ (Р=К) содержит умножитель, узел вычисления обратной величины, два регистра, четыре триггера, два элемента И, две группы элементов И, элемент

ИЛИ вЂ” НЕ, группу элементов ИЛИ. РК-й

ОБ (Р(К) содержит умножитель, сумматор, пять регистров, восемь триггеров, группу элементов И, два элемента И. Поставленная цель достигается за счет алгоритмических и структурных решений, реализованных в устройстве. 3 з.п. ф-лы, 5 ил.

1387013

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

Цель изобретения — повышение быстродействия.

На фиг. 1 представлена функциональная схема устройства для обращения (п)(п) плотных матриц для случая п=4; на фиг. 2— функциональная схема соединения четырех операционных блоков; на фиг. 3 и 4 временные диаграммы устройства; на фиг. 5 — таблицы, описывающие логику работы операционных блоков.

Устройство для п=4 содержит информационные входы 11, 14 группы, операционные блоки (ОБ) 211, ..., 244, выходы

31,, 34, синхровход 4.

ОБ 2;;(i=j) содержит первую группу входов 5, синхровход 6, умножитель 7, узел

8 вычисления обратной величины числа, регистры 9 и 10, триггеры 11 — 14, элементы

И 15 и 16, группы элементов И 17 и 18, элемент ИЛИ вЂ” НЕ 19, группу элементов ИЛИ

20, первую группу выходов 21, вторую группу выходов 22, третью группу выходов

23 (фиг.. 2).

ОБ 2;; (i= — 2,п; j=l, n — 1; i)j) содержит синхровход 6, первую группу входов 24, вторую группу входов 25, умножитель 26, сумматор 27, регистры 28 — 30, триггеры

3! — 34, элементы И 35 и 36, группу элементов И 37, первую группу выходов 38, вторую группу выходов 39 (фиг. 2).

ОБ 2ij (i=1, и — 1; j=2, и; i(j) содержит синхровход 6, первую группу входов 40, втору(о группу входов 41, умножитель 42, сумматор 43, регистры 44 — 48, триггеры

49 — 56, группу элементов И 57, элементы

И 58 и 59, первую группу выходов 60, вторую группу выходов 61.

В основу работы устройства обращения (п)(п) матрицы A=(a;;), положен метод, п ри котором расширенная (п)(2п) матрица (А, Е) сводится к (п)(2п) матрице (Е/А ) по рекуррентным соотношениям (0) для а;,— — a;;; 1, 1=1,п и к= l, и (x) (к-l) (x-i)

Логика работы ОБ 211()=() задается табл. 1, ОБ 2;;(i=2,ï; =l,ï — 1 i)j) табл. 2, ОБ 2;;(i= 1,ï — 1; j=2,n;i(j) табл. 3 (фиг. 5).

Устройство работает следующим образом.

В исходном состоянии регистры 9, 10, 28, 29, 30, 44 — 48 и триггеры 11 в 14, 31 — 34, 49 — 56 (фиг. 2) ОБ 2;;(i, j=1,n) устанавливаются в нулевое состояние цепи установки (не показано).

Очередность подачи элементов а ; матрицы А, где 1 — номер такта, показана на фиг. 1. Элементы а;; подаются íà m входов первой группы входов ОБ. Одновременно с элементами а;; на (и+ 1-й и m+2-й входы

5 !

О !

55 первой группы входов подаются два дополнительных разряда, принимающие значения 0 или 1.

На нулевом такте элемент а „и дополнительные разряды 1 и 0 подаются соответственно на гп входов, гп+1-й вход и

m+2-й вход первой группы входов 11 ОБ

211. При этом на вход элемента И 16 подается единичный дополнительный разряд, а на его выходе формируется единичный сигнал, который разрешает запись элемента а11 в регистр 10 по заднему фронту тактового импульса. Кроме того, дополнительный единичный разряд устанавливает и триггер 1 в единичное состояние (фиг. 2 — 4).

На первом такте на вход 11 подаются элемент а12 и дополнительные разряды

0 и 1, на аХоП 12 — элемент а21 и дополнительные разряды 1 и 0 (фиг. 1). В ОБ 21)триггер 11 устанавливается в нулевое состояние, триггеры 12 и 13 — в единичное состояние, в регистр 9 записывается элемент а12, так как на вход элемента И 15 подается единичный дополнительный разряд и на его выходе формируется единичный сигнал, который разрешает запись элемента а(2 в регистр

9 по заднему фронту тактового импульса (фиг. 2 — 4). На входе узла 8 вычисления обратной величины числа формируется значение 1/al l, которое поступает на вход умножителя 7, на второй вход которого подается элемент а(2. На выходе умножителя 7 форми(1) руется значение a12=a12/а11, которое через открытые элементы И 17, ИЛИ 20 подается на выходы 21 — 23. В ОБ 221 триггер 31 устанавливается в единичное состояние, на входе элемента И 35 формируется единицный сигнал, с помощью которого по заднему фронту тактового импульса в регистр

29 записывается эле,мент а21 (фиг. 2 — 4) .

На втором такте на вход l l подаются соответственные элементы а13 и дополнительные разряды 0 и 1, на вход 12 — элемент а2 и дополнительные разряды 0 и 1, на вход

13 — элемент а31 и дополнительные разряды г

1 и 0 (фиг. 1). В ОБ 211 в регистр 9 записывается элемент а13, триггер 13 устанавливается в нулевое состояние, триггер 14— в единичное состояние. На выходе умножи(1) теля формируется значение a13=a13/a I l.

В ОБ 221 в регистр 28 записывается элемент а12, в регистр 30 — элемент а22, триггер (4)

31 устанавливается в нулевое состояние, триггеры 32 и 33 — в единичное состояние.

На входе умножителя 26 формируется значение а12а21, которое поступает на вход сумматора 27. На второй вход сумматора 27 через открытые элементы И 37 подается элемент а22. На выходе сумматора 27 форми(1) (i) руется значение а22 a22 — a12 а21 В ОБ 212 в (1) регистр 44 записывается а12, триггер 49 устанавливается в единичное состояние (фиг. 2 — 4).

На третьем такте на вход 11 подаются э элемент а14 и дополнительные разряды 0 и 1, 1387013

5 (О

b11

b21

Ь31

b12 Ь1з Ь14

Ьгг Ьгз b24

Ьзг bçç Ьз4

b42 b43 b44

25

Формула изобретения

55 на вход 12 — элемент а23 и дополнительные разряды 0 и 1, на вход 13 — элемент азг и дополнительные разряды О и 1, на вход

14 — элемент а41 и дополнительные разряды

1 и О (фиг. 1). В ОБ 211 в регистр 9 записывается а14, на выходе умножителя форо) мируется значение а14=а(4/ajj, которое через элементы И 17 и ИЛИ 20 подается на выходы 21 — 23. В ОБ 221 в регистр 28 записывается a(3, в регистр ЗΠ— агз, на (1) выходе умножителя 27 формируется зна(1) И) чение агз=агз — a13a21 которое поступает на выход 38. В ОБ 212 в регистр 44 записывается а13, в регистр 45 — а12, триггер 49 устанав(1) (1) л и в а ется в нулевое состояние, триггеры 53 и

50 — в единичное состояние . В О Б 2» в регистр 1 О записывается а 22, триггер 1 1 ус(2) танавливается в единичное состояние (фиг. 2 — 4) .

На четвертом такте на вход 11 подаются произвольное m-разрядное число (признак ) и дополнительные разряды О и О, на вход 12 — элемент а24 и дополнительные разряды О и I на вход 13 — элемент

4 р а33 и дополнительные разряды О и 1, на

4 вход 14 — элемент а42 и дополнительные разряды О и 1 (фиг. 1).

В ОБ 211 триггер 12 устанавливается в нулевое состояние, при этом на выходе элемента ИЛИ вЂ” НЕ 19 формируется единичный сигнал, который открывает группу из элементов И 18 и через элементы ИЛИ

ЯО значение b(!1=1/a11 поступает на входы

21 — 23. В ОБ 221 в регистр 28 записывается а Д, в регистр 30 — а24. На выходе сумматора (1) (1)

27 формируется значение а24=а24 —,а14а21, которое поступает на вход 38. В ОБ 2гг в регистр 44 записывается à114, в регистр 45— а13, в регистр 46 — а(, триггер 50 устанав(i) (1) ливается в нулевое состояние, триггеры 51 и

54 — в единичное состояние. В ОБ 222 в регистр 9 записывается а23, триггер 11 устанав(1) ливается в нулевое состояние, триггеры 12 и 13 — в единичное состояние. На выходе умножителя 7 формируется значение а23= (2)

= a23/ a », которое поступает н а выходы 2 1— (1) (1)

23 (фиг. 2 — 4).

На пятом такте на вход 11 может подаваться элемент а„новой матрицы А или нулевое значение с дополнительными разрядами 1 и О, на вход 12 — признак ": и дополнительный разряды О и О, на вход 13 — a34 и дополнительные разряды О и 1, на вход

14 — а43 и дополнительные разряды О и 1 (фиг. !). В ОБ 211 в регистр 10 записывается элемент à11 новой матрицы или нулевое значение, триггер 11 устанавливается в единичное состояние. В ОБ 221 в регистр

28 записывается b„, триггер ЗЗ устанавливается в нулевое состояние, на выходе сумматора 27 формируется значение Ь21= (1) — а21/ajj в ОБ 212 в регистр 44 записывается b„, в регистр 45 — a14, в регистр 46— (1) (1) (1) (1) (2) а12 в регистр 47 — а(3, в регистр 48 — a23 триггер 51 устанавливается в нулевое состояние, триггеры 55 и 52 — в единичное состояние, на выходе сумматора 43 форми(2) (1) (11 12) руется а(з=а(з — а1га23 В ОБ 22 в регистр 9 записывается элемент а(24, триггер -- 13 уста (1) навливается в нулевое состояние, а триггер

14 — в единичное состояние, на выходе умножителя 7 и соответственно элементов

ИЛИ 20 формируется а24)=а 4)/ар)((фиг. 2 — 4), На последующих тактах работы в ОБ 2„ формируются значения элементов обратной матрицы аналогично согласно табл.

1 — 3 (фиг. 5). Первый элемент Ь41 обратной матрицы формируется на выходе ОБ 214 на такте с номером 10, а последний элемент b14 — в ОБ 214 на такте с номером 16 (фиг. 1) . Полученные элементы образуют обратную матрицу вида

Таким образом, в предлагаемом устройстве для выполнения обращения (и г< и) плотной матрицы требуется п2 операционных блоков и (5п — 4) тактов работы.

I. Устройство для обращения плотных (nXn) матриц, содержащее и- операционных блоков, отличающееся тем, что, с целью повышения быстродействия, i-й информационный вход устройства соединен с первой группой входов ij-го операционного блока (i= l, п), первая группа выходов ij-го операционного блока (i=i, и, 1=i, и 1ii соединена с первой группой входов 1 (j+

+1)-го операционного блока, вторая группа выходов ij-го операционного блока (ц=l, п — 1, I)j) соединена с второй группой входов (i+1) j-го операционного блока, третья группа выходов ij-го операционного блока (ц=2,п, i=j) соединена с второй группой входов (i — 1, j)-го операционного блока, вторая группа выходов tj-го операционного 6 o((a(i(j, i=2,п — 1, 1=3,п) соединена с второй группой входов (i — I,j)-го операционного блока, первая группа выходов (i,ï-го операционного блока (i= l,è) соединена с i-м выходом устройства, управляющий вход которого соединен с синхровходами ij-x операционных блоков i,j=l,ï).

2. Устройство по и. 1, отличающееся тем, что ij-й операционный блок (ц=l,п, i=j) содержит умножитель, узел вычисления обратной величины числа, два регистра, четыре триггера, две группы элементов И, два элемента И, группу элементов ИЛИ, элемент ИЛИ вЂ” НЕ, причем m входов первой группы операционного блока соединены с информационными входами первого и второго регистров, где m — разрядность элементов матрицы, (гп+1)-й вход первой группы опе1387013 тем, что ij-й операционный блок (i=2,п, $ =1, и — 1, i)j) содержит умножитель, сумматор, три регистра, четыре триггера, два элемента И, и группу элементов И, при- 40 чем m входов первой группы операционного блока соединены с информационными входами второго и третьего регистров, (m+1)-й вход первой группы операционного блока соединен с первым входом первого элемента И и с информационным вхо- 45 дом первого триггера, в (m+2)-й вход первой группы операционного блока соединен с первым входом второго элемента И и с информационным входом третьего триггера, вторая группа входов операционного блока соединена с информационным входом первого регистра, выходы которого соединены с второй группой выходов операционного блока и с первым входом умножителя, второй вход которого соединен с выходом второго регистра, а выход — с первым входом сумматора, второй вход которого соединен с выходом элементов И группы, выход сумматора подключен к m-выходам рационного блока соединен с первым входом второго элемента И и с информационным входом первого триггера, а (m+2)-й вход первой группы операционного блока соединен с первым входом первого элемента И и с информационным входом второго триггера, выход второго элемента И соединен с входом разрешения записи второго регистра, выход которого соединен с входом узла вычисления обратной величины числа, выход которого соединен с первыми входами элементов И второй группы и с входом первого сомножителя умножителя, вход второго сомножителя которого соединен с выходом первого регистра, вход разрешения записи которого соединен с выходом первого элемента И, выход умножителя соединен с первыми входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ группы, вторые входы которых соединены с выходами элементов И второй группы, вторые входы элементов И второй группы соединены с выходом элемента ИЛИ вЂ” НЕ, первый вход которого соединен с выходом первого триггера и с информационным входом третьего триггера, второй вход элемента ИЛИ вЂ” НЕ соединен с выходом второго триггера, с вторыми входами элементов И первой группы и с информационным входом четвертого триггера, выходы элементов ИЛИ группы подключены к выходам первой, второй и третьей группы выходов операционного блока, выходы третьего и четвертого триггера являются соответственно (m+1)-м и (m+2)-м выходами первой группы операционного блока, синхровход которого соединен с вторыми входами первого и второго элементов И, с синхровходами первого, второго, третьего и четвертого триггеров.

3. Устройство по п. 1, отличающееся

35 первой группы операционного блока, выходы первого и второго элементов И соединены с входами разрешения записи соответственно второго и третьего регистров, выход третьего регистра соединен с первыми входами элементов И группы, вторые входы которых соединены с выходом третьего триггера и с информационным входом четвертого триггера, выход четвертого триггера подключен к (m+2)-му выходу первой группы операционного блока, (m+1) -й выхрд которого соединен с выходом второго триггера, информационный вход которого соединен с выходом первого триггера, синхровход операционного блока соединен с входом разрешения записи первого регистра, вторым входом первого и второго элементов

И и с синхровходами первого, второго, третьего и четвертого триггеров.

4. Устройство по п. 1, отличающееся тем, что i -й операционный блок (i= I, й1, j=2, и, i(j) содержит умножитель, сумматор, пять регистров, восемь триггеров, два элемента И и группу элементов И, причем m входов первой группы операционного блока соединены с информационным входом первого регистра, выход которого соединен с информационным входом второго регистра, выход которого соединен с информационными входами третьего и четвертого регистров, выходы которых соединены соответственно с первым входом умножителя и с первыми входами элементов И группы, (m+1) -й вход первой группы операционного блока соединен с информационным входом первого триггера, выход которого соединен с информационным входом второго триггера, выход которого соединен с первым входом первого элемента И и с информационным входом третьего триггера, выход которого соединен с информационным входом четвертого триггера, выход которого подключен к (гп+1)-му выходу первой группы операционного блока, (m+2)-й вход первой группы которого соединен с информационным входом пятого триггера, выход которого соединен с информационным входом шестого триггера, выход которого соединен с первым входом второго элемента И и с информационным входом седьмого триггера, выход которого соединен с вторыми входами элементов И группы и с информационным входом восьмого триггера, выход которого подключен к (m+2) -му выходу первой группы операционного блока, вторая группа входов которого соединена с информационным входом пятого регистра, выход которого соединен с второй группой выходов операционного блока и с вторым входом умножителя, выход которого соединен с первым входом сумматора, второй вход которого соединен с выходами элементов И группы, выход сумматора подключен к m выходам первой группы операционного блока, синхровход которого соединен с вторыми вхо1387013

24 юг 1 дами первого и второго элемента И и с входами разрешения записи первого, второго и пятого регистров, с синхровходами с первого по восьмой триггеров.

8)cF 61

12 f

2З )Ф зч з

1387013

22I

Фиг. Ф

1387013

ТаЮлаиа t

Составитель М. Силин

Редактор И. Шулла Техред И. Верес Корректор И.Муска

Заказ 1223/48 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раугиская наб., д. 4i5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4