Содержание к диссертации
Стр.
ВВЕДЕНИЕ 5
1. АНАЛИЗ АЛГОРИТМОВ И СПЕЦИАЛИЗИРОВАННЫХ СРЕДСТВ
РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ ТЕОРИИ ПОЛЯ 14
1.1. Решение систем разностных уравнений на
однородной вычислительной среде 14
Распараллеливание вычислений при избыточном количестве узловых процессоров 19
Основные способы организации решения
систем большой размерности 25
1.4. Специализированные вычислительные
средства решения 34
Аналоговые сеточные процессоры 35
Цифровые сеточные процессоры 37
1.5. Цель и задачи исследований 41
2. РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ ОСНОВ ПОСТРОЕНИЯ
СПЕЦИАЛИЗИРОВАННОГО ВЫЧИСЛИТЕЛЯ ДЛЯ РЕШЕНИЯ
СИСТЕМ УРАВНЕНИЙ БОЛЬШОЙ РАЗМЕРНОСТИ 43
2.1. Организация процесса решения на однородной вычислительной среде методом циклической редукции .. 43
2.1.1. Свойство многовариантности ветвления
процесса вычислений прямого хода 49
Организация вычислений обратного хода .... 51
Проблема выделения двух подмножеств
узлов сетки 55
Стр.
2.2. Ограничения метода циклической редукции
и разработка основ его модификации 57
2.3. Проблема модифицированной редукции
трехмерных сеток 65
2.4. Редукция как средство аппроксимации
сеточных областей 67
2.5. Оценка сходимости процесса итерационных
вычислений 71
2.6. Выводы 73
3. ОПТИМИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ И ОРГАНИЗАЦИИ
ВЫЧИСЛЕНИЙ 74
Минимизация погрешности аппроксимации 74
Управление скоростью сходимости
итерационных вычислений 94
Организация процесса решения задач с резко неоднородной моделируемой средой 104
Применение вычислительной среды
упрощенной структуры 118
3.4.1. Образование графа матрицы редукции
без диагональных связей 118
3.4.2. Реализация результатов исследований на
вычислительных системах АЦВК "Сатурн-1и
и ЕС-І022 со спецпроцессором "0мега-2М" .... 128
3.5. Выводы 130
4. СПЕЦИАЛИЗИРОВАННЫЕ СТРУКТУРЫ ДЛЯ РЕАЛИЗАЦИИ
ОСНОВНЫХ ЭТАПОВ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ 131
4.1. Специализированный аналоговый сеточный
процессор 131
Стр.
Особенности выбора параметров массовых элементов 133
Обоснование выбора топологии связей 146
4 Л .3. Матрица узловых процессоров 154
4.2. Организация хранения и поиска данных
в памяти 157
4.3. Оценка количества выполняемых
арифметических операций 173
4.4. Настраиваемая структура цифровой обработки .... 182
Структура процессора прямого хода 186
Структура процессора масштабирования 190
Структура процессора первого этапа
обратного хода 193
4.4.4. Структура процессора второго этапа
обратного хода 195
4.4.5. Ориентировочные оценки эквивалентного
быстродействия и конструктивного
исполнения структуры 199
4.5. Выводы 203
ЗАКЛЮЧЕНИЕ 204
ЛИТЕРАТУРА 207
ПРИЛОЖЕНИЕ I * 218
ПРИЛОЖЕНИЕ II 228
Введение к работе
Одним из решающих условий развития советского общества является непрерывный рост производительности труда. С этих позиций следует рассматривать и задачи, поставленные ХХУІ съездом КПСС, перед советской наукой в восьмидесятые годы. В области естественных и технических наук, в частности, это означает "развитие математической теории, повышение эффективности ее использования в прикладных целях; совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации" / 52 / .
Дальнейшее развитие ЕС ЭВМ, предусмотренное проектом "Ряд-ЗУ намечено путем создания архитектур, в составе которых широко используются специализированные процессоры для решения определенных классов задач / 34 / . Применение проблемно-ориентированных процессоров позволит повысить быстродействие вычислительных систем до Ю7 - Ю9 оп./с / 24 / .
Важным классом таких задач для народного хозяйства, требующих наиболее крупные вычислительные ресурсы, являются краевые задачи теории поля, описываемые дифференциальными уравнениями в частных производных при исследовании явлений в ядерной и термоядерной энергетике, фильтрации нефти и подземных вод, тепловых и электрических машинах, метеорологии и др.
Высокий порядок N (в / 14 / приводится оценка N = 0(10")) систем алгебраических уравнений, аппроксимирующих эти задачи, требует не только создание специализированных процессоров и соответствующих структур памяти для работы с большими разреженными матрицами, но и также разработку новых методов
- б -
и алгоритмов организации вычислений / 102 /. По оценкам / 73 / для успешного решения такого типа задач потребуется быстродействие порядка 10 оп./с , что не может быть обеспечено без применения вычислительных средств параллельного действия.
На важность создания специализированных устройств для моделирования краевых задач теории поля указывалось в решениях Всесоюзного семинара по специализированным процессорам параллельного действия для решения краевых задач (Рига, 1981), Всесоюзного научно-технического семинара по развитию машинных методов и средств решения краевых задач (Донецк, 1983), Всесоюзного научно-технического семинара "Методы и средства решения краевых задач" (Казань, 1984).
Исследования по созданию специализированных вычислительных средств для решения задач в частных производных в настоящее время ведутся в Институте проблем управления АН СССР, Институте проблем моделирования в энергетике АН УССР, Институте кибернетики им.В.М.Глушкова АН УССР, Таганрогском радиотехническом институте им.В .Д.Калмыкова, Донецком политехническом институте, Всесоюзном нефтегазовом научно-исследовательском институте, Пензенском научно-исследовательском институте математических машин , Рижском политехническом институте им.А.Я.Пельше и других организациях. Большой вклад в развитии данного направления внесли советские ученые И.М.Витенберг, Б.А.Волынский, А.В.Каляев, Л.А.Коздо-ба, Э.С.Козлов, И.Д.Коноплев, М.М.Максимов, Б.Н.Малиновский , Ю.М.Мацевитый, И.А.Николаев, Н.С.Николаев, Л.В.Ницецкий, Р.А. Павловский, И.В.Прангишвили, В.Е.Прокофьев, Г.Е.Пухов, В.Б.Смолов, А.П.Спалвинь, А.Е.Степанов и другие. Ими разработаны основы теории машинных методов решения уравнений в частных производных, сформулированы основные принципы построения вычислительных сие-
тем, разработка которых в нашей стране ведутся по двум направлениям.
К первому направлению, исторически сложившемуся в ходе многолетнего опыта решения краевых задач теории поля аналоговым способом, следует отнести структуры с аналоговым сеточным процессором. Из-за представления входной и выходной информации в аналоговой форме (коэффициенты матрицы и вектор правой части системы разностных уравнений моделируются кодоуправляемыми магазинами проводимостей и источниками возмущения, а решение - распределением потенциалов в узлах сетки) в таком процессоре нет проблем по распараллеливанию вычислений. Он также обладает исключительно высоким процессорным быстродействием, которое в эквивалентных цифровых операциях исчисляется десятками и сотнями миллиардовоп./с уже при относительно небольшом числе (тп »N - 0(10 - 10 )) узлов сеточной модели / 75/. Однако рациональное использование этого быстродействия сдерживается из-за относительно медленной цифровой настройки сеточного процессора и цифровой обработки данных.Поэтому в настоящее время интенсивно исследуются структуры по распараллеливанию цифровых вычислений во вспомогательных процедурах обслуживания аналогового сеточного процессора.Для обеспечения высокой точности решения в такой структуре организуется итерационный процесс, сходимость которого при Н ^ т практически не зависит от
Успехи технологии по выпуску быстродействующих интегральных микросхем с широкими функциональными возможностями, разработка более совершенных микропроцессоров, современная тенденция ускорения цифровых вычислений путем их распараллеливания - все это способствовало развитию специализированных структур второго направления - цифровых сеточных процессоров,использующих итерационные методы решения. Для этих методов скорость сходимости решения в большей или меньшей степени зависит от порядка N
Несмотря на непрерывный рост функциональных возможностей (в смысле числа узловых процессоров и объема памяти) разрабатываемых специализированных структур, потребность в вычислительных мощностях при решении научно-технических задач растет намного быстрее. Поэтому продолжает оставаться актуальной проблема решения систем разностных уравнений большой размерности на структурах с ограниченным числом элементарных узловых процессоров (ТТ1 < N ).
Известные методы, применяемые при организации цифровых вычислений и основанные на сегментации исходной области при N >тп на ряд подобластей N1 < Щ , существенно увеличивают время решения на аналоговом сеточном процессоре, так как в результате сегментации скорость сходимости решения зависит от N Высокая скорость локальной сходимости решения в подобласти не распространяется на сходимость решения исходной задачи в целом. При N > ТП теряется также способность аналогового сеточного процессора определить решение с инженерной точностью (I - 5 %) безытерационным путем.
Для устранения потери скорости сходимости решения при М>тп интерес представляет идея об организации вычислений на аналоговом сеточном процессоре с диагональными связями с использованием комбинации алгоритмов исключения неизвестных и многосеточного метода,предложенная в работе /74/.В диссертационной работе эта идея нашла дальнейшее развитие и практическое применение.
Следует отметить, что для подобных целей в последнее время за рубежом ведутся интенсивные исследования по использованию такого подхода при организации вычислений в цифровых сеточных структурах / 119 /.
Вышеизложенное показывает актуальность проблемы по расширению области эффективного применения специализированного сеточного процессора аналогового типа и позволяет сформулировать цель
диссертационной работы.
Целью работы является разработка и исследование организации вычислений и структуры аналогового сеточного процессора для эффективного решения систем разностных уравнений, порядок которых существенно превышает число узловых процессоров вычислительной среды.
Методы исследований основываются на теории соответствующих разделов линейной алгебры; разделах вычислительной математики , связанных с решением систем разностных уравнений итерационными методами и методами исключения неизвестных; теории моделирования на сеточных моделях. Экспериментальная проверка теоретических положений осуществлялась путем цифрового моделирования на ЭВМ и решения задач на существующих параллельных вычислительных системах ЩВК "Сатурн" и спецпроцессоре "0мега-2М". В основу разработок положен принцип структурной реализации предложенных алгоритмов организации вычислительного процесса.
Научная новизна диссертационной работы состоит в следующем :
разработан новый эффективный способ организации вычислений при решении систем разностных уравнений большой размерности на однородной вычислительной среде. Для понижения порядка исходной системы уравнений способ не требует ее сегментации на подсистемы, а предусматривает параллельное и циклическое исключение неизвестных равномерно из всей системы ;
предложены специализированные структуры аналогового сеточного процессора (типа диагональная сетка) и средств обработки цифровой информации ;
разработаны алгоритмические основы построения и функционирования специализированного вычислителя для решения краевых задач теории поля, базирующиеся на предложенном автором методе модифицированной циклической редукции ;
разработана и исследована оптимальная организация процесса вычислений и хранения данных по критерию минимума затрат арифметических операций и объема памяти ;
разработан и.исследован вариант организации вычислений на существующих структурах аналогового сеточного процессора без диагональных связей.
Новизну предлагаемых структурных решений аналогового сеточного процессора подтверждает положительное решение по заявке на изобретение.
. Практическая ценность. Полученные в работе результаты исследований могут быть положены в основу разработок специализированных сеточных структур для эффективного решения краевых задач теории поля, описываемых дифференциальными уравнениями в частных производных второго порядка.
Реализация результатов работы. Диссертация выполнена в проблемной научно-исследовательской лаборатории электромоделирования Рижского политехнического института. Проведенные исследования являются частью хоздоговорных работ РПИ с Всесоюзным нефтегазовым научно-исследовательским институтом (ВНИИ НЕФТИ) г. Москвы (№№ гос.рег. 75029614, 77056213, 79053299, 8I0488II) и госбюджетной темы (№ гос.рег. 8I0488I4).
Результаты исследования организации вычислений включены в состав предложений по разработке специализированного процессора ЕС ЭВМ в рамках проекта "Ряд-3" (темы "Исследование и разработка средств повышения эффективности решения краевых задач теории поля на специализированных процессорах ЕС ЭВМ","Исследование и разработка структурно-технических решений и программно-математического обеспечения спецпроцессора ЕС ЭВМ для решения краевых задач теории поля" №№ гос.per.01820086845, 01830043892, координируемые ГКНТ СМ СССР и выполненные РПИ для НЩЭВТ и ПНИИММ) .
- II -
На основе полученных результатов исследований разработаны и внедрены комплексы программ в вычислительных системах АЦВК нСатурн-1" (ВНИИ НЕФТИ г.Москвы) и ЭВМ EC-I022 со спецпроцессором "0мега-2М" (РПИ, г.Рига). От внедрения программных разработок в одной организации получен подтвержденный годовой экономический эффект 41,6 тыс.руб.
Теоретические разделы диссертационной работы включены кафедрой ВТ РПИ в курс лекций "Параллельные специализированные процессоры", использованы в дипломном проектировании и учебно-исследовательской работе студентов специальностей 0608 и 0647.
Апробация работы
Результаты работы докладывались и обсуждались на республиканских семинарах по гибридным вычислительным машинам и комплексам (Житомир, 1974, 1977), III и ІУ республиканском семинаре "Методы и средства решения краевых задач" (Рига, 1975, 1978), 21-ом и 27-ом Международном научном коллоквиуме (Ильменау, ГДР, 1976, 1982), республиканских семинарах АН УССР по параллельным машинам и параллельной математике (Киев, 1978, 1980), семинаре по математическим методам в электротехнике (Ополе, ПНР, 1980), Международном симпозиуме по системному анализу и моделированию (Берлин, 1980), Всесоюзном семинаре по специализированным процессорам параллельного действия для решения краевых задач (Рига, 1981), Всесоюзном научно-техническом семинаре по развитию машинных методов и средств решения краевых задач (Донецк,1983), Всесоюзной школе-семинаре по прикладным методам расчета физических полей (Кацивели, 1984).
Материал в диссертационной работе изложен по следующей схеме.
В первом разделе рассматривается организация процесса реше-
ния на однородной вычислительной среде систем разностных уравнений, полученных аппроксимацией дифференциальных уравнений эллиптического и параболического типов методом конечных разностей.
Сопоставление параллельных численных методов и средств решения этих систем уравнений по ряду показателей позволяет сделать вывод о том, что весьма экономичной является организация вычислений на аналоговом сеточном процессоре. Однако эти преимущества теряются, если моделируемая сеточная область по своим размерам не вписывается в вычислительную среду.В этом случае для организации процесса решения предлагается использовать комбинации алгоритмов параллельного исключения неизвестных и многосеточного метода. При этом возникает проблема построения такой системы уравнений пониженного порядка, которая допустила бы применение вычислительной среды простой структуры. Проблема является принципиально новой для организации вычислений на аналоговом сеточном процессоре. В соответствии с этим сформулированы цель и задачи исследований.
Второй раздел посвящен разработке алгоритмических основ построения и функционирования специализированного вычислителя для решения систем разностных уравнений большой размерности. В качестве базы этих разработок использован предложенный автором метод модифицированной циклической редукции,являющийся комбинацией алгоритмов циклической редукции и метода релаксации Федорен-ко. Предложен математический аппарат описания процесса решения и управления вычислениями. Показано,что предлагаемый способ решения, основанный на параллельном исключении узлов исходной сетки, в отличие от известных способов, позволяет вместо полносвязной вычислительной среды использовать среду с диагональными связями. Разработаны основные положения безытерационной (режим аппроксимации) и итерационной схемы организации вычислений. Рассмотрено
- ІЗ -
несколько вариантов организации прямого и обратного ходов редукции.
В третьем разделе приводятся результаты экспериментальных и некоторых теоретических исследований по повышению эффективности алгоритмов решения и оптимизации организации вычислений. Предложены способы коррекции по минимизации методической погрешности и ускорению сходимости решения. Разработана итерационная схема организации вычислений с чередованием вариантов прямого хода редукции для эффективного решения задач с резко неоднородной моделируемой средой. Разработан вариант организации вычислений на структурах с упрощенной вычислительной средой без диагональных соединений. Приводятся краткие характеристики разработанных комплексов программ, реализующих этот вариант в программном уровне на АЦВК "Сатурн-1" и вычислительной системе ЭВМ ЕС-І022 со спецпроцессором "0мега-2М".
В четвертом разделе для предложенных вычислительных процессов получены оценки по количеству выполняемых арифметических операций и объему запоминаемой информации. Даны рекомендации по выбору параметров элементов аналогового сеточного процессора. Разработаны алгоритмы оптимальной организации хранения и поиска данных в памяти. Предложены специализированные структуры аналогового сеточного процессора и средств цифровой обработки информации.
В заключении сформулированы основные результаты диссертационной работы.
В приложениях помещены результаты решения ряда задач, полученные путем численного моделирования на ЭВМ или на АЦВК типа "Сатурн". Приводятся также текст и структура управляющих модулей разработанных комплексов программ.
