SU744527A2 - Устройство дл стохастических вычислений - Google Patents

Description

На фиг. 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 вывод тс  координаты вектора иензвестных систем.

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

о

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

Claims (1)

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

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

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

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