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

• Трапезникова, Марина Александровна
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Трапезникова, Марина Александровна

Оглавление

Введение

Глава 1. Постановка задачи многофазной фильтрации. Разностная аппроксимация и методы решения уравнения Баклея - Леверетта

1.1 Основные характеристики движения многофазной системы

1.2 Модель Баклея-Леверетта

1.3 Уравнение Баклея-Леверетта в одномерном случае. Скачок

насыщенности

1.4 Методы численного решения уравнения Баклея-Леверетта.

Результаты тестовых расчетов

Рисунки

Глава 2. Параллельные алгоритмы решения разностных

эллиптических уравнений

2.1 Эллиптическое уравнение в модели Баклея-Леверетта

2.2 Параллельный (а — /3)-итерационный алгоритм

2.2.1 Описание (а — /3)-алгоритма

2.2.2 Принципы параллельной реализации (а—¡3)-алгоритма

2.2.3 Анализ параллельных версий (а — /3)-алгоритма

2.3 Параллельные варианты методов Зейделя, верхней и

локальной релаксации

2.4 Расчеты тестовой задачи с помощью различных

параллельных итерационных алгоритмов

Таблицы

Рисунки

Глава 3. Моделирование процесса нефтедобычи на параллельных вычислительных системах

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

3.2 Методы численного решения

Рисунки

3.3 Эффективность параллельных алгоритмов при расчетах

на многопроцессорной системе

Таблица

Рисунок

3.4 Результаты расчетов

Рисунки

3.5 Сравнение обобщенного попеременно - треугольного

