Вычислительная среда для моделирования задач механики сплошной среды на высокопроизводительных системах тема диссертации и автореферата по ВАК РФ 05.13.18, доктор физико-математических наук Якобовский, Михаил Владимирович

• Якобовский, Михаил Владимирович
• доктор физико-математических наук
• 2006

Оглавление диссертации доктор физико-математических наук Якобовский, Михаил Владимирович

Введение.

Глава 1. Статическая балансировка загрузки.

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

Критерии декомпозиции графов.

Иерархический алгоритм декомпозиции графа.

Огрубление графа.

Первичное разбиение графа.

Спектральная бисекция.

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

Дополнительные критерии декомпозиции.

Инкрементный алгоритм декомпозиции графа.

Иерархическое хранение больших сеток.

Измельчение пирамидальных сеток.

Глава 2. Динамическая балансировка загрузки.

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

Алгоритм серверного параллелизма.

Структура параллельной программы

Управляющий алгоритм балансировки загрузки.

Основной цикл взаимодействия управляющих процессов.

Двухуровневый алгоритм серверного параллелизма.

Глава 3. Распределенная визуализация.

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

Архитектура системы визуализации.

Этапы визуализации.

Серверная и клиентская части системы визуализации.

Визуализация трехмерных скалярных данных.

Методы преобразования решеток в пирамидальные сетки.

Разбиение ячейки на 24 пирамиды.

Разбиение 8-ми ячеек на 24 пирамиды.

Разбиение ячейки на 5 пирамид.

Симметричное разбиение смежных ячеек.

Разбиение ячейки на 6 пирамид.

Аппроксимация изоповерхности.

Виды данных описывающих триангуляцию.

Точность аппроксимации.

Вычисление абсолютной ошибки.

Сохранение топологических особенностей.

Методы построения аппроксимирующей триангуляции.

Метод кластеризации.

Метод детализации.

Метод синтеза.

Метод редукции.

Параллельные алгоритмы построения аппроксимирующих триангуляций.

Результаты тестирования.

Зависимость времени обработки и коэффициента сжатия методом редукции от точности аппроксимации.

Зависимость времени и коэффициента сжатия от гладкости изоповерхности .119 Соотношение времени чтения данных и времени их обработки.

Сравнение метода синтеза и метода редукции.

Зависимость времени расчета и коэффициента сжатия от числа используемых процессоров.

GRID технологий визуализации данных.

Интерфейс системы визуализации.

Глава 4 Среда моделирования сеточных задач на распределенных вычислительных системах.

Управление вычислительным экспериментом.

Моделирование обтекания трехмерных тел сложной формы.

Моделирование обтекания ступеньки.

Моделирование обтекания сферы.

Моделирование обтекания летательных аппаратов.

Распределенное хранение сеточных данных.

Моделирование задач горения.

Моделирование распространения горячей газовой струи.

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

Параллельный алгоритм генерации последовательностей псевдослучайных чисел

Введение диссертации (часть автореферата) на тему «Вычислительная среда для моделирования задач механики сплошной среды на высокопроизводительных системах»

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

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

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

Значительный качественный разрыв между производительностью компьютеров рабочего места пользователя и распределенного вычислительного пространства, обуславливающий возникновение многих проблем практического использования многопроцессорных систем, будет продолжать возрастать. Подтверждением тому служит активное развитие GRID технологий и возможностей метакомпьютинга, приводящее к интенсивному росту объединенных вычислительных мощностей при относительно низкой стоимости их объединения. В настоящее время нет доступных пакетов, обеспечивающих использование терафлопных вычислительных систем для решения задач механики сплошной среды. Существующие пакеты ориентированы на использование последовательных систем, например FlowVi-sion [1,2,3], либо кластерных систем с ограниченным числом процессоров, например пакет GDT [4,5], или один из ведущих пакетов численного моделирования двух и трехмерных задач газовой динамики, Fluent [6]. Подобная ситуация складывается и в ряде других областях знаний. Создание пакетов, снимающих с прикладного программиста вопросы, не относящиеся непосредственно к предметной области, является приоритетной задачей, поскольку целесообразность дальнейшего развития самих вычислительных систем непосредственно зависит от наличия инструментария, обеспечивающего возможность их эффективного применения.

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

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

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

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

Эффективным методом построения параллельных вычислительных алгоритмов моделирования задач механики сплошной среды является метод геометрического параллелизма. Основная проблема при его использовании связана с необходимостью решения задачи статической балансировки загрузки - выбора такой декомпозиции расчетной сетки, при которой вычислительная нагрузка распределена равномерно между процессорами, а накладные расходы, вызванные возможным дублированием вычислений и необходимостью передачи данных между процессорами малы. Задача сводится к разбиению вершин некоторого графа на заданное число классов эквивалентности - доменов. Задача рационального разбиения графов, наиболее близкой к которой можно считать задачу о разрезании графов [7], принадлежит классу yVP-полных [8], что обуславливает необходимость использования для ее решения эвристических алгоритмов.

