автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Расчет газодинамических течений с применением нерегулярных сеток на параллельных вычислительных системах

Оглавление.

Введение.

Глава 1. Постановка задачи.

Описание рассматриваемых задач.

Кинетически-согласованные разностные схемы.

Описание расчетного алгоритма.

Параллельная реализация алгоритма.

Глава 2. Балансировка загрузки.

Геометрический параллелизм.

Иерархический алгоритм разбиения графов.

I этап. Огрубление графа.

II этап. Разбиение графа.

III этап. Восстановление графа.

Параллельная реализация алгоритма.

I этап. Огрубление графа.

II этап. Разбиение графа.

III этап. Восстановление графа.

Двухуровневая схема работы с большими сетками

Глава 3. Результаты расчетов.

Расчет газодинамических течений.

Разбиение нерегулярных сеток.

Используемые технические и программные ресурсы Заключение.

В диссертации рассматриваются вопросы эффективного использования больших параллельных вычислительных систем при моделировании газодинамических течений с применением нерегулярных расчетных сеток.

Математическое моделирование и вычислительный эксперимент на сегодняшний день играют немаловажную роль в физических и других научных исследованиях. Ни для кого не секрет, что грамотное проведение математических расчетов помогает сэкономить массу времени и материальных средств при выполнении реальных экспериментов, предваряя и существенно облегчая их, а иногда и заменяя полностью. Появление и активное развитие теории и практики численных методов и разностных схем в последние несколько десятилетий было подкреплено столь же бурным развитием вычислительной техники, взявшей на себя непосредственное проведение численных операций и предоставившей таким образом совершенно новые возможности для науки. Каждый очередной виток в процессе усовершенствования вычислительных систем, приводящий к значительному увеличению темпов и объемов вычислений, позволяет открывать все новые горизонты в этой области исследований.

Анализ математических моделей многих задач вычислительной физики показывает, что для их решения необходимо задействовать вычислительные системы как можно большей производительности. С течением времени возможности электронной техники все увеличиваются, и одновременно с этим возрастают и требования, предъявляемые к численным результатам решений конкретных задач. Объемы вычислений постоянно растут: повышается точность получаемых количественных характеристик, особенно критических, предельных значений величин, степень детализации в описании картины физических явлений. Усложняются и сама постановка задачи, и математический аппарат, применяемый в моделировании.

Порой увеличение точности расчетов приводит даже к обнаружению новых, неизвестных ранее явлений и свойств исследуемых объектов.

Пока на протяжении нескольких десятилетий в архитектуре ЭВМ доминировала концепция Фон-Неймана, теория численных методов занималась в основном «классическими» вопросами существования и сходимости численных решений, теми или иными свойствами методов и разностных схем, увеличением точности получаемых результатов по отношению к объему производимых вычислений. Для решения задач из самых разных областей науки было разработано огромное количество алгоритмов, многие из которых являлись по характеру своего построения сугубо последовательными.

Качественный скачок в развитии вычислительной техники произошел с появлением и распространением параллельных систем, когда стало возможным производить расчеты в рамках одной задачи одновременно на нескольких вычислительных модулях. И оказалось, что новыми возможностями, которые техника предоставила ученым, не так легко воспользоваться. Для обеспечения эффективного использования всех одновременно участвующих в работе процессоров потребовалось специальным образом строить новые расчетные алгоритмы или адаптировать уже имеющиеся, рассчитанные на работу в последовательном режиме [8,27]. За прошедшее время в данной области проделана большая теоретическая и практическая работа, и она активно продолжается по сей день.

В принципе, параллелизм как способ увеличения скорости совершения различных действий путем одновременного выполнения соответствующих операций сразу на некотором множестве устройств, имеет длинную историю. В определенной смысле его можно наблюдать уже на уровне выполнения простейших команд микропроцессором. Сегодня практически все вычислительные системы в той или иной форме используют методы совмещения операций: совмещаются процессы выборки из памяти команды и ее операнда, осуществляется опережающий просмотр исполняемой программы и одновременно выбирается несколько команд и операндов, на разных функциональных устройствах параллельно выполняются арифметические операции или элементы этих операций. Наконец, на разных процессорах совмещается выполнение разных задач или их частей. Вычислительные системы, базирующиеся на принципах параллельной обработки информации, призваны удовлетворять все более растущие требования пользователей к таким характеристикам вычислительных средств, как быстродействие, надежность, точность. Но большие потенциальные возможности таких систем могут быть полностью раскрыты и использованы только после тщательного анализа всех аспектов организации вычислений: от создания математических методов до реализации прохождения в системе соответствующим образом построенных параллельных программ [27].

Со временем в архитектуре параллельных вычислительных систем возникло значительное разнообразие, и она приобрела уже свою собственную классификацию [32]. Разработчики системного и прикладного программного обеспечения всегда были вынуждены учитывать конкретные особенности той или иной системы и находить внутри структуры вычислительных алгоритмов возможности распараллеливания, оптимально использующего эти особенности. В настоящей работе речь будет идти только о многопроцессорных системах с архитектурой MIMD (multiple instructions, multiple data). Для этих систем характерно то, что процессоры работают асинхронно и в любой момент времени выполняют, вообще говоря, разные операции над разными данными.

Центральная проблема, возникающая при использовании такого рода систем, - это обеспечение равномерной загруженности вычислениями всех процессоров, участвующих в совместной работе. Иначе говоря, необходимо создать такие условия, при которых каждый из процессоров как можно большее время находился бы в состоянии счета и как можно меньшее - в состоянии простоя (т.е. в ожидании следующих инструкций или данных - результатов работы других процессоров). Этим, собственно, и определяется в первую очередь эффективность использования параллельной системы, или же эффективность распараллеливания алгоритма. Задача равномерного распределения нагрузки по процессорам получила название проблемы балансировки загрузки (load balancing).

Методы осуществления балансировки загрузки подразделяются в первую очередь по двум критериям: где и когда решается эта задача [23]. Выделяют следующие основные типы:

• Централизованная (глобальная) балансировка загрузки - выполняется в целом для всех процессоров и всего объема распределяемой нагрузки.

• Диффузная (локальная) - каждый из процессоров решает эту задачу для себя самостоятельно либо с участием нескольких других процессоров.

• Статическая - выполняется единовременно, до начала основной работы, для решения которой проводится.

• Динамическая - уже в процессе основной работы балансировка может при необходимости повторяться, частично или полностью.

В диссертационной работе рассматриваются методы статической глобальной балансировки загрузки применительно к решению вполне определенного класса задач, а именно к расчетам газодинамических течений на нерегулярных сетках.

Чтобы в любой момент времени обеспечить все задействованные процессоры работой, нужно поделить общую решаемую задачу на некоторое количество подзадач, вычисления внутри которых относительно независимы и могут выполняться одновременно на разных процессорах. Такое разделение может проводиться как по множеству обрабатываемых данных, так и по объему производимых над ними операций. Существует ряд методов распараллеливания, каждый из которых подходит для своего класса решаемых задач и соответствующих алгоритмов [23,37].

Зачастую можно выделить в общем процессе решения задачи отдельные этапы, находящиеся в зависимости друг от друга и выполняемые поэтому в строгой временной последовательности, так что все вычисления внутри одного из них с одной стороны требуют завершения предыдущих этапов и с другой стороны в свою очередь должны быть завершены до начала последующих. Тогда распараллеливание производится внутри одного такого этапа как фактически отдельной задачи. Нередко такая подзадача заключается в выполнении одинаковых вычислительных операций над большим множеством однотипных данных. В этом случае наиболее естественным представляется распределить суммарный объем обрабатываемых данных поровну по всем процессорам (насколько это возможно). Вычислительная нагрузка окажется одинаковой, и все процессоры закончат выполнение расчетов практически одновременно.