метода и (а — (3)-алгоритма

Таблица, рисунки

3.6 Расчеты на кластерах и неоднородных сетях рабочих

станций

Таблицы

Заключение

Список литературы

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

Введение

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

Источники сырья, топлива, питьевой воды исчерпаемы. Сегодня особенно остро встает вопрос бережного отношения к природным ресурсам и преодоления последствий антропогенного воздействия на окружающую среду. Перспективы дальнейшего развития добывающих отраслей промышленности характеризуются переходом на интенсивные способы ведения разработок. При эксплуатации нефтяных месторождений существенная доля нефти добывается с помощью вторичных методов, таких как вытеснение нефти из пласта водой или растворителями [1]-[4]. Однако неэффективное применение этих методов приводит к тому, что коэффициент нефтеотдачи месторождений не превышает 40-50 %. Возникает необходимость рационального проектирования и управления разработкой нефтяных и газонефтяных залежей при заводнении. Выбор системы управляющих воздействий (дополнительное бурение и дополнительная перфорация стволов скважин, изменение типов и режимов скважин) всегда происходит в рамках многочисленных условий и ограничений, осложняется нехваткой геолого-промысловой информации и не может быть осуществлен лишь на основе имеющегося опыта и интуиции. Для реализации очевидных, но не всегда совместимых друг с другом целей заводнения — увеличения добычи нефти, снижения отбора попутных воды и газа, сокращения сроков разработки, повыше-

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

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

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

Создание вычислительных систем массового параллелизма на базе ШБС-процессоров (изначально - транспьютеров [5], а затем - более

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

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

и газовых месторождений выделяют как одну из основных областей, где необходимо использование многопроцессорных суперкомпьютеров [8]-

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

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

Теория фильтрации имеет глубокие исторические корни (см. очерк развития теории фильтрации в [14]). В 1852-1855 гг., производя опыты по фильтрации в песчаных грунтах, французский инженер Г.Дарси установил линейную связь между скоростью фильтрации воды и потерями напора, называемую ныне законом фильтрации Дарси. Первые теоретические исследования, основанные на линейном законе фильтрации, были начаты Ж.Дюпюи в 60-х годах XIX столетия и продолжены в 80-х годах Ф.Форхгеймером. В 1889 г. вышла в свет работа выдающегося русского математика и механика Н.Е.Жуковского "Теоретическое исследование о движении подпочвенных вод", в которой выведены дифференциальные уравнения фильтрации, проведена математическая аналогия фильтрации и теплопроводности, и показано, что напор как функция координат удовлетворяет уравнению Лапласа.

В нашей стране исследования фильтрации развивались в двух ос-

новных направлениях: в гидротехническом и в области проблем добычи нефти и газа. Фундаментом для первого направления послужил труд Н.Н.Павловского "Теория движения грунтовых вод под гидротехническими сооружениями и ее основные приложения", опубликованный в 1922 г. Н.Н.Павловский заметил, что критерием применимости линейного закона фильтрации должно служить число Рейнольдса. Задача о напорной фильтрации под гидротехническими сооружениями впервые трактуется Н.Н.Павловским как задача математической физики. Для ее решения был применен метод конформных преобразований. Позднее стали создаваться приближенные методы получения расчетных зависимостей для гидросооружений.

Направление теории фильтрации, связанное с технологией добычи нефти и газа, возглавил академик Л.С.Лейбензон. В 20-х годах появился ряд его работ, отражающих теоретические и экспериментальные исследования, а в 1934 г. была опубликована обширная монография "Нефтепромысловая механика", в которой выведены уравнения турбулентной фильтрации, разработана теория фильтрации газа и газированной жидкости. Вопросы рациональной расстановки скважин в связи с их взаимодействием были изучены В.Н.Щелкачевым [15], Г.Б.Пыхачевым, И.А.Чарным [16]. Значительный вклад в развитие как гидротехнического, так и нефтегазового направлений внесла академик П.Я.Полубари-нова-Кочина [17], исследовавшая вопросы фильтрации в анизотропных и слоистых грунтах, в криволинейных пластах.

Большой опыт в области теории многофазной фильтрации накоплен зарубежными учеными. Американскими исследователями Р.Виковым и Г.Ботсетом в 30-е годы проведены классические эксперименты по изучению фазовых проницаемостей. Существенное значение имеют основы теории многофазной фильтрации, разработанные С.Баклеем и М.Левереттом [18]. Заметим, что задача о перемещении границы раздела двух жидкостей с различными вязкостью и плотностью впер-

вые была рассмотрена Л.С.Лейбензоном (1934 г.) в связи с исследованием фильтрации нефти или газа в условиях водонапорного режима течения. Явление одновременной фильтрации двух жидкостей (вода - нефть или вода - газ) было названо Л.С.Лейбензоном гидравлическим режимом, а явление фильтрации воды и газированной нефти — газово-гидравлическим режимом [19], [20]. В гидротехническом аспекте задачи двухфазной фильтрации впервые были рассмотрены П.Я.Полубариновой-Кочиной [17] (1940 г.) при изучении плоской напорной неустановившейся фильтрации пресной и соленой воды в основании бетонной плотины гидроузла. Без учета силы тяжести двухфазная фильтрация для случая прямолинейно-параллельного вытеснения рассматривалась С.Баклеем и М.Левереттом [18] (1942 г.), а позже независимо от них А.М.Пирвердяном [21]. Задачи двухфазной фильтрации без учета капиллярных сил известны как задачи (модель) Баклея-Леверетта. Уравнение для насыщенности вытесняющей фазы с учетом капиллярных сил было получено в 1953 г. американскими учеными Л.Рапопортом и В.Лисом (соответствующие модели называют моделями Рапопорта - Лиса или Маскета - Леверетта). Известны труды М.Маскета о фильтрации однородных и неоднородных жидкостей [22], а также о теории упругого режима нефтегазоносного пласта [23]. Большое значение для развития теории фильтрации в целом имеют фундаментальные работы Р.Коллинза (США) [24], Н.Кристеа (Румыния) [25], Х.Азиза и Э.Сеттари (Канада) [26].

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

ности (см. [23], [16], [24], [2], [4]).

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

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

Название "параллельные" стало собирательным для всех вычислительных систем, способных одновременно использовать для обработки информации большое число функциональных устройств [29]. Разработки в области параллельных вычислительных систем проводились, начиная еще с 60-х годов. Наиболее успешным практическим результатом развития этого направления в нашей стране можно считать серийный выпуск многопроцессорных ЭВМ ПС-2000 и Эльбрус-2. Истории и со-

временному состоянию параллельных вычислений в России посвящена статья [30], текст которой доступен через Internet — см. Web-страницу Лаборатории параллельных информационных технологий НИВЦ МГУ им. М.В. Ломоносова "Все (или почти все) о параллельных вычислениях и супер-ЭВМ" [10]. Заметим, что указанный русскоязычный сервер содержит очень квалифицированную и систематизированную подборку информации. Также может быть полезна Web-страница Центра суперкомпьютерных приложений [31].

В 80-х годах многопроцессорные системы совершили настоящий прорыв из области научных публикаций, проектов и пробных малых серий в область коммерческой вычислительной техники. Импульсом послужил выпуск фирмой INMOS Ltd. (Великобритания) в 1985 году микроэлектронного прибора, названного транспьютер (транзисторный компьютер) [5], [32], [33] и специально предназначенного для использования в качестве вычислительного элемента в параллельных архитектурах. Этот прибор объединяет микропроцессор, систему связи и память в одной микросхеме, изготовленной по технологии СБИС, и осуществляет поддержку параллельных вычислений на аппаратном и программном уровне. Из транспьютеров собирались относительно дешевые, но мощные и надежные настольные суперкомпьютеры с перестраиваемой архитектурой. Появлению транспьютера предшествовала разработка фирмой INMOS в содружестве с Оксфордским университетом языка параллельного программирования высокого уровня Оккам (Occam) [34]-[36] для описания модели взаимодействующих последовательных процессов (ВПП) [37]. Основы теории взаимодействия последовательных процессов были заложены Дийкстрой в работе [38]. Транспьютер разрабатывался для реализации модели ВПП и языка Оккам "в железе", в нем имеется аппаратная поддержка основных конструкций языка Оккам, что позволяет выполнять программы на этом языке с эффективностью Ассемблера [39], [40].

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

Параллельные алгоритмы, изучаемые в диссертации, адаптированы к многопроцессорным системам с распределенной памятью. Тип строения памяти — разделяемая (общая) или распределенная (локальная) — является одним из основных признаков классификации параллельных систем. Системы разделяют по различным признакам: по типу потока команд, типу потока данных, способу обработки данных, типу коммуникационной сети, степени однородности компонент системы, степени согласованности режимов работы устройств и т.д. (см. [29], [41]). Первым вариантом классификации была классификация Флинна по типу потока команд и данных, которая делит все вычислительные системы на четыре класса [42], [5]: 81МБ (Одиночный поток команд - множественный поток данных), МПУГО (Множественный поток команд -множественный поток данных), ЭКБ (Одиночный поток команд - одиночный поток данных), МШБ (Множественный поток команд - одиночный поток данных). Далее различными авторами уточнялось понятие М1МБ (классификации Ванга и Бриггса, Хокни, Джонсона и др. - см. [10]). С этих позиций алгоритмы, представленные в диссертации, можно считать ориентированными на М1МБ- и ЭРМБ (Одна программа -множественный поток данных)-системы со слабой связью.

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

мыми, является спорным. Итак, основные классы современных параллельных вычислительных систем:

1) Массивно-параллельные системы (МРР) — однородные, с локальной памятью, могут содержать до нескольких тысяч вычислительных узлов, программирование для них происходит в рамках модели передачи сообщений;

2) Симметричные мультипроцессорные системы (SMP) — содержат небольшое число однородных процессоров, память общая, программирование - в рамках модели общей памяти;

3) Векторно-конвейерные компьютеры — в процессоре предусмотрены команды однотипной обработки векторов независимых данных, выполняющиеся на конвейерных функциональных устройствах, возможно объединение несколько таких процессоров над общей памятью, программирование предусматривает векторизацию циклов и их распараллеливание;

4) Гибридные (кластерные) системы — объединение векторных или SMP-компьютеров в массивно-параллельные системы через высокоскоростную коммуникационную среду, программирование - также в рамках гибридной модели;

5) Сети (кластеры) рабочих станций — сеть общего назначения, возможно неоднородная (кластеры на базе процессоров Intel и ОС Linux, любые локальные сети UNIX-компьютеров с системой поддержки параллельных приложений типа MPI [43]), используемая в качестве дешевого варианта массивно-параллельного компьютера, программирование - в рамках модели передачи сообщений.

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