К простым, но малоэффективным алгоритмам относятся методы рекурсивного координатного [10,11] и инерциального [9] разбиения. Заслуживают упоминания алгоритмы рациональной декомпозиции сеток, основанные на методах спектрального разбиения, алгоритмах Kernighan-Lin (KL) и Fiduccia-Mattheyses (FM) [62, 67]. Наиболее эффективны иерархические методы рационального разбиения графов [61,78,79]. Доступен ряд пакетов декомпозиции графов, среди которых выделяются последовательные и параллельные версии пакетов СНАСО [12,17] и PARMETIS [13], пакеты PARTY [14], JOSTLE [15], SCOTCH [16], Zolman [189].

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

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

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

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

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

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

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

Общее время расчета уравнений блока кинетики горения многократно превышает время расчета уравнений блока газовой динамики, причем распределение вычислительной загрузки процессоров на этапе расчета кинетики горения отличается сильной неоднородностью из-за большой разницы времён необходимых для расчета областей интенсивного протекания химические реакции и областей, расположенных на удалении от зоны горения. В связи с этим известных алгоритмов статической (геометрический параллелизм, он же «domain decomposition») и динамической (коллективное решение, он же «processor farm» [143,111], диффузная балансировка

19]) балансировки загрузки не достаточно для организации эффективного вычислительного процесса. Так же неэффективен для задач с высокой динамикой миграции по сетке вычислительной нагрузки блочный алгоритм

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

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

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

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

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

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

Созданная система визуализации RemoteView обеспечивает изучение трехмерных скалярных данных. Одним из наиболее мощных и наглядных методов представления трехмерных скалярных данных является визуализация изоповерхностей, в связи с чем поддерживается именно этот метод. Среди подходов к визуализации поверхностей, выделяется метод, основанный на использовании мультитриангуляций [173,172,72,169]. Использование относительно простых структур данных - линейных массивов треугольников, позволяет опираться на известные алгоритмы огрубления триангуляций. Кроме того, современные видеоускорители аппаратно поддерживают отображение массивов треугольников, что значительно повышает наглядность визуализации, как за счет высокой скорости вывода данных на экран, так и за счет возможности автоматического формирования стереоизображений.

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

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

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

Для системы визуализации разработаны алгоритмы сжатия триангулированных поверхностей на основе методов синтеза и, созданные в соавторстве с С.В.Муравьевым, методы сжатия редукцией.

Разработанная в соавторстве с П.С.Криновым и С.В.Муравьевым система визуализации успешно функционирует не только на кластерах и суперкомпьютерах, но и на метакомпьютерах, поскольку объемы передаваемых в ходе ее работы данных относительно невелики.

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

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

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

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

Моделирование обтекания трехмерных тел сложной формы.

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

Моделирование задач горения. Моделирование процессов горения является одной из наиболее сложных с вычислительной точки зрения проблем и требует больших вычислительных ресурсов. Результаты моделирования горения струи метана на многопроцессорной системе МВС-1000М показывают, что применение алгоритма серверного параллелизма обеспечивает эффективность на уровне 60% при расчете сетки, содержащей 1000x1000 узлов, на 600 процессорах, что подтверждает хорошую масштабируемость метода. Так же высокую эффективность подтвердили расчеты горения метановой струи на объединении двух кластеров. Несмотря на медленный канал связи между системами (30 и 12-процессорной) была получена более, чем 90% эффективность.

Моделирование добычи углеводородов с помощью методов пер-коляции. Актуальность проблемы интенсификации добычи нефти обусловлена истощением месторождений и необходимостью снижения остаточной нефтенасыщенности и обводнённости продукции. Перспективным выглядит использование для этих целей подхода, основанного на методах теории перколяции. Для достоверного описания трехмерного пористого коллектора месторождения с помощью перколяционной модели необходимо использовать решетки содержащие более 107 узлов [174], что стало возможным в последнее время благодаря развитию высокопроизводительных многопроцессорных систем. Изучению методов теории перколяции и свойств, описываемых ими многомерных геометрических структур, посвящены монографии [175, 176]. Перколяционный подход для описания фильтрации флюидов и активного нефтевытеснения рассматривается в работах [103,104,105,106].

Трёхфазная динамическая перколяционная модель (ДПМ) [105] хорошо описывает такие эффекты, как наличие порога протекания, кластеров запертой нефти и рукавов прорыва вытесняющего агента, конечное время распространения волн давления. Использование больших вычислительных мощностей позволило обнаружить важное для практических приложений свойство ДПМ: увеличение фильтрационного потока при использовании импульсного режима внешней накачки.

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

При построении генератора использован подход, основанный на рекуррентных соотношениях [119] и аналогичных им генераторах Фибоначчи [177,179]. Разработаны алгоритмы формирования ПСЧ длины 2"5-1, 2ЗП -1 , 21023 - 1 бит, что соответствует 1076, 10ш, Ю307 вещественных чисел.

По теме диссертации опубликовано более 40 работ [21-60], из них 9 статей - в ведущих рецензируемых научных журналах и изданиях, перечень которых определен Высшей аттестационной комиссией [21-29].