При численном решении многих задач математической физики, и не только их, возникает ситуация как^аз указанного типа. Нахождение физических величин на всем протяжении исследуемой области проводится синхронно по временным шагам. Расчеты газодинамических течений, рассматриваемые в настоящей работе, являются характерным примером такого рода задач. На каждом шаге по времени во всех узлах расчетной сетки проводится решение разностных уравнений, при этом выполняется набор схожих операций. Традиционно параллельное решение этих задач обеспечивается разбиением всей расчетной сетки на части и последующим распределением ее по процессорам. Поскольку при этом вся исследуемая область пространства делится на соответствующие подобласти, метод получил название геометрического параллелизма (domain decomposition).

Немаловажную роль здесь играет также выбор вычислительного алгоритма. Наиболее удобными для равномерной загрузки процессоров являются однородные разностные схемы, так как они позволяют проводить вычисления в каждом из узлов расчетной сетки по единому алгоритму.

Тем самым, осуществление балансировки загрузки сводится к равномерному распределению узлов сетки по всем используемым процессорам, то есть к разбиению сетки на соответствующее число частей одинакового размера.

Новый этап в развитии вычислительной техники начался с появлением систем с распределенной памятью, состоящих из практически независимых вычислительных модулей, связанных между собой специальными каналами связи для обмена данными. Такое решение оказалось плодотворным по целому ряду причин. Во-первых, стоимость систем с разделяемой памятью резко повышается с ростом числа процессоров. Увеличение количества процессоров в системе приводит к техническим сложностям в использовании ими общих системных ресурсов, в первую очередь оперативной памяти. Организация доступа к одному и тому же блоку памяти нескольких процессоров является очень непростой с технической точки зрения задачей, связанной с необходимостью обеспечения синхронизации и другими специфическими проблемами. Поэтому системы с распределенной памятью обладают сравнительно низкой удельной стоимостью, то есть меньшим отношением цены к суммарной производительности. Кроме этого, следует отметить другое важное свойство этих систем - масштабируемость. В любой системе с общей памятью максимально возможное число устанавливаемых в ней процессоров так или иначе фиксировано. На сегодняшний день этот предел составляет около 20-30 единиц. Системы же с распределенной памятью можно наращивать практически неограниченно, причем постепенно, по мере улучшения материальных возможностей. К тому же аппаратная независимость отдельных модулей повышает общую надежность системы в целом: если некоторые из них находятся в нерабочем состоянии, это никак не влияет на возможность нормальной работы других.

Появление систем с распределенной памятью породило новые, особенные трудности в разработке параллельных программ [20]. Для достижения высокой эффективности использования этих систем необходимо предельно уменьшить объем и частоту обменов данными между отдельными модулями, поскольку для осуществления межмодульной пересылки данных требуется весьма значительное (по сравнению с доступом в память) время. Кроме того для организации такой пересылки требуются и определенные ресурсы памяти, и участие процессора либо другого специального устройства. Возникают накладные расходы, которые никак нельзя отнести к полезной вычислительной нагрузке. В принципе, почти все системы, начиная с широко известных в свое время транспьютерных [30], позволяют одновременно производить вычисления и пересылать данные, стоит лишь предусмотреть это при разработке алгоритма и написать адекватную программу, в которой была бы реализована указанная возможность [25]. И то и другое не совсем тривиально. Отметим однако важность использования специальных средств передачи и синхронизации, при наличии таковых, для обмена данными на фоне полезных вычислений.

Таким образом, проблема балансировки загрузки разделилась на две составляющие: с одной стороны, обеспечение равномерной занятости процессоров вычислительной работой, с другой - также равномерное распределение дополнительной нагрузки, связанной с пересылками общих используемых данных между различными модулями системы, одновременно с максимальным сокращением этих дополнительных действий. При этом обе задачи - балансировка вычислительной загрузки и снижение нагрузки коммуникационной - как правило не являются независимыми и должны решаться совместно.

Сравнительная легкость наращивания мощности многопроцессорных систем с распределенной памятью обернулась возникновением и множества других специфических проблем. В результате эффективное использование систем массового параллелизма до сих пор требует значительных усилий и возможно далеко не для всех типов задач. За прошедшие годы в решении обозначенных выше проблем адаптации последовательных алгоритмов достигнуты ощутимые успехи. Однако, несмотря на наличие сегодня алгоритмов и программ, имеющих весьма высокую (часто более 90%) эффективность распараллеливания, типичный коэффициент интегральной загрузки большинства систем массового параллелизма составляет, по разным оценкам, всего от 10% до 30%.

При переходе на новую технику значительно возрастает нагрузка на разработчиков прикладного программного обеспечения. Ситуация усугубляется отсутствием привычных инструментов разработки программ (удобных средств отладки, интегрированных сред программирования и т.п.) и анализа получаемых результатов. Аналогичные сложности испытывает и системный администратор, отвечающий за функционирование комплекса. Первое приводит к значительным затратам на адаптацию уже не алгоритмов, но рабочего коллектива к новой ситуации. Этот процесс может занимать весьма длительный период времени, исчисляемый иногда месяцами, если не годами. Второе проявляется в многочисленных простоях вычислительной системы, даже в условиях наличия достаточного набора заданий, способных в принципе обеспечить ее загрузку вплоть до 100%, так как служба системного администрирования просто не в состоянии обеспечить эффективную дисциплину запуска задач без соответствующего системного обеспечения, а оно нередко отсутствует [21].

Впрочем, ситуация имеет тенденцию к постепенному улучшению. Если еще в прошлом десятилетии массово-параллельные вычислительные системы создавались как уникальные экземпляры в исследовательских центрах, то в настоящее время многопроцессорные машины - основа продукции многих преуспевающих компьютерных фирм. Эта эволюция в первую очередь обусловлена прогрессом микроэлектроники, превратившим интеллектуальные элементы построения ЭВМ - микропроцессоры, микросхемы памяти, адаптеры внешних устройств - в массово доступные. Значительное продвижение наблюдается также в развитии коммуникационной среды - и протоколов связи, и аппаратной части: высокоскоростных соединительных кабелей, специальных эффективных коммутирующих устройств, позволяющих упростить топологию связей между вычислительными модулями системы [24].

Немалая работа проделывается международным сообществом в плане стандартизации интерфейсов - как на уровне взаимодействия между различными физическими устройствами, так и на уровне программного обеспечения. Определенные наработки в этой области существуют не только у таких организаций, как ANSI или IEEE, но и у отдельных производителей. В качестве удачного примера можно привести систему программирования Parix (Parallel Unix) [66] немецкой фирмы Parsytec, продукция которой используется в Институте математического моделирования на протяжении последних нескольких лет [37]. На текущий момент фактическими стандартами интерфейсов прикладных параллельных программ для систем с распределенной памятью стали PVM (Parallel Virtual Machine) и MPI (Message Passing Interface) [53-55]. Оба стандарта включают в себя возможность асинхронных передачи и приема данных, а также средства синхронизации и широковещания. Последний из них является относительно более новым и, по всей видимости, более предпочтительным интерфейсом, активно развиваемым в настоящее время. Существование таких стандартов сводит к минимуму расходы на адаптацию прикладного программного обеспечения при его переносе между многопроцессорными системами разных серий и фирм. Все программы, разработанные в данной диссертации, способны работать и в среде MPI, и в системе Parix.

С учетом всего вышесказанного, по-видимому, следует рассчитывать на использование в дальнейшем при решении масштабных задач именно систем с распределенной памятью. По существу, на современном этапе развития большие параллельные системы часто имеют иерархическую структуру, когда на верхнем уровне они представляют собой МРР (Massive Parallel Processing) или кластерную систему, каждый вычислительный модуль которой может являться в свою очередь SMP (Symmetrical Multi-Processor) системой (с общей памятью), состоящей также из нескольких процессоров. Далее в работе речь везде будет идти о распределенных параллельных системах.