Использованию для высокопроизводительных параллельных вычис-

лений сетей рабочих станций способствовал прогресс в сетевых технологиях, наблюдающийся с начала 90-х годов [7]. Трудности параллельного программирования на сетях вызваны неоднородностью как вычислительных узлов, так и каналов связи, что оказывает существенное влияние на эффективность программ. Простейший подход к разработке параллельных приложений для расчетов на гетерогенных сетях состоит в переносе программ, написанных в стандартах PVM [44], MPI [43] или HPF [45] и изначально ориентированных на МРР (см. п.1)). Другой подход заключается в разработке новых приложений, учитывающих все особенности используемой параллельной платформы, для чего нужны специализированные средства программирования. В диссертации на примере решения задачи нефтедобычи демонстрируются оба указанных подхода.

Все параллельные модификации рассматриваемых в диссертационной работе алгоритмов основываются на принципе геометрического параллелизма [5] — параллелизма данных или декомпозиции области [46], который состоит в разбиении расчетной на подобласти в соответствии с количеством используемых процессоров, так что каждый процессор производит вычисления в своей подобласти и обрабатывает данные только из своей памяти, а также может обмениваться информацией с другими процессорами. Такой принцип распараллеливания чрезвычайно удобен при решении задач математической физики на системах с распределенной памятью. Помимо геометрического параллелизма различают алгоритмический параллелизм, называемый также функциональным или параллелизмом потока данных [5], когда алгоритм разбивается на участки, которые могут выполняться параллельно разными процессорами. Иногда выделяют еще параллелизм типа "Коллективное решение" [5], при котором одна и та же программа или ее часть выполняется на разных процессорах над разными начальными данными с последующим объединением результатов. В некоторых

областях применения возможно использование "гибридного" — комбинации геометрического и алгоритмического — параллелизма.

В книге американского ученого Теда Льюиса [47] вводятся только две основные парадигмы параллельного программирования: "data-parallel programming" (параллелизм данных) и "control-flow programming" (параллелизм потока управления), все остальные парадигмы по отношению к этим являются подчиненными или уточняющими. В его трактовке data-parallel предполагает, что процессоры выполняют (синхронно или асинхронно) идентичные операции над различными данными, а control-flow соответствует алгоритмическому параллелизму, описанному выше. Эта книга являет собой редкий образец машинно- и язы-ковонезависимого подхода к изложению основ параллельного программирования. Машинная независимость состоит в том, что единственное предположение об архитектуре, которое делается при разработке алгоритма, это наличие N процессоров, возможно неоднородных, связанных сетью или действующих над общей памятью. Для описания параллельных программ предлагается простой псевдо-код, а также используются графы сетей Петри. Льюис вводит очень небольшой набор фундаментальных конструкций, с помощью которых можно выразить любой параллельный алгоритм, а также развивает теорию корректности параллельных программ и строит аналитические модели производительности.

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

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

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

Солидный сборник [6] может служить справочным пособием по совместному исследованию параллельных компьютеров и алгоритмов. Сборник отражает все возможные аспекты параллельных вычислений — от парадигм до высокопроизводительных приложений.

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

- ускорение программы в зависимости от числа процессоров;

- величина затрат времени на синхронизацию;

- влияние размера задачи на ускорение;

- максимальное число занятых процессоров при решении задачи;

- детерминизм выполнения программы.

Эти критерии учитывались в диссертации при разработке и анализе

параллельных алгоритмов и программ.

В упомянутых монографиях преимущественно разрабатывались основы теории параллельных вычислений. Также хочется уделить внимание некоторым книгам, которые можно считать учебниками по параллельным численным методам. Во-первых, это известная книга Дж. Ор-тега [50]. В диссертации на нее есть многочисленные ссылки, особенно в связи с распараллеливанием итерационных методов решения систем сеточных уравнений. В работе [51], как и в книге Дж.Ортега, основное внимание уделяется параллельным методам решения задач линейной алгебры, но также исследуются параллельные методы решения обыкновенных дифференциальных уравнений и задач оптимизации. Методы разрабатываются как в рамках модели передачи сообщений, так и в рамках модели синхронизации для MIMD-систем с общей памятью. Приводится обзор параллельных алгоритмов и программ, использующих расширения языка Fortran, из различных проблемных областей. Подробнее с этой книгой, как и со множеством других ценных материалов и обучающих курсов в режиме on-line, можно познакомится на Web-странице IEEE Parallel Processing Technical Committee [52].

Весьма полно современное состояние в области итерационных методов решения больших разреженных линейных систем отражает книга Й.Саада [53], несколько разделов которой посвящены параллельным численным методам. Описаны как техники, требующие определения оптимальных ускоряющих параметров, так и класс методов сопряженных градиентов с предобусловливателями. Большой интерес представляют работы известных теоретиков вычислительной математики и информатики Дж. Донгарра и X. Ван дер Ворста, например, недавно вышла книга [54]. Дж. Донгарра преимущественно развивает прямые методы решения линейных систем. В то время как X. Ван дер Ворст показывает (см. [55]), что для решения одной (а не множества идентичных с разными правыми частями) системы с большим размером матрицы

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

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

Наиболее распространенными и привлекательными с точки зрения распараллеливания являются явные методы сквозного счета для решения уравнения Баклея-Леверетта, основанные на аппроксимации направленными разностями [56] (схема "уголок" [8]) и центральными разностями с особой аппроксимацией производной по времени [56] (схема Лакса [8]). Эти схемы обладают рядом недостатков, а именно, аппрок-

симационной вязкостью и органичениями на шаг по времени.

Существуют методы решения уравнения Баклея-Леверетта, организованные по принципу "предиктор"-"корректор" [8]. В основном методы такого типа являются модификациями явной схемы Лакса и требуют очень подробной пространственно-временной сетки, что приводит к значительному увеличению общего объема вычислений.