Автор глубоко благодарен Б.Н.Четверушкину, оказавшему большое влияние на все этапы выполнения исследований, за неослабевающее внимание к работе и постоянную поддержку. Автор выражает искреннюю благодарность своему учителю Е.И.Леванову за постоянное внимание и поддержку. Автор глубоко благодарен А.Р.Кесселю и С.С.Лапушкину за постановку задачи моделирования динамики заводнения месторождений нефти и газа с помощью перколяционных методов, предложенную математическую модель и плодотворные обсуждения. Автор выражает глубокую благодарность С.В.Полякову, за многочисленные дискуссии по широкому кругу затрагиваемых в диссертации вопросов. Автор благодарен П.С.Кринову, С.А.Сукову, С.В.Муравьёву, М.А.Корнилиной,

С.В.Болдареву, И.И.Антоновой и Д.В.Петрову за совместную работу над созданием и реализацией ряда рассматриваемых в диссертации алгоритмов, библиотек и программ. Автор благодарен Б.М.Шабанову, О.С.Аладышеву, П.Н.Телегину и другим сотрудникам МСЦ РАН за внимательное отношение и всестороннюю поддержку, позволившую успешно выполнить значительную часть вычислительных экспериментов. Автор выражает свою особую благодарность И.И.Галигузовой за доброжелательную поддержку на протяжении многих лет.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Якобовский, Михаил Владимирович

Заключение

В заключении сформулируем основные результаты диссертации:

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

• Предложена модель и создана система распределенной визуализации трехмерных результатов вычислительных экспериментов.

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

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

Список литературы диссертационного исследования доктор физико-математических наук Якобовский, Михаил Владимирович, 2006 год

1. Зибаров A, Бабаев Д., Шадский A GasDynamicsTool 4.0: передовые CFD-технологии для персонального компьютера. // «САПР и графика» Ю'2000. С.44-53, http://www.sapr.ni/Archive/SG/2000/10/8/5. http://www.cfd.ru6. http://www.fluent.co.uk/

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

3. Гэри М, Джонсон Д., Вычислительные машины и труднорешаемые задачи: Пер. с англ. -М. Мир, 1982.-416 е., ил.

4. К. Gremban, G. L Miller, and S.-H. Teng Moment of inertia and graph separators. In Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp452«461, January 1994.

5. R. D Williams, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency: Practice and Experience, 3 (1991), pp. 457-481.

6. Bruce Hendrickson and Robert Leland The Chaco User's Guide: Version 2.0, Sandia Tech Report SAND94--2692,1994.

7. Rolf Diekmann, Robert Preis, Frank Schlimbach, Chris Walshaw. Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM // Parallel Computing, 26,2000 pp.1555-1581

8. R Diekmann, S. Munhukrishman, M V Nayakkankuppam, Engineering diffusive load balancing algorithms using experiments Lecture Notes in Computer Science, 1253 (1997), pp. 111-122.

9. Ф HЯсинский, Л.П.Чернышева, В В Пекунов. Математическое моделирование с помощью компьютерных сетей. Иваново, 2000 204 с.

10. Якобовский МВ. Обработка сеточных данных на распределенных вычислительных системах. // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2004. Вып.2. с. 40-53.

11. Якобовский М.В Инкрементный алгоритм декомпозиции графов. // Вестник Нижегородского Университета им. Н.И.Лобачевского. Серия «Математическое моделирование и оптимальное управление». 2005. Вып. 1(28). Нижний Новгород: Издательство ННГУ. с. 243-250.

12. Корнилина МА., ЯкобовскийМВ Моделирование эволюции сложных нелинейных систем на многопроцессорных вычислительных комплексах // М.:Журнал физической химии. 1995. Т.69. N 8. МАИК «Наука» С.1533-1536.

13. Дородницын Л В, Корнилина М.А , Четверушкин Б Н, Якобовский М В. Моделирование газовых течений при наличии химически активных компонентов // М.: Журн. физ. химии. 1997. Т.71, N 12. МАИК «Наука» с. 2275-2281.

14. Лапушкин С С, Бренерман MX, Якобовский М.В. Моделирование динамических процессов фильтрации в перколяционных решетках на высокопроизводительных вычислительных системах. // М.: Математическое моделирование. 2004. Т. 16, № 11. с. 77-88.

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

16. Самарская Е А., Четверушкин Б И., Чурбанова Н Г, Якобовский М.В. Моделирование на параллельных вычислительных системах процессов распространения примесей в горизонтах подземных вод // Математическое моделирование. 1994. Т.6. N 4. С.3-12.

17. КорнилинаМА, СамарскаяЕА, Четверушкин Б Н, Чурбанова Н Г, Якобовский М.В. Моделирование разработки нефтяных месторождений на параллельных вычислительных системах // М.: Математическое моделирование. 1995. Т.7. N 2. с. 35-48.

18. IakobovskiM.V Parallel Sorting of Large Data Volumes on Distributed Memory Systems. // В кн.: Mathematical modeling: modern methods and applications. The book of scientific articles/edited by Lyudmila A.Uvarova. -Moscow: Yanus-K. 2004. c.153-163.

19. Якобовский MB Распределенные системы и сети. Учебное пособие. // М.: МГТУ "Станкин", 2000, 118 с, ил

