Устройство для стохастических вычислений Советский патент 1980 года по МПК G06F7/70 G06F15/173 G06F17/18 

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

Устройство содержит блок I ввода-вывода даниых, выходы которого соединены со входами блока 2 памяти, а входы - с выходами блока 3 задаиия режима работы н блока 4 унравлеиия, выходы которого соединены со входами всех остальных блоков, управляемый вероятностный преобразователь (блок 5), вход которого соединен с выходом блока 2 памяти, а выходы - со входами блока 4 уиравлення и со входами блока 6 памяти вектора свободных членов, выходы которого соединены со входами 7 суммирования, выходы которого соединены со входами блока 8 деления на число испытаний, выход которого соединен со входом блока 2 намяти, выходы которого соединены со входами коммутатора, другие входы которого соединены с выходами блока 5, а выход - со входами блока 7.

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

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

После запуска устройства тактовые импульсы поступают в блок управления. Первый импульс переводит регистр сдвига блока S первое состояние; имнульс, соответствующий этому состоянию регистра сдвига, возбуждает первую строку матрицы и одновременно переводит триггер Т в состояние «1. При этом открывается вентиль и очередной тактовый пмпульс поступает в 1,л-полюсник (блок 5). 1, п-полюсннк отрабатывает. Сигнал, возникающий па одном из его выходов, поступает в блок управления, дешифрируется н возбуждает соответствующую строку матрицы В в блоке памяти. Описанная процедура повторяется до попадания процесса в поглощающее состояние, что определяется появлеиием сигпала на шине а. Длительность процесса блуждания может быть также ограничена наперед заданным числом переходов цепи. Сигиал попадания процесса в поглощающее состояние устанавливает регистр сдвига и триггер Гз в ноложение. «О и поступает на счетчик, в котором фиксируется факт проведения первого испытания. После N испытаний импульс переполнения счетчика переключает триггер TZ в полол ение «1, чем фиксируется факт вычислеиия одной строки матрицы, и возбуждает первый элемент И блока 9. Описанный процесс повторя()тся до перенолиения счетчика числа строк, импульс переполнения которого останавливает вычислительиый цикл. Коммутатор состоит из дешифратора и

п-1 элементов И. Блок 4 )шравлеиия отмечает вычисленные строки обратной матрицы возбуждением соответствующего элемента И блока 9 (если вычислена первая строка, то возбуждается первый элемепт И

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

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

В блок 2 памяти через блок 1 вводятся

исходные данные, образуемые из матрицы

О.-1,;( - /1-1,я-1 -Д;-1,« -1,

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

п - 1

uij). Таким образом, матрица В

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

В блок 6 заносятся единицы или коордииаты вектора /. При возбуждеиии блоком 4 адреса f (вычисляемой строки обратной матрицы) в блоке 5 считываются значения Ззловых точек Fi. После срабатывания блока 5 иа его одном из выходов появляется сигнал. Если это не сигнал попадани в поглощающее состояние (выход п), то он включает соответствующий сумматор блока 7, в котором происходит наконлеиие или

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

4, который выбирает из ОЗУ строку матрицы с номером, равным номеру выхода блока 5, блок 5 срабатывает, и описанный процесс повторяется до тех пор, пока ие появится сигнал на п выходе блока 4, что означает, что траектория блуждания закопчена в поглощающем состоянии. Число таких траекторий выбирается исходя из задаииой точности вычислений, заносится в счетчик блока 4 (фиг. 2). После проведения N траекторий (испытаний) блок 4 подает сигнал иа блок 8 деления, по которому суммы, накопленные на сумматорах блока 7, поступают в блок 8, где делятся иа число траекторий Л и полученные таким образом приближенные зиачения t-ной строки обратной матрицы занисываются в ОЗУ на место i-ной строки исходной матрнцы. Кроме этого, блок 4 возбуждает i-иый элемент И блока унравлеиия обратной связью, отмечая факт вычисления г-ной строки исходной матрицы. В дальнейшем г-ная строка в вычислениях выстунает как поглощающая. В блоке 9 идет контроль: не перещла ли траектория в состояние, соответствующее уже вычисленной строке. При этом в блоке 9 сигнал с выхода 1,«-полюсннка (блока 5) дещнфрируется и поступает на соответствующий элемент И. Если этот элемент И был уже возбужден блоком 4 (например, элемент Hj+;i это означает что траектория понала в поглощающее состояние) , то сигнал с выхода элемента Vii+k включает обратную связь ив блок 7 суммирования на соответств пощие сумматоры поступают значення i-}-k строки обратной матрицы. Введение указанной обратной связи резко сокращает траекторию блуждання и в связи с этим сокращается общее время решения задачи.

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

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

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

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

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

о

среднем в я т раз.

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

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

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

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