Устройство для стохастических вычислений

 

О П И с А Н И Е (ii)744527

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистический

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву 208340 (22) Заявлено 15.12.77 (21) 2556186/18-24 с присоединением заявки № (51) М. Кл.

G 06F 1/02

G 06F 15/36 (43) Опубликовано 30.06.80. Бюллетень № 24 (53) УДК 681.325 (088,8) по делам изобретений и открытий (45) Дата опубликования описания 30.06.80 (72) Авторы изобретения (71) Заявитель

В. С. Гладкий и Л. Б. Овсянникова

Московский ордена Трудового Красного Знамени институт нефтехимической и газовой промышленности им. М. М. Губкина (54) УСТРОЙСТВО ДЛЯ СТОХАСТИЧЕСКИХ ВЪ|ЧИСЛЕНИЙ

Государственный комитет (23) Приоритет

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

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

В основу работы известного устройства, как и в основу предлагаемого устройства положен принцип построения и статистического испытания последовательной дискретной марковской цепи, моделируемой по определенным правилам согласно заданным матрицам, над которыми оно осуществляет операции умножения и возведения в степень. Однако схемное решение известного устройства приводит к тому, что время решения велико и пропорционально n4 (n— размерность обрабатываемых матриц) .

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

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

Поставленная цель достигается тем, что

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

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

20 входов дополнительного блока памяти соответственно, выход которого соединен с первой группой входов блока суммирования, вторая группа входов которого подключена к выходу коммутатора, выходы блока сум25 мирования соединены со входами блока деления на число испытаний соответственно, вторая группа входов дополнительного блока памяти и третья группа входов блока суммирования подключены к выходу блока

30 управления.

744527

На фиг. 1 изображена блок-схема предлагаемого устройства; па фпг. 2 — пример выполнения блока управления.

Устройство содержит блок 1 ввода-вывода данных, выходы которого соединены со входами блока 2 памяти, а входы — с выходами блока 3 задаппя режима работы и блока 4 управления, выходы которого соединены со Bxoj3,i AIII Bccx ocT2 il llblx блоков, управ;1яемый BCpOIITIIOCTIIblll IipC06pB3033тель (блок 5), вход которого coeplIIICII с выходом блока 2 памяти, а выходы — со гходами блока 4 управления и со входамп блока G памяти вектора свободных члс;:1ов, выходы которого соединены со ",õîäàìè блока 7 суммирования, выходы которого соединены со входами блока 8 деления па число испытаний, выход которого соединен со входом блока 2 памяти, выходы которого соединены со входами коммутатора, другие входы которого соединены с выходамп блока 5, а выход — со входами блока 7.

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

Блок управления (фиг. 2) содерж11т счетчик номеров исходных строк матриць1, счетчик числа испытаний, цепи синхронизации, которые реализуют заданную последовательность работы остальных блоков устройства.

После запуска устройства тактовые импульсы поступают в блок управления. Первый импульс переводит регистр сдвига блока в; импульс, соответствующий этому состоянн.ю регистра сдвига, возбуждает первую строку матрицы и одновременно переводит триггер Òç в состояние «1». Прн этом открывается вентиль и очередной тактовый импульс поступает в

1,п-полюсник (блок 5). 1,п-полюсник отрабатывает. Сигнал, возникающий на одном из его выходов, поступает в блок управления, дешифрируется и возбуждает соответствующую строку матрицы о в блоке памяти. Описанная процедура повторяется до попадания процесса в поглощающее состояние, что определяется появлением сигнала на шине а. Длительность процесса блуждания может быть также ограничена наперед заданным числом переходов цепи. Сигнал попадания процесса в поглощающее состояние устанавливает регистр сдвига и триггер Т в положение. «О» и поступает па счетчик, в котором фиксируется факт проведения первого испытания. После Ж пспы5

65 таний импульс переполнения счетчика переключает триггер Т> в положение «1», чем фиксируется факт вычисления одной строки матрицы, и возбуждает первый элемент И блока 9. Описанный процесс повторяется до переполнения счетчика числа строк, импульс переполнения которого останавливает вычислительный цикл.

Коммутатор состоит из дешифратора и