20. КульковаЕЮ, Якобовский М.В Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. Учебное пособие. //М.: «Янус-К», 2004.-32 с.

21. Abalakin I.V Boldyrev S.N Chetverushkin В N. Zhokhova A.V, Iakobovski M V Parallel Algorithm for Solving Flow Problems on Unstructured Meshes 16th IMACS World Congress 2000. Proceedings. Lausanne August 21-25, Switzerland, 2000

22. Корнилина МА, Четверушкин БН, Якобовский MB Моделирование фильтрации двухфазной жидкости в водонапорном режиме на высокопроизводительном модуле POWER РС-601 Препринт ИММ, 1995. N 12. 17 с.

23. Якобовский MB. Параллельные алгоритмы сортировки больших объемов данных. В сб. "Фундаментальные физико-математические проблемы и моделирование технико-технологических систем", вып. 7, под ред. Л.А. Уваровой. М., Изд-во "СТАНКИН", 2004. с. 235-249

24. В. Hendricbon, R. Leland. Multilevel Algorithm for Partitioning Graphs. // Supercomputing '95 Proceedings. San Diego, CA, 1995.

25. В Kernighan and S Lin, An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 29 (1970), pp. 291-307.

26. BN. Parlett, H.Simon and LMStringer. On Estimating the Largest Eigenvalue with the Lanczos Algorithm. // Mathematics of computation March 1995. - Vol. 38, Number 157. - p. 153-165.

27. Bruce Hendrickson and Robert Leland A Multi-Level Algorithm for Partitioning Graphs, Tech. Rep. SAND93-1301, Sandia National Laboratories, Al-buquerce, October 1993.

28. Bruce Hendrickson and Robert Leland An Improved Spectral Partitioning Algorithm for Mapping Parallel Computations. // SIAM J. Comput. Phys. -March 1995. Vol. 16, N 2. - p. 452-469.

29. CAR Hoare Communicating sequential processes. In B. Shaw, editor, Digital Systems Design. Proceedings of the Joint IBM University of Newcastle upon Tyne Seminar, 6-9 September 1977, pp. 145-56. Newcastle University, 1978.

30. С Fiduccia and R Mattheyses A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175181, 1982.

31. Deshpande S M. Kinetic theory based new upwind methods for inviscid compressible flow. AIAA Paper 86-0275, 1986.

32. Dijkstra E. W. Cooperating Sequential Processes in Programming Languages, ed. F.Genuys, Academic Press, New York. NY, 1968.

33. Dijkstra E W. Solution of a Problem in Concurrent Program Control. // CACM, Vol. 8, No. 9, Sept. 1965, p. 569.

34. Domain decomposition method for partial differential equations. Proc. of the 1st Int. Symp. (Eds. R.Glowinsti et al.), SIAM, Philadelphia. 1988.