Помимо уже упомянутых проблем, следует еще отметить, что проведение масштабных вычислительных экспериментов с использованием больших технических мощностей неизбежно приводит к образованию соответствующих объемов данных. Возникают задачи их хранения и обработки, использования различных алгоритмов сжатия информации, анализа результатов вычислений и их визуализации. Например, в некоторых задачах требуется интерактивный просмотр результатов моделирования с целью наглядного определения качественной картины явлений. Вычислительных ресурсов традиционного средства визуального отображения -персонального компьютера - хватает, в лучшем случае, для вывода графической картинки на экран, но никак не для ее расчета. С увеличением числа процессоров, занятых моделированием, следует пропорционально увеличивать число процессоров, занятых обработкой результатов (например построением изолиний или поверхностей), а кроме того нужно еще обеспечить эффективное взаимодействие всех участников этого процесса [22].

При решении подобного рода проблем возникает необходимость применения нетривиальных подходов, опирающихся на информацию практически со всех областей знаний, включая специальные вопросы системного программирования, в тесной связи с решением конкретных задач. Проблемы, связанные с эффективным использованием современных вычислительных систем, созданием для них математического обеспечения, носят системный характер, и их решение невозможно без привлечения средств и методологии фундаментальной науки. Поэтому реальные возможности крупномасштабного моделирования на нынешнем этапе развития определяются не только наличием высокопроизводительной компьютерной техники, а в первую очередь оригинальными решениями, полученными на базе фундаментальных исследований [34].

Обратимся теперь к моделированию газодинамических течений и геометрическому параллелизму. Итак, первая задача состоит в обеспечении равномерного распределения вычислительной нагрузки, что сводится к разбиению всего множества узлов расчетной сетки на некоторое число групп равного размера, соответствующее количеству процессоров, которые будут задействованы в предстоящих расчетах. Но если при использовании системы с общей памятью вставал вопрос только о том, чтобы разбить узлы поровну, то для систем с распределенной памятью встает и другой вопрос - как именно это разбиение должно быть осуществлено, поскольку параллельно приходится решать и вторую задачу: уменьшения дополнительной коммуникационной нагрузки.

Здесь возникает вопрос об информационной взаимозависимости данных во время расчетов. Если рассмотреть крайний случай и предположить, что для вычислений в каждом узле сетки в процессе счета необходимо наличие данных со всех остальных узлов, то очевидно, что от характера разбиения ничего не зависит: все равно каждому из процессоров для получения недостающей информации придется организовывать обмен данными со всеми остальными процессорами, и причем в полном объеме. Алгоритм, предполагающий подобное глобальное использование данных, обречен на чрезвычайное падение эффективности с ростом числа процессоров, или, во всяком случае, требует каких-либо других схем распараллеливания. Впрочем, существует уже достаточное количество алгоритмов, обладающих свойством локальности, то есть для их работы при проведении вычислений в одном из узлов сетки требуются только данные из небольшого количества близлежащих узлов. В качестве примера можно привести параллельный а-|3 алгоритм итераций для решения эллиптических уравнений [35].

В данном контексте большую ценность приобретают также явные расчетные схемы. В явных схемах значение функции на новом слое по времени строится исключительно на основе уже известных значений с предыдущего слоя. Разностный шаблон как правило содержит небольшое число близко расположенных друг от друга точек. К сожалению, явные схемы зачастую требуют для устойчивости счета очень жесткого ограничения на шаг по времени. Поэтому успешную многопроцессорную реализацию могут обеспечить лишь явные схемы с хорошим критерием устойчивости [43]. К числу таких схем относятся кинетически-согласованные разностные схемы, используемые в настоящей работе и обсуждаемые в первой главе.

При использовании алгоритмов, обладающих свойством локальности, каждому из процессоров требуются данные только из узлов, являющихся соседними или, по крайней мере, слабо удаленными по отношению к узлам, расположенным в его собственной памяти. Поэтому обмен данными между процессорами включает в себя только информацию об узлах, находящихся в непосредственной близости от взаимной границы областей, лежащих на разных процессорах. Отсюда становится ясным следующее требование, предъявляемое к разбиению расчетной сетки: минимизация длин (или площадей - в трехмерном пространстве) смежных границ подобластей, принадлежащих различным процессорам. Сразу же угадываются и общие черты формы таких областей: они должны быть связными и компактными, так как именно в этом случае отношение размера границы к размеру самой области (в двумерном случае - периметра к площади, в трехмерном - площади поверхности к объему) минимально. Вследствие этого и согласно сложившейся практике будем в дальнейшем называть зоны, полученные в результате разбиения всей расчетной области по процессорам, доменами.

Проиллюстрируем данное положение на простых примерах. Пусть мы хотим разбить исходную область всего на две части. Выделим одну из координат и разделим точки на имеющие значение этой координаты меньше и больше некоторого среднего значения (аналога центра масс). Такой метод получил название координатной бисекции. Выбор координаты, по которой производится разбиение, следует делать, исходя из протяженности сетки по различным направлениям. Ясно, что разбиение на рис. В. 1а предпочтительнее, чем на рис. В. 16, поскольку длина границы между доменами в нем почти вдвое меньше. а) б)

Рис. В.1. Координатная бисекция.

Теперь предположим, что разбивать область надо не пополам, а на большее количество частей. Тогда проводить все разбиение вдоль одной координаты может оказаться нецелесообразным. Более выгодно будет воспользоваться, например, рекурсивной бисекцией, то есть разбить исходную сетку на две части, затем каждую из этих частей снова разбить надвое, и так далее. Если необходимо получить в результате число доменов, отличное от степени двойки, можно некоторые из промежуточных областей разбивать не строго пополам, а в определенной пропорции. Впрочем, не исключено применение и более простых методов. На рис. В.2а и В.26 можно сравнить результаты двух разных разбиений. Видно, что периметр каждого из доменов на втором рисунке существенно меньше по сравнению с первым, а именно - в два с половиной раза. а) б)

Рис. В.2. Примеры разбиения на 25 доменов.

Далее, существует еще одна составляющая в вопросе минимизации межмодульных взаимодействий. Как правило, задача заключается не только в снижении суммарного объема передаваемых данных, но и в уменьшении числа процессоров, граничащих между собой (домены которых имеют общие границы). Связано это с тем, что для инициализации самой процедуры передачи требуются также некоторые временные затраты, в результате чего передавать данные одним сообщением большого объема гораздо эффективнее, чем малыми порциями. Ситуацию приближенно можно описать следующим образом. Суммарное время передачи пакета данных складывается из двух величин: одна из них - время инициализации пересылки - постоянна, другая - время непосредственной передачи - пропорциональна объему пакета: tъ-t¡+te^x.V, где 1е - чистое время прохождения единичного объема информации по каналу связи. Видно, что отношение выражающее реальную скорость передачи данных в пределах одной пересылки, сильно падает при малых V.

Применительно к рисунку В.26 это означает следующее. Положим, в области задана обычная прямоугольная сетка. Если расчетный алгоритм устроен таким образом, что между узлами, находящимися по диагонали друг от друга, информационная зависимость отсутствует, то домены внутри области имеют всего по четыре соседа. Если же такая зависимость есть, то домены, расположенные по диагонали, также приходится включить в число соседних, и это число возрастает уже до восьми, причем обмен данными с «диагональными» соседями оказывается крайне неэффективен. В таком случае более подходящим окажется разбиение, представленное на рис. В.З. Здесь уже внутренние домены имеют по шесть соседей (приграничные, соответственно, меньше). Стоит заметить, что не всегда все домены обязательно должны быть связными: подобласти, помеченные цифрами, вполне могут принадлежать одним и тем же процессорам. Поскольку, рассматривая минимизацию обменов данными, мы учитываем смежные границы доменов, а не границы расчетной области, то это не имеет существенного значения. Правда, по отношению к остальным указанные домены являются скорее внутренними и имеют тоже по шесть соседей.

I II т тт

Рис. В.З. Уменьшение числа соседей среди доменов путем их сдвига.

