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

(71) Киевский инсской авиации им.%44 итут инжен 60-летия С Я. Нэгорны видетельст 6 Р 7/38, 19 видетельст 06 Г 15/347 еров граждан й и А.А, Хлайелво СССР75.во СССР ится к вычислительачено для построеециализированных быть использовано нивэния и упрэвлетвиям над матрицаетение относ ке, предназн го основе сп в и может ии задач оц ихся к дейИзоб ной техн ния на е процессорапри решенния, сводящми. ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССРГОСПАТЕНТ СССР) 54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ57) Изобретение относится к вычислительной технике и предназначено для построеИзвестно устроиство для решения матриц, содержащее входной регистр, входы которого соединены с информационными входами устройства, четыре группы блоков суммирования и вычитания, блок управления, блок обращения чисел, блок деления 11, Обращение матрицы сводится к обращению одноГО Вектора-строки, который должен полность о характеризовать исходную матрицу.Наиболее 5 лизким по функциональному назначению и конструктивно является устройство для обращения матриц 2), содержащее информационные входы элементов ния на его основе специализированных процессоров для задач оценивания и управления, сводящихся к действиям над матрицами. Цель изобретения - повышение быстродействия при одновременном сокращении аппаратурных затрат за счет того, что устройство содержит блок управления, ключ выдачи, мультиплексор, вычислительный блок, блок памяти, блок памяти констант. Реализация обращения матрицы осуществляется на основе О-разложения по методу "цифра за цифрой", причем алгоритм преоб. разован к виду, удобному для параллельных вычислений, Устройство обладает высокой однородностью структуры, 1 з.п. ф-лы, 12 ил. матрицы, сумматоров константы, коммутатор, содержащий пять блоков мультиплексора, вычислитель, буферный блок памяти, ключ выдачи, блок памяти констант и блок управления. Элементы исходной матрицы а 1) образуют первые информационные входы сумматоров констант, выход первой константы блока памяти констант подключен к вторым входам сумматоров константы, выход и сумматоров константы и информационные входы элементов матрицы (=, и; )=1, и; ) Ф образуют первый информационный вход коммутатора, выход буферного блока памяти подключен к второму информационному входу коммутатора и к информационному входу ключа вь 1 дачи, третий и четвертый информационные входы коммутатора подключены к выходам втЬрой и третьей константы блока памяти констант, входы промежуточных результатов уменьшэемых, первых и вторых сомножителей45 50 55 вычислителя подключены к одноименным выходам коммутатора, вход кода управления и вход выбора которого подключены к одноименным выходам блока управления, выход выдачи результата которого подключен к входу стробирования информации ключа выдачи, выходы первой и второй константы блока памяти констант подключены к одноименным входам вычислителя соответственно, выход которого подключен к информационному входу буферного блока памяти, первый и второй входы записи которого подключены к прямому и инверсному выходам записи блока управления, вход константы которого подключен к выходу четвертой константы блока памяти констант. В данном устройстве для вычисления и-разрядной матрицы выполняется и шагов повторных вычислений, Для получения результата одного шага необходимо выполнить три операции умножения, две операции сложения и операцию нахождения обратной величины. При этом для коммутации используется большое количество мультиплексоров, До начала пошаговых вычислений выполняется операция сложения на п сумматорах константы.Недостатком устройства - прототипа является большое количество элементов и низкое быстродействие.Цель изобретения - повышение быстродействия при одновременном сокращении аппаратурных затрат.Цель достигается тем, что в предложенное устройство, содержащее блок управления, ключ выдачи и блок памяти, причем выход устройства соединен с выходом ключа выдачи, вход разрешения выдачи которого соединен с первым выходом блока управления, второй и третий выходы которого соединены соответственно с входами разрешения записи и чтения блока памяти, введены мультиплексор, вычислительный блок, блок памяти констант и умножитель. Информационный вход устройства подключен к первому информационному входу мультиплексора, второй информационный вход которого соединен с первым информационным входом умножителя и выходом блока памяти, информационный вход которого соединен с выходом мультиплексора, вход управления которого соединен с четвертым выходом блока управления, первый выход которого соединен с синхровходом умножителя, выход и второй информацион.ный вход которого соединены соответственно с информационным входом ключа выдачи и первым ввходом блока памяти констант, второй выход которого подключен к информационному входу блока управле 5 10 15 20 25 30 35 40 ния, первый, второй, третий и четвертый выходы мультиплексора соединены соответственно с первым, вторым, третьим и четвертым информационными входами вычислительного блока, пятый информационный вход и выход которого соединены соответственно с первым выходом блока памяти констант и информационным входом блока памяти.Изобретение обладает существенными отличиями по сравнению с известными техническими решениями, поскольку совокупность отличительных признаков с известными признаками и их взаимосвязь между собой позволяют повысить быстродействие устройства и упростить его конструкцию, что невозможно осуществить с помощью аналогов и прототипов.На фиг, 1 представлена функциональная схема устройства для обращения матриц; на фиг, 2 - функциональная схема мультиплексора; на фиг, 3 - функциональная схема вычислительного блока; на фиг. 4 - функциональная схема блока памяти; на фиг, 5 - функциональная схема умножителя; на фиг, 6 - функциональная схема блока управления; на фиг. 7 - функциональная схема блока, объединяющего узел вычисления обратной величины числа, первый умно- житель и группу умножителей; на фиг. 8 - функциональная схема второго умножителя; на фиг. 9 - функциональная схема группы сумматоров; на фиг, 10 - функционэльная схема формирователя сигнала выбора; на фиг, 11 - временная диаграмма работы блока управления; на фиг. 12 - таблица результатов вычислений на выходах блоков на каждом шаге вычислений. Устройство для обращения матриц (фиг.1) содержит первый информационный вход 1 элементов матрицы, мультиплексор 2, вычислительный блок 3, блок 4 памяти, умно- житель 5, ключ б выдачи, блок 7 памяти констант, блок управления 8, выход 9 злементов обращенной матрицы, второй информационный вход 10 мультиплексора 2 и вход умножителя 5, вход 11 ключа выдачи 6, вход 12 вычислительного блока 3 (вход 12.а узла вычисления обратной величины числа, вход 12.Ь умножителей руппы, вход 12.с второго умножителя, вход 12,0 сумматоров группы), шину 13 первой константы, выход 14 вычислительного блока 3, шину 15 второй константы, выход 16 формирователя сигнала выбора, прямой и инверсный входы 17 и 18 записи блока 4 памяти, вход 19 выдачи результата ключа б выдачи и синхровход умножителя 5, разрешающий инвертировать результат,-0,2 0 0,2 -1,3 0,5 -0,2 1,27 -0,335 0,067 10 15 20 25 30 35 40 а 11 а 12а 1. э 21 а 22 " а 2 п А= ап 1 алгаппв двоичном коде "1" на вход формирования Согласно алгоритму вычислительная схемаопределения А имеет вид;, Чп щп = 2; .Уп пппк=1 К=гиах (Ц)или для 1=1,2," и 45 50 55 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.В устройстве реализован алгоритм обращения матрицы на основе Ш-разложения по методу "цифра зэ цифрой". Пусть требуется обратить матрицу порядка п х,ф = хц) =0 (, )х = х)И - Чни 1 ц , ))Работу устройства можно пояснить на примере обращения произвольной матрицы третьего порядка вида Покажем, что обратная ей матрица Абудет вида Работа устройства начинается с того, что исходная. матрица А в виде последовательности ее элементов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. Период следования синхроимпульсов выбирается из условия полного завершения одного шага вычислений. На первом шаге вычислений с выхода счетчика 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 от10 15 20 25 30 35 40 45 50 55 элементы а 21, аз 1 а,1, на вход 12,с второго умножителя поступают элементы а ц, а 1 з,; а 1 п, на вход 12,б сумматоров группы поступают элементы аЯ=)=2,п).По входу 12,э узла вычисления обратнойвеличины числа элементы матрицы а, который для данного примера на первом шагеравен "1", преобразуется в обратную величину, поступает по входу 23 на первыйумножитель и умножается на "1", поступающую по шине 12 первой константы,По шине 24 выхода первого умножителячисло "-1" поступает на группу умножителей и умножается с числами5 бпоступающими по входу 12. Ь из мультиплексора 2, На первом шаге на шину 25 входавторого умножителя поступают числа- 5 - 6 -1где производится их взаимное перемножение с числами2 3На шину 26 входа сумматоров группы,поступает последовательность чисеЛ- 10 - 12 -2 - 15 - 18 - 3 - 5 - б - 1,из которых выбираются числа а 1-1-1 и складываются с числами аи (=2,п; )=2 у), поступающими по шине 12.б из мультиплексора 28 2 9 3,На выходе группы сумматоров на первом шаге формируется последовательностьчисел-2 -10 -2 -б -15 -3 -5 -б -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, Устройство для обращения матриц, содержащее блок управления, ключ выдачи и блок памяти, причем выход устройства соединен с вь 1 ходом ключа выдачи, вход разрешения выдачи которого соединен с первым выходом блока управления, второй и третий выходы которого соединены соответственно с входами разрешения записи и чтения блока памяти,.о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при одновременном Сокращении аппаоатурных затрат, устройство содержит мультиплексор, вычислительный блок, блок памяти констант и умножитель, причем информационный вход, устройства подключен к первому информационному входу мультиплексора. второй информационный вход которого соединен с первым информацион 1778762 10ным входом умножителя и выходом блока памяти, информационный вход которого соединен с выходом вычислительного блока,вход управления которого соединен с четвертым выходом блока управления, первый 5 выход которого соединен с синхровходом умножителя, выход и второй информационный вход которого соединены соответственно с информационным входом ключа выдачи и первым выходом блока памяти 10 констант, второй выход которого подключен к информационному входу блока управления, первый, второй, третий и четвертый выходы мультиплексора соединены соответственно с первым, вторым, третьим и 15 четвертым информационными входами вычислительного блока, пятый информационный вход и выход которого соединены соответственно с первым выходом блока памяти констант и информационным входом 20 блока памяти.2,Устройство поп.1, отл ич а ю щее- . с я тем, что вычислительный блок содержит узел вычисления обратной величины числа. три умножителя и группу умножителей. и ричем первый информационный вход вычислительного блока соединен с входом узла вычисления обратной величины числа, выход которого соединен с первым входом первого умножителя, второй вход и выход которого соединены соответственно с пятым информационным входом вычислительного блока и объединенным первым входом умножителей группывыходы которых подключены к разрядам первого входа второго умножителя, второй вход и выход которого соединены соответственно с третьим информационным входом вычислительногб блока и первым входом третьего умножителя, второй вход и выход которого соединены соответственно с четвертым информацион= ным входом вычислительного блока и его выходом, 1-й разряд второго информационного входа вычислительного блока (1=1,п, где и+1 в . порядок матрицы) подключен к второму входу -го умножителя группы,.; -0,2;-1,3 г 1,27;0;0,5:к г, 1 актор Т СССР оизводственн каз 419 ВНИИ-0,2;0,2;-0,%7; остввитель И.Жуковхред М,Моргентал Корректор Н ТУ Тираж Подписное Государственного комитета по изобретениям и открытиям и 113035, Москва, Ж, Раушская наб., 4/5атее некии комбинат "Патент", г. Улггород, ул, Гагарина, 101