35. E Puppo and R. Scopigno. Simplification, LOD, and Multiresolution- Principles and Applications. Technical Report C97-12, CNUCE, C.N.R., Pisa (Italy), June 1997. (also in: EUROGRAPHICS'97 Tutorial Notes, Eurographics Association, Aire-la-Ville (CH)).

36. Fiedler M A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Praha, Czechoslovak Mathematical Journal, 25(100) 1975, pp. 619-633.

37. Fiedler M Eigenvectors of aciyclic matrices. Praha, Czechoslovak Mathematical Journal, 25(100) 1975, pp. 607-618.

38. Flynn MJ. Some Computer Organizations and their Effectiveness. // IEEE Trans Comput., vol. C-21, pp. 948-960, 1972.

39. George Karypis, Vipin Kumar: Multilevel Graph Partitioning Schemes. ICPP (3) 1995: 113-122

40. Glouber R. II J. Math Phys., 1963, v.4, P.469

41. Hendrickson B. and Leland R. A Multi-Level Algorithm for Partitioning Graphs, Tech. Rep. SAND93-1301, Sandia National Laboratories, Albu-querce, October 1993.

42. Huffman D A. Amethod for the construction of minimum redundancy codes. // Proc. Of IRE., 1952,40, p.1098-1101.

43. I.V. Abalakin, SN. Boldyrev, B.N. Chetverushkin, M V Iakobovski, A.V. Zhokhova Parallel Algorithm for Solving Problems on Unstructured Meshes. 16th IMACS World Congress 2000 Proceedings. Lausanne, August 21-25, 2000.

44. Iakobovski M V, Krinov P.S, Muravyov S V. Large data volume visualization on distributed multiprocessor systems. // Book of Abstracts. Parallel Computational Fluid Dynamics. «Янус-К». 2003. p.301-304.

45. Juan Raul Cebral ZFEM: Collaborative visualisation for parallel multidisci-plinary applications. Parallel CFD '97: Recent development and advances using parallel computes, Manchester, May 19-21, 1997, Preprints.

46. Kershaw D.S The incomplete cholesky-conjugate gradient method for the iterative solution of linear equations. // J. Comput. Phys. 1978. - Vol. 26, N l.-p. 43-65.

47. Kessel A R., Berim G.O./fProg. Synopsis of VI UNITAR International Conference on Heavy Crude and Tav Sands, Houston Texas, 1995, P. 147

48. M. Vlakobovski, P.S Krinov. Visualisation of grand challenge data on distributed multiprocessor systems. // 5 International congress of mathematical modeling. Books of abstracts, V.l // responsible for volume L.A.Uvarova -M.: "JANUS-K", 2002.

49. P.S Krinov, M.V.Iakobovski, S.V.Muravyov. Large data volume visualization on distributed multiprocessor systems. // Book of Abstracts. Parallel Computational Fluid Dynamics.: May 13-15, Moscow, Russia, "JANUS-K", 2003,. c. 301-304.

50. PARIX 1.3 for Power PC: Software documentation and Reference manual, Parsytec Computer GmbH, 1994.

51. Roe L Approximate Riemann Solvers, Parameter Vectors, and Difference Schemes, J. Сотр. Phys.,1981,43, p.357-372.

52. SunOS 5.2 Network interfaces programmer's guide, Sun Microsystems, 1992.

53. T. J. Barth and D. C.Jespersen The Design and Application of Upwind Schemes on Unstructured Meshes, AIAA paper 89-0366, 1989.

54. Welch T.A. A technique for high-perfomance data compression. // IEEE Corn-put. 17, 6 (June 1984), p. 8-19.

55. Ziv J, and Lempel A Compression of individual sequences via variable-rate coding. // IEEE Trans. Inf. Theory IT-24, 5 (Sept. 1978), p. 530-536.

56. Абалакин И.В, Жохова A.B., Четверушкин Б H. Разностные схемы на основе кинетического расщеплении вектора потока, Математическое моделирование, 2000,13, № 4, с.73-82.

57. Архитектура ЭВМ и численные методы. Сб. науч. трудов / Под ред. В.В.Воеводина. М.: ОБМАН СССР, 1983г. 142 с.

58. Бердышев В И, Петрак JI.B Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999.

59. Берим Г.О, Кессель А.Р, Обобщенная кинетическая модель Изинга. Приложение к задачам фильтрации нефти // Известия академии наук, Энергетика, 1998, N 4, с. 52-64.

60. В.ЕАлемасов, Д.В Апросин, МХ.Бренерман, А.Р.Кессель, Я И.Кравцов, Численное моделирование процессов фильтрации в нефтяном пласте // Журнал физической химии, 1998, т.72, № 3, с. 569-573.

61. ВЕАлемасов, Д В Апросин, МХБренерман, А.Р.Кесселъ, Я.И Кравцов, Динамическая перколяционная модель двухфазной фильтрации как модель процессов в нефтяном пласте// Известия академии наук, Энергетика, 1998, N4, с. 65-77.

62. В.Е.Алемасов,МХ.Бренерман,А.Р.Кесселъ,Я.И.Кравцов, Моделирование процессов в "слабо" перемешанных многофазных средах с помощью случайных блужданий. Модели "блуждающих фаз" и "блуждающих волн'7/Математическое моделирование, 1996, т.8, N 5, 37-51.

63. В Мельников Криптография от папируса до компьютера М., ABF, 1996, ил., 336 с.

64. ВатолинД, Ратушняк А., Смирнов М, Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2002. - 384 с.

65. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ: Пер. с англ./ Под ред. Я.Ковалика. Москва: Радио и связь, 1988,432 с.

66. Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Пер. с англ. Мир, 1981,368 с.

67. Д А Аляутдинов, А.НДалевич Параллельный СИ (PARALLEL С). М.: МАИ, 1991, 112 с.

68. Дж. Ортега. Введение в параллельные и векторные методы решения линейных систем: Пер.с англ-М.:Мир, 1991, с.24, с.34.

69. Джамса К, Коуп К Программирование для Internet в среде Windows. -Санкт-Петербург: Питер пресс, 1996.

70. Добеши И. Десять лекций по вейвлетам. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2004,464 стр.

71. Дональд Жнут Искусство программирования, т.З. Сортировка и поиск 2-е изд.: Пер. с английского М.: Издательский дом «Вильяме», 2001.

72. Дородницын Л.В, Четверушкин Б.Н, Чурбанова Н Г. Кинетически согласованные разностные схемы и квазигазодинамическая система для моделирования течений плотных газов и жидкостей. Математическое моделирование, 2001,13, № 4, с. 56-79.

73. Дородницын JI.В, Корнилина МА., Четверушкин Б.Н, Якобовский МВ. Моделирование газовых течений при наличии химически активных компонентов // М.: Журн. физ. химии. 1997. Т.71, N 12. МАИК «Наука» с. 2275-2281.

74. Ентов В.М, Мусин P.M. Микромеханика нелинейных двухфазных течений в пористых средах. Сточное моделирование и перколяционный анализ. М.: Изв. РАН, МЖГ, 1997.

75. ИМ.Соболь Численные методы Монте-Карло. М.: Наука, 1973.

76. Климов А.С. Форматы графических файлов: К.: НИПФ "ДиаСофт Лтд.", 1995-480 с.

77. Ковеня В Я., Тарнавский ГА., Черный С.Г. Применение метода расщепления в задачах аэродинамики. — Новосибирск: Наука. Сиб. отд-ние, 1990.-247 с.

78. Коновалов А.Н. Введение в вычислительные методы линейной алгебры. Новосибирск: ВО "Наука". Сибирская издательская фирма, 1993,159 с.

79. Корнилина МА., Самарская ЕА., Четверушкин БН, Чурбанова Н.Г., Якобовский М.В. Моделирование разработки нефтяных месторождений на параллельных вычислительных системах. Математическое моделирование. М.: Т.7. № 2, 1995. С.35-48.

80. Кринов П.С., Якобовский М.В, Муравьев С.В Сжатие и визуализация триангулированных поверхностей // V-я научная конференция МГТУ "Станкин" и "Учебно-научного центра математического моделирования

81. МГТУ "Станкин" ИММ РАН". Программа, сборник докладов. - М.: Янус-К, ИЦ МГТУ "Станкин" с. 32-42.

82. Маркин МА , Лопатин В.А. Т9000. // Журнал д-ра Добба N 3, 1991, стр. 34-37.

83. Митчел ДА.П., Томпсон ДжА., Мансон ГА., Брукс Г Р. Внутри транспьютера. М.: Мейкер, 1992, 206 с.

84. Никифоров А.И., Никанъшин ДП Перенос частиц двухфазным фильтрационным потоком. Математическое моделирование 10, N 6,42-52 (1998)

85. Оре О. Теория графов. 2- изд.- М.: Наука, Главная редакция физико-математической литературы, 1980,336с.

86. ПХоровиц, У.Хилл. Искусство схемотехники: В 2-х томах. Пер. с англ. -М.: Мир, 1983.-Т.2 590с.

87. Питерсон У. Коды, исправляющие ошибки. // М.: Пер. с англ. Мир, 1964,338 с., ил.

88. Программирование на параллельных вычислительных системах: Пер. с англ. /Р.Бэбб, Дж.Мак-Гроу, Т.Акселрод и др.; под ред. Р.Бэбба II. -М.:Мир, 1991,-376 е., ил.

89. Рождественский Б Л., Яненко Н Н. Системы квазилинейных уравнений и их приложения к газовой динамике. М.: Наука, 1978.

90. С.Гудман, С Хидетниеми. Введение в разработку и анализ алгоритмов. М.: Пер. с англ. Мир, 1981, 368 с.

91. Самарский А А. Математическое моделирование и вычислительный эксперимент // Вестник АН СССР. 1979. - №5. - С. 38-49.

92. Самарский А.А Теория разностных схем. М.: Наука, 1989. - 616 с.

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

94. Самарский А А , Михайлов А.П Математическое моделирование: Идеи. Методы. Примеры. М.: Наука. Физматлит, 1997. - 320 с. - ISBN 5-02015186-6.

95. Самарский А.А., Попов ЮП. Разностные схемы газовой динамики. Главная редакция физико-математической литературы изд-ва «Наука», М., 1975.

96. Скворцов А В, Костюк Ю.Л. Сжатие координат узлов триангуляции // Изв. вузов. Физика, 2002, № 5, с. 26-30

97. С.В Муравьев. Параллельные алгоритмы сжатия результатов численного моделирования трехмерных задач гидродинамики. Диссертация на соискание ученой степени кандидата физико-математических наук

98. Стивене У. Unix: взаимодействие процессов. Мастер-класс./ Пер. с англ.Д.Солнышков. Спб: Питер, 2002.-576 с. ISBN 5-318-00534-9.

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

100. Флетчер К. Численные методы на основе метода Галеркина, Мир, 1988

101. ХейгеманЛ, ЯнгД Прикладные итерационные методы. М.: Мир, 1986. - 448 с.

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

103. Шенен П., Коснар М, Гардан И., Робер Ф., Робер И., Витомски П, Кас-тельжо П. Математика и САПР. М.: Мир, 1988.

104. Эксперимент на дисплее: Первые шаги вычислительной физики / Автор предисловия А.А. Мигдал. М.: Наука, 1989. 175 е., ил. - (Серия "Кибернетика - неограниченные возможности и возможные ограничения").

105. Языки программирования. Под ред. Ф.Женуи, Пер. с англ. В.П.Кузнецова, Под ред. В.М.Курочкина. М.: Мир, 1972,406 стр.150. hypeffun.org

106. Якобовский MB. Распределенные системы и сети. Учебное пособие. -М.: МГТУ "Станкин", 2000, 118 с, ил

107. Куценко JIН., Маркин Л.В Формы и формулы- М.:Изд. МАИ.-1994-176с.

108. Васильев BP., Волобой А.Г., Вьюкова НИ, Галактионов В А., Контекстная визуализация пространственных данных. «Информационные технологии и вычислительные системы», № 4, 2004, стр. 25-34.

109. Бочков М.В, Четверушкин Б.Н. Об одном алгоритме численного решения уравнений кинетики пробоя. М.: Ин-т прикл. матем. им. М.В.Келдыша АН СССР, 1985. Препр. N 123.

110. Бочков MB. Об одном вычислительном алгоритме для систем неоднородных уравнений математической физики // Дифференц. ур-ния. 1988. -Т.24, N7. - С.1150-1160.

111. V. Skala Precission of iso-surface extraction from, volume Data and Visualization, Algoritmy'2000. Int.Conf., Slovakia, 2000, pp.368-378.

112. Rosenbrock H H. Some general implicit processes for the numerical solution of differential equations. // Comput. J. 1963. V.5. №4. P.329-330

113. А.Б Альшин, ЕА.Альшина, H.H. Калиткин, А.Б Корягина Численное решение сверхжестких дифференциально-алгебраических систем.// ДАН, 2006, том 408, №4, с. 1-5.

114. А.Б. Алыиин, ЕА Альшина, Н.Н. Калиткин, А Б Корягина Схемы Розен-брока с комплексными коэффициентами для жестких и дифференциально-алгебраических систем.// :ЖВМиМФ, 2006, том 46, №8, с. 14101431..

115. Buscaglia G.C., Dari Е A. Anisotropic mesh optimization and its application in adaptivity // Internat. J. Numer. Neth. Eng. 1998.

116. Castro Diaz MJ, Hecht F Mohammadi B. New progress in anisotropic grid adaptation for inviscid and viscous flows simulations: Rapp. Rech. 2671, Inst. Nat. Rech. Informat. Automat. France, 1995. P. 1-22.

117. Fortin. M., Vallet M.-G, Dompierre G., Bourgault Y., Habashi W.G Anisotropic mesh adaptation: theory, validation and application // Comput. Fluid. Dynamic. Chichester etc.: John Wiley and Sons Ltd. 1996 P. 174-180.

118. George P.L Automatic mesh generation. Chichester: John Wiley & Sons Ltd., 1991.

119. Yu Vassilevski and К Lipnikov, An adaptive algorithm for quasioptimal mesh generation, Computational Mathematics and Mathematical Physics, 39, № 9, p.1468-1486.

120. Zavattieri P D, Dari E A , Buscaglia G.C. Optimization strategies in unstructured mesh generation // Internat. J. Numer. Meth. In Engng. 1996. V.39.P. 2055-2071.

121. Puppo E, Scopigno R Simplification, LOD and multiresolutional principles and applications // EUROGRAPHICS'97. 1997. -Vol. 16, № 3.

122. Enrico Puppo, Larry Davis, Daniel DeMenthon, Y Ansel Teng Parallel terrain triangulation. Intl. J. of Geographical Information Systems, 8(2): 105128, 1994.

123. Michael Garland and Paul S Heckbert Fast polygonal approximation of terrains and height fields. Technical Report CMU-CS-95-181, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA, September 1995.

124. Delingette H Simplex Meshes: a General Representation for 3D Shape Reconstruction. INRIA research report no. 2214. March 1994.

125. Скворцов А В. Триангуляция Делоне и ее применение // Томск: Изд-во Томск, ун-та, 2002.

126. Мирза НС, Скворцов А.В., Чадное Р.В. Упрощение триангуляционных моделей поверхности. // Теоретическая и прикладная информатика: Сборник статей / Под ред

127. АФ Терпугова Томск: Изд-во Том ун-та, 2004 Вып 1 154 с.

128. В И. Селяков, В В Кадет. Перколяционные модели процессов переноса в микронеоднородных средах. М., Недра, 1995 г.

129. Тарасевич Ю.Ю Перколяция: теория, приложения, алгоритмы: Учебное пособие. М.: Едиториал УРСС, 2002. 112 с.

130. Медведев Н Н. Метод Вороного-Делоне в исследовании структуры некристаллических систем / РАН, Сиб. отд-ние, РФФИ, Институт химической кинетики и горения СО РАН. Новосибирск: НИИЦ ОИГГМ СО РАН, Издательство СО РАН, 2000,214 с.

131. G. Marsaglia, "Random numbers fall mainly on the planes", Proc. Nat. Acad. Sci. USA 61, 1 (1968), 25-28.

132. R. P. Brent, On the Periods of Generalized Fibonacci Recurrences, Technical Report TRCS -92-03, Computer Sciences Laboratory, ANU, March 1992.

133. Кнут Дональд Эрвин, искусство программирования, том.2. Получисленные алгоритмы, 3-е издание.: Пер с англ., : Уч пос М.: Издательский дом <Вильямс>, 2001. - 832 е., ил.

134. John Brillhart, D Н. Lehmer, J.L. Selfridge, Bryant Tuckerman, and SS.

135. Wagstaff, Jr. "Factorizations of bAn+l, b=2,3,5,6,7,10,l 1,12 up to High Powers", Third Edition, American Mathematical Society, 2002,236 pp.

136. Коновалов H.A., Крюков В А., Погребцов A A , Сазанов ЮЛ. C-DVM -язык разработки мобильных параллельных программ // Программирование. 1999. №1.

137. Н.А Коновалов, В А Крюков DVM-подход к разработке параллельных программ для вычислительных кластеров и сетей // "Открытые системы", 2002, №3

138. В А.Крюков, Р В.Удовиченко. "Отладка DVM-программ", Программирование 2001, № 3, стр. 19-29

139. G.Karypis, V.Kumar. Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, 48 (1998), pp. 96-129.

140. Pilkington, J.R, and Baden, S.B Dynamic partitioning of non-uniform structured workloads with spacefilling curves. IEEE Trans, on Parallel and Distrib. Sys. 7(3), Mar. 1996.

141. R Diekmann, R Preis, F. Schlimbach, C. Walshaw. Aspectratio for mesh partitioning. In D. Pritchard and J. Reeve, editors Proc. EuroPar'98 pages 347351, LNCS 1470 SpringerVerlag, 1998.

142. А.Н.Андрианов Разработка методов и программных средств для параллельного программирования вычислительных задач на адаптивных сетках (Грант РФФИ № 05-07-90080-в)

143. К Devine, Е Вотап, R. Heaphy, В Hendricks on, and С. Vaughan Zoltan Data Management Services for Parallel Dynamic Applications. Computing in Science and Engineering, Vol. 4, No. 2, March/April 2002, pp. 90-97.

144. B.J1 Авербух Специализированные системы научной визуализации. Институт математики и механики УрО РАН, г. Екатеринбург, Россия http://www.vniitf.ru/rig/konfer/8zst/s6/6-18.pdf

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

146. КеллиДж. J1 Общая топология. М.: Наука, 1968. - 384 с.

147. P. Cignoni, С Montani and R. Scopigno. "A comparison of mesh simplification algorithms". Computers and Graphics 22 (1998), pp.37-54.

148. P. Hinker and C. Hansen. Geometric optimization. In IEEE Visualization '93 Proc., pages 189-195, October 1993.

149. A.D. Kalvin and R H. Taylor. Superfaces: Poligonal mesh simplification with bounded error. IEEE C.G.&A., 16(3):64-77, 1996

150. William J. Schroeder, Jonathan A Zarge, and William E Lorensen. Decimation of triangle meshes. In Edwin E. Catmull, editor, ACM Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 65-70, July 1992.

151. R Ronfard and J. Rossignac. Full-range approximation of triangulated poly-hedra. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):67-76, 1996.

