Устройство для обращения матриц

 

Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных процессоров для задач оценивания и управления , сводящихся к действиям над матрицами. Цель изобретения - повышение быстродействия при одновременном сокращении аппаратурных затрат за счет того, что устройство содержит блок управления, ключ выдачи, мультиплексор, вычислительный блок, блок памяти, блок памяти констант. Реализация обращения матрицы осуществляется на основе Ш-разложения по методу цифра за цифрой, причем алгоритм преобразован к виду, удобному для параллельных вычислений. Устройство обладает высокой однородностью структуры 1 з п ф-лы, 12 ил.

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

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

P ЕСПУ БЛИК (я)5 G 06 F 15/347

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ 4

Н

И

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4815062/24 (22) 16,04.90 (46) 30.11.92. Бюл, ¹ 44 (71) Киевский институт инженеров гражданской авиации им. 60-летия СССР (72) И.А, Жуков, Л.Я. Нагорный и А.А, Хлайел (56) 1. Авторское свидетельство СССР

¹ 595726, кл. G 06 F 7/38, 1975.

2, Авторское свидетельство СССР

¹ 1211755, кл. G 06 F 15/347, 1984, (54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и предназначено для построе1

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

Известно устройство для решения матриц, содержащее входной регистр, входы ° которого соединены с информационными входами устройства, четыре группы блоков суммирования и вычитания, блок управления, блок обращения чисел, блок деления (11. Обращение матрицы сводится к обращению одноГО Ве ктора-строки, который должен полность о характеризовать исходную матрицу.

Наиболее близким по функциональному назначению и конструктивно является устройство для обращения матриц (21, содержащее информационные входы элементов. Ж 1778762 А> ния на его основе специализированных процессоров для задач оценивания и управления, сводящихся к действиям над матрицами. Цель изобретения — повышение быстродействия при одновременном сокращении аппаратурных затрат за счет того, что устройство содержит блок управления, ключ выдачи, мультиплексор, вычислительный блок, блок памяти, блок памяти констант.

Реализация обращения матрицы осуществляется на основе LU-разложения по методу

"цифра за цифрой", причем алгоритм преоб. разован к виду, удобному для параллельных вычислений, Устройство обладает высокой однородностью структуры, 1 з.п. ф-лы, 12 ил. матрицы, сумматоров константы, коммутатор, содержащий пять блоков мультиплексора, вычислитель, буферный блок памяти, ключ выдачи, блок памяти констант и блок управления. Элементы исходной матрицы

a;I образуют первые информационные входы сумматоров констант, выход первой константы блока памяти констант подключен к вторым входам сумматоров константы, выход и сумматоров константы и информационные входы элементов матрицы (I= T, и; )=1, и; 3 Ф j) образуют первый информационный вход коммутатора, выход буферного блока памяти подключен к второму информационному входу коммутатора и к информационному входу ключа выдачи, третий и четвертый информационные входы коммутатора подключены к выходам втОрой и третьей константы блока памяти констант, входы промежуточных результатов уменьшэемых, первых и вторых сомножителей

1778762

30

55 вычислителя подключены к одноименным выходам коммутатора, вход кода управления и вход выбора которого подключены к одноименным выходам блока управления, выход выдачи результата которого подключен к входу стробирования информации ключа выдачи, выходы первой и второй константы блока памяти констант подключены к одноименным входам вычислителя соответственно, выход которого подключен к информационному входу буферного блока памяти, первый и второй входы записи которого подключены к прямому и инверсному выходам записи блока управления, вход константы которого подключен к выходу четвертой константы блока памяти констант. В данном устройстве для вычисления и-разрядной матрицы выполняется и шагов повторных вычислений, Для получения результата одного шага необходимо выполнить три операции умножения, две операции сложения и операцию нахождения обратной величины. При этом для коммутации используется большое количество мультиплексоров. До начала пошаговых вычислений выполняется операция сложения на и сумматорах константы.

Недостатком устройства — прототипа является большое количество элементов и низкое быстродействие.

Цель изобретения — повышение быстродействия при одновременном сокращении аппаратурных затрат.

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

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

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

На фиг. 1 представлена функциональная схема устройства для обращения матриц; на фиг, 2 — функциональная схема мультиплексора; на фиг. 3 — функциональная схема вычислительного блока; на фиг. 4— функциональная схема блока памяти; на фиг, 5 — функциональная схема умножителя; на фиг, 6 — функциональная схема блока управления; на фиг. 7 — функциональная схема блока, объединяющего узел вычисления обратной величины числа, первый умножитель и группу умножителей; на фиг. 8— функциональная схема второго умножителя; на фиг. 9 — функциональная схема группы сумматоров; на фиг. 10 — функциональная схема формирователя сигнала выбора; на фиг, 11 — временная диаграмма работы блока управления; на фиг. 12 — таблица результатов вычислений на выходах блоков на каждом шаге вычислений.

Устройство для обращения матриц (фиг.

1) содержит первый информационный вход

1 элементов матрицы, мультиплексор 2, вычислительный блок 3, блок 4 памяти, умножитель 5, ключ 6 выдачи, блок 7 памяти констант, блок управления 8, выход 9 злементов обращенной матрицы, второй информационный вход 10 мультиплексора 2 и вход умножителя 5, вход 11 ключа выдачи 6, вход 12 вычислительного блока 3 (вход 12.а узла вычисления обратной величины числа, вход 12.b умножителей руппы, вход 12.с второго умножителя, вход 12,d сумматоров группы), шину 13 первой константы, выход 14 вычислительного блока 3, шину 15 второй константы, выход 16 формирователя сигнала выбора, прямой и инверсный входы

17 и 18 записи блока 4 памяти, вход 19 выдачи результата ключа 6 выдачи и синхровход умножителя 5, разрешающий инвертировать результат.

1778762

-0,2 0 0,2

-1,3 0.5 -0,2

1,27 -0,335 0,067

a11 312 ... а1, а21 а22 " э2п

А=

Эп1 ЭП2 ° ° ° Эпп в двоичном коде "1" на вход формирования

1 2 3

5 8 9

6 2 3

Мультиплексор 2 выполнен по схеме, представленной на фиг, 2 с использованием мультиплексоров 45.

Вычислительный блок 3 (фиг. 3) содержит узел 46 вычисления обратной величины числа, первый умножитель и группу умножителей, объединенных в блок 20, второй умножитель 21, группу сумматоров 22, вход

23 — первый вход первого умножителя, вход

24 — первый вход умножителей группы, вход

25 — первый вход второго умножителя, вход

26 — первый вход сумматоров группы. Первый, второй умножители и группа умножителей содержат умножители 47, группа сумматоров содержит сумматоры 48.Блок памяти 4 (фиг. 4) содержит первый и второй регистры 27, Блок управления 8 (фиг. 6) содержит генератор 28 тактовых импульгов, первый одновибратор 29, триггер 30.1 запуска, триггер 30.2 выдачи, триггер 31 состояния, элемент И 32, элемент НЕ 33, второй одновибратор 34, счетчик 35, схема 36 сравнения и формирователь 37 сигнала выбора, вход

38 запуска блока 8 и устройства, выход 39 генератора 28, информационный вход 40 триггера 31, первый и второй входы 41, 42 элемента И 32, выход 43 схемы 36, счетный вход 44 счетчика 35, выход 51 счетчика 35, Формирователь 37 сигнала выбора (фиг. 10) содержит элемент НЕ 49 и элемент

И вЂ” НЕ 50.

В устройстве реализован алгоритм обращения матрицы на основе Ш-разложения по методу "цифра зэ цифрой". Пусть требуется обратить матрицу порядка и

Согласно алгоритму вычислительная схема определения А имеет вид;

-1 -1 -1

A =U L = VM=(XIJ)=

ll, Vlk mkj = Я На mkI

k=max {Ц} или для 1=1,2,... и х () = хц"=0 (I,J t)l

>IIJ = хл — Ч1тЦ (I, J — t):

Работу устройства можно пояснить на примере обращения произвольной матрицы третьего порядка вида

Покажем, что обратная ей матрица А будет вида

Работа устройства начинается с того, что исходная.матрица А в виде последовательности ее элементов

1 5 6 2 8 2 3 9 3 поступает нэ первый информационный вход

1 мультиплексора 2. По сигналу на вход 38 внешнего запуска (фиг. 11) блока 8 управления счетчик 35 сбрасывается в нулевое состояние, переводится в нулевое состояние триггер 30.2 выдачи, закрывая ключ 6 выдачи и умножитель 5, который запрещает вывод информации из блока 4 памяти во время вычислений, а также переводится в единичное состояние триггер 30,1 запуска, обеспечивая появления "1" на информационном входе триггера 31 состояния (фиг. 11). Перевод триггера 31 в единичное состояние происходит в момент появления на его счетном входе тактового импульса от генератора 28 тактовых импульсов. С выхода триггера 31 состояния "1" поступает на первый вход элемента И 32, обеспечивая происхождение синхроимпульсов, поступающих на второй вход от первого одновибратора 29, С выхода элемента И 32 синхроимпульсы поступают на вход второго одновибратора 34, формирующего импульсы по заднему фронту синхроимпульсов, которые являются счетными импульсами счетчика 35. Период следования синхроимпульсов выбирается из условия полного завершения одного шага вычислений. ka первом шаге вычислений с выхода счетчика 35 поступает

37 сигнала выбора, в соответствии с законом работы которого (фиг, 10) на его выходе на первом шаге формируется "0". На последующих шагах на выходе 16 присутствует

"1". Выход 16 является управляющим для мультиплексора 2, поэтому в соответствии с законом работы на его выход передается последовательность чисел с шины 1 при сигнале на выходе 16, равном "0" (первый шаг вычислений), или последовательность чисел с шины 10 при сигнале на выходе 16, равном

"1" (фиг. 2), т.е. на первом шаге на выходе мультиплексора 2 будет сформирована по следовательность чисел

1 5 6 2 8 2 3 9 3, которая распределяется следующим образом: на вход 12.а узла вычисления обратной величины числа поступает элемент а11, нэ вход 12.Ь умножителей группы поступэ1от

1778762

35

50

55 элементы аг, аз, ..., a», на вход 12,с второго умножителя поступают элементы э 12, э13, ...; 81n, на вход 12.б сумматоров группы поступают элементы ai (i=j=2,n).

По входу12,э узла вычисления обратной величины числа элементы матрицы а„„, который для данного примера на первом шаге равен "1", преобразуется в обратную величину, поступает по входу 23 на первый умножитель и умножается на "1", поступающую по шине 12 первой константы, По шине 24 выхода первого умножителя число "-1" поступает на группу умножителей и умножается с числами

5 б поступающими по входу 12. Ь из мультиплексора 2. На первом шаге на шину 25 входа

atoporo умножителя поступают числа — 5 — 6 -1 где производится их взаимное перемножение с числами

2 3

На шину 26 входа сумматоров группы, поступает последовательность чисеЛ вЂ” 10 — 12 -2 — 15 — 18 -3 — 5 — б — 1, из которых выбираются числа а1->, -1 и складываются с числами аи (i=2,п; )=2у), поступающими по шине 12.d из мультиплексора 2

8 2 9 3.

На выходе группы сумматоров на первом шаге формируется последовательность чисел

-2 -10 -2 -6 -15 -3 -5 -6 -1, которая по шине. 14 поступает на входы первого регистра 27 блока 4 памяти (фиг. 4), который служит для развязки между собой шагов вычислений и устранения эффекта

"гонок". Во время вычисления на каком-либо шаге на первый регистр 27 по выходу 17 поступает управляющий сигнал "0" с выхода элемента И 32 блока управления 8 (фиг, 5), разрешающий запись информации в данный регистр, в то время как по выходу 18 на второй регистр 27 поступает "1" с выхода элемента И вЂ” НЕ 33 блока управления 8, разрешая чтение информации из этого регистра. Период следования синхроимпульсов с выхода первого одновибратора 29 выбирается таким образом, чтобы за время существования низкого перепада напряжения на

его выходе полностью завершилось вычисление на данном шаге и запись результата в первый регистр 27 (фиг, 11). При появле нии высокого потенциала на выходе элемента И 32 на первый регистр 27 поступает "1", а на второй регистр — "0", т.е. происходит перезапись-информации с первого регистра на второй. При появлении следующего синхроимпульса выдается разрешение на чтение результата из второго регистра 27 и на запись результата следующего шага вычисления в первый регистр 27, Количество шагов вычислений равно порядку обращаемой матрицы (п), Результаты нэ выходах отдельных блоках для каждого шага приведены в таблице (фиг, 12).

На каждом шаге вычисления в схеме сравнения 36 происходит сравнение номера шага вычисления, поступающего с выхода счетчика 35 и числа "4" (в общем случае

"и+1"), поступающего по шине третьей константы 51 из блока 7 памяти констант. По окончании последнего третьего шага вычисления во второй регистр 27, блока 4 памяти записывается последовательность чисел

0.2 1,3 — 1,27 0 — 0,5 0,335 — 0,2 0,2 — 0,067.

При появлении следующего четвертого синхроимпульса на выходе элемента И 32 блока 8 управления на управляющий вход второго регистра 27 блока 4 памяти поступает сигнал "1" разрешения чтения. Номер четвертого синхроимпульса поступает также на вход схемы сравнения 36, в результате чего на ее выходе формируется упрэвляющий импульс, который переводит триггер

30.2 в единичное состояние, тем самым разрешая открытие ключа б выдачи вместе с умножителем 5 (инвертирующим результат) и, соответственно, вывод результата, а также перебрасывает в нулевое состояние триггеры 30.1 и 31, что соответствует запирэнию блока 8 управления и окончанию вычисления, Устройство решает задачу обращения для матриц произвольной размерности, Экспериментальные исследования устройства для обращения матриц показали, что по сравнению с устройством аналогичного назначения,(прототип) оно упрощено конструктивно и быстродействие повышается в 1.5 раза, Формула изобретения

1, Устройство для обращения матриц, содержащее блок управления, ключ выдачи и блок памяти, причем выход устройства соединен с выходом ключа выдачи, вход разрешения выдачи которого соединен с первым выходом блока управления, второй и третий выходы которого соединены соответственно с входами разрешения записи и чтения блока памяти,.о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при одновременном Сокращении аппаратурных затрат, устройство содержит мультиплексор, вычислительный блок, блок памяти констант и умножитель, причем информационный вход, устройства подключен к первому информационному входу мультиплексора. второй информационный вход которого соединен с первым информацион1778762

10 ным входом умножителя и выходом блока памяти, информационный вход которого соединен с выходом вычислительного блока, „ вход управления которого соединен с четвертым выходом блока управления, первый 5 выход которого соединен с синхровходом умножителя, выход и второй информационный вход которого соединены соответственно с информационным входом ключа выдачи и первым выходом блока памяти 10 констант, второй выход которого подключен к информационному входу блока управления, первый, второй, третий и четвертый выходы мультиплексора соединены соответственно с первым, вторым. третьим и 15 четвертым информационными входами вычислительного блока, пятый информационный вход и выход которого соединены соответственно с первым выходом блока памяти констант и информационным входом 20 блока памяти.

2,Устройство по п.1, отл и ч а ю ще е- . с я тем, что вычислительный блок содержит узел вычисления обратной величины числа. три умножителя и группу умножителей. и ричем первый информационный вход вычислительного блока соединен с входом узла вычисления обратной величины числа, выход которого соединен с первым входом первого умножителя, второй вход и выход которого соединены соответственно с пятым информационным входом вычислительного блока и объединенным первым входом умножителей группы„выходы которых подключены к разрядам первого входа второго умножителя, второй вход и выход которого соединены соответственно с третьим информационным входом вычислительного блока и первым входом третьего умножителя, второй вход и выход которого соединены соответственно с четвертым информацион= ным входом вычислительного блока и его выходом, i-й разряд второго информационного входа вычислительного блока (i=1,п, где n+1 †. порядок матрицы) подключен к второму входу i-го умножителя группы..

1778762

t2a f28

1778762

l778762

1778762

Фгга. 10.

Фггз. Е.

1; 5; 6; 2; 8; 2; 3; 9; 3; .-2;-ХО;-2;-б;-15;-3;-5;-б;-I - 15; 3;Д19; 4; -2.5

:-5;-I;05 — --«+ — -- - — ---- — ---- —--5;-I;05; -0,2; 0,2; -0,067; з

-5; -6; -I;

-IO;-12;-2;-15;-18;-3;-5; : 30; 6;-3;25;5:-2,5;-5;-1;

-6; -I; : О 5;

-2;-10:-2;-б;-15;-3;-5;-6; : 15;3;з;19;4:-2.5:-5;-I;0,5;: 0.2;1.3:-1.27;О:

-Т; : : -О, 5; 0.335;

-0,2;0,2;-0,%7;

-2;-IO;-2;-6;-IS;-3;-5;-6; : 15;3;-3;19;4;-2,5;-5;-I:0,5;: 0,2:1,3;-1,27;О;-0,5;

: -0,2,-1,3;1.27;0 0,5;

: -0,335; 0,2;-0,2;0,067;

-0,2;-1,3;1,27;0;0,5:

Фяр. 12

Корректор Н.Тупица

Редактор

Заказ 4194 Тираж Подписное

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

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издателвскии комбинат "Патент", г. Улггород, ул.Гагарина, 101

Составитель И Жуков

Техред M,Mîðãåíòàë

-3,8;3,8;-1;27:I;

-I,0,335,-О,2, 0,2, -О,C67;