Другой класс методов решения уравнения Баклея-Леверетта основан на локализации скачка водонасьпценности [8], [57]. Так как из-за аппроксимационной вязкости фронт решения "размазывается", нужно уметь либо управлять эффектом "размазывания", либо иметь способ выделения "истинного" разрыва из сглаженного решения. Предлагается вести расчет с использованием подвижной пространственной сетки, сгущающейся в окрестности разрыва. При этом возникает дополнительный круг задач: определить положение фронта на данный момент времени, задать закон сгущения сетки на следующий момент времени, произвести интерполяцию искомых величин с одной сетки на другую. Центральной является задача локализации разрыва, которая обычно решается оптимизационными методами. В одномерном случае локализовать скачок водонасьпценности на составляет труда, при этом численное решение совпадает с точным аналитическим. Но целью исследования является эффективное многопроцессорное решение прикладных задач фильтрации, а в случае многомерного потока указанный способ решения слишком сложен и заведомо неэкономичен, а также весьма нетривиален при распараллеливании, поскольку для балансировки загрузки требует перераспределения данных между процессорами при переходе от одного временного слоя к другому.

Также следует отметить характеристико-интерполяционный метод решения уравнения переноса [58], который хорошо передает положение фронта водонасьпценности (разрыв "размазывается" не более, чем на одну ячейку), однако является весьма трудоемким.

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

♦

влялось с помощью явных разностных схем — схемы с направленными разностями первого порядка точности в сочетании со схемой повышенного порядка аппроксимации LSUDS (the Leonard super upwind difference scheme) и схемы с явным выделением скачка водонасыщенности [12].

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

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

тических уравнений, допускающие эффективную многопроцессорную реализацию. Это направление исследований усиленно развивается — достаточно сослаться на уже упоминавшиеся книги [50], [51], [53]—[55], а также труды ведущих конференций по параллельным вычислениям [59]-[61].

Разрабатываются библиотеки параллельных подпрограмм, в первую очередь реализующие методы решения систем линейных уравнений. Наиболее известны пакет ScaLAPACK [62], [63], включающий в основном прямые методы, и универсальные библиотеки фирмы NAG Ltd. — NAG Parallel Library [64] — для систем с общей, локальной памятью и сетей рабочих станций. Особый интерес представляет новый проект при участии NAG, находящийся в стадии разработки и названный PINEAPL, — переносимые параллельные библиотеки для трудоемких индустриальных приложений [65], [66], предлагающие широкий спектр методов, в том числе и итерационных. Вообще говоря, параллельных численных библиотек немного, доступ к ним бывает затруднен по коммерческим соображениям, как правило, они содержат умеренно эффективные реализации — за универсальность всегда приходится расплачиваться эффективностью. На реальных приложениях эффективность окажется ниже ожидаемой, поскольку библиотечные подпрограммы не учитывают ни специфики конкретной задачи, ни особенностей используемой для проведения расчетов вычислительной техники. В диссертации параллельные численные библиотеки не использовались.

Для решения эллиптических уравнений в ряде трудоемких задач, таких как задачи радиационной газовой динамики, задачи ионосферной физики, при моделирование течений вязкой жидкости, с успехом применялся (а — ¡3)-итерационный алгоритм [67], [68]. Этот алгоритм может быть эффективно распараллелен, о чем свидетельствует опыт его реализации на мультитранспьютерной станции APS-48 [69]-[71]. Таким образом, к моменту начала работы над диссертацией имелся некото-

рый задел, однако расчетов практически важных трудоемких задач с помощью параллельного (а —/3)-алгоритма не проводилось. Различные параллельные версии (а—/3)-алгоритма не были достаточно изучены, и основное внимание уделялось версии, соответствующей декомпозиции расчетной области по первой координате, которая при анализе локальных обменов оказалась наименее эффективной. Также не проводилось сравнения параллельного (а — /3)-алгоритма с какими-либо другими методами. В диссертационной работе все эти упущения были исправлены, (се — /3)-алгоритм использовался при моделировании процессов разработки нефтяных месторождений на вычислительных системах с распределенной памятью и сравнивался с параллельными модификациями таких популярных итерационных методов, как метод Зейделя [50], [53], методы верхней [72]-[74] и локальной релаксации [75]-[78].

Следует заметить, что наиболее экономичными итерационными техниками решения больших линейных систем в настоящее время считаются методы проекций на подпространства Крылова [55], [53] — класс методов, объединяющий различные модификации GMRES, CG, GCR и др. — в комбинации с различными формами предобусловливания для ускорения сходимости. Интересны результаты, изложенные в работе [79], где для построения оператора верхнего слоя в методе сопряженных градиентов (CG) применяется нетрадиционный вариант неполного блочного разложения — иерархическое неполное разложение. Результаты вычислительных экспериментов показывают неоспоримое преимущество этого метода по сравнению с рядом других методов при решении тестовых, а также практических задач многофазной фильтрации. В последовательном варианте скорость сходимости указанного метода выше скорости сходимости (а — /3)-алгоритма, и для достижения заданной точности потребуется меньшее время вычислений, однако эффективная многопроцессорная реализация методов сопряженных градиентов является сложной и не всегда успешно разрешимой задачей. На-

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

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

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

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

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

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

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

и и Т1 и

ние метода секущих на многомерный случаи — метод Ьроидена для решения систем нелинейных уравнений.

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

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

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

С целью ускорения сходимости итераций /3-процесса в уравнения для определения прогоночных коэффициентов /3 и й включается итерационный параметр. Предлагаются различные подходы к определению итерационного параметра при распараллеливании (а — /3)-алгоритма.

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

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

различных параллельных алгоритмов.

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