152. ME Algorri and F. Schmitt. Mesh simplification. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):78-86, 1996.

153. B. Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design, 11(2): 197-214, 1994.

154. A Ciampahni, P Cignoni, C. Montani, and R. Scopigno. Multiresolution decimation based on global error. The Visual Computer, 13(5):228-246, June 1997

155. Greg Turk. Re-tiling polygonal surfaces. In Edwin E. Catmull, editor, ACM

156. Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 55-64, July 1992

157. KL Low and T.S Tan. Model simplification using vertex clustering. In 1997 ACM Symposium on Interactive 3D Graphics, pages 75-82, 1997

158. J. Cohen, A. Varshney, D. Manocha, G. Turk, H Weber, P Agarwal, F Brooks, andW. Wright. Simplification envelopes. In Computer Graphics Proc., Annual Conf. Series (Siggraph '96), ACM Press, pages 119-128, Aug. 6-8 1996

159. M Reddy. Scrooge: Perceptually-driven polygon reduction. Computer Graphics Forum, 15(4): 191-203, 1996

160. C. Andujar, D Ayala, P. Brunei, R. Joan-Arinyo, and J. Sole'. Automatic generation of multiresolution boundary representations. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):87-96, 1996

161. Соколинский JT.Б Обзор архитектур параллельных систем баз данных // Программирование. -2004. -No. 6. -С. 49-63.

162. Соколинский Л.Б Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой // Программирование. -2001. -No. 6. -С. 13-29.

163. С. L. Bajaj and D.R. Schikore. Error bounded reduction of triangle meshes with multivariate data. SPIE, 2656:34-^5, 1996

164. K.Lipnikov, Yu.Vassilevski On control of adaptation in parallel mesh generation. // Engrg. Computers, V.20, pp. 193-201

165. KLipnikov, Yu.Vasilevski Generators of anisotropic adaptive grids. http,//math.lanl.gov/~lipnikov/Research/AniGrids/AniGrids.html

166. С.Н.Боровиков, И.Э.Иванов, И А.Крюков Построение тетраэдризации Делоне с ограничениями для тел с криволинейными границами. // Журнал вычислительной математики и математической физики. 2005, Т. 45, № 8, с. 1407-1423

167. С.Н.Боровиков Построение нерегулярных треугольных сеток на криволинейных гранях на основе триангуляции Делоне. // Математическое моделирование. 2005, Т. 17, № 8, с. 31-35

168. Л Ю. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел, Безопасность информационных технологий, 2 (2005) 27-38.

169. Lorenz CD Ziff R.M. Precise determination of the bond percolation thresholds and finite-size scaling corrections for the sc, fee, and bcc lattices.// Phys. Rev. E 57,230-236 (1998).

170. Kesten H. The critical probability of bond percolation on the square lattice equals 1/2/// Comm. Math. Phys. 74,41-59 (1980).

171. Gushin V. A., Matyushin P V. et al., 2003, Parallel Computing of 3D Separated Homogeneous and Stratified Fluid Flows around Bluff Bodies, Parallel Computational Fluid Dynamics, May 13-15, Abstracts, p. 100.