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

О П И С А Н И Е 011744527ИЗОБРЕТЕНИЯ Союз Советских Сециалистическии Республик(43) Опубликовано 30.0 по делам изобрете и открытий 5) Дата опубликованияБ. Овсянник В, С, Гладкий и вский ордена Трудо нефтехимической и им, М, МКрасного Знамени институтвой промышленностиГубкина Мос вогга ОХАСТИЧЕСКИХ ВЪЧИСЛЕНИЙ 4) УСТРОЙСТВО Д чис- об- ерноенияакой 5 Изобретение лительной техн ращения матри стей (500 Х 500 системы алгеб же размерност относится к области в ки и используется дл цы сверхбольших разм и более) или для ре аических уравнений По ос устройст содержа чики, бл данных,ды кото памяти,с конечн памяти,ключеньновному авт. св.208340 известно во для стохастических вычислений, щий блок памяти, регистры, счет ок управления и блок обработки управляемый преобразователь, вхорого соединены с выходами блока а выходы через вентили соединены ыми счетчиками и входами блока 15 управляющие входы вентилей под-к блоку управления. В основу работы известного устроиства, как и в основу предлагаемого устройства 20 положен принцип построения и статистического испытания последовательной дискретной марковской цепи, моделируемой по определенным правилам согласно заданным матрицам, над которыми оно осуществляет 25 операции умножения и возведения в степень. Однако схемное решение известного устройства приводит к тому, что время решения велико и пропорционально п 4 (и - размерность обрабатываемых матриц). 30 Кроме того, известное устроиство не позволяет обращать матрицы и решать системуалгебраических уравнений,Целью изобретения является повышение быстродействия устройства при обращении матриц и решении системы алгебраических уравнений.Поставленная цель достигается тем, что предлагаемое устройство содержит дополнительный блок памяти, блок суммирования и коммутатор, первая группа входов которого подключена к выходу блока управления, вторая группа входов коммутатора подключена к группе выходов блока памяти, третья группа входов коммутатора соединена с выходами управляемого вероятностного преобразователя соответственно, выходы которого подключены к первой группе входов дополнительного блока памяти соответственно, выход которого соединен с первой группой входов блока суммирования, вторая группа входов которого подключена к выходу коммутатора, выходы блока суммирования соединены со входами блока деления на число испытаний соответственно, вторая группа входов дополнительного блока памяти и третья группа входов блока суммирования подключены к выходу блока управления.На фиг. 1 изображена блок-схема предлагаемого устройства; па фпг. 2 - пример выполнения блока управления.Устройство содержит блок 1 ввода-вывода данных, выходы которого соединены со входами блока 2 памяти, а входы - с выходами блока 3 задаппя режима работы и блока 4 управления, выходы которого соединены со входамп всех остальных блоков, управляемый вероятностный преобразователь блок 5), вход которого соединен с выходом блока 2 памяти, а выходы - со входами блока 4 управления и со входамп блока б памяти вектора свободных членов, выходы которого соединены со входами блока 7 суммирования, выходы которого соединены со входами блока 8 деления па число испытаний, выход которого соединен со входом блока 2 памяти, выходы которого соединены со входами коммутатора, другие входы которого соединены с выходамп блока 5, а выход - со входами блока 7.Блок задания режима работы содержит переключатель и сумматор. Устройство может работать в двух режимах: режим обращения матрицы, при котором переключатель блока задания режима соединяст непосредственно блок памяти с блоком ввода-вывода; режим решешгя системы алгебраических уравнений, прп котором переключатель блока задания режима соединяет блок памяти с сумматором, в котором производится суммирование компонент вектора неизвестных.Блок управления (фиг. 2) содержит счетчик номеров исходных строк матрицы, счетчик числа испытаний, цепи синхронизации, которые реализуют заданную последовательностьь работы остальных блоков устройства.После запуска устройства тактовые импульсы поступают в блок управления. Первый импульс переводит регистр сдвига блока в первое состояние; импульс, соответствующий этому состоянн.ю регистра сдвига, возбуждает первую строку матрицы и одновременно переводит триггер Тз в состояние 1. Прн этом открывается вентиль и очередной тактовый импульс поступает в 1,п-полюсник (блок 5). 1,п-полюсник отрабатывает. Сигнал, возникающий на одном из его выходов, поступает в блок управления, дешифрируется и возбуждает соответствующую строку матрицы о в блоке памяти. Описанная процедура повторяется до попадания процесса в поглощающее состояние, что определяется появлением сигнала на шине а. Длительность процесса блуждания может быть также ограничена наперед заданным числом переходов цепи. Сигнал попадания процесса в поглощающее состояние устанавливает регистр сдвига и триггер Т, в положение. 0 и поступает па счетчик, в котором фиксируется факт проведения первого испытания. После Лг пспьг 5 10 15 20 25 30 35 40 45 50 55 60 65 таний импульс переполнения счетчика переключает триггер Т в положение 1, чем фиксируется факт вычисления одной строки матрицы, и возбуждает первый элемент И блока 9. Описанный процесс повторяется до переполнения счетчика числа строк, импульс переполнения которого останавливает вычислительный цикл.Коммутатор состоит из дешифратора и п - 1 элементов И. Блок 4 управления отмечает вычисленные строки обратной матрицы возбуждением соответствующего элемента И блока 9 (если вычислена первая строка, то возбуждается первый элемент И и т. д,), Второй сигнал на каждый из элементов И поступает с выхода 1, и-полюсника. Третий сигнал на каждый элемент И поступает из блока памяти, При одновременном появлении двух сигналов (с 1, п-полюсника и блока управления) элемент И пропускает третий сигнал (с блока памяти), который через дешифратор подается па сумматоры блока 7, чем реализуется обратная связь по решению, существенно увеличивающая быстродействие устройства.Работает устройство следующим образом.В блок 2 памяти через блок 1 вводятся исходные данные, образуемые пз матрицыд - г,л - л - 1,п - , А - 1, д - г где Аь г - обращаемая матрица коэффициентов системы алгебраических уравнений (матрица В дополняется столбиком компонент вектора поглощения, элементы которого определяются как Ь =лг/=1есть полная стохастическая матрица, абсолютные значения элементов по строкам которой образуют дискретные распределения вероятностей полной группы событий. В блоке 2 указанные распределения записываются в виде функции распределения (Рг). В блок б заносятся единицы или координаты вектора . При возбуждении блоком 4 адреса г (вычисляемой строки обратной матрицы) в блоке 5 считываются значения узловых точек Р;. После срабатывания блока 5 на его одном пз выходов появляется сигнал. Если это не сигнал попадания в поглощающее состояние (выход и), то он включает соответствующий сумматор блока 7, в котором происходит накопление или единиц, если идет обращение матрицы, илп соответствующей координаты вектора свободных членов, если идет решение системы алгебраических уравнений, Этот же сигнал с выхода блока 5 поступает на вход блока 4, который выбирает из ОЗУ строку матрицы с номером, равным номеру выхода блока 5, блок 5 срабатывает, и описанный процесс повторяется до тех пор, пока не появится сигнал на и выходе блока 4, что означает, что траектория блуждания закопчена в поглощающем состоянии. Число таких траекторий выбирается исходя из заданной точности вычислений, заносится в счетчик блока 4 (фиг. 2). После проведения У траекторий (испытаний) блок 4 подает сигнал на блок 8 деления, по которому суммы, накопленные на сумматорах блока 7, поступают в блок 8, где делятся на число траекторий У, и полученные таким образом приближенные значения -ной строки обратной матрицы записываются в ОЗУ на место с-ной строки исходной матрицы. Кроме этого, блок 4 возбуждает -ный элемент И блока управления обратной связью, отмечая факт вычисления -ной строки исходной матрицы. В дальнейшем -ная строка в вычислениях выступает как поглощающая. В блоке 9 идет контроль: не перешла ли траектория в состояние, соответствующее уже вычисленной строке. При этом в блоке 9 сигнал с выхода 1,и-полюсника (блока 5) дешифрируется и поступает на соответствующий элемент И. Если этот элемент И был уже возбужден блоком 4 (например, элемент И;+, это означает, что траектория попала в поглощающее состояние), то сигнал с выхода элемента И,+, включает обратную связь и в блок 7 суммирования на соответствующие сумматоры поступают значения + й строки обратной матрицы. Введение указанной обратной связи резко сокращает траекторию блуждания и в связи с этим сокращается общее время решения задачи.Описанный процесс вычислений повторяется при вычислении всех оставшихся строк обратной матрицы.Если устройство работает в режиме обращения матрицы, то через переключатель блока 3, который находится в состоянии 1, элементы вычисленной обратной матрицы выводятся блоком 1,Если устройство работает в режиме решения системы алгебраических уравнений,то через переключатель блока 3, которыйстоит в положении П, элементы обратнойматрицы поступают в сумматор, где суммируются в каждой строке по столбцам.и через блок 1 выводятся координаты векторанеизвестных систем.Использование обратной связи по решению между блоком суммирования и блокомпамяти увеличивает скорость решения взсреднем в и траз.15Формула изобретенияУстройство для стохастических вычислений по авт. св.208340, отл и ч а ю щ е е ся тем, что, с целью повышения быстродействия устройства, оно содержит дополнительный блок памяти, блок суммирования и коммутатор, первая группа входов которого подключена к выходу блока управ ления, вторая группа входов коммутатораподключена к группе выходов блока памяти, а третья группа входов коммутатора соединена с выходами управляемого вероятностного преобразователя соответственно, 31 выходы которого подключены к первойгруппе входов дополнительного блока памяти соответственно, выход которого соединен с первой группой входов блока суммирования, вторая группа входов которого под ключена к выходу коммутатора, выходыблока суммирования соединены со входами блока деления соответственно, вторая группа входов дополнительного блока памяти и третья группа входов блока суммирования 40 подключены к выходу блока управления.744527 блоиу 2 Заказ 1016/13 Изд.350 Тираж 772 ПодписноНПО Поиск Государственного комитета СССР по делам изобретений и открыти113035, Москва, Ж, Раушская наб д. 4/5 Типографь