На примере решения эллиптического уравнения в задаче нефтедобычи параллельный (ее — /3)-алгоритм для линейки процессоров сравнивается с методом локальной релаксации, а параллельная версия (се — (3)-алгоритма для решетки процессоров сравнивается с параллельным вариантом обобщенного попеременно-треугольного метода сопряженных градиентов (ОПТМ-СГ). Определяется общее время вычислений и эффективность распараллеливания. В первом случае — сравнение в пользу [а — /3), во втором — в пользу ОПТМ-СГ.

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

Параллельные алгоритмы решения задачи нефтедобычи были эффективно адаптированы к многопроцессорным системам с распределенной памятью Parsytec PowerXplorer и Parsytec СС, соответствующие параллельные программы написаны на языке Fortran77 с использованием библиотек и средств параллельного программирования PARIX [81]. Расчеты этой же задачи проводились на кластерах рабочих станций с конкурентной сетевой архитектурой, для чего были разработаны параллельные Fortran-программы в стандарте РVM [44]. Для расчетов на гетерогенных сетях компьютеров были написаны программы на языке трС [82] — система программирования трС в качестве коммуникационной платформы использует библиотеку функций передачи сообщений MPI. Таким образом, получены эффективно переносимые программы для моделирования нефтяных месторождений на параллельных вычислительных системах разных классов, представлены данные о производительности соответствующих реализаций.

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

Результаты диссертации опубликованы в научных журналах, сборниках и трудах конференций [83]—[90].

Основные результаты докладывались и обсуждались на

- V Всероссийской конференции РТА "Транспьютерные системы и их применение" (г.Домодедово, октябрь 1995 г.);

- VII Всероссийской школе-семинаре " Современные проблемы математического моделирования" (пос.Абрау-Дюрсо, сентябрь 1997 г.);

- международной конференции ARCS'97: "Architectur von Rechen Systemen" (Германия, г.Росток, сентябрь 1997 г.);

- научном семинаре ИММ РАН "Моделирование процессов нефтедобычи на гетерогенных сетях компьютеров" (май 1998 г.);

- международной конференции Euro-Par'98: "Parallel Processing" (Великобритания, г. Саутгемптон, сентябрь 1998 г.);

- совместном семинаре ИММ РАН и кафедры математического мо-

делирования МФТИ под руководством Е.И. Леванова (февраль 1999 г.);

- научном семинаре кафедры нефтегазовой и подземной гидромеханики РГУ нефти и газа им. И.М. Губкина под руководством В.В. Кадета (февраль 1999 г.).

Опыт автора, приобретенный в ходе работы над диссертацией, отчасти нашел отражение в постановке учебного курса "Организация параллельных вычислений" (лекции, семинары, лабораторные и курсовые работы) для студентов кафедры "Информационные технологии" в МГАТУ им. К.Э. Циолковского (1994-1995 учебный год) и разработке методических указаний к лабораторным работам по дисциплине с тем же названием для студентов кафедры "Вычислительные системы и сети" в МГИЭМ (ТУ) [91].

Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н., проф. Борису Николаевичу Четверушкину за постоянное внимание и поддержку, к.ф.-м.н. Наталье Геннадьевне Чурбано-вой за тесное научное сотрудничество, к.ф.-м.н. Михаилу Владимировичу Якобовскому за ценные обсуждения, к.ф.-м.н. Александру Георгиевичу Чурбанову за полезные советы, к.ф.-м.н. Ольге Юрьевне Милюковой за предоставление программы, реализующей параллельный попеременно-треугольный метод, д.ф.-м.н. Алексею Леонидовичу Лас-товецкому за реализацию программ в системе трС, к.ф.-м.н. Сергею Владимировичу Полякову за разностороннюю помощь. Хочу искренне поблагодарить д.ф.-м.н., проф. Игоря Анатольевича Николаева, оказавшего огромное влияние на формирование моих научных интересов. Также благодарю зарубежных коллег проф. Джамшида Тавангаряна, д-ра Хервига Унгера и д-ра Гунтера Хиппера (Университет г.Росток, Германия) за помощь в проведении расчетов на кластере рабочих станций. Кроме того, благодарю всех сотрудников ИММ РАН за доброжелательное отношение и содействие в работе.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Трапезникова, Марина Александровна

Заключение

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

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

- Проанализированы параллельные варианты некоторых итерационных методов решения разностных эллиптических уравнений; для параллельных версий (а — /3)-алгоритма выведены формулы, определяющие время локальных обменов за одну итерацию, и выявлена наиболее эффективная версия; с помощью тестовых расчетов проведено сравнение времени вычислений и эффективности распараллеливания (а — /3)-алгоритма, методов Зейделя, верхней, локальной релаксации и обобщенного попеременно-треугольного метода сопряженных градиентов.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Трапезникова, Марина Александровна, 1999 год

Список литературы

[1] Басниев К.С., Власов A.M., Кочина И.Н., Максимов В.М. Подземная гидравлика. - М.: Недра, 1986. - 303 с.

[2] Басниев К.С., Кочина И.Н., Максимов В.М. Подземная гидромеханика. - М.: Недра, 1993. - 416 с.

[3] Ентов В.М., Зазовский А.Ф. Гидродинамика процессов повышения нефтеотдачи. - М.: Недра, 1989. - 233 с.

[4] Цынкова О.Э., Мясникова H.A., Баишев Б.Т. Гидродинамические методы увеличения нефтеотдачи. - М.: Недра, 1993. - 160 с.

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

[6] Parallel computing: paradigms & applications. / Ed. by Albert Y. Zomaya. - Int. Thomson Comp. Press, 1996. - 676 p.

[7] El-Rewini H., Lewis T.G. Introduction to distributed computing. -Manning Publications Co., 1997. - 324 p.

[8] Коновалов A.H. Задачи фильтрации многофазной несжимаемой жидкости. - Новосибирск: Наука. Сиб. отд-ие, 1988. - 166 с.

[9] Максимов М.М., Рыбицкая Л.П. Вычислительные машины и математическое моделирование процессов разработки нефтяных месторождений // Нефтяное хозяйство. - 1993. - N3. - С.34-41.

[10] Parallel computing. - http://www.parallel.srcc.msu.su/

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

[12] Якобовский М.В. Решение задач подземной гидравлики на параллельных вычислительных системах: Дис. канд. физ.-мат. наук: 05.13.18. - М., 1995. - 133 с.

[13] Baker M.A., Bowler K.C., Kenway R.D. MIMD implementations of linear solvers for oil reservoir simulation // Parallel Comput. - 1990. - V.16. - pp.313-334.

[14] Аравин В.И., Нумеров С.H. Теория движения жидкостей и газов в недеформируемой пористой среде. - М.: ГИТТЛ, 1953. - 616 с.

[15] Щелкачев В.Н. Избранные труды. - М.: Недра, 1990. - Т. 1-Й.

[16] Чарный И.А. Подземная гидрогазодинамика. -М.: Гостоптехиз-дат, 1963. - 396 с.

[17] Полубаринова-Кочина П.Я. Теория движения грунтовых вод. Изд. 2-е. - М.: Наука, 1977. - 664 с.

[18] Buckley S.Е., Leverett M.С. Mechanism of fluid displacement in sands // Trans. AIME. - 1942. - V.146. - pp.107-116.

[19] Лейбензон Л.С. Собрание трудов: В 2 т. - M.: АН СССР, 1953. -Т. 2: Подземная гидрогазодинамика. - 544 с.

[20] Лейбензон Л.С. Движение природных жидкостей и газов в пористой среде. - М.; Л.: Гостехиздат, 1947. - 244 с.

[21] Пирвердян A.M. Физика и гидравлика нефтяного пласта. - М.: Недра, 1982. - 192 с.

[22] Маскет М. Течение однородных жидкостей в пористой среде: Пер. с англ. изд. 1937 г. - М.; Л.: Гостоптехиздат, 1949. - 628 с.

[23] Маскет М. Физические основы технологии добычи нефти: Пер. с англ. - М.; Л.: Гостоптехиздат, 1953. - 606 с.

[24] Коллинз Р. Течение жидкостей через пористые материалы. -М.: Мир, 1964. - 350 с.

[25] Кристеа Н. Подземная гидравлика: В 2 т. - М.: Гостоптехиздат, 1962.

[26] Азиз X., Сеттари Э. Математическое моделирование пластовых систем. - М.: Недра, 1982. - 407 с.

Максимов M.M., Рыбицкая JI.П. Математическое моделирование процессов разработки нефтяных месторождений. - М.: Недра, 1976. - 264 с.

Жумагулов Б.Т. Математические модели фильтрации неоднородной жидкости и их приложение в компьютерных технологиях для нефтяных месторождений: Автореф. дис. док. тех. наук: 05.13.16. - Бишкек, 1997. - 53 с.

Воеводин В.В. Математические модели и методы в параллельных процессах. - М.: Наука. Гл. ред. физ.-мат. лит., 1986. - 296 с. Fet Ya., Pospelov D. Parallel computing in Russia. - In: Lect. Notes in Comp. Sei. , Vol. 964. - Springer, 1995. - pp. 464-476. Federal Informational and Computing Server of Russian National Network for Science and Education. Center for Supercomputing Applications. - http://www.csa.ru/CSA/

Митчелл Д.А.П., Томпсон Дж.А., Мансон Г.А., Брукс Г.Р. Внутри транспьютера: Пер. с англ. - М.: Мейкер, 1993. - 206 с. Бахтеяров С.Д., Дудников Е.Е., Евсеев М.Ю. Транспьютерная технология. / Под ред. акад. C.B. Емельянова. - М.: Радио и связь, 1993. - 304 с.

Джоунз Г. Программирование на языке Оккам: Пер. с англ. - М.: Мир, 1989. - 208 с.

Бахтеяров С.Д. Язык программирования Оккам. - М.: МНИИПУ, 1989. - 88 с.

Сырков Б.Ю., Матвеев C.B. Программное обеспечение мульти-трансьютерных систем. - М.: Диалог-МИФИ, 1992. - 224 с. Хор Ч.А.Р. Взаимодействующие последовательные процессы: Пер. с англ. - М.: Мир, 1989. - 256 с.

Дийкстра Э. Взаимодействие последовательных процессов. - В кн.: Языки программирования: Пер. с англ. / Под ред. Ф. Же-нюи. - М.: Мир, 1972. - С.9-86.

[39] ИНМОС Лтд. Система команд транспьютера: Пер. с англ. - М.: Мир, 1993. - 264 с.

[40] Стерник О.Г., Корнев Ю.П. Программирование на языке ассемблера для транспьютера: Учебное издание. (Математическое обеспечение и программирование для многопроцессорных систем: Вып. 3) / Под ред. В.К. Левина. - М.: Изд-во МАИ, 1991. - 100 с.

[41] Воеводин Вл.В., А.П. Капитонова. Методы описания и классификация вычислительных систем. - М.: Изд-во МГУ, 1994. - 79 с.

[42] Flynn M.J. Some computer organizations and their effectiveness // IEEE Trans. Comput. - 1972. - C-21, No.9. - pp.948-960.

[43] Message Passing Interface Forum. MPI: a Message-Passing Interface standard, version 1.1. - June 1995.

[44] PVM 3 user's guide and reference manual. - Oak Ridge National Laboratory. - May 1993.

[45] High Performance Fortran Forum. High Performance Fortran language specification, version 2.0. - Rice University, Houston TX. - January 1997.

[46] Domain decomposition methods for partial differential equations. Proc. of the 1st Int. Symp. (Eds. R. Glowinsti et al.), SIAM, Philadelphia. - 1988.

[47] Lewis T.G. Foundations of parallel programming: a machine-independent approach. - IEEE Computer Society Press, 1994. - 284 p.

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

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

[50] Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. - М.: Мир, 1991. - 367 с.

[51] Freeman L., Phillips C. Parallel numerical algorithms. - Prentice Hall, 1993. - 350 p.

[52] IEEE Parallel Processing Technical Committee. -http://www.cs.buifalo.edu/tcpp/

[53] Saad Y. Iterative methods for sparse linear systems. - PWS Publishing Co., Int. Thompson Publ. Co., 1995. - 447 p.

[54] Dongarra J., Duff I., Sorensen D., Van der Vorst H. Numerical linear algebra for high-performance computers. - SIAM, Philadelphia, 1998.

- 342 p.

[55] Van der Vorst H.A. Parallel iterative solution methods for linear systems arising from discretized PDE's. In: Special course on parallel computing in CFD, AGARD - R - 807, AGARD, Neuily-sur-Seine, France. - Workshop Lecture Notes, 1995. - 39 p.

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

[57] Узаков 3. О локализации разрыва в численном решении задачи Баклея-Леверетта // Численные методы механики сплошной среды / АН СССР. Сиб. отд-ние. ВЦ и ИТиПМ. - 1979. - Т.10, N6.

- С.141-149.

[58] Бакирова М.И., Зембеков Н.А., Карпов В.Я. Метод моделирования задачи фильтрации со скачком насыщенности // Математическое моделирование. - 1993. - Т.5, N2. - С.4-65.

[59] Parallel numerical algorithms. In: Euro-Par'97, Proc. of the 3 Int. Euro-Par Conf., August 1997, Passau, Germany (Eds. C. Lengauer et al.), Springer, 1997. - pp.683-759. (Lect. Notes in Сотр. Sci., Vol. 1300.)

[60] Numerical and symbolic algorithms. In: Еиго-Раг'98, Proc. of the 4th Int. Euro-Par Conf., September 1998, Southampton, UK (Eds. D. Pritchard and J. Reeve), Springer, 1998. - pp.747-861. (Lect. Notes in Сотр. Sci., Vol. 1470.)

[61] Parallel computing in CFD. In: CFD'98. Proc. of the 4th European CFD Conf., September 7-11 1998, Athens, Greece (Eds. K.D. Papailiou et al.), John Wiley к Sons. - 1998. - pp.471-500, pp.913-948.

[62] ScaLAPACK user's guide. Eds. L.S. Blackford et al. - SIAM, Philadelphia, 1997.

[63] ScaLAPACK Home Page. -

http://www.es.utk.edu/~ susan/scalapack/scalapack2_home.html

[64] Krommer A., Derakhshan M., Hammarling S. Solving PDE problems on parallel and distributed computer systems using the NAG Parallel Library. In: High-Performance Computing and Networking (Eds. B. Hertzberger and P. Sloot), Springer, 1997. - pp.440-451. (Lect. Notes in Сотр. Sci., Vol. 1225.)

[65] Krommer A.R. Parallel sparse matrix computations using the PINEAPL Library: a performance study. In: Euro-Par'98, Proc. of the J^th Int. Euro-Par Conf., September 1998, Southampton, UK (Eds. D. Pritchard and J. Reeve), Springer, 1998. - pp.804-811. (Lect. Notes in Сотр. Sci., Vol. 1470.)

[66] PINEAPL: A European Project in HPCN. http://www.nag.co.uk/projects/PINEAPL/

[67] Четверушкин Б.Н. Об одном итерационном алгоритме решения разностных уравнений // ЖВМ и МФ. - 1976. - Т.16, N2. - С.519-524.

[68] Волчинская М.И., Четверушкин Б.Н. Об одном итерационном методе решения двумерных уравнений диффузии излучения // ЖВМ и МФ. - 1977. - Т.17, N2. - С.428-436.

[69] Четверушкин Б.Н., Чурбанова Н.Г. О применении принципа геометрического параллелизма для (а — /^-итерационного алгоритма // Математическое моделирование. - 1991. - Т.З, N3. - С.23-128.

[70] Chetverushkin B.N., Churbanova N.G. Solution of elliptic equations using the iterative (a — /3)-solver and domain decomposition technique. In: PACT-93, Proc. of the Int. Conf., August 30-September 4 1993, Obninsk, Russia (Ed. V. Malyshkin). - 1993. - pp.97-101.

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

[72] Evans D.J. Parallel S.O.R. iterative methods // Parallel Comput. -1984. - V.l. - pp.3-18.

[73] Block U., Frommer A., Mayer G. Block colouring schemes for the SOR method on local memory parallel computers // Parallel Comput. -1990. - V. 14. - pp.61-75.

[74] Asenov A., Reid D., Barker J.R. Speed-up of scalable iterative linear solver implemented on an array of transputers // Parallel Comput. -1994. - V.20. - pp.375-387.

[75] Ehrlich L.W. An ad hoc SOR method // J. Comput. Phys. - 1981. -V.44. - pp.31-45.

[76] Botta E.F.F., Veldman A.E.P. On local relaxation methods and their application to convection-diffusion equations //J. Comput. Phys. -1982. - V.48. - pp.127-149.

[77] Ehrlich L.W. The ad-hoc SOR method: a local relaxation scheme. -In: Elliptic Problem Solvers II (Eds. G. Birkhoff and A. Schoenstadt). - Academic Press, Orlando. - 1984. - pp.257-269.

[78] Kuo C.-C.J., Levy B.C., Musicus B.R. A local relaxation method for solving elliptic PDEs on mesh-connected arrays // SIAM J. Stat. Comput. - 1987. - V.8. - pp.550-573.

[79] Максимов M.M., Рыбицкая Л.П., Травкина M.E. Один из методов неполного блочного разложения при численном моделировании за-

дач фильтрации // Математическое моделирование. - 1990. - Т.2, N11. - С.99-107.

[80] Милюкова О.Ю. Параллельный вариант обобщенного попеременно - треугольного метода для эллиптических уравнений // ЖВМ и МФ. - 1998. - Т.38, N12. - С.2003-2013.

[81] PARIX 1.3 for Power PC: Software documentation and Reference manual. - Parsytec Computer GmbH, 1994.

[82] Arapov D., Kalinov A., Lastovetsky A., Ledovskih I., Lewis T. A programming environment for heterogeneous distributed memory machines. In: HCW'97, Proc. of the 6th Heterogeneous Computing Workshop of the 11th Int. Parallel Processing Symp. (IPPS'97), April 1997, IEEE CS Press, Geneva, Switzerland. - 1997. - pp.32-45.

[83] Трапезникова M.A., Чурбанова Н.Г. Неявные параллельные алгоритмы моделирования процесса нефтедобычи // Наука и технология в России. - 1995. - N3(9). - С.21-22.

[84] Chetverushkin B.N., Churbanova N.G., Trapeznikova М.А. Simulation of oil production on parallel computing systems. In: ЯРС97: Grand Challenges in Computer Simulation. Proc. of Simulation MultiConf., April 6-10, 1997, Atlanta, USA (Ed. A.Tentner), SCS, San Diego, CA. - 1997. - pp.122-127.

[85] Трапезникова M.A., Чурбанова Н.Г. Моделирование процесса нефтедобычи явными и неявными численными методами // Математическое моделирование. - 1997. - Т.9, N6. - С.53-66.

[86] Трапезникова М.А., Чурбанова Н.Г. Моделирование процесса нефтедобычи на параллельных вычислительных системах // Тез. докл. VII Всерос. школы-семинара "Современные проблемы математического моделирования", 8-13 сентября 1997, пос.Абрау-Дюрсо (под ред. И.А.Николаева). - РГУ, 1997. - С.134-135

[87] Churbanova N.G., Trapeznikova М.А. Parallel simulation of oil production using explicit and implicit algorithms. In: ARCS'97.

Vortr. der 14.ITG/GI- Fachtagung, September 8-11, 1997, Rostock, Deutschland (Hrsg. D.Tavangarian), VDE-Verlag Gmbh, Berlin, Offenbach. - 1997. - pp.281-290.

[88] Trapeznikova M.A., Churbanova N.G. Simulation of multi-phase fluid filtration on parallel computers with distributed memory. In: CFD'98. Proc. of the 4th European CFD Conf., September 7-11 1998, Athens, Greece (Eds. K.D. Papailiou et al.), John Wiley & Sons. - 1998. -pp.929-934.

[89] Chetverushkin В., Churbanova N., Lastovetsky A., Trapeznikova M. Parallel simulation of oil extraction on heterogeneous networks of computers. In: CSMA'98. Proc. of the Int. Conf., November 1-3 1998, Orlando, FL (Eds. R.K. Guha et al.), SCS, San Diego, CA. - 1998. -pp.53-59.

[90] Трапезникова M.A., Четверушкин Б.Н., Чурбанова Н.Г. Параллельные алгоритмы решения разностных эллиптических уравнений // Фундаментальные физико-математические проблемы и моделирование технико-технологических систем: Сб. науч. тр./ Под ред. Л.А.Уваровой. - М.: "Станкин", 1999. - Вып.2. - С.178-197.

[91] Авдошин С.М., Денисов С.Г., Трапезникова М.А. Программирование на языке ОККАМ в среде OPS (Occam Programming System). Метод, ук. к лаб. раб. М.: МГИЭМ(ТУ). - 1994. - 24 с.

[92] Калиткин Н.Н. Численные методы. / Под ред. А.А. Самарского. М.: Наука, 1978. - 512 с.

[93] Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987. - 600 с.

[94] Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений: Пер. с англ. М.: Мир, 1988. - 440 с.

[95] Самарский А.А. Введение в теорию разностных схем. - М.: Наука, 1971. - 552 с.

[96] Самарский A.A., Андреев В.Б. Разностные методы для эллиптических уравнений. - М.: Наука, 1976. - 352 с.

[97] Четверушкин Б.Н., Чурбанова Н.Г. О многопроцессорном варианте трехмерного итерационного (а — /3)-алгоритма. - М.: Ин-т матем. мод. РАН, 1991. - Препр. N44. - 12 с.

[98] Дорофеева H.H., Кучеров А.Б. Исследование метода двумерных прогонок для решения сеточных эллиптических уравнений. -В сб.: Разностные методы математической физики. / Под ред. Ю.П. Попова и Е.С. Николаева. - М.: МГУ, 1980. - С.3-10.

[99] Кучеров А.Б., Макаров М.М. Применение метода двумерных прогонок к решению пятиточечных разностных уравнений. - В сб.: Разностные методы математической физики. Теория численных методов. / Под ред. A.A. Самарского и Е.С. Николаева. - М.: МГУ, 1981. - С.31-38.

[100] Мажорова О.С. Итерационный метод решения двумерных матричных уравнений. - М.: Ин-т прикл. матем. им. М.В. Келдыша АН СССР, 1989. - Препр. N48. - 12 с.

[101] Самарский A.A., Николаев Е.С. Методы решения сеточных уравнений. - М.: Наука, 1978. - 592 с.

[102] Асенов А., Рейд Д., Браун А., Баркер Дж.Р. Реализация методов верхней релаксации с упорядочением для решения трехмерных задач на многопроцессорных транспьютерных системах и анализ эффективности распараллеливания этих методов: Пер. с англ. Л.Ю.Бирюковой-Савичевой // Вестник РТА. - 1995. - N1(16). -С.18-27.

[103] Reichelt M.W, White J.K., Allen J. Optimal convolution SOR acceleration of waveform relaxation with application to parallel simulation of semiconductor devices // SIAM J. Sci. Comput. - 1995. - V.16. - pp.1137-1158.

[104] Самарский А.А., Попов Ю.П. Разностные методы решения задач газовой динамики. М.: Наука, 1980. - 352 с.

[105] Роуч П. Вычислительная гидродинамика. - М.: Мир, 1980. - 616 с.

[106] Бакирова М.И., Герасимов Б.П., Калачинская И.С., Карпов В.Я, Чурбанов А.Г. Программа расчета уравнений Навье-Стокса в приближении Буссинеска. - М.: Ин. прикл. матем. им. М.В. Келдыша АН СССР, 1983. - Препр. N13. - 24 с.

[107] Tavangarian D., Hipper G., Klein M., Koch M. Performance of workstation clusters with a concurrent network architecture. In: HPC'95: Grand Challenges in Computer Simulation. Proc. of Simulation MultiConf., April 1995, Phoenix, Arizona (Ed. A.Tentner), SCS, San Diego, CA. - 1995. - pp.128-133.

[108] Hipper G., Tavangarian D., Koch M. A concurrent communication architecture for workstation clusters. In: ISMM 95, Washington, D.C. - 1995. - pp.215-224.

[109] The mpC project. - http://www.ispras.ru./" mpc/

[110] Ластовецкий А.Л. Язык и система параллельного программирования для разработки программ, эффективно переносимых в классе распределенных вычислительных систем. Дис. докт. физ.-мат. наук: 05.13.11. - М., 1997. - 189 с.

[111] Гайсарян С.С., Ластовецкий А.Л., Ледовских И.Н., Халецкий Д.А. Расширение ANSI С для векторных и суперскалярных компьютеров // Программирование. - 1995. - N1. - С.26-36.

[112] Милюкова О.Ю., Четверушкин Б.Н. Параллельный вариант попеременно-треугольного метода // ЖВМ и МФ. - 1998. - Т.38, N2. - С.228-238.