Содержание к диссертации
Введение
Глава 1. Краткий обзор современных программных технологий параллельных вычислений
1.1. Введение 14
1.2. Параллельные программные средства 18
1.3. Системы общего назначения
1.4. Проблемно-ориентированные системы 37
1.5. Глобальные проекты 40
Глава 2. Базовые вычислительные алгоритмы 44
2.1. Вычисления с плавающей точкой 44
2.2. Масштабирование 48
2.3. Структуры данных 53
2.4. Базовые матричные операции 56
Глава 3. Блочно-параллельные матричные алгоритмы 60
3.1. Матричные вычисления в задачах управления . 60
3.2. Быстрые матричные алгоритмы 64
3.3. Алгоритмы для симметрических матриц 67
3.4. Рекурсивное -разложение 72
3.5. Параллельное -разложение 80
3.6. Параллельные вращения 84
3.7. Рекурсивные вращения 96
3.8. Параллельные отражения 102
3.9. Организация вычислений 106
3.10. Параллельный алгоритм решения задачи оценки пара метров дискретной линейной системы управления 110
Глава 4. Уравнения в частных производных 113
4.1. Введение 113
4.2. Численное решение уравнение Пуассона 123
4.3. Параллельный алгоритм решения прямой задачи магнитотеллурики 152
4.4. Численное моделирование нестационарных течений многокомпонентных сжимаемых сред
4.5. Моделирование ядерных реакторов 172
Глава 5. Цифровая обработка изображений и сигналов 175
5.1. Параллельные вычисления в научной визуализации 175
5.2. Лучевая вычислительная томография 191
5.3. Численное моделирование переноса излучения 197
5.4. Объектно-ориентированная библиотека цифровой обработки сигналов "Спектр" 201
Список литературы 207
- Параллельные программные средства
- Вычисления с плавающей точкой
- Матричные вычисления в задачах управления
- Численное решение уравнение Пуассона
Введение к работе
Супер-ЭВМ и супер-вычисления являются, несомненно, важнейшим разделом современной науки о вычислениях. Основные области применения, а также основные достижения "суперов" связаны с большими научными и инженерными задачами. Потребность в супервычислениях появилась, по-видимому, одновременно с появлением первых ЭВМ. В классической работе [12] сформулированы требования к быстродействию ЭВМ для решения задач математической физики, актуальные и по сей день. Потребности таких наук, как ядерная физика, механика сплошных сред, классическая и квантовая электродинамика далеко обгоняют достигнутые вычислительные мощности.
В настоящее время выделился класс задач, называемый Grand Challenge [187], для решения которых требуются экстремально высокие вычислительные мощности. К ним относятся глобальное моделирование климата, вычислительная гидродинамика, квантовая хромодинамика, численное моделирование токамака и современного ускорителя со сверхнизкими потерями, создание новых материалов и другие задачи. Для их решения проводятся интенсивные исследования как в области создания математических моделей и алгоритмов, так и в области разработки новых параллельных вычислительных систем и усовершенствования существующих.
Важным классом больших задач являются задачи оптимального управления сложными объектами и процессами. В настоящее время такие задачи базируются практически на всем спектре современных численных методов [33].
Применение вычислительных методов линейной алгебры к задачам теории управления исследовалось в работах Х.Д. Икра-мова [39,40,41]. В частности, были рассмотренны задачи вычисления собственных значений, решения матричных уравнений различного вида, размещения полюсов линейных стационарных
систем. Решение каждой из указанных задач требует большого объема вычислений с плотными матрицами. Исследования алгоритмов линейной алгебры проводились в классической работе Уилкинсона [109], в работах В.В.Воеводина [20-25], Вл.В. Воеводина [26], Е.Е.Тыртышникова [106-108], Дж.Донгарры [124,184], Дж. Ортеги [70], в [47,61,64,112]. Различные аспекты сложности алгебраических алгоритмов исследовались в классической работе Штрассена [158], далее в работах А.О. Слисенко [80], В.И. Солодовникова [81,82], О.М. Макарова [62], см. также обзор В.Б. Алексеева [1] и приведенные там источники, в работах [5,13,20,51,56,60,164].Отмечается, что уменьшение показателя степени в выражении сложности алгоритма одновременно сопровождается ростом мультипликативной постоянной до астрономической величины. Это приводит к тому, что большинство быстрых матричных алгоритмов имеет чисто академический интерес.
Вопросы распараллеливания линейной алгебры исследовались в работах [42,57,77,125,149,162].
В качестве фундаментальных задач оптимального управления, для решения которых требуются супервычисления, можно указать следующие:
1). Управление сложными объектами и процессами с распределенными параметрами (управление ядерным реактором, сложными технологическими процессами, управление в экономике, медицине и т.п.).
2). Управление разведкой полезных ископаемых в геофизике.
3). Управление современным вычислительным экспериментом.
4). Управление сложным физическим экпериментом с использованием методов реконструктивной томографии.
5). Управление сложными системами с участием людей (со циальные проблемы, экология, эпидемии).
Легко усмотреть связь указанных задач управления с задачами Grand Challenge, поскольку управление сложным объектом должно базироваться на некоторой реалистической модели [55]. Это дает основание рассматривать современные задачи управления в общем контексте больших вычислительных задач, находящихся на переднем крае современной вычислительной науки.
Этот список далеко не полон. Важно отметить, что в основе методов решения данных задач лежит математическое моделирование с развитым набором численных алгоритмов и подходов. Базовыми методами для решения задач данного класса являются численные методы линейной алгебры, конечно-разностные мед-оды, методы оптимизациии и идентификации.
Вопросы управления системами с распределенными параметрами исследовались А.Г. Бутковским [11], Р.Беллманом [7], Р.П. Федоренко [103,110], в работах [69,73,153]. Большие задачи оптимизации были рассмотрены в [122,141, 145], задачи идентификации в [83-85]. Параллельные методы решения задач математической физики изучались в работах Н.Н. Яненко, А.Н. Андрианова, И.Б. Задыхайло,К.Н. Ефимкина [3,4,32], А.В.Забродина [31], И.Д. Софронова [87], О.М. Белоцерковского [8], в работах [9,37,38,45,46,49,63,67,69,112,121,152].
В то же время, для аудио- и видео- демонстрации результатов вычислений необходимо привлечение методов томографии и цифровой обработки сигналов и изображений, а также методы современной трехмерной графики [16,17,36,72,104,114,117,119, 148,165].
Достижения современной вычислительной математики и прогресс в области технологий, основанных на сверхбольших интегральных схемах, позволяет надеяться на значительный прорыв в сторону решения больших задач. Вследствие достижения практического предела повышения быстродействия элементной
базы, термин "супервычисления" стал вытесняться синонимом "параллельные вычисления", который и будет использоваться в данной работе. Появление параллелизма, т.е. дополнительной степени свободы в традиционной архитектуре ЭВМ, немедленно привело к большому разнообразию типов вычислительных систем. Этот процесс продолжает развиваться. В то же время процесс использования появившихся возможностей для решения больших научных задач гораздо более болезнен. Прогресс в разработке программных средств в принципе не может быть столь же стремительным, как в области элементной базы. Возникает вопрос — можно ли вообще сейчас (или в ближайшем будущем) воспользоваться в реальных вычислениях всеми теми возможностями, которые предоставляет современная элементная база. Положительный ответ на этот вопрос представляет собой наиболее актуальную задачу.
Суммируя сказанное, можно отметить три актуальных направления в проблеме " супервычисления в научных задачах".
1). Разработка современных численных методов (и анализ существующих) с ориентацией на параллельные вычисления, анализ их устойчивости, вычислительной сложности, технологичности.
2). Разработка и анализ моделей параллельных вычислений для анализа алгоритмов п.1, исследование емкостной и вычислительной сложностей в терминах параллельных элементов памяти и параллельных вычислительых операций.
3). Разработка технологических аспектов параллельного программирования и параллелизации накопленного программного обеспечения.
Современные технологии решения больших вычислительных задач были разработаны В.П. Иванниковым с сотрудниками [34, 35,135,136], А.Н. Андриановым, И.Б. Задыхайло, К.Н. Ефимки-ным [3,4,32], параллельные вычислительные технологии были пред ставлены в работах [48,49,50,58,66,75,79,105], см. также ссылки в главе 1.
Целью работы является разработка и исследование эффективных методов параллельных вычислений для широкого круга задач моделирования и оптимального управления, пригодных для достаточно широкого спектра архитектур параллельных ЭВМ
Основным параметром задачи является число процессоров W, выполняющих вместе одну и ту же задачу. Поскольку максимальный теоретический выигрыш в скорости равен W, возникает вопрос, как распорядиться этим числом. Первый подход предполагает не ограничивать W заранее, и связан с концепцией неограниченного параллелизма [20]. В рамках этой концепции, представляющей чисто академический интерес, решаются задачи о нижних границах вычислительной сложности параллельных алгоритмов. Второй подход, более реалистический, предполагает, что величина W заведомо ограничена. Для решения задачи с характерным параметром размерности N наиболее реальным является случай промежуточной асимптотики 1 С И С iV ( є = W/N — малый параметр).
В работе принята следующая иерархическая вычислительная модель:
1). Элементарным устройством является "численный модуль" (кластер), расположенный на нижнем уровне иерархии. В рамках декомпозиции исходной задачи кластер решает задачи самого нижнего уровня. Основное требование здесь — эффективность, т.е. задача нижнего уровня должна быть хорошо согласована с архитектурой кластера.
В работе полагается, что численный кластер представляет собой паралельний процессор типа ОКМД (SIMD) — общий поток команд, множественный поток данных — с простой топологией связи в виде кольца.
Будем считать, что численный кластер состоит из W элементарных процессоров, каждый из которых имеет собственную локальную память глубины h. Таким образом, имеем естественные масштабы W, h, характеризующие систему. Хотя каждый кластер имеет архитектуру ОКМД, в работе не делается предположения о внешней глобальной синхронизации. Вполне допустим случай, когда каждый процессор управляется своей копией одной и той же программы. Хотя формально режим вычислений является асинхронным (МКМД — множественные потоки команд и данных), во многих важных случаях характерное время рассогласования вычислений в разных процессорах можно считать малой величиной по сравнению с общим временем работы программы.
2). Кластеры нижнего уровня объединяются в кластеры следующего уровня, которые, в свою очередь, образуют еще более высокий уровень, и т.д. На верхнем уровне находится вычислительная система, решающая исходную задачу. На каждом промежуточном уровне не делается никаких предположений о топологии связей между кластерами. Единственное, что считается известным — характерные размеры каждого уровня по ширине (W1) и по памяти( hi) в в терминах кластеров следующего по глубине уровня. Полезным является также предположение о том, что на каждом уровне работает рассмотренный выше режим псевдо-ОКМД.
3). Число промежуточных уровней не фиксируется и может определяться либо параметрами вычислителя (при решении задачи на "готовой" ЭВМ), либо в результате решения задачи проектировния оптимальной архитектуры под заданные вычисления.
Выбор базовой архитектуры ОКМД основывался на следующих соображениях:
1). Данная архитектура соответствует наиболее простой и
ясной концепции параллелизма. Это позволяет построить достаточно продвинутую теории сложности ОКМД-вычислений.
2). Данная архитектура является оптимальной для широкого круга численных методов линейной алгебры, разностных схем, задач управления и оптимизации, которые находятся на переднем крае прикладной математики.
3). Программы для ОКМД-вычислителей могут рассматриваться как естественные обобщения последовательных программ, поэтому проблемы переносимости (трансфера) решаются проще, чем в случае иных архитектур.
4). ОКМД-архитектура проще в аппаратной реализации.
Методы исследования настоящей работы опираются на современные методы вычислительной математики, математического моделирования и анализа алгоритмов. Для исследования вопросов программной реализации учитывались современные вычислительные технологии, например, объектно-ориентированное программирование, библиотеки передачи сообщений.
Научная новизна работы связана с разработкой и исследованием новых параллельных вычислительных алгоритмов для решения широкого круга задач теории управления и идентификации. Для этого проивлекаются методы динейной алгебры, теории разностных схем, математического моделирования. Важное место в работе отводится построению цифровых изображений, а также вычислительной томографии. Основанием для этого является тот факт, что полное решение задачи управления включает в себя представление результатов в наглядном виде, часто требуется и решение обратной задачи. Во всех случаях выполнялось исследование временной сложности предлагаемых параллельных реализаций и выполнялись численные эксперименты. Во многих случаях были выполнены решения реальных задач.
Практическая ценность результатов работы определяется
тем, что в настоящее время параллельные вычислительные устройства являются доступными широкому кругу непрграммирующих специалистов. Это связано с внедрением сетевых технологий, удешевлением компонентов, повышением компьютерной грамотности научного сообщества.
Реализация результатов работы осуществлена при решении задач магнитотеллурики, физической гидродинамики, численного моделирования системы управления ядерным реактором, обработки данных виброиспытаний, компьютерной томографии. Эти исследования проводились совместно с ВНИИ Неф-тегеофизика, НПО "Энергия", ИАЭ им. И.В. Курчатова, ВНИ-ИЭФ, Институтом прикладной физики, г. Новосибирск.
Апробация работы.
Основные теоретические и практические результаты диссертации докладывались на международных, всесоюзных и республиканских конференциях, симпозиумах и семинарах, в том числе на Всесоюзном научно-техническом совещании " Проблемы создания и использования высокопроизводительных информационно-вычислительных машин" (Кишинев, 1979г.), 3-й,4-й и 5-й Всесоюзных школах-семинарах "Распараллеливание обработки информации" ( РОИ-81, РОИ-83, РОИ-85, г. Львов), 4-й и 5-й Всесоюзных школах " Многопроцессорные вычислительные системы" (Звенигород, 1981, 1983 гг.), 4-й международной научно-технической конференции "Вычислительная техника-83 — Микропроцессорные системы (Пловдив, 1983 г.), 9-м Всесоюзном совещании по проблемам управления (Ереван, 1983 г.), 3-м симпозиуме " Методы решения нелинейных уравнений и задач оптимизации" (Таллинн, 1984 г.), Всесоюзном научно-техническом семинаре " Программное обеспечение многопроцессорных систем" (Тверь, 1985г.), Всесоюзной конференции "Высокопроизводительные вычислительные системы для комплексных центров Математического моделирования" (Новосибирск, Академгоро док, 1989 г.), Международной конференции " Технологические средства создания систем управления" (Кяэрику, 1992г.), 15-м семинаре по однородным вычислительным системам и систолическим структурам (Львов, 1992 г.), Национальных конферн-циях с международным участием "Автоматика и информатика-95", "Автоматика и информатика-96" (София, 1995, 1996 гг.), На Международной конференции "Идентификация систем и задачи управления" (Москва, ИПУ РАН, 2000г.)
Публикации.
По теме диссертации опубликованы работы [6,17,18,28,43,44, 74,86,88-102, 160.161].
Объем и структура работы.
Диссертация содержит 206 стр. текста, включая рисунки. Текст разделен на введение, 5 глав, и список литературы из 197 наименований.
В главе 1 приводится краткий обзор современных параллельных и распределенных вычислительных технологий. Отмечается доступность распределенных вычислений на разнородных компьютерах, соедененных сетью EtherNet. В то же время вопрос о максимальной производительности, которая может быть достигнута в таком режиме, остается открытым.
В главе 2 приводятся базовые положения параллельных вычислений, которые легли в основу настоящей работы и исследуются основные алгоритмы. Отмечается важное значение вычислений с плавающей точкой в безаварийном режиме. Предлагается методика вычислений с последовательно увеличивающимся динамическим диапазоном. Обосновывается необходимость блочно-рекурсивного (клеточного) подхода к большим задачам линейной алгебры, решаемым на параллельных вычислительных системах.
В главе 3 рассматриваются блочные (клеточные) алгоритмы,
предназначенные для решения больших задач линейной алгебры. Все алгоритмы приводятся в рекурсивной формулировке. Исследованы как классические, так и быстрые (сложности 0(nlog7)) алгоритмы. Приводится параллельный алгоритм решения задачи оценки параметров дискретной линейной системы.
В главе 4 представляются параллельные разностные алгоритмы для решения задач математической физики. Исследуются задачи быстрого численного решения уравнения Пуассона, задача магнитотеллурики, задача течения многокомпонентной сжимаемой среды на основе нового метода " индивидуальных частиц", задача решения уравнения диффузии, необходимая при моделировании кинетики ядерного реактора. Решение данных задач на вычислительном комплексе ПС-2000, разработанном в Институте позволило получить решение задач, недоступных традиционной вычислительной технике.
В главе 5 рассматриваются задачи, связанные с построением и обработкой сигналов и изображений. Здесь рассмотрены задачи синтеза трехмерных изображений, связанных с визуализацией результатов численных экспериментов по моделированию сплошных сред. Исследованы задачи вычислительной томографии на основе лучевого подхода и подхода на основе метода Монте-Карло моделирования распространения фотонов в среде. Предложены вычислительные технологии на основе объектно-ориентированного подхода, предназначенные для параллельных вычислений при решении больших задач.
Параллельные программные средства
В настоящее время деятельность по разработке параллельных программных средств ведется не автономно, а в рамках многочисленных объединений, коллабораций, консорциумов и т.п. Каждое такое объединение включает представителей крупных научных лабораторий, университетов, производственных и финансовых фирм. Издаются труды, имеются Web-страницы. Количество публикаций растет лавинообразно.
Наиболее авторитетным объединением такого рода является РТС (Parallel Tools Consortium) [187]. РТС — это коллаборация исследователей, разработчиков и пользователей параллельного программного обеспечения. Собирает, систематизирует и анализирует всю информацию о параллельном программном обеспечении.
Отмечается, что средства параллельных вычислений (parallel tools) в настоящее время используются вычислителями, решающими большие задачи. Здесь важны три мешающих фактора. 1. Современные средства параллельного программирования не соответствуют требованиям научных вычислителей, которым приходится становиться попутно специалистами по вычислительной науке. 2. Одновременное наличие многих аппаратных платформ затрудняет переносимость программ. 3. Недостаток специальных программных средств поддержки гетерогенных и масштабируемых параллельных вычислений отталкивает программистов от работ в этом направлении. Консорциум призван объединить усилия федеральных, промышленных и академических кругов для исправления положения в данной области. Согласно идеологии РТС, параллельные программмные средства (ППС) могут быть классифицированы по функциям следующим образом: 1) Анализаторы исходного кода анализируют исходный последовательный программный текст и приводят его к параллельному виду. 2) Параллельные языки и библиотеки позволяют программисту пользоваться специальными расширениями традиционных языков программирования. 3) Анализаторы выполнения включают в себя отладчики, ви-зуализаторы прогонов программ и анализаторы производительности. Эта классификация является весьма условной. Возможны ППС, объединяющие в себе сразу несколько функций. Другая классификация может быть связана с целевыми назначениями ППС. На данном этапе здесь просматриваются следующие группы: 1). Концептуальные ППС, призванные внедрять новые парадигмы параллельного программирования. 2). ППС общего назначения, одинаково пригодные для решения всех задач. 3). Проблемно-ориентированные ППС, призванные особенно эффективно решать задачи из какой-либо предметной области (линейная алгебра, разностные методы, моделирование аэродинамической трубы и т.д.). Дадим краткий обзор основных программных средств по каждой категории, после чего более детально рассмотрим наиболее интересные решения. Параллельные языки и анализаторы исходного кода. Традиционой областью параллельных вычислений является создание новых параллельных языков высокого уровня (в меньшей степени ) и добавления средств распараллеливания в Фортран и С. Эти средства могут быть в виде расширений синтаксиса языка за счет новых операций и макросов и в виде встроенных анализаторов кода. Анализаторы кода анализируют исходный последовательный программный текст и приводят его к параллельному виду. При этом могут использоваться как чисто встроенные анализаторы (программист не видит параллельной программы), так и отдельно стоящие, выход которых поступает на вход распараллеливающему компилятору. Все достижения в этой области связаны с более или менее удачным распараллеливанием циклов. Преимуществом данного подхода является то, что исходный текст программы не изменяется, что важно в случае использования стандартного программного обеспечения. Другим направлением является обогащение языков средствами управления параллельными вычислительными процессами. Такие средства поддерживают модель МКМД и используют терминологию процессов (цепочек управления). Основными средствами управления является синхронизация, доступ к ресурсам и обмен сообщениями. Средства синхронизации. Барьер — точка в программе, где все процессы приостанавливаются и ждут выполнения какого-либо условия для возможности продолжения работы. Глобальный барьер обеспечивает это продолжение только в том случае, если все процессы достигли данной точки. Может использоваться и частный барьер — продолжение работы (всеми) возможно если хотя бы один процесс достиг данной точки. Управление событиями — процессы ждут наступления определенного события. Семафоры — стандартный дийкстровский механизм управления взаимодействующими процессами. Средства доступа. Важной задачей является обеспечение доступа к разделяемым ресурсам. Основным понятием является критический участок, который должен выполняться без прерываний только одним процессом. В зависимости от особенностей доступа критические участки могут быть простыми, спаренными и упорядоченными. Во всех случаях для работы с критическими участками используется механизм замков, подобных семафорам.
Вычисления с плавающей точкой
Известно, что все научные вычисления можно разделить на два частично пересекающихся множества в зависимости от того, с какими объектами проводятся исследования.
К первому множеству относятся задачи моделирования, которые оперируют с моделями некоторых классов объектов или явлений. Исходными данными таких задач являются, как правило, безразмерные параметры, составленные из характерных величин объектов и физических констант в соответствии с методами размерности и подобия. Эти исходные данные принципиально можно задать с любой степенью точности. Вследствие этого, при использовании аппробированных устойчивых алгоритмов, всегда можно оценить ту точность исходных данных, которая дает требуемую точность результатов. С вычислительной точки зрения это приводит к необходимости вычислений (при решении больших задач) с длинной разрядной сеткой. Имеется устойчивая тенденция удлинения разрядной сетки в современных суперкомпьютерах, которая сдерживается только техническими и стоимостными соображениями. К примеру, в [118] рассматриваются задачи, для которых требуется 10000-разрядная арифметика.
Ко второму множеству относятся задачи, условно говоря, обработки данных экперимента. Исходные данные таких задач относятся к единичному объекту или явлению и известны с конечной, часто небольшой, точностью. В этом случае даже для хорошо обусловленных (устойчивых) алгоритмов может ощущаться нехватка точности исходных данных. Здесь может помочь экстраполяция точности исходных данных до размера используемой разрядной сетки. Для устойчивых алгоритмов и задач это проходит.
Другая ситуация имеет место в случае плохо обусловленных задач. Здесь никакое увеличение разрядной сетки само по себе не дает результатов, и требуется применять методы регуляризации. Эти методы позволяют привести в соответствие точность исходных данных и точность получаемых результатов. При этом требуется весьма умеренная по ширине разрядная сетка, которая также определяется точностью исходных данных. Здесь открываются возможности применения недорогих малоразрядных вычислителей.
В данной главе рассматриваются особенности вычислений с плавающей точкой при реализации базовых вычислительных алгоритмов.
Известна важность вопроса о вычислительной погрешности при выполнении крупномасштабных расчетов. Теоретическому анализу этого вопроса посвящены работы [19,65,68,78,109]. Обычно в литературе любую вычислительную погрешность называют "погрешностью округления". Это, конечно, не совсем корректно. В буквальном смысле слова погрешность округления связана с событиями на границе между "хвостом мантиссы" (который усекается) и ее последним сохраняемым разрядом. Как показано в [6], эта погрешность может иметь решающее значение при работе на малоразрядных ЭВМ.
Помимо основных действий действительной и комплексной арифметики, необходимо корректно и быстро производить некоторые операции, характерные для матричных алгоритмов. Рассмотрим эти операции. 1). Накопление с двойной точностью (флоп) с = ах + Ь, где a, b,c,x — комплексные числа. Применение такой операции позволяет удобно организовывать вычисление скалярного произведения.
Пусть вектор размерности N расположен в памяти модуля послойно, т.е. первые W компонент — по адресу 1, следующие — по адресу 2, и т.д. Весь вектор займет, таким образом, N/W суперслов памяти модуля. Здесь и далее будем предполагать, что N кратно W. Тогда сложение двух векторов потребует N/W параллельных сложений (флопов для х = 1), а умножение вектора на константу потребует столько же параллельных умножений (флопов для 6 = 0). В дальнейшем для краткости всюду будем опускать слово "параллельное", понимая для каждого арифметического действия его параллельный аналог. Обоснованием для этого служит тот факт, что время выполнения операции не зависит от того, сколько процессоров ее одновременно выполняют. 2). Вычисление обратной величины с одинарной и двойной точностью. Применение такой операции с серией последующих умножений значительно экономичнее деления. 3). Извлечение квадратного корня из вещественного числа с одинарной и двойной точностью. Эта операция часто требуется при решении систем линейных алгебраических уравнений и вычислении норм. Указанные операции могут быть реализованы как программным, так и аппаратным путем [57,146].
Матричные вычисления в задачах управления
На основе рассмотренного выше пирамидально-рекурсивного представления матриц и связанных с ними алгоритмов была разработана библиотека классов РЕКЛАБ (Рекурсивная лаборатория). В качестве рабочего инструмента было выбрано объектно-ориентированное программирование (ООП) в системе МАТЛАБ. В настоящее время ООП начинает активно использоваться при решении больших задач на параллельных и распределенных вычислительных системах [170,171,173,191]. Это объясняется такими качествами ООП, как возможность быстрой модификации при изменениях в постановках задач, переносимость, в том числе от традиционных компьютеров к параллельным, возможность написания кодов для многократного использования. В качестве основных классов в библиотеке фигурируют разбиваемые векторы и матрицы, причем требуемая структура разбиения (пирамида) задается глобальным вектором, состоящим из величин ki,k2,---,kr. При этом само построение пирамиды происходит динамически, синхронно с работой вычислительного алгоритма. В качестве методов классов были выбраны базовые алгоритмы линейной алгебры. Основные из них, сложность которых равна 0(N3), были рассмотрены в предыдущем параграфе.
Результаты вычислений полностью подтвердили справедливость приведенных выше формул для размерностей до 1000. Это дает основание для их экстраполяции в область больших размерностей. На рис. 3.4.1 представлена зависимость TLLT/NZ ОТ порядка матрицы N для полного квадродерева (к = 2) при различной глубине рекурсии. Видно, что при N 1000 кривые стремятся к асимптотическим значениям в окрестности величины 0.5. Для сравнения на том же графике показана кривая для числа операций в нерекурсивном случае с асимптотическим значением равным 0.33. Таким образом, применение рекурсии даже значительной глубины требует менее чем двукратного увеличения числа операций по сравнению с нерекурсивными вычислениями. Аналогичный вид имеют кривые и для других значений к.
На рис. 3.4.2 представлены зависимости той же величины на асимптотической размерности от глубины рекурсии при различных значениях основания к. Максимальная глубина рекурсии по горизонтальной оси соответствует полному разбиению, при котором порядок терминальной матрицы равен к. При этом условии увеличение высоты пирамиды, т.е. числа уровней рекурсии не изменяет принципиально хода кривых, а лишь удлиняет горизонтальный участок (эффект "отложенной сложности").
На рис. 3.4.3 даны зависимости числа операций по переносу данных от размерности приразличных глубинах рекурсии, а на рис. 3.4.4 — зависимости той же величины от глубины рекурсии для полной пирамиды при различных основаниях. Ход этих кривых аналогичен кривым на рис. 3.4.1-3.4.2. Отметим, что для универсальности используется нормировка Г/ап3, где а — параметр, зависящий от реализации (в нашем случае а — 4).
Рассмотрение указанных кривых позволяет сделать вывод о несущественном увеличении числа требуемых арифметических и переносных операций при использовании пирамидально-рекурсивных структур по сравнению с нерекурсивными вычислениями. Это дает основание полагать, что применение параллельных вычислительных систем даст значительный выигрыш в быстродействии, поскольку приведенные накладные расходы могут быть в значительной степени компенсированы увеличением числа процессоров. Что касается реального времени вычислений, то оно целиком определяется аппаратурной реализацией.
Предложенные выше пирамидально-рекурсивные структуры данных и связанные с ними алгоритмы естественным образом отображаются на многоуровневые клеточные разбиения больших матриц при решении систем линейных алгебраических уравнений. Применение таких разбиений неизбежно при решении алгебраических задач на параллельных и распределенных вычислительных системах. В то же время рекурсивная формулировка позволяет записать клеточные алгоритмы в простом и элегантном виде, что резко ускоряет программную реализацию, особенно при использовании объектно-ориентированного подхода.
Приведенные оценки показывают приемлемое увеличение сложности алгоритмов при использовании рекурсии, заключающееся в увеличении мультипликативной постоянной при члене п3 в выражении для числа операций. Этот вывод относится как к полезным вычислительным операциям, так и к операциям переноса данных, связанным с формированием клеточных структур.
Численное решение уравнение Пуассона
Первая часть алгоритма (до оператора с меткой 1) вычисляет вспомогательные массивы CS и ЕТ, по формулам прямого хода прогонки. Вторая часть осуществляет обратный ход. Результат получается на месте исходного массива U.
После того, как сделан первый дробный шаг, выполняется транспонирование массива t/,после чего делается второй дробный шаг по точно такому же алгоритму. Заметим, что на этом шаге используется другой массив F и другое значение коэффициента В. Все эти массивы, естественно, рассчитываются в режиме предварительных вычислений.
Из алгоритма видно, что он поддается практически полному распараллеливанию. Накладными расходами являются операции транспонирования. При более сложных краевых условиях целесообразно использовать скошенную форму.
Пусть имеется W = 2W одинаковых процессорных элементов (ПЭ), синхронно выполняющих команды из общего потока. Выполнение каждой такой команды порождает "супероперацию" - покомпонентную операцию над вектором размерности W (суперсловом), каждая компонента которого находится в отдельном ПЭ.
При реализации алгоритма необходимо принять во внимание, что существует два основных режима проведения вычислений [74].
Если предполагается эпизодически решать несвязанные между собой задачи различного типа, различной размерности, то необходимо каждый раз, начиная с нуля, проводить весь комплекс вычислений для конкретной решаемой задачи. В этом случае при выборе алгоритма принимаются во внимание, как правило, многие факторы, такие, как время счета, необходимый объем памяти, логическая сложность и т.д.
Другое дело, если приходится решать большое количество однотипных задач, например, задач с фиксированной сеточной областью, но с различными правыми частями. Такая ситуация часто возникает при решении разностных задач эволюционного типа, нелинейных задач, при работе в реальном масштабе времени. В этом случае главной задачей является минимизация времени вычислений. Можно вычислить значительную часть величин, необходимых для решения, один раз и хранить их в памяти ЭВМ. Такое предварительное вычисление обычно называется препроцессингом.