Так или иначе, пока мы имеем дело с «классическими» регулярными сетками, найти их адекватное разбиение на заданное число доменов обычно не составляет особого труда. Такие сетки по определению имеют структуру, регулярно повторяющуюся на всем протяжении исследуемой области пространства, что позволяет ввести нумерацию узлов сетки (точек области) согласно размерности этого пространства. Как правило, такая нумерация существует уже изначально, естественным образом возникая в процессе построения сетки. Расположение узлов и ребер в расчетной области тем или иным образом привязывается к физическим (или геометрическим) координатам, а следовательно, нумерация соответствующей размерности представляет собой фактически систему целочисленных координат, которые в форме простой функциональной зависимости отражают положение узла в сетке.

Так, для простой прямоугольной сетки, заданной в пространстве с декартовыми координатами, можно ввести двумерную нумерацию узлов по индексам г и у. Тогда для каждого из доменов на предыдущих рисунках совершенно несложно будет определить, какие из его точек являются граничными: слева и справа это будут точки с соответствующими фиксированными значениями индекса г, а сверху и снизу - с фиксированными индексами у. Также легко определить для любого отдельно взятого домена, какие именно из узлов соседних к нему доменов являются соседними для его узлов, и соответственно с этим настроить программные процедуры для обмена данными в ходе выполнения расчетов. Выяснить, какие из доменов с какими граничат, тоже просто: коль скоро сама сетка имеет регулярную структуру, то и расположение доменов обычно устанавливается регулярным, а значит их тоже можно аналогичным образом пронумеровать.

При этом, чем менее сложный метод использовать при разбиении, тем меньше необходимость выделять решение проблемы балансировки загрузки как отдельную серьезную задачу. По сути, она может быть неявно решена одновременно с распределением данных на стадии запуска вычислений. Для нахождения своего домена, т.е. подмножества узлов, которые нужно выбрать из всей сетки в оперативную память, равно как и для определения границ этого домена, процессору достаточно самых общих сведений о сетке и параметрах запуска, таких как число участвующих в расчете процессоров (эквивалентно числу доменов), общее количество узлов и т.п. Вся процедура может состоять буквально из нескольких операций, и каждый процессор в состоянии решить для себя эту задачу достаточно быстро и независимо от других.

Тем не менее, при численном решении задач газовой динамики, да и во многих других пространственных вычислительных задачах, нередко возникает потребность в применении сеток более сложной структуры. Так, в работе [6] отмечается, что при построении двумерных разностных схем, моделирующих газодинамические течения, важную роль играет процесс дискретизации расчетной области. В частности, при использовании схем с направленными разностями (схем Годуновского типа в нелинейном случае) для аппроксимации конвективных членов важно, чтобы угол между линией разрыва переносимых величин и гранью расчетной ячейки был максимально близок к нулю [64]. Этого можно достичь двумя способами -либо используя адаптивную сетку, либо выбирая в качестве расчетной ячейки многогранник с наибольшим числом граней.

В настоящей работе используются треугольные сетки, в которых расчетная ячейка, или контрольный объем, довольно естественно строится в виде многогранника с числом граней, в среднем равным шести. (Несложно показать, что это число вообще свойственно двумерному пространству. Именно столько соседей в среднем имеет некоторый конечный элемент при стремлении числа этих элементов, распределенных на плоскости, к бесконечности. Поэтому данное правило относится не только к расчетным ячейкам, но в равной степени и к доменам). Впрочем, треугольная сетка также может иметь практически регулярную структуру. На рис. В.4 представлен фрагмент сетки, целиком состоящей из одинаковых треугольников. На нем отчетливо видны несколько выделенных направлений. Для такой сетки ввести двумерную нумерацию узлов не представляется сложным точно так же, как и для прямоугольной. Хотя ребер в этой сетке больше, а углы между ними меньше.

Рис. В.4. Равномерная треугольная сетка.

Качественно иная ситуация возникает при использовании нерегулярных сеток, которые обладают особой ценностью для некоторых классов задач. Из названия видно, что в этих сетках отсутствует какая-либо регулярно повторяющаяся по пространству структура, поэтому их еще называют неструктурированными (unstructured). В таких сетках взаимное расположение узлов и ребер подчиняется гораздо менее жестким ограничениям, что и придает им в определенных случаях важные достоинства.

Нерегулярные сетки обладают по крайней мере двумя заметными преимуществами перед сетками регулярными. Во-первых, плотность расположения в них узлов может быть существенно неоднородной, что позволяет сконцентрировать значительное большинство расчетных узлов в тех областях сетки, где необходимо получить решение с повышенной точностью, и меньшее число узлов в тех областях, где к точности решения не предъявляются высокие требования. Во-вторых, поскольку ограничения на углы между ребрами, как правило, достаточно невелики, то узлы сетки можно располагать непосредственно на границе расчетной области, независимо от ее сложности. Если при этом учесть предыдущее свойство, то эти узлы можно расположить в достаточно большом количестве, и таким образом может быть достигнута высокая точность дискретизации границы области в расчетной сетке.

К примеру, в задачах аэродинамического обтекания, рассматриваемых в данной работе, основной интерес представляет ка^аз определение физических параметров на самом крыле, поверхность которого является границей расчетной области, а также в непосредственной близости от него. Нерегулярная сетка позволяет одновременно и описать поверхность крыла с повышенной точностью, и сконцентрировать вблизи этой поверхности наибольшее число расчетных узлов. Указанные свойства способны помимо прочего компенсировать тот факт, что разностная аппроксимация на неструктурированных сетках обычно уступает по точности варианту с использованием сеток регулярных.

Рис. В.5а. Нерегулярная треугольная сетка: общий вид.

П.501

0.5

0.490

0.400 0.49Т 0.495

0.598 0.509 0.В 0.601 0.602

Рис. В.56. Нерегулярная треугольная сетка: увеличенный фрагмент.

На рис. В.5а изображена одна из сеток, используемых в работе. Видно, что около поверхности крыла и закрылка, особенно в зоне переднего и заднего окончаний, она значительно сгущается. Для данной сетки линейный коэффициент сгущения, то есть отношение максимальной длины ребра к минимальной, составляет почти 10 . На рис. В.56 можно также увидеть, насколько аккуратно ломаная линия описывает границу профиля.

При наличии всех упомянутых достоинств, использовать нерегулярные сетки для параллельных расчетов значительно труднее. В силу отсутствия глобальной упорядоченности в топологии этих сеток для них в общем случае невозможно построить систему целочисленных координат той же размерности, что и у пространства задачи, которые имели бы какую-либо простую функциональную связь со структурой взаимного расположения узлов и ребер. Следовательно, нерегулярная сетка в пространстве любой размерности имеет лишь одномерную нумерацию узлов.

22

Таким образом, из того, в каком порядке пронумерованы узлы, невозможно извлечь практически никакой полезной информации о том, какие узлы с какими связаны, и насколько они удалены друг от друга. К тому же структура этих связей неоднородна. Возникает необходимость анализа информации о связях между узлами в явном виде. Поэтому нерегулярные сетки традиционно рассматривают, абстрагируясь от каких бы то ни было координат, в виде графов. Разбиение произвольного графа на домены с учетом определенных критериев - задача, алгоритмически гораздо более сложная, и требует применения специальных математических методов.

Построение графа, отражающего распределение вычислительной и коммуникационной нагрузки, осуществляется по довольно естественной схеме. Вершины графа представляют собой некоторые элементарные вычислительные задачи, а присутствие ребра между двумя вершинами свидетельствует о наличии информационной связи между ними, т.е. необходимости обмена данными между задачами, соответствующими этим вершинам. В тривиальном случае, если установить взаимно однозначное соответствие между вершинами графа и узлами сетки, а также между их ребрами, такой граф является точной копией расчетной сетки. В этом базовом варианте в качестве элементарной задачи выступает набор вычислительных операций, производимых в одном узле. Расположение же таким образом ребер предполагает, что в каждом узле требуются данные из всех соседних по сетке узлов и только из них. В действительности это строго верно только для некоторых видов расчетных схем, другие схемы могут содержать в разностном шаблоне и прочие узлы. Но на практике, для алгоритмов, обладающих свойством локальности, эти узлы являются если не соседями по сетке, то соседями соседей, и т.д., поэтому одно ребро к одной из соседних вершин в графе может неявно отражать также и поток информации о вершинах, соседних с ней.