n — 1 элементов И. Блок 4 управления отмечает вычисленные строки обратной матрицы возбуждением соответствующего элемента И блока 9 (если вычислена первая строка, то возбуждается первый элемент И и т. д.), Второй сигнал на каждый из элементов И поступает с выхода 1, и-полюсника. Третий сигнал на каждый элемент И поступает из блока памяти. При одновременном появлении двух сигналов (с 1, и-полюсника и блока управления) элемент И пропускает третий сигнал (с блока -памяти), который через дешифратор подается»а сумматоры блока 7, чем реализуется обратная связь по решению, существенно увеличивающая быстродействие устройства.

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

В блок 2 памяти через блок 1 вводятся исходные данные, образуемые пз матрицы

В,,1, 1:„1, А,1„1, 1де Ап — ь n — 1 обращаемая матрица коэффициентов системы алгебраических уравнений (матрица В дополняется столбиком компонент вектора поглощения, элементы которого определяются как b,, л --1

=1 —, " а;,). Таким образом, матрица В

j=1 есть полная стохастическая матрица, абсолютные значения элементов по строкам которой образуют дискретные распределения вероятностей полной группы событий. В блоке 2 указанные распределения записываются в виде функции распределения (F;).

В блок б заносятся единицы или координаты вектора 1 . При возбуждении блоком 4 адреса i (вычисляемой строки обратной матрицы) в блоке 5 считываются значения узловых точек F;. После срабатывания блока 5 на его одном из выходов появляется сигнал. Если это не сигнал попадания в поглощающее состояние (выход n), то он включает соответствующий сумматор блока

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

4, который выбирает из ОЗУ строку матрицы с номером, равным номеру выхода блока 5, блок 5 срабатывает, и описанный процесс повторяется до тех пор, пока не появится сигнал на и выходе блока 4, что означает, что траектория блуждания закоп744527 чена в поглощающем состоянии. Число таких траекторий выбирается исходя из заданной точности вычислений, заносится в счетчик блока 4 (фиг. 2). После проведения У траекторий (испытаний) блок 4 подает сигнал на блок 8 деления, по которому суммы, накопленные на сумматорах блока 7, поступают в блок 8, где делятся на число траекторий N, и полученные таким образом приближенные значения i-ной строки обратной матрицы записываются в ОЗУ на место -ной строки исходной матрицы.

Кроме этого, блок 4 возбуждает -ный элемент И блока управления обратной связью, отмечая факт вычисления i-ной строки исходной матрицы. В дальнейшем i-ная строка в вычислениях выступает как поглощающая. В блоке 9 идет контроль: не перешла ли траектория в состояние, соответствующее уже вычисленной строке. При этом в блоке 9 сигнал с выхода 1, и-полюсника (блока 5) дешифрируется и поступает на соответствующий элемент И. Если этот элемент И был уже возбужден блоком 4 (например, элемент И;, это означает, что траектория попала в поглощающее состояние), то сигнал с выхода элемента И,+>, включает обратную связь и в блок 7 суммирования на соответствующие сумматоры поступают значения i + k строки обратной матрицы. Введение указанной обратной связи резко сокращает траекторию блуждания и в связи с этим сокращается общее время решения задачи.

Описанный процесс вычислений повторяется при вычислении всех оставшихся строк обратной матрицы.

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

«1», элементы вычисленной обратной матрицы выводятся блоком 1.

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

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

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

Устройство для стохастических вычислений по авт. св. № 208340, отл и ч а ю щ е е20 ся тем, что, с целью повышения быстродействия устройства, оно содержит дополнительный блок памяти, блок суммирования и коммутатор, первая группа входов которого подключена к выходу блока управ25 ления, вторая группа входов коммутатора подключена к группе выходов блока памяти, а третья группа входов коммутатора соединена с выходами управляемого вероятностного преобразователя соответственно, З выходы которого подключены к первой группе входов дополнительного блока памяти соответственно, выход которого соединен с первой группой входов блока суммирования, вторая группа входов которого под35 ключена к выходу коммутатора, выходы блока суммирования соединены со входами блока деления соответственно, вторая группа входов дополнительного блока памяти и третья группа входов блока суммирования

40 подключены к выходу блока управления.

744527

VP. и и

3« и с блошку (Пцг. 2

Составитель А. Карасов

Техред А, Камышникова

Корректор Т, Трушкина

Редактор T. Горячева

Типография, пр. Сапунова, 2

Заказ 1016/13 Изд. № 350 Тираж 772 Подписное

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

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