Параллельное вычислительное устройство для решения разностных уравнений задач теории поля

ощ 742945 1 ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ИТЕЛЬСТВУ Союз Советскик Социалистических Республик(51) М. Кл.2 С 06 Р 15/32 с присоединением заявки Ио Государственный комитет СССР но делам изобретений я открытий(72) Авторы изобретения В.П. Ильин и Я.И. Фет Вычислительный центр Сибирского отделения АН СССРи Институт математики Сибирского отделения АН СССР(54) ПАРАЛЛЕЛЬНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВОДЛЯ РЕШЕНИЯ РАЗНОСТНЫХ УРАВНЕНИЙ ЗАДАЧТЕОРИИ ПОЛЯ Изобретение относится к цифровой вычислительной технике .Известны .цифровые вычислительные устройства, предназначенные для решения разностных уравнений, в которых для повышения производитель" ности используется множество параллельно работающих арифметических блоков (1).Недостатком этих устройств является низкое быстродействие, .Наиболее близкой по технической сущности к предлагаемому устройству является цифровая вычислительная система для решения раэностных уравнений задач теории поля и арифметических задач, содержащая блок управления и Н арифметических блоков,каждый из которых содержит сумматор, регистр сдвига и, элементы И, ИЛИ, причем управляющие входы каждого арифметического блока соединены с соответствующими выходами блока уп" равления (2) .Недостатком известной системы является низкое .быстродействие, обусловленное тем, что вычисления ведутся последовательно по строкам сеточной области, а также тем, что в каждом арифметическом блоке в данный момент времени суммируютсятолько два аргумента сеточной функции.Цель изобретения - повыаение бы"стродействия цифрового вычислительного устройства при решении раэностных уравнений задач теории поля,1 О Эта цель достигается тем, что впредлагаемом устройстве Н арифметических блоков соединены в матрицу,первый, второй, третий, четвертыйинформационные входы (1,3) -го ариф 5 метического блока сод"иены соответственно с информационными выходамитий и четвертый регистры сдвига идополнительный сумматор; первый,второй, третий, четвертый, пятыйи шестой входы сумматора соединенысоответственно с выходами первого,второго, третьего, четвертого,пятого и шестого элементов ИЛИ) первый, второй и третий входы первогоэлемента ИЛИ подключены соответственно через первый, пятый и девятый элементы И к первому, пятому и девятому входам арифметического блока, первый, второй и третий входы второгоэлемента ИЛИ - через второй, шестойи десятый элементы И - ко второму,шестову и десятому информационнымвкодам арифметического блока, первый, второй и третий входы третьегоэлемента ИЛИ - через третий, седьмойи одиннадцатый элементы И - к третьему, седьмому и одиннадцатому информационным входам арифметическогоблока, первый, второй и третий входычетвертого элемента ИЛИ - через четвертый, восьмой и двенадцатый элементы И - к четвертому, восьмому и двенадцатому информационным нходам арифметического блока; выходы первого,второго, третьего, четвертого и пятого разрядов первого регистра сднига подключены соответственно черезтринадцатый, четырнадцатый, пятнадцатый, шестнадцатый и семнадцатыйэлементы И к четвертым входам первого, нторого, третьего, четвертогоэлементов ИЛИ и к третьему входупятого элемента ИЛИ, кроме того,второй и первый входы пятого элемента ИЛИ соединены через восемнадцатый и девятнадцатый элементы И соответственно с инверсными выходамивторого и четвертого регистров сдвига, а первый и второй входы шестого элемента ИЛИ соединены через двадцать первый и двадцатый элементы Исоответственно с прямым выходом второго регистра сдвига и с инверснымвыходом третьего регистра сдвига;первый вход дополнительного сумматора соединен через двадцать второйэлемент И с выходом сумматора, авторой вход дополнительного сумматора через двадцать третий элементИ - с инверсным выходом второго регистра сдвига, выход дополнительногосумматора - с управляющим выходомарифметического блока, а выходсумматора подключен через двадцатьЧетвертый элемент И ко входу первогорегистра сдвига и через двадцатьвосьмой элемент И - к первому входуседьмого элемента ИЛИ,прямой выходвторого регистра сдвига подключенЧерез двадцать шестой элемент И ковходу четвертого регистра сдвигаи через двадцать седьмой элемент Ико второму входу седьмого элемента ИЛИ, а третий вход седьмогоэлемента ИЛИ соединен через двадцать35 где й и д - заданные значе 1)Э 1)5ния правой части и граничных функций.Устройство работает следующимобразом.В соответствии с методом верхнейрелаксации с шахматной упорядоченностью узлов нсе арифметические блоки 4 параллельного вычислительногоустройства 2 разбиваются на четыремножества:Я. - АУ н узлах с четными значениям 1+3Я. - АУ в узлах с нечетнымизначениями 1+3 .й 1 - АУ н узлах с четными1+для которых - 1 четно.2Й - АУ в узлах с четными 1,1,Ь2% Ь ЪМножество Я =й+Я-образует густую сетку, множество Я =Я., явспомогательную редкую сетку.Перед началом вычислений н регистры сднига 7 всех арифметическихблоков засылаются значения правыхчастей разностных уравнений, а н 40 45 50 55 бО 65 5 10 15 20 25 30 девятый элемент И с тринадцатым.информационным входом арифметическогоблока, а также через двадцать пятыйэлемент И со входом третьего регистра сдвига, выход седьмого элемента ИЛИ соединен со входом второгорегистра сдвига, а также с информационным выходом арифметического блока, управляющие входы всех элементов И и регистров сдвига соединеныс соответствующими управляющими входами арифметического блока.На фиг. 1 приведена блок-схемаустройства; на фиг, 2 - схема арифметических блоков.Устройство содержит универсальную вычислительную машину 1, параллельное вычислительное устройство2 для решения разностных управленийзадач теории поля, которое содержитблок 3 управления н матрицу М арифметических блоков 4, вычислительное устройство 2 соединено с цифровой вычислительной машиной 1 каналом связи 5.Каждый арифметический блок(фиг.2) содержит регистры сдвига6-9, дополнительный сумматор 10,сумматор 11, элементы 12-18 ИЛИ иэлементы 19-47 И,Работа устройства заключается ваппаратной реализации решения разностных уравнений Пуансона: 0 0 О 0 -41, .:, .регистры сдвига б граничных узлов "значения граничных Функций.Решение задачи делится на следую-щие этапы:А. Решение разностных уравненийна редкой сетке с помощью итерационного процесса:и+1 ж и и к щич, = - ,;., Ь-,4 ЧУ ) +Ч(2) 10цвв К 1)Е а".(3) длЯ (1,3)6 Я 20Б. Вычисление начальных приближений для узлов густой сетки с помощью интерполяции: 11 4 (-Ц1 чД1+1,ф 1(-1,+1 (,31. для (1,3)Ей, /аг.для (1.З)Еа"гВ, Решение разностных уравнений на густой сетке с помощью интерационного процесса: 30 для (1 3)6 аД. Вычисление точных значений для остальных узлов густой сетки с помощью интерполяции по формулам (4) и (5) .Укаэанные вычисления выполняются в параллельном вычислительном уст ройстве 2 следующим образом.А. В каждый из арифметических блоков 4.множества узлов Япода" ются из блока управления 3 разрешающие сигналы на элементы 23-26 И. 60 Этим обеспечиваются соединения, необходимые для того, чтобы на первые четыре входа сумматора 11 поступали Ъ; , Одновременйо в этй арифмети1(7)Г. Комбинация раэностных решенийузлов редкой сетки: 45/ ь 2 Ьо,= - 4 ,; - ,ческие блоки подаются разрешающиесигналы на элементы 36 к 39 И, которые обеспечивают соответственно поступление учетверенных (например, предварительным сдвигом алево на два разряда) значений Ч - с кнверсноговыхода регистра сцвига б и Г - сдинверсного выхода регистрасдвига 7 на пятый и шестойвходы сумматора 11. Кроме того, на элемент 40 И подается сигНал, разрешающий запись результатас выхода сумматора 11 на регистрсдвига 9. На элементы 42 И всехарифметических блоков множестваузлов Я. подается сигнал, разрегишающий регенерацию содержимого регистров сдвига б,После этих подготовительных дей-ствий из блока управления 3 подается серия из Р импульсов сдвига(Р - разрядность переменных) на ре-гйстры сдвига 6 всех арифметическихблоков множества узлов Й г и нагрегистры сдвига 6,7 и 9 всех арифметических блоков множества узловЙ, В результате в каждом арифмегитическом блоке множества узлов Я.вычисляется и записывается в регистрсдвига 9 выражение, заключенное вскобки в формуле (2) . Данное вычисление является первой Фазой итерации.Затем начинается вторая фаза итерации. При этом блок управления 3в каждоь арифметическом блоке множества Я , снимает разрешающие сигнаглы со всех элеМентов И, работающихво время выполнения первой фазы,подает разрешающие сигналы на элементы38 и 41 И и, кроме того, подает наэлементы 31-35 И, сигналы, соответствующие значениям разрядов множителя (щ- параметр релаксации),После этих подготовительных действий подается серия изР импульсовсдвига на регистры сдвига б и 9 всехариФметических блоков множества Яг".При этом на первые пять входов сумматора 11 подается (со сдвигом соответственно на один, два, три, четыре и пять разрядов) вычисленное впервой фазе выражение (в скобке),причем поступление этих величинуправляется значениями разрядовмножителя 4 (О или 1), В резуль 0тате на выходе сумматора 11 образуется произведение скобки на множитель-. Так как на шестой вход сумматора11 через элемент 38 И поступает значение Ч; с прямого выхода регистраисдвига б, то одновременно с вычислением укаэанного произведения происходит сложение этого произведенияс переменной Ч , Результат - новоеезначение переменной - Ч,", (формула (2) через элементы 4 И, 18 ИЛИпоступает в регистр сдвига б, замещаяВычисления по формуле (3) производятся аналогично, но при этомарифметические блоки множеств Я иЯ меняются ролями.Проверка условия окончания итерационного процесса 513 - 1) с 6производится с помощью дополнительного сумматора 10. Если во время выполнения второй фазы итерации податьразрешающие сигналы на элементы46 и 47 И, то на первый вход сумматора 10 будут поступать последовательно (начиная с младшего) разрядыца на второй - также последоваи+тельно, но в обратном коде, разрядыП ., Значит, на выходе сумматора 10ии,образуется разность О -1); . При"7 1152"62 условие окончанй я итерационного процесса ( 9 ) выполнитс я тогда, когда старшие Р- г разрядов этойразности равны нулю . Для проверкиусловия ( 9 ) подаются на элементы 46и 4 7 И всех арифметических блоковданного множества разрешающие си гналы с задержкой на г тактов относительно начала второй Фазы. Если сигналы на выходах 62 всех арифметических блоков данного множества нулевые, итерационный процесс окончен. 30Полученные значения переменныхзаписываются в регистры сдвидга 8, для этого в каждый арифметический блок множества Я. из блокауправления 3 подается разрешающий З 5сигнал на элемент +3 И и Р импуль-сов сдвига на регистры сдвига б и 8.Б. В каждый из арифметическихблоков 4 множества Я."(Д- подаютсяиз блока управления 3 разрешающие 40сигналы на элементы 27-30 И. Одновременно в эти арифметические блоки подаются разрешающие сигналына элементы 39 И и +1 И. Потом изблока управления 3 подаются Р им.пульсов сдвига на регистры сдвигаб всех арифметических блоков множества Я. и на регистры сдвига б и7 множества Я."Я. , таким образомв каждом арифметическом блоке множества Я.Я. вычисляется и запиИ 2 Ъсывается в регистры сдвига б выражение, заключенное в скобки в формуле (4) .Затем выполняется делениена 4(например, путем сдвига вправона два разряда). В результате ви 55регистрах сдвига б множества Й.Яобразуются начальные приближенияПо,(5) . Для этого в каждый арифметический блок данного множества подаются разрешающие сигналы на элементы 19-22 И, чтобы на первые четыре входа сумматора 11 поступали 65 переменныеи( Оо 1 о-1,11,1-1 +,1) 1,)+Одновременно в эти арифметическиеблоки подаются разрешающие сигналына элемент 39 И, через который й 1 Дпоступает с инверсного выхода регистра сдвига 7 на шестой вход сумматора 11. Сложение выполняется спомощью серии импульсов сдвига, подаваемых на регистры сдвига б множества Й и регистры б и 7 мноИжества Я, После деления на 4 врегистрах б множества ЯобраЪзуются начальные приближения П1,В. В каждый из арифметическихблоков множества узлов Я.подаются разрешающие сигналы на элементы 19-22 И для поступления пеТ 3менных 4 1, ф 11ф 1+ )1 д 1Одновременно в эти арифметическиеблоки подаются разрешающие сигналына элементы И 36 и 39 (для подачипеременных - 4 Ч;" и й; ) и на11)элемент 40 И (для записй промежуточного результата на регистр 9)Далее выполняются первая и втораяФазы итерации (этап А),Результат - новое значение перев+1менной Ч. (см, Формулу (б - оказывается в регистре б,Вычисления по формуле (7) производятся аналогично, но при этомарифметические блоки множеств Я иЯ" мен яют ся ролями .2На этом заканчивается выполнение одной итерации на густой сетке.Проверка условий окончания итерационного процесса производится также, как описано выше (этап А). Еслипроцесс не окончен, вычисления поформулам (6) и (7) повторяются (впротивном случае устройство управления 3 переходит к выполнению этапа Г).Г. В каждый арифметический блокмножества узлов Й. подаются разрешающие сигналы на элементы 38, 37 и40 И для поступления соответственно учетверенного (например, предварительным сдвигом влево на два раз -ряда) значения О,. с прямого выходарегистра б на шестой вход сумматора11, значения П.," - с инверсного113выхода регистра 8 н а пятый входсумматора 1 1 и записи результата свыхода сумматора 1 1 в регистр 9Затем подается серия и з Р импул ьсов сдвига для вычисления и записив регистр 9 разности , заключеннойв скобки в формуле ( 8 ) . После этогоблок управления 3 снижает разрешающие сигналы с элементов 3 8, 3 7 и 4 0 И ,подает разрешающие сигналы на элемент 4 1 И и , кроме того, подаетн а элементы 3 1 -3 5 И сигналы , соот в е т -ст вующие значениям разрядов множител я ; Затем выполняется умножен ие та , к ак описано выше ( э т ап А ) .В рез ульт ате в регистре б АУ множе 742945ства 9 образуется комбинация разностных решений О в соответствиис формулой (8),Д. Вычисления выполняются так же,как было описано выше для этапа Б.По окончании этапа Д в регистрах 5б всех арифметических блоков вычислительного устройства 2 находятся результирующие значения переменных(1 , которые и составляют решениезадачи. ОИспользование регистров сдвига споследовательным доступом и последовательных сумматоров существенноуменьшает стоимость арифметическогоблока 4. Кроме того, облегчаетсяреализация параллельного вычислительного устройства 2, так как обменинформацией между арифметическимиблоками производится последовательным кодом, что позволяет значительно уменьшить количество соединительных каналов. Это обстоятельствоособенно важно при реализации арифметических блоков 4 в виде микропроцессоров на БИС, имеющих жесткиеограничения по числу вводов. 25 Формула изобретения 30 Параллельное вычислительноеустройство для решения разностныхуравнений задач теории поля, содержащее блок управления и Н арифметических блоков, каждый из которыхсодержит сумматор, регистр сдвига 35и элементы И, ИЛИ, причем управляющие входы каждого арифметическогоблока соединены с соответствующимивыходами блока управления, о т л ич а ю щ е е с я тем, что, с целью щповышения быстродействия, И арифметических блоков соединены в матрицу,первый, второй, третий , четвертыйинформационные входы (1,Э)-го арифметического блока соединены соответственно с информационными выходами (1 - 1, -го, (1,-1) -го,(+1,-го (1,З+1)-го арифметических блоков; пятый, шестой, седьмойи восьмой информационные входы - 50с информационными выходами (1-2, 1) -го, (1, -2) -го, (1+2,З) -го и(1,+2) -го арифметических блоков;девятый, десятый, одиннадцатый идвенадцатый информационные входы -с информационными выходами (1-1,3-1) -го, (1+1,Э) -го, (1+1,+1) -го и(1-1, 1+1)-го арифметических блоков,причем в каждый арифметический блоквведены дополнительно второй, третий и четвертый регистры сдвига и бОдополнительный сумматор; первый,второй, третий, четвертый, пятыйи шестой входы сумматора соединеныссответственно с выходами первого,второго, третьего, четвертого, 65 пятого и шестого элементов ИЛИ; первый, второй и третий входы первогоэлемента ИЛИ подключены соответственно через первый, пятый и девятый элементы И к первому, пятому идевятому входам арифметического блока, первый, второй и третий входывторого элемента ИЛИ - через второй,шестой и десятый элементы И - ковторому, шестому и десятому информационным входам арифметического блока,первый, второй и третий входы третьего элемента ИЛИ - через третий, седьмой и одиннадцатый элементы И - ктретьему, седьмому и одиннадцатомуинформационным входам арифметического блока, первый, второй и третийвходы четвертого элемента ИЛИ -через четвертый, восьмой и двенадцатый элементы И - к четвертому, восьмому и двенадцатому информационнымвходам арифметического блока, выходы первого, второго, третьего,четвертого и пятого разрядов первого регистра сдвига подключены соответственно через тринадцатый, четыр"надцатый, пятнадцатый, шестнадцатыйи семнадцатый элементы И к четвертымвходам первого, второго, третьего,четвертого элементов ИЛИ и к третьемувходу пятого элемента ИЛИ, крометого, второй и первый входы пятогоэлемента ИЛИ соединены через восемнадцатый и девятнадцатый элементыИ соответственно с инверсными выходами второго и четвертого регистровсдвига, а первый и второй входышестого элемента ИЛИ соединены черездвадцать первый и двадцатый элемейты И соответственно с пряиим выходом второго регистра сдвига и с инверсным выходом третьего регистрасдвига; первый вход дополнительногосумматора соединен через двадцать второй элемент И с выходом сумматора,а второй вход дополнительного сумматора через двадцать третий элементИ - с инверсным выходом второго регистра сдвига, выход дополнительногосумматора - с управляющим выходомарифметического блока, а выход сумматора подключен через двадцать четвертый элемент И ко входу первогорегистра сдвига, и через двадцатьвосьмой элемент И - к первому входу седьмого элемента ИЛИ, прямойвыход второго регистра сдвига подключен через двадцать шестой элементИ ко входу четвертого регистра сдвига и через двадцать седьмой элементИ ко второму входу седьмого элемента ИЛИ, а третий вход седьмогоэлемента ИЛИ соединен через двадцатьдевятый элемент И с тринадцатым информационным входом арифметическогоблока, а также через двадцать пятыйэлемент И со входом третьего регистра сдвига, выход седьмого элемента ИЛИ соединен со входом второгорегистра сдвига, а также с информационным выходом арифметического блока, управляющие входы всех элемен.тов И и регистров сдвига соединеныо соответствующими управляющими входами арифметического блока е Источники информации,принятые во внимание при экспертиэе1. Х 1 гясЬ 1 пдЭ.Е . Моча: а 1 в 1 -742945 Составитель Н. Палеева Техред М.Петко Корректор Н. Стец Редактор Т. Киселева Тираж 751 Подписное ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5