Однородная вычислительная структура Советский патент 1986 года по МПК G06F15/324 

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

Цель изобретения -- увеличение быстродействия.

На фиг. 1 приведена схема одно- родной вычислительной структуры для , когда число п треугольных матриц вычислительных ячеек равно четырем ()j на фиг. 2 - схема вычислительных ячеекJ начиная с второй строки каждой треугольной матрицы устройства} на фиг. 3 - введена схема вычислительных ячеек цервой строки, начиная с второго столбца каждой треугольной матрицы, представляющие собой параллельный делительi на фиг, 4 - схема вычислительных ячеек первой строки первого столбца каждой треугольной матрицы устройства5пред- ставляющие собой параллельный корне- извлекатель.

Однородная вычислительная структура содержит п треугольных матриц вычислительных ячеек, каждая треугольная матрица содержит вычисли- тельную ячейку 1, представляющую собой параллельный корнеизвлекатель, треугольные матрицы, начиная с первой по (п-1)-ю, содержат вычисли- тельнутю ячейку 2, представляющую со- бой параллельный делитель, вычислительные ячейки 3, информационные входы 4, выходы 5 результата устройства, параллельный умножитель 6, параллельный сумматор 7, одноразрядные сумматоры 8, сумматоры 9 по модулю два, выходы 10 параллельного делителя, вторые II и первые 12 входы параллельного делителя, элементы НЕ IS элемент ИЛИ 14, выходы 15 корнеиэ- влекателя, входы 6 корнеизвлекате- ля.

Работа однородной вычислительной структуры для вычисления элементов нижней треугольной матрицы L, формируемой из элементов симметричной матрицы А как , где L - транспонированная по отношению к L матрица, осуществляется следующим образом.

Вычисление элементов матрицы L реализуется методом квадратного кор42

я по следующим рек.уррентнь1М выраениям