В такой интерпретации задача балансировки загрузки сводится к разрезанию графа на определенное количество частей, содержащих равное число вершин, при условии минимизации числа разрезанных ребер и равномерного их распределения по всем подграфам. Длина смежной границы двух доменов, о которой говорилось ранее, и которая подлежит предельному уменьшению, приобретает здесь уже конкретное выражение - это число ребер графа, которые пересекает данная граница. Условие равномерного распределения разрезанных ребер с одновременным уменьшением их общего количества можно выразить в виде требования минимизации их максимального числа по всем доменам. В формализованном виде постановка задачи выглядит следующим образом:

Пусть задан граф G = (V,E), в котором V - множество вершин v(., Е - множество ребер e{j, число вершин \ V\=n. Требуется найти разрезание R(V) = (Vl,.,Vr) графа на заданное число г подграфов Vk, для которых выполнены следующие условия: к=1

J = max I e : v, eVk,v£Vk\-> min k=\,.,r J J

Объем вычислений в различных узлах может быть не везде одинаковым и для однородных схем. Например, в узлах на границе расчетной области и во внутренних узлах обычно выполняются разные вычисления. Аналогично, может отличаться и объем передаваемой между узлами информации. При необходимости эти различия можно отразить в графе при помощи введения системы весов для вершин и для ребер - с. и су. В таком случае надо говорить не об одинаковых количествах вершин и разрезанных ребер в каждом из подграфов, а о равенстве их суммарных весов. Кроме этого, можно объединить вычислительную и коммуникационную загрузку и рассматривать весь вес полной нагрузки как единую меру ценности процессов вычислений и обменов данными. Тогда два различных требования сводятся к одному обобщенному скалярному критерию - минимизации общего времени работы самого загруженного из процессоров. При этом пропадает условие равенства размеров доменов и решается задача минимизации одного составного функционала 3:

Здесь а - коэффициент, согласующий единицы измерения весов с{ и c{J. Например, если ci выражает время выполнения задачи vn a c(J - объем данных, передаваемых между задачами v(. и v., то а определяет время передачи единичного объема информации. В случае, когда ci и сд уже выражены в одних единицах, можно положить а = 1.

К сожалению, поставленная задача как в первой, так и во второй формулировке является NP-полной (non-polynomial - не полиномиальный), и поиск ее точного решения при числе вершин произвольного графа, измеряемом тысячами и более, за обозримое время неосуществим [51,52]. В подобных случаях используют следующие основные подходы:

• Отказ от поиска точного решения и переход к поиску приближенных решений, например с использованием вероятностных алгоритмов, алгоритмов локального поиска и т.д. (В нашем случае это может быть неточное равенство размеров доменов или, что более типично, приближенная минимизация их границ, или же и то и другое одновременно).

• Отказ от поиска решения для задач общего вида и сужение класса рассматриваемых задач за счет присущих возникающим на практике проблемам различных смысловых ограничений. Иногда такие частные ситуации допускают эффективное решение (точное или приближенное) г при помощи алгоритмов, неприемлемых или вовсе неприменимых в более общем варианте. (Например, в нашем случае максимальная степень вершин может быть ограничена небольшим числом, или граф может иметь блочную структуру, или он может быть планарным, и т.д.). • Использование эвристических алгоритмов. (Можно, например, более или менее успешно применять координатную бисекцию и для нерегулярных сеток, особенно сильно вытянутых, но это оправдывает себя только для сеток со слабыми степенями сгущения и относительно простыми формами расчетных областей). Кроме того, для ряда ОТ-полных задач существуют алгоритмы с полиномиальной трудоемкостью проверки решения, что позволяет эффективно использовать алгоритмы типа управляемого случайного поиска (поиска локального оптимума) и т.п. [29].

Одной из наиболее близких по формулировке к поставленной нами является задача о разрезании графов, описанная в работе [17].

Пусть задан взвешенный граф 0 = (Х,11), \Х\ =п, вершины и дуги Ыу которого имеют веса с1 и су соответственно, и пусть задан набор чисел {щ}, Щ> 0, £ е [1: г]. Требуется найти разрезание Я(Х) = (Х1,.,ХГ) графа на г кластеров - подграфов <Хк >, для которых выполнены следующие условия: a) Х = (]Хк, Х{{)Х; = 0, 1Ф] к=1 b) С{к)=^с1<тк, к = \,.,г хк г к=1

Ограничение Ъ) может также иметь один из следующих видов:

С(к)=М , С{к)<М , С{к) = тк , С(к)е[А:В] .

Задача о разрезании бесконтурного ориентированного графа на минимальное число частей сводится к задаче целочисленного программирования [17,18]. Пусть п - число вершин в графе, q - число кластеров, полученных после разрезания (в такой постановке оно неизвестно заранее). Пусть, далее, т{] - суммарный вес дуг, ведущих из кластера Х1 в кластер

Х] и наоборот. Задача оптимального разрезания состоит в нахождении двоичных у у (у. =1, если предмет г находится в кластере Х] и = 0 в противном случае), таких, что выполняются ограничения п

1=1 п м и таких, что п п д

1 и=\ j=l

В работе [17] приводится алгоритм разрезания деревьев методом динамического программирования и показано, что вычислительная сложность алгоритма пропорциональна М2п независимо от структуры дерева. Аналогичный алгоритм для графа общего вида имеет экспоненциальную оценку сложности и мало пригоден для эксплуатации. В связи с этим предлагаются некоторые соображения, использующие свойства изолированных множеств. Показано, что блоки в графах блочной структуры можно разрезать независимо один от другого, комбинируя в дальнейшем получившиеся части для определения точного решения, что значительно снижает общее время решения задачи. Предлагается эвристический алгоритм разрезания графа общего вида, построенный на базе алгоритма разрезания деревьев. В его основе лежит идея получения каркаса наибольшего веса, разрезания его и дополнения разрезов каркаса до разрезов всего графа в целом.

Описание аналогичной задачи можно найти в работе [10], в которой рассматривается информационный граф решаемых в вычислительной сети задач, учитывающий операторы обмена информацией. При этом сеть предполагается неоднородной, и в связи с этим вводятся векторные веса вершин (элементы векторов отражают время, необходимое для выполнения заданного оператора на каждом из процессорных элементов). Временная сложность предлагаемых в работе алгоритмов не приводится, но по существу используется метод ветвей и границ, имеющий обычно экспоненциальную оценку сложности.

Стоит отметить также работу [9], в которой содержится достаточно полный обзор различных способов хранения и представления графов. Кроме того в ней присутствует описание некоторых ЫР-полных задач. Там же рассматривается ряд методов оптимизации, среди которых - метод ветвей и границ, метод неявного перебора, метод динамического программирования, метод Лагранжа, метод снижения требований. Вводятся понятие спектра графа и различные операции над графами.

Теме эффективного использования параллельных систем посвящено большое количество работ В.В. Воеводина [38]. Процитируем здесь фрагмент одной из них [13]. Указывая на 1\ГР-сложность задачи эффективной реализации алгоритма, заданного графом С;, на вычислительной сети, определяемой графом (^2, автор пишет: нет никаких оснований надеяться на получение эффективного решения общей задачи отображения проблем вычислительной математики на архитектуру вычислительных систем с помощью некоторого универсального метода. . Прежде чем делать окончательные выводы, полезно понять, откуда все же возникает ИР-сложность задач в наших исследованиях и появляется ли она по существу, или из-за того, что мы недостаточно хорошо знаем задачи, которые собираемся решать. Вернемся к задаче «гомоморфизм графов». Ее ЫР-сложностъ доказана в том случае, когда графы О] и 02 произвольные. . Используемые в действительности алгоритмы нельзя отнести к произвольным. Они обладают рядом характерных отличий, связанных, например, с существованием периодически повторяемых участков вычислений. Следовательно, есть основания предполагать, что, изучая реальные алгоритмы и выделяя их специфику, удастся избежать ЫР-сложности больших дискретных задач и найти эффективные методы решения общей задачи, по крайней мере в практически важных случаях.»

Далее обращается внимание на важность разумного выбора ограничений, сужающих класс рассматриваемых графов, поскольку их чрезмерное ужесточение может оставить в нашем распоряжении только тривиальные графы, или случаи, представляющие малый практический интерес. И, наконец, следует заключение:

Выбор правильного пути исследований должен начинаться с изучения особенностей графов практически используемых алгоритмов.»

Некоторые отличительные особенности графов алгоритмов рассматриваются также в работах [14,15].

Одним из несомненно наиболее успешных эвристических алгоритмов разбиения графов является спектральный метод. Свое название он получил в силу того, что базируется на анализе собственных векторов матрицы Лапласа (Лапласиана) графа, содержащей практически полную информацию о его ребрах. Пусть дан граф О = (У,Е) с вершинами у;., ребрами ец и количеством вершин N. Матрица Лапласа для этого графа выглядит следующим образом: С /,, . /, где 1,к = , Ьк ••• У в которой hk = Kl = 0, eik € E

L = hi =1 , eik eE lu = ' v/>v*eF кФ1

Легко увидеть, что L{G) - -D + А, где А - матрица смежности графа, а D -диагональная матрица степеней его вершин. Видно также, что для графов, соответствующих реальным расчетным сеткам, матрица L(G) является сильно разреженной и помимо того симметричной. Возможности практического использования свойств матрицы смежности исследовались уже давно [46,70], но позже было показано, что анализ спектра матрицы Лапласа имеет некоторые преимущества [65].

Теоретическую основу спектрального метода заложил в своих работах чешский математик Мирослав Фидлер [48-50]. Именно он обратил внимание на особые свойства собственных векторов Лапласиана графа. Из определения матрицы следует, что ее первое и наибольшее собственное число всегда равно нулю. Остальные собственные числа матрицы являются отрицательными. В спектральной бисекции используется второй собственный вектор матрицы Лапласа, соответствующий наименьшему (наибольшему по абсолютной величине) собственному числу. Иногда его еще называют, в честь исследователя, вектором Фидлера.

Идея метода спектральной бисекции состоит в следующем. Находится l2(G) - второй собственный вектор матрицы L(G). Для получения искомого разрезания графа G следует упорядочить его вершины по значениям соответствующих координат вектора l2(G) и разделить их на две группы, с большими и с меньшими значениями этих координат, соответственно. Практическая реализация алгоритма в указанном виде была построена в работе [69].

Впоследствии метод получил дальнейшее развитие. Было предложено анализировать более одного собственного вектора матрицы Лапласа, что дало возможность разрезать граф не только на две, но и на 4, на 8 частей одновременно [56,58-60]. Кроме этого, был усовершенствован и сам способ построения матрицы, позволивший учитывать различие весов ребер графа. Для этого в непустых недиагональных элементах матрицы вместо единиц записываются веса ребер с1к, соответствующим образом корректируются и диагональные элементы:

4=4/=^, е1к еЕ ш

Многочисленные эксперименты показали, что разбиение, получаемое в результате применения спектрального алгоритма, не хуже, а, как правило, лучше разбиений, получаемых при помощи других ранее известных методов [71]. Однако, спектральному методу присущи и определенные ограничения. Наиболее трудоемким этапом при его использовании является поиск собственных векторов матрицы, что ограничивает на практике размер разрезаемого графа [67,72]. Обычно вычисление собственного вектора выполняется с помощью итераций, путем задания некоторых начальных приближений и перемножения последующих векторов с исследуемой матрицей. Например, в работе [68] предлагается воспользоваться в этих целях довольно эффективным алгоритмом Ланцоша. Тем не менее, сходимость итераций все же ухудшается с увеличением размеров графа и, кроме того, существенно зависит и от его внутренних свойств, и от выбора начального приближения. Использование нескольких собственных векторов также несет в себе определенные трудности, из-за того, что предыдущие найденные векторы могут быть вычислены уже с некоторой погрешностью, способной оказать влияние на дальнейший процесс поиска. Во многих случаях выгоднее воспользоваться рекурсивной бисекцией, которая к тому же допускает распараллеливание методом сдваивания, при котором разбиение двух подграфов, полученных в результате предшествующего разбиения, производится одновременно.

Для эффективного разбиения графов большого размера был предложен радикально иной подход. Суть его состоит в том, что перед началом непосредственного разбиения для исходного большого графа строится его макет, в определенном смысле приближенная копия, в которой одна вершина соответствует целому подмножеству вершин исходного графа. Размер такого приближенного графа получается значительно меньше, поэтому к нему уже и применяется какой-либо из обычных методов разбиения, например, описанный выше спектральный. Затем осуществляется проецирование полученного разбиения на начальный граф. В зависимости от соотношения размеров исходного и приближенного (или огрубленного) графов, а также от методов построения последнего, процесс этого построения может идти в несколько стадий. В таком случае образуется иерархия различных уровней огрубления исходного графа. Обратный процесс переноса разбиения с конечного на предыдущие уровни проходит, соответственно, те же стадии (см. рис. 2.1 во второй главе). Алгоритмы такого типа получили название иерархических или многоуровневых (multilevel) [57,61,62]. С их помощью стало возможным разбивать сетки размером в десятки и сотни тысяч узлов. По большому счету, алгоритмические ограничения сменились только ограничениями по оперативной памяти компьютера (без учета, конечно, вопросов качества и скорости выполнения).

Каждая стадия огрубления на первом этапе работы иерархического алгоритма состоит, как правило, в объединении нескольких вершин предыдущего графа в небольшие подмножества, каждое из которых соответствует одной вершине следующего графа. Например, такое объединение можно осуществить, выделив некоторый набор не соприкасающихся друг с другом ребер и стянув эти ребра, соединяя вершины на их концах в пары.

Ребра получаемых огрубленных вершин в новом графе выражают суммарные связи между соответствующими им подмножествами вершин предыдущего графа. При этом размер этих подмножеств и объем связей между ними находят отражение в суммировании весов образующих их вершин и ребер. Огрубление продолжается до тех пор, пока размер графа не достигнет желаемой степени, при которой к нему уже можно применять тот или иной выбранный метод разбиения.

Разбиение огрубленного графа по процессорам, то есть, по сути, распределение его вершин по различным группам, легко переносится на исходный граф путем отнесения к тем же группам соответствующих им подмножеств. Однако, получаемое в результате такого прямого переноса разбиение может оказаться не самого лучшего качества, даже если для грубого графа оно выполнено оптимальным образом. Причина этого заключается в том, что в грубом графе границы доменов могут пролегать только между его вершинами, не пересекая их, тогда как на предыдущих стадиях огрубления этим вершинам соответствуют целые множества, и линия оптимального разреза может проходить внутри них. Чтобы использовать такую возможность и подкорректировать расположение границ, на этапе возврата от грубого графа к исходному на всех или некоторых стадиях выполняется процедура локальных уточнений. Ее целью является уже не нахождение границ целиком, а лишь внесение в них небольших поправок.

Центральные идеи применяемых на сегодняшний день алгоритмов локальных уточнений были предложены в работе [63]. В общих чертах, процедура состоит поиска вершин, перемещение которых через смежную границу доменов дает выигрыш в качестве разбиения, и соответствующего переноса этих вершин из одних доменов в другие. Выгода, получаемая от такого переноса, может выражаться как в уменьшении разницы между размерами доменов, так и в уменьшении числа разрезанных границей ребер. На базе этой схемы впоследствии было построено семейство алгоритмов, отличающихся в различных аспектах, в основном в устройстве процедуры выбора перемещаемых вершин, в критериях продолжения или прерывания процесса их поиска [47,57]. В том числе, модификация алгоритма, построенная в работе [57], позволяет учитывать веса и вершин, и ребер, а также различия в затратах на пересылки данных между процессорами, имеющими разное топологическое расположение в вычислительной системе.

В настоящее время технические возможности позволяют относительно недорогое наращивание систем с распределенной памятью до уровня не только десятков, но уже сотен и тысяч процессорных модулей. Количество постепенно переходит в качество, и возникают новые сложности в эффективном использовании таких систем. Из-за того, что общая вычислительная мощность системы и объем ее ресурсов на порядки превосходят таковые для одного модуля, возникает необходимость в распределенном хранении и распределенной обработке данных, в том числе и в тех случаях, когда их централизованное хранение является более выгодным, но физически невозможным. Это предъявляет новые требования к внутреннему устройству параллельных алгоритмов, особенно в той их части, которая содержит элементы последовательной обработки данных или предполагает централизацию управления. Общая организация вычислительного процесса и контроля над ресурсами также требует тщательного пересмотра. До недавнего времени эти проблемы не вставали столь остро из-за отсутствия соответствующей техники. Сейчас, в связи с появлением в России первых параллельных систем такого масштаба, работа в указанном направлении становится довольно актуальной.

Если раньше в качестве серьезных расчетных задач рассматривались вычислительный эксперимент, численное моделирование сложных физических процессов, решение больших систем уравнений и т.п., то в новой ситуации и те задачи, которые обычно относились к разряду побочных, служебных, требуют внимательного рассмотрения и зачастую применения параллельной обработки данных. В этой связи уже упоминались проблемы хранения и сжатия больших объемов информации, их анализа и визуализации.

Размеры расчетных сеток, которые способны обработать современные системы с тысячами процессоров, приближаются к миллиардам точек. Построение нерегулярных сеток такого масштаба уже само по себе является весьма нетривиальной задачей. Существующие последовательные алгоритмы не только будут справляться с ней очень долго, но могут и не справиться совсем: если для их работы требуется присутствие данных по всей сетке, то эти данные могут не уместиться в памяти одного процессора. Аналогично обстоит дело с балансировкой загрузки. Разбиение сеток большого размера тоже должно осуществляться параллельно, по той же самой причине. Особый интерес здесь вызывают иерархические алгоритмы, поскольку по ходу своего выполнения они позволяют прийти к объектам малых размеров и таким образом дают возможность частично применять в случае необходимости и последовательные методы.

Несколько отдельно стоит не менее важный практический вопрос о коллективном использовании крупномасштабных многопроцессорных систем. В силу ряда причин редко является возможным использование значительного количества процессоров, особенно одних и тех же, для решения одной задачи в течение длительного периода времени. Как правило, существует система очередей заданий, задачи многократно запускаются и снимаются со счета службой системного управления. В такой ситуации особую роль начинают играть процессы загрузки и распределения информации по модулям перед началом вычислений, а также записи промежуточных результатов расчетов после их окончания. Время выполнения этих предварительных и заключительных действий должно занимать малую

часть от времени полезных вычислений, в противном случае эффективность использования системы будет катастрофически низкой. Следовательно, при расчетах на большом числе процессоров необходимо обеспечить параллельность чтения и записи основных данных.

Исследованию и решению обозначенных проблем уделяется сегодня значительное внимание. Настоящая диссертация является одной из немалого количества работ, посвященных этой тематике.

Центральной задачей диссертационной работы является построение параллельного алгоритма для разбиения нерегулярных сеток больших размеров (особенно, в перспективе, трехмерных) на системах с распределенной памятью. Рассматриваются также другие проблемы, связанные с практическим использованием нерегулярных сеток: построение параллельного расчетного алгоритма (на примере расчетов двумерных газодинамических течений), вопросы хранения соответствующих объемов данных и ускорения их загрузки.

Диссертация состоит из введения, трех глав, заключения и списка используемой литературы.

Заключение

Сформулируем основные результаты диссертационной работы:

Предложены методика и математическое обеспечение для численного решения задач газовой динамики с применением нерегулярных сеток большого размера на параллельных вычислительных системах с распределенной памятью.

На основе кинетически-согласованной разностной схемы создана программа для расчета газодинамических течений на неструктурированных сетках, позволяющая эффективно использовать современные многопроцессорные системы.

Разработан параллельный иерархический алгоритм разбиения двумерных и трехмерных нерегулярных расчетных сеток большого размера.

Предложена двухуровневая схема разбиения больших нерегулярных сеток, их хранения, а также чтения и записи данных в процессе проведения многократных вычислений.

При помощи разработанного комплекса программ выполнен ряд численных расчетов стационарного сверхзвукового аэродинамического обтекания двумерных тел.

1. Абалакин И.В., Бабакулов А.Б., Музафаров Х.А., Якобовский М.В. Моделирование течений умеренно-разреженного газа на транспьютерных системах. // Математическое моделирование, 1992. Т.4. №11. С.3-18.

2. Абалакин И.В., Жохова A.B. Кинетически-согласованные схемы с коррекцией на треугольных сетках. //Дифференциальные уравнения, 1998. Т.34. № 7. С.904-910.

3. Абалакин И.В., Жохова A.B., Четверушкин Б.Н. Кинетически-согласованные разностные схемы на нерегулярных сетках. // Математическое моделирование, 1997. Т.9. №7. С.44-53.

4. Абалакин И.В., Жохова A.B., Четверушкин Б.Н. Кинетически-согласованный алгоритм для расчета газодинамических течений на треугольных сетках. // Математическое моделирование, 1998. Т. 10. №4. С.51-60.

5. Абалакин И.В., Четверушкин Б.Н. Кинетически-согласованные разностные схемы как модель для описания газодинамических течений. // Математическое моделирование, 1996. Т.8. №8. С. 17-36.

6. Т. Акселрод, М. Беккерман и др. Программирование на параллельных вычислительных системах: Пер. с англ. / Под ред. Р. Бэбба И. М.: Мир, 1991.

7. Асельредов З.М., Донец Г.А. Представление и восстановление графов. Киев: Нау-кова думка, 1991.

8. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990.

9. Болдырев С.Н. Решение некоторых задач газовой динамики с применением нерегулярных сеток на параллельных вычислительных системах. // Некоторые проблемы фундаментальной и прикладной математики: Междувед. сб. / МФТИ. М., 1998. С.159-167.

10. Власов A.A. Статистические функции распределения. М.: Наука, 1966.

11. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, Главная редакция физико-математической литературы, 1986.

12. Воеводин В.В. Математические основы параллельных вычислений. М.: Издательство МГУ, 1991.

13. Воеводин В.В. Параллелизм в алгоритмах и программах. // Вычислительные процессы и системы. Выпуск 10. / Под ред. Г.И. Марчука. М.: Физматлит., 1993.

14. Дворников М.В., Тишкин В.Ф., Филатов А.Ю. Триангуляция произвольной многосвязной области со сложной границей. М.: Препринт Института математического моделирования РАН, 1995. №7.

15. Евстигнеев В.А. Применение теории графов в программировании. / Под ред. А.П. Ершова. М.: Наука, Главная редакция физико-математической литературы, 1985.

16. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: ВО «Наука», Сибирская издательская фирма, 1994.

17. Елизарова Т.Г., Четверушкин Б.Н. Кинетически-согласованные разностные схемы для моделирования течений вязкого теплопроводного газа. // ЖВМ и МФ, 1988. Т.28. №11. С.1695-1710.

18. Елизарова Т.Г., Четверушкин Б.Н. Применение многопроцессорных транспьютерных систем для решения задач математической физики. // Математическое моделирование, 1992. Т.4. №11. С.75-100.

19. Карпенко А.П. Параметрическое согласование вычислительных алгоритмов с архитектурой многопроцессорных систем. Диссертация на соискание ученой степени доктора физ.-мат. наук. М.: Институт высоких температур РАН, 1995.

20. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», 1999.

21. Любимов H.A., Русанов В.В. Таблицы газодинамических функций. Т.2. М.: Наука, 1970.

22. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989.

23. Самарский A.A., Колдоба A.B., Повещенко Ю.А., Тишкин В.Ф., Фаворский А.П. Разностные схемы на нерегулярных сетках. Минск, 1996.

24. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985.

25. Транспьютеры. Архитектура и программное обеспечение: Пер. с англ. / Под ред. Г. Харпа. М.: Радио и связь, 1993.

26. Тхир A.B. Метод продвинутого фронта для построения двумерных неструктурированных сеток. // Численные методы и приложения / Под ред. Ю.А. Кузнецова. Институт вычислительной математики РАН, 1995.

27. Р. Хокни, К. Джессхоуп. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: Радио и связь, 1986.

28. Четверушкин Б.Н. Кинетически-согласованные схемы в газовой динамике. М.: Издательство МГУ, 1999.

29. Четверушкин Б.Н. Проблемы эффективного использования многопроцессорных вычислительных систем. // Информационные технологии и вычислительные системы, 2000. №2. С.22-34.

30. Четверушкин Б.Н., Чурбанова Н.Г. О применении принципа геометрического параллелизма для (a-ß) итерационного алгоритма. // Математическое моделирование, 1991. Т.З. №3. С.123-128.

31. Шильников Е.В., Шумков М.А. Моделирование трехмерных нестационарных течений газа на МВС с распределенной памятью. // Математическое моделирование, 2001. Т.13. №4. С.35-46.

32. Якобовский М.В. Распределенные системы и сети. М.: МГТУ «Станкин», 2000.38. http://parallel.ru Информационно-аналитический центр по параллельным вычислениям. Сайт лаборатории параллельных информационных технологий НИВЦ МГУ.

33. V. Abalakin, S.N. Boldyrev, B.N. Chetverushkin, M.V. Iakobovski, A.V. Zhokhova. Parallel Algorithm for Solving Flow Problems on Unstructured Meshes. // 16th MACS World Congress 2000 Proceedings. Lausanne, Switzerland, 2000.

34. T.J. Barth. On Unstructured Grids and Solvers. // Computational Fluid Dynamics, Lecture Series 1990-03. Von Karman Institute, Belgium, 1990.

35. TJ. Barth, D.C. Jespersen. The Design and Application of Upwind Schemes on Unstructured Meshes. // Proceedings of the 27th Aerospace Sciences Meeting, AIAA Paper 89-0366, 1989.

36. B.N. Chetverushkin. On improvement of gas flow description via kinetically-consistent difference schemes. // Experimentation, Modelling and Computation in Flow, Turbulence and Combustion, Vol.2. John Wiley & Sons, Chichester, 1997. pp.27-38.

37. B.N. Chetverushkin. Solution of gasdynamic problems on massively parallel computer systems // Proceedings of the II European Computational Fluid Dynamic Conference. Stuttgart, Wiley-Addison, 1994. pp.397-401.

38. B.N. Chetverushkin, E.V. Shilnikov. Kinetic-consistent finite difference schemes and quasigasdynamic equations as the physical models for gasdynamic flow description. // Proceedings of the III Asian CFD Conference. Bangabore, India, 1998. pp.243-248.

39. S.M. Deshpande. Kinetic Flux Splitting Schemes. // Сотр. Dynamic Review. John Wiley & Sons, Chichester, 1995, pp. 161-181.

40. W. Donath, A. Hoffman. Algorithms for Partitioning of Graphs and Computer Logic Based on Eigenvectors of Connection Matrices. IBM Technical Disclosure Bulletin, 1972. Vol.15, pp.938-944.

41. C.M. Fiduccia, R.M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions. // Proceedings of the 19th IEEE Design Automation Conference. IEEE, 1982. pp.175-181.

42. M. Fiedler. Algebraic Connectivity of Graphs. // Czechoslovak Mathematical Journal, Praha, 1973. No.23. pp.298-305.

43. M. Fiedler. Eigenvectors of Acyclic Matrices. // Czechoslovak Mathematical Journal, Praha, 1975. No.25. pp.607-618.

44. M. Fiedler. A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Application to Graph Theory. // Czechoslovak Mathematical Journal, Praha, 1975. No.25. pp.619-633.

45. N. Garey, D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: Freeman, 1979.

46. M. Garey, D. Johnson, L. Stockmeyer. Some Simplified NP-complete Graph Problems. // Theoretical Computer Science, 1976. No.l. pp.237-267.

47. A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam. PVM: Parallel Virtual Machine: A Users' Guide and Tutorial for Networked Parallel Computing. Scientific and Engineering Computation. MIT Press, Cambridge, MA, USA, 1994.

48. G. Geist, J. Kohl, P. Papadopoulos. PVM and MPI: A Comparison of Features. // Calculateurs Paralleles, 1996. No.8.

49. W. Gropp, E. Lusk, N. Doss, A. Skjellum. A High-performance, Portable Implementation of the MPI Message Passing Interface Standard. // Parallel Computing, 1996. No.22. pp.789-828.

50. S. Hammond. Mapping Unstructured Grid Computations to Massively Parallel Computers. Ph.D. thesis. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 1992.

51. B. Hendrickson, R. Leland. A Multilevel Algorithm for Partitioning Graphs. // Supercomputing '95 Proceedings. San Diego, CA, 1995.

52. B. Hendrickson, R. Leland. An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations. // SIAM Journal on Scientific Computing, 1995. Vol.16. No.2. pp.452-469.

53. B. Hendrickson, R. Leland. An Improved Spectral Load Balancing Method. // Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics, 1993, pp.953-961.

54. B. Hendrickson, R. Leland. Multidimensional Spectral Load Balancing. Technical report SAND 93-0074, Sandia National Laboratories, Albuquerque, NM, 1993.

55. G. Karypis, V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. Technical report CORR 95-035, University of Minnesota, Dept. Computer Science, Minneapolis, MN, 1995.

56. G. Karypis, V. Kumar. Analysis of Multilevel Graph Partitioning. Proceedings of the 7th Supercomputing Conference, 1995.

57. B. Kernighan, S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. // Bell System Technical Journal, 1970. No.29. pp.291-307.

58. B. van Leer. Progress In Multidimensional Differencing. // Proceedings of the XIII International Conference on Numerical Methods in Fluid Dynamics. Rome, Italy, 1992.

59. B. Mohar. The Laplacian Spectrum of Graphs. // Graph Theory, Combinatorics, and Applications. John Wiley, New York, 1991. pp.871-898.

60. Embedded Parix, Version 1.9.4/3.1. Software documentation and Reference manual. Par-sytec GmbH, 1997.

61. B. Parlett. The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs, NJ, 1980.

62. B.N. Parlett, H. Simon, L.M. Stringer. On Estimating the Largest Eigenvalue with the Lanczos Algorithm. // Mathematics of Computation, 1982. Vol.38. No.157. pp.153-165.

63. A. Pothen, H. Simon, K. Liou. Partitioning Sparse Matrices with Eigenvectors of Graphs. // SIAM Journal on Matrix Analysis and Applications, 1990. No.l 1. pp.430-452.

64. D. Powers. Graph Partitioning by Eigenvectors. // Linear Algebra and its Applications, 1988. Vol.101, pp.121-133.

65. H.D. Simon. Partitioning of Unstructured Problems for Parallel Processing. // Computing Systems in Engineering, 1991. Vol.2. No.2/3. pp.135-148.

66. L.M. Stringer. Efficient and Optimal Methods for Finding the Largest Eigenvalue of a Real Symmetric Matrix. Ph.D. thesis. University of California, Berkeley, 1980.