Устройство для решения разностных краевых задач
ОП ИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВНДЕТЕЛЬСТВУ (61) Дополнительное к авт. свиа-ву(22) Заявлено 01.06.77 (21) 2490390/18-24 Союз Соввтскнх
Социалистических
Республик
G 06 V 1ÇË1 с присоединением заявки №вЂ” Государственный комитет СССР но делам изобретений н открытий (23) ПриоритетОпубликовано15.10.79.бюллетень № З8 Дата опубликования описания 20.10.79 (53) УДК 681 14(088.8) (72) Автор . изобретения К3. В. Ладыженский Докепкий ордена Трудового Красного политехнический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ РАЗНОСТНЫХ КРАЕВЫХ ЗАДАЧ Изобретение относится к области вычислительной техники и может быть использовано .в универсальных и спепиализированных цифровых вычислительных системах при решении краевых задач для уравнений в частных производных и обыкновенных дифференциальных уравнений. Известно устройство для решения ал, гебраических уравнений содержащее блоки ввода и вывода, управляющие входы которых подключены к выходу блока уп-. равления, комбинационные цифровые сумматоры по числу неизвестных, первые входы которых соединены с выходами блока ввода, матрицу комбинапионных множительных блоков по числу коэффици15 ентов уравнений, первые входы которых подключены к соответствующим выходам блока ввода, выходы комбинационных множительных блоков каждой строки матрицы под20 . ключе ны ко второму входу соответствуюшего комбинационного цифрового сумматора, выход которого подключен ко вторым входам комбинационных множительных блоков соответствующего столбца матрицы и выходу блока вывода, а также группу блоков для обеспечения стабильности работы устройства (1), Недостатком рассмотренного устройства является большое количество операционных блоков. Число сумматоров равно числу неизвестных, число множительных блоков равно квадрату числа неиэвестных. Поэтому с увеличением порядка решаемой системы уравнений число сумматоров растет пропорционально числу неизвестных, а число множительных блоков увеличивается пропорционально квадрату числа неизвестных. Вследствие этого увеличивается также число связей между блоками. Указанные факторы делают рассмотренное устройство неэкономичным по затратам оборудования для решения больших систем линейных алгебраических уравнений, возникающих в краевых задачах для уравнений в част ных производных и обыкновенных диффе89 5 4 25 з рецциальнь1х уравнений, 11 снижает его надежность. Наиболее близким к данному является устройство, содержащее блок. управления, блок ввода-вывода, первый и вто5 рой блоки памяти, выполненные на сдви» говых регистрах, первый и второй сумматоры, первый и второй блоки умножения, группы элементов И, группы элементов И-ИЛИ, причем выходы первых t0 разрядов сдвиговых регистров первого блока памяти подключены через элементы И первой группы к первой группе входов первого блока умножения, выходы (N Ф 1 )Х разрядов сдвиговых ре- 15 гистров второго блока памяти подключены к первым входам элементов И-ИЛИ первой группы, выходы которых соединены с первой группой входов первого блока умножения, группа выходов блока ввода-вывода соединена с первыми входами элементов И-ИЛИ второй группы, выходы которых подключены ко входам первых разрядов сдвиговых регистров первого блока памяти, выходы первого и второго блоков умножения через элементы И второй и третьей групп подключены к первым входам первого и вто» рого сумматоров соответственно, управляющие входы элементов И всех групп и элементов И-ИЛИ всех групп подключены к выходам блока управления (2). Рассмотренное устройство имеет низкое быстродействие, так как реализует последовательный принцип вычислений, Кроме того, оно имеет ограниченные функциональные возможности, обусловленные тем, что выход сумматора связан со входом записи информации и первые Щ (левые) разряды второго блока памяти, выходы первых ра зрядов второго блока памяти связаны с устройством ввода-вы- вода, вход записи инф. рмации в первые разряды первого блока памяти связан с устройством ввода-вывода. Поэтому дан45 ное устройство не позволяет решать разностные краевые задачи. Иелью изобретения является повышение быстродействия устройства и расщи50 рение класса решаемых задач. Указанная цель достигается тем, что в устройство введены первый и второй блоки деления, причем выходы первого блока деления подключены ко вторым 55 входам элементов И-ИЛИ второй группы, выходы второго блока деления соединены с первыми входами элементов И-ИЛИ третьей группы, выходы которых подсоединены ко входам первых разрядов сдвиговых регистров второго блока памяти, выходы первого сумматора подсоединены к первым входам элементов И-ИЛИ че1 вертой группы и через элементы И четвертой группы с первыми группами входов первого и второго блоков деления, выходы элементов И-ИЛИ четвертой группы сое- динены с соответствующими входами (М+ 2 )- x разрядов сдвиговых регистров второго блока памяти, выходы второго сумматора через элементы И пятой группы соединены со второй группой входов второго блока деления, вторая группа входов первого блока деления через элементы И шестой группы соединены с группой выходов блока ввода-вывода, выходы (Я 41 )-х разрядов сдвиговых регистров второго блока памяти через элементы И седьмой группы подключены ко втбрым входам элементов И-ИЛИ третьей группы, к группе входов блока ввода-вывода, и через элементы И восьмой группы ко второй группе входов второго сумматора, группа выходов блока вводавывода соединена со вторыми входами элементов И-ИЛИ первой группы, первыми входами элементов И-ИЛИ пятой группы, и через элементы И девятой группы к первой группе входов второго блока умножения, выходы первых разрядов сдвиговых регистров второго блока памяти соединены со вторыми входами элементов И-ИЛИ четвертой и пятой групп, и через элементы И десятой группы подключены ко второй группе входов второго блока умножения, выходы элементов И-ИЛИ пятой группы соединены со вто- рой группой входов первого сумматора, управляющие входы блоков памяти, блоков деления, блоков умножения и сумматоров подключены к выходам блока управления. Такое выполнение устройства обеспечивает его высокое быстродействие за счет coBMemeBHs вычислительных операций и процедуры ввода-вывода. На фиг. 1 показана конструкция блоков памяти,, выполненных на сдвиговых регистрах, на фиг. 2 — схема устройства для решения разностных краевых задач. Блок памяти выполненный на сдвиговых регистрах имеет входы 1 в первые разряды сдвиговых регистров, выходы 2 информации из первых регистров сдвиговых регистров, сдвиговые реверсивные регистры, один из которых 3 5 69 1865 б служит для х анения сталиих а у . р тарших разрядов Работа устройства происходит слелуючисел, управляющие входы 4 служащие шим образом, для сдвига информации вправо и влево, Блок ввода-вывола 7 по сигналам бловходы 5 (Я 4 l ()-х разрядов сдвиговых . ка управления 6 записывает значение регистров, выходы 6 (Я t1 )-х разря- 5 Во и значение 7 в первые разряды лов сдвиговых регистров. регистров первого блока памяти 16 и в У стройство для решения разностных первые разряды регистров второго блока краевых задач содержит: блок ввода-вы- памяти 17 соответственно. Эти операвода 7, первую группу алементо И 8, ции соответствуют формулам (2) рекурблок управления 9, первый блок умно- 10 рентного алгоритма, жения 10, второй блок умножения 11, Далее устройство работает по следуюпервый сумматор 12, второй сумматор шему циклическому алгоритму соответ++pè ™7 I 13. Первый блок деления 14, второй ствуюшему формулам (3) - (4). Блок блок деления 15, первый блок памяти, ввода-вывода выдает очередное Я, . На выполненный на сдвиговых регистрах 16, 11 входы блоков умножения 10 и 11 постувторой блок памяти, выполненный на сдви- пают значения Я с хранящиес говых регистрах 17, вторая группа эле- вых разрядах регистров 16, Я, хра1 ментов И 18, первая группа элементов няшиеся в первых разрядах регистров 17, И-ИЛИ 19, вторая группа элементов И- . причем с<; поступает с обратным знаком. ИЛИ 20, третья группа элементов И 21, 2О Начинается вычисление произведения в третья группа элементов И-ИЛИ 22, чет- обоих блоках умножения по формулам (3), вертая группа алементов И 23, четвер-. (4). Содержимое регистров 16 и 17 сдвитая группа элементов И-ИЛИ 24, пятая гается на один разряд вправо, освобожгруппа алементов И 25, пятая. группа дая первые разряды регистров памяти для элементов И-ИЛИ 26, шестая группа 25 приема информации. Далее блок вволаэлементов И 27, седьмая группа элемен- вывода выдает (. u F . Значения Г 1 1 1 тов И 28, восьмая группа элементов И 1 И ВЫЧИСЛЕННЫЕ ПРОИЗВЕДЕНИЯ С ВЫ-! И 29, девятая группа элементов И 30, хода блоков умножения 10, 11 поступадесятая группа алементов И 31, управ- ют на входы сумматоров 12, 13 где вызо Э ляюшие входы 32 элементов групп И, полняют суммирование по формулам (3), И-ИЛИ, блоков памяти, блоков умноже- (4). Блок ввода-вывода выдает Ь; ния, блоков деления, сумматоров, выхо- Ъ, полается на вторые входы первого ды блока управления 33. блока деления 14, (входы делимого), а. Устройство решает разностные крае- значение на выходе второго сумматора вые задачи вида 13 подается на вторые входы (входы де-C>.) у =-у. лимого) второго блока деления 15, зна1 1 f « и1 чение на выходах первого сумматора 12 1=01 Я (М) подается на первые входы (делителя) АаО 1 Со =, С =1, В = О О)О1Н)Н 40 обоих блоков деления 14, 15. Результат по рекурентному алгоритму деления с выходов первого блока деления 14 записывается в первые разряды сдви(2) говых регистров перзого блока 16, а ре5Ä зультат деления с выхолов второго блока tel C;-А;А; 1 (3) деления 15 записывается в первые разряды сдвиговых регистров второго блока — памяти 17. Описанный циклический алЯ,в +7 1+1 Ci — 1 i 1 " ритм вь олняется в течение И т тов работы устройства. В результате, в сдвиYN= Shak (5) говых регистрах первого и второго блоков 50 памяти 16 и 17 будут записаны коаффи1 = 1 (++i«1 А.1 (6) циенты К„ и /51, причем значения а(, и /Ь, будут записаны в (N+1 ).-х разря1 ) дах сдвиговых регистров, а значениями hlif где А В 2 Р— известные величины. и/ . 1 бУдУт хРанитьсЯ в пеРвых РазРЯ1) 11 У вЂ” искомое решение за- лах слвиговых регистров. На атом закан- 1 дачи. чивается первый атап вычислений, t д . A — промежуточные козф» На втором атапе работы устройства ре„ > Л 1 ! фициенты. анализируются вычисления по формулам (5 }, (6 ). 7 601 Происходит сдвиг влево в сдвиговых регистрах первого блока памяти 16 и циклический сдвиг влево в. сдвиговых регистрах второго блока памяти 17. В результате циклического сдвига значения первых разрядов сдвиговых регистров второго блока памяти 17, в которых хранится /Ь = 1 будут переписаны м н в освободившиеся (N 4 1 )-е разряды сдвиговых регистров второго блока памя- !О ти 17. Затем устройство работает по следующему циклическому алгоритму. Значение хранящееся в (й Ф 3 )-х раз1 4 рядах сдвиговых регистров второго блока памяти 17 поступает на входы первого блока умножения 10. Одновременно на входы первого блока умножения подается сА, +1 хранящееся в первых разрядах сдвиговых регистров первого блока памяти 16. Выполняется операция в блоке умножения 10. Значение /5„ > хранящееся в первых разрядах сдвйговых регистров второго блока памяти 17, поступает на входы сумматора 12. Одновременно про25 изведение с выходов первого блока умножения 10 поступает на входы сумматора 12. Производится суммирование. Qaлее производится сдвиг на один разряд влево в сдвиговых регистрах блоков па30 мяти 16, 17..При этом требуемые на следующем шаге вычислений значениями, ° и Д„оказываются в первых разрядах соответствующих сдвиговых регистров, a (N+ 1 )- -е . разряды сдвиговых регистров второго блока памяти 17 освобождаются для приема вычисленного значения 1 . Производится запись результа1 та с выходов сумматора 12 в (Я 11 )-е 40 разряды сдвиговых регистров второго блока памяти 17. B результате выполнения описанного алгоритма в течение М тактов в сдвиговых регистрах второго t блока памяти 17 окажутся значения (, 45 У, ...., У . Величина У будет зеN N писана в первых разрядах сдвиговых ре гистров второго блока памяти 17, а величина У будет храниться в (М +1 )-х разрядах. Блок управления 6 обеспечивает требуемую синхронизацию работы устройства. Порядок выдачи информации на блок ввода-вывода в этом случае У, У .-., Y Вывод решений может производиться также в процессе его получения. В этом случае решение будет выорядке YN, YN< ""Y„YîПоследний способ выдачи информации ,увеличивает .быстродействие устройст86 Я ем, так как позволяет использовать ком поненты решения краевой задачи сразу в процессе их получения. Высокое быстродействие устройства по сравнению с прототипом обеспечивается параллельным вычислением знаменателя формул (3) и (4) и числителя формулы (4), параллельным выполнением операций умножения и сдвига в регистрах памяти, одновременным выполнением операции деления в обоих блоках деления, совмещением во времени вычислений и процесса выдачи информации из устройства. Точность решения в устройстве не зависит от числа шагов, а определяется количеством двоичных разрядов в прелставлении обрабатываемых чисел. Формула изобретения Устройство для решения разностных краевых задач, содержащее блок управления, блок ввода-вывода, первый и второй блоки памяти, выполненные на сдвиговых регистрах, первый и второй сумматоры, первый и второй блоки умножения, группье элементов И, группы элементов И-ИЛИ, причем выходы первых разрядов сдвиговых регистров первого блока памяти подключены через элементы И первой группы к первой группе входов первого блока умножения, выходы (N a ) ) х разрядов сдвиговых регистров второго блока памяти подключены к первым входам элементов И-ИЛИ первой группы, выходы которых соединены с первой группой входов первого блок» умножения, группа выходов блока ввода-вывода соединена с первыми входами элементов И-ИЛИ второй группы, выходы которых подключены ко входам первых разрядов сдвиговых регистров первого бло- ка памяти, выходы первого и второго блоков умножения через элементы И второй и третьей групп подключены к первым входам первого и второго сумматоров соответственно, управляющие входы элементов И-ИЛИ и элементов И всех групп подключены к выходам блока управления, о т л.и ч а ю щ е е с я тем, что, с целью повышения быстродействия и расширения класса решаемых задач, в него введены первый и второй блоки деления, причем выходы первого блока деления подключены ко вторым входам элементов И-ИЛИ второй группы, 9 69 выходы второго блока деления соединены с первыми входами элементов И-ИЛИ третьей группы, выходы которых подсоединенй ко входам первых" разрядов сдвиговых регистров второго блока памяти, выходы первого сумматора подсоединены к первым входам элементов И-ИЛИ чет- вертой группы и через элементы И четвертой группы с первыми группами входов первого и второго блоков деления, выходы элементов И-ИЛИ четвертой группы соединены с соответствующими входами (Я Ф f )х разрядов сдвиговых регистров второго блока памяти выходы второго сумматора через элементы И пятой группы соединены со второй группой входов второго блока деления, вторая группа входов первого блока деления через элементы И шестой группы соеди-, нена с группой выходов блока ввода-вывода, выходы (Й+ 3 )х разрядов сдвиговых регистров второго блока памяти через элементы И седьмой группы подключены ко вторым входам элементов И-ИЛИ тре- тьей группы, к группе входов блока ввода-вывода, и через элементы И восьмой 1865 10 группы ко второй группе входов второго сумматора, группа выходов блока вводавывода соединена со вторыми входами элементов И-ИЛИ первой.группы, первыми входами элементов И-ИЛИ пятой груп пы, и через элементы И девятой группы к первой группе входов второго блока умножения, выходы первых разрядов сдвиговых регистров второго блока памяти I0 соединены со вторыми входами элементов И-ИЛИ четвертой и пятой групп, и через элементы И десятой группы подключены ко второй группе входов второго блока умножения, выходы элементов И-ИЛИ пятой группы соединены со второй груп.пой входов первого сумматора, управля ющие входы блоков памяти, блоков деления, блоков умножения и сумматоров подключены к выходам блока управления. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР М 482752, кл, 9 06 У 15/32, 1971 . 2, Авторское свидетельство СССР Хю 209030, кл. G 06F 15/32, 1968. 691865 Составитель А, Шмид Редактор Э. Губниикая Техред О, Андрейко Корректор Н. Стен Заказ 6218/40 Тираж 780 Подписное LiHHHfIH Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Филиал ППП Патент, r. Ужгород, ул. Проектная, 4