I J -- Гч I ) i, -ча,, , i,g (.Р I; ,

i-f

, ,

brj- i-iii.. М----

(I : i i п, i S) ,

где 1,-s - элементы матрицы L; а... элементы матрицы А,

Ь

Для выражения 1„, 1,д, I,-;, Ijg в развернутом виде при ,2,3,4 будут иметь вид

, I -Г: , 1 а1г . , at , 1- J-,,,, , i,2 - (з

1 21 . 1.,

, -7 I -JT -1 . 1 - Sl-Ciisil - . - -1Г« « 12 I

I .

-2г

т-ч I ,1я ,. , SlCillitiiiail

--

АЭЭ

i .В соответствии с развернутым представлением при ,2,3,4, организацию параллельного вычисления элементов L,- можно представить в вие п групп уравнений. При первая группа уравнений имеет вид

1 ils 1 . I §2 . J-,, л/а,, т I -Г5

1 . i,

.(О

If,

гг г

я -1 1 r я -1 I « -14 i 1 1э - эз

,., 4 r l4 « 44

Вторая группа уравнений имеет вид (1 , М

1 :Jj . J ilL . 1 - ill

- - - 9 ЭЯI

гг 22 г i

11

li

24 1,, i 1 .

i г 25 S

.i2,Третья и четвертая группы уравнений имеют вид

1 - . I - ill .

Э 33 1

1

44

И соответственно

v.

Группы уравнений являются основой доя определения элементов Ц с помощью операций деления и извлечения корня.

Частное X от деления делимого Z на делитель Y реализуется по , нию представленному в разрядной форме г- Х Д, где ..Л ; Z....f; ...О - разрядные векторы, представляющие собой разрядные изображения X, Z и О соответственно.

У 1 1

У -У Ъ г I У У У разрядная матрица,

у у представляющая собой изображение делителя

Y при .

Процесс определения k-ro (, 2,..,,n) разряда искомого вектора X реализуется на основании зависимости вида

. I

10

где f

(««)

, . при г, 1;

n

при I 0,

--значение переноса из та шего разряда вектора Z определяемого по выражен

:(i:

z -Ye

м.

G

Ш 2 12

е«

- величина,, принчение-к -()

J(x)- 5 при f П.

}1ри , ,.

В качестве примера рассмотрим вычисление выражения Z/Y, где Y «0,96875, ,4296875. Запишем Y Z, X в разрядной форме

Y°10ir, Z OinillO,- Х 1010;

k i zj oiioi;

Yrf 10101 ;

(гТ

Z р0010-.

Nfl)

00101; Y M01015

z noiOj

V(4)

00000-, YC 1010U

Vro

10101;

Ye ; oioir, -, .

Z 00000; z ilOlOl,

Таким образом, решение равно Х 1010-. (,625).

Параллельный корнеизвлекатель работает следующим образом. Старший разряд X искомого вектора X зависи1251104

мости видя определяется новании выражения, 1 . г V Y . ,

i«

Далее каждый последующий разряд ,2,.,.,п искомого вектора X определяется по выражению

CIM)

-U

при

при ,

где f

(ot)

- значение переноса нз старшего разряда вектора Y , определяемого на основании выражения

,

где -.величина, принимающая 3jja- чения

е4

с 2при fJ;M; при f 0,

5

0

5

Когда

V(,) V,,l v.-«

t

Векторы

... xV-Hb x7 dxpl)

,;-x 4xx4i 1)-, r (i ,,. xi 1)4

в качестве примера рассмотрим вычисление, выражения -{Y , где 0,4306640625. В разрядной форме У(0110111001) и Х(10101),, старший разряд 1.

(OIIO) ; .Y (ign.i/

Y (OOIOIO)

(ОИО) ; /F /E (01011); №(101011); ,„ (1111); Y (00010) ; Y (H

(H0101)

to

L(

0

(ч 4 Д (1010101);

7,х % (01010П) ;

Y(0000000) (,65625).

X

Однородная вычислительная структура работает следующим образом.Наинфор- .мационные входы 4,,,4,,4,,,4,ячеек 1,, Вой строки первой матрицы подаготся соот- ветственно значения а,,, а,,,,на формационные входы 4j,4j ,4j ячеек 3, второй строки первой матрицы подаются исходные значения а , а,а,далее на входы 4,4д, ячеек 3,третьей строки первой матрицы подаются значения а ,а .,на вход .4 ячейки 3 последней строки первой матрицы подается значение а После этого в схеме устройства протекает переходной процесс, по оконч ании которого на выходе ячейки 1( первой строки первой матрицы образуется значение 1,, элемента искомой матрииьГ Lj которое поступает на выход 5„ и на входы ячеек 2 первой строки первой матрицы, В ячейках 2, первой строки первой матрицы образуются зна чения элементов первой строки l, I,, искомой матрицы L, которые поступают соответственно ка выходы 5,, 5,,,5,4, на входы ячеек 3 столбца первой матрицы и входы ячеек 3., вто- рой,третьей и четвертой строк первой матрицы. В ячейках 3, второй ..третьей и четвертой строк первой матрицы образуются значения: 1

11 3

гз

i f f- }

Г (вторая строка) , 1 (третья

it )

строка), (четвертая строка). Значения . аз, Ц поступают на входы ячеек 1,, .;, первой строки вто СО /1)

рой матрицы. Значения Ц

,(0

4

поступают на входы ячеек 3 вто- рой строки и 3 третьей строки второй матрицы. На выходах ячеек 1 ,, 2 - первой строки второй матрицы образуются значения элементов l j yз 1 второй строки искомой матрицыэ которые поступают на выходы Sj ) Sj и на соответствующие входы ячеек Ъ второй и третьей строк второй матрицы. На выходах ячеек 3„ второй и

Ct

третьей строк второй матрицы образу-

. (г) , (г; ются значения 1,, , Ц4 (вторая строка) и 1Д (третья строка). Значения Чэ 4 поступают на входы ячеек L, 2 первой строки третьей матрицы, а значение 144. на вход ячейки Зз второй строки третьей матрицы, На выходах ячеек Ц, 2 первой строки третьей матрицы образуются элементы Ij, Ц третьей строки искомой матрицы, которые подаются на выходы 5.j, 5.4, и на соответствуюпще входы ячеек 3 последующих строк третьей матрицы В ячейке 3 второй строки третьей матрицы формируется значение , которое подается на вход ячейки 1 первой строки четвертой матрщ ;ы, в которой образуется значение 1 последней строки Матрицы L., которое поступает на выход 54, Управление работой однородной вычислительной структуры осуществляется с помощью синхросигналов, поступающих На. все вычислительные ячейки.

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

ние элементов матрицы L и сбответст венно представления происходит за время переходного процесса в схеме. Это позволяет использовать однородную вычислительную структуру в качестве спецпроцессора для организации вычислительного процесса в реальном масштабе времени.

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

Однородная вычислительная структура, содержащая первую верхнюю треугольную матрицу из п(п+1)/2 вычислительных ячеек, отличающаяся тем, что, с целью повьппе- ния быстродействия, в нее введены с второй по п-ю треугольные матрицы вычислительных ячеек, первые информационные входы вычислительных ячеек первой треугольной матрицы подключены к информационным входам устройства, первые информационные входы вычислительных, ячеек i-й строки j-ro столбца j -и треугольной матрицы (,,.,,n; ,2,,,,,n-m-i+2) подключены к выходам вычислительной ячейки i-й строки j-ro столбца (т-1)-й треугольной матрицы, выход вычислительной ячейки первой строки первого столбца г-й (...,п-1) треугольной-матрицы подключен к йто- рым информационным входам вычислительных ячеек первой строки с второго по ()-й столбец г-й треугольной матри1Цз1, выходы вычислительных ячеек первой строки 1-го (1 2,.,.,n-k) столбца k-й треугольной матрицы подключены к вторым информационным входам вычислительных ячеек столбцов с (l-l)-ro по первый соответственно строк с второй по (n-k)-ю и к вторым информационным входам ячеек строки k-треугольной матри- цы, выход вычислительной ячейки (n-k+l)-ro столбца первой строки k-й треугольной матрицы подключен к третьим информационным входам вычислительных ячеек (n-k-iH-2)-ro столбца с второй по (n-k)-ю строк и к второму информационному входу вычислительной ячейки первого столбца поспедней строки k-й треугольной матрицы, выходы вычислительных ячб- ек первых строк треугольных матриц подключены К выходам результата уст ройства, при этом вычислительные ячейкиJ, начиная с второй строки каж

7

дои треугольной -матрицы, содержат суммат ор и умножитель, первьш и второй входы умножителя подключены со ответственно к второму и третьему информационным входам вычислитель- ных ячеек, начиная с второй строки каждой треугольной матрицы, первый . и ВТО 1ОЙ входы сумматора подключены соответственно к выходу умйожителя и к первому информационному входу вычислительной ячейки, начиная с второй строки каждой треугольной матрицы, выход сумматора подключен к выходу вычислительной ячейки, начиная с второй строки каждой тре- угольной матрицы, причем вычислительные ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, содержат N групп (где N - разрядность поступающих операндов) по N+1 сумматоров и N групп по N сумматоров по модулю два, с первого по N-Й разряды первого входа вычислительной ячейки первой строки, начиная с второго столбца каждой тре- угольной Матрицы, являются входами делимого и подключены к первым входам сумматоров соответственно с первого по N-й первой группы, с (N+l)-r по 2N-1 разряды первого входа вычис- лительной ячейки первой строки, начиная с второго столбца каждой треугольной -матрицы, подключены также к третьим входам (N+l)-x сумматоров, групп с первой по N-ю, вторые входы/ 9-го разряда (-), o«.,N) второго входа вычислительной ячейки первой строки, начиная с второго столбца каждой треугольной матрицы, являются входами делителя и подключены к- первым входам - -го сумматора по мрду лю два групп с первой по N-ю, выход

5-го сумматора по модулю два р-и группы (jU,...,N) подключен к второму входу (|Ч + 1)-го сумматора aj-и rpyn пы, второй вход первого сумматора первые входы (N-t-l)-x сумматоров первой группы, в торые входы сумматоров по модулю два первой группы подключены к шине единичного сигнала уст- ройства, выхс5д переноса (9 + 1)-го сумматора jU -и группы подключен к третьему входу -го сумматора щ-и группы, выходы переноса первых сумматоров f-й группы (,...,N-1) подклю- чены соответственно к вторым входам первых сумматоров, первым входам (N+l)-x сумматоров и к вторым входам

0

1

5

1-04-

сумматоров по модулю два (+1)-й группы, выход s-ro (, .« , ,N-f О сумматора f-й группы подключен к первому входу (s-l)-ro сумматора (f+ + 1)-й группы, выходы переносов первых сумматоров групп с первой по подключены к выходам вычислительных ячеек первой строки, начиная с второго столбца каждой треугольной матрицы, причем вычислительные ячейки

первой строки первого столбца каждой треугольной матрицы содержат элемент ИЛИ, N групп сумматоров, при этом р-я (,...,N) группа сумматоров Содержит р+2 сумматора, N-1 группу сум шторов. по модулю два, при этом .q-я группа (,...,N-1) суммат оров по модулю два содержит q сумматоров по модулю два, N элементов НЕ, первый разряд входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключен JK первому входу элемента ИЛИ и к первому входу первого сумматора первой группы, второй разряд входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключен к второму входу элемента РШИ и к BTopoivjy входу второго сумматора первой группы, (2р+1)-е разряды входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключены к первым входим последнего сумматора р-й группы, (2р+2)-е разряды входа вычислительной ячейки первой строки первого столбца каждой треугольной матрицы подключены к вторым входам последнего сумматора р-й группы И к входу (р+1)-го элемента- НЕ, выход элемента ИЛИ подключен к входу первого элемента НЕ и к первым входам первых сумматоров по модулю два групп:, выход переноса первого сумматора р-й группы подключен к первому входу первого сумматора(р+1)-и группы, к второму входу сумматоров по модулю два р-й грутгпы, к первому входу последнего сумматора по модулю два (р+О-й группы и к первому входу второго сумматора по модулю два третьей группы, третий вход второго сумматора и третьи входы последних сумматоров групп подключены к шине нулевого- потенциала устройстваS выход первого элемента НЕ подключен ic второму входу .первого сумматора первой группы.

выходы переноса (р- -2)-х сумматоров р-й группы подключены к первым входам (Р+О-Х сумматоров р-й группы, выходы переноса v-x сумматоров (,,,.р+1) р-й группы подключены к третьим входам (v-)-x сумматоров, выходы U-X сумматоров (,.,.,р+2) р-й группы подключены к вторым входам (u-l)-x сумматоров ()-й группы, выходы t-x элементов НЕ (,,.

251104 10

р) подключены к вторым входам (p-t- -t-l)x сумматоров г{зуппы$ выходы gtix сумматоров по модулю два (, q-l) q-й группы подключены к пер 5 вым входам (g+l)-x сумматоров (q+l)й группы, выходы переноса первых сум-- маторов групп подключены к выходам вычислительной ячейки первой строки первого столбца каждой треуголь- 10 ной матрицы.

ff,

тз

Изобретение относится к области вычислительной техники и может быть исЛользовано для оперативного разложения квадратной симметричной матрицы на две треугольные, решения систем алгебраических уравнений, вычисления определителей матриц. Цель изобретения - увеличение быстродействия. Устройство содержит п треугольных матриц вычислительных ячеек. Однофазная структура имеет параллельную организацию5 благодаря чему время решения равно задержке сигнала между входом и выходом.структуры, 4 ил. § (Л