автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Комплекс программно-математических средств исследования сложных нестационарных объектов на многопроцессорных системах

На правах рукописи

Антонова Ирина Игоревна

Комплекс программно - математических средств исследования сложных нестационарных объектов на многопроцессорных системах

Специальность 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва 2004

Работа выполнена в Московской государственной академии приборостроения и информатики (МГАПИ).

Научный руководитель: кандидат технических наук,

профессор Р.А.Ашинянц

Официальные оппоненты: доктор технических наук,

профессор Л.Г. Башкиров

кандидат технических наук, доцент В.М.Шишкин

Ведущая организация: Московский горный институт

Защита диссертации состоится «16» ноября 2004г. на заседании диссертационного совета Д 212.119.02 Московской академии приборостроения и информатики по адресу: 107076, Москва, ул. Стромынка, д.20 (тел. 269-58-10).

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

Автореферат разослан «15» октября 2004г.

Ученый секретарь диссертационного совета Д 212.119.02, к.т.н., доцент

?.Ульянов

200^4 14523

I.ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ. Построение математических моделей технологических объектов, особенно нестационарных и распределенных, , представляют сложную задачу. Известные математические модели, развитые в работах академиков Полубариновой-Кочиной П.Я. и Басниева К.С. , описываются дифференциальными уравнениями в частных производных, при этом допускают значительную неопределенность в конкретизации модели. Построение таких моделей основано на предположении о стационарности среды и нестационарности процесса. Основанные на таком подходе модели не адекватны реальному положению, и не учитывают, например, наличие случайных микрогеометрических неоднородностей среды, существование порогового давления и т.д.

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

В связи с этим актуальны две ключевые задачи, решаемые в настоящей диссертации:

1. Создание математических моделей распределенных объектов, основанных на перколяционном подходе, когда среда «обитания» объекта является стохастической и ее влияние на объект существенно.

2. Создание алгоритмов и программ реализации разработанных моделей на многопроцессорных вычислительных системах (МВС).

Со времени появления первой публикации в 1957 г. работы Броадбента и Хаммерсли по теории перколяции подавляющее большинство научных работ издано за рубежом. Отечественная научная литература ограничена несколькими переводными фундаментальными изданиями (например Кестен X. «Теория просачивания для математиков») , работами Тарасевича Ю.Ю., Эфроса А.Л., Шкловского Б.И. в области теоретических исследований и отдельных публикаций по приложению теории перколяции к решению различных задач.

РОС.

БИБЛИОТЕКА СПетерМуг <

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

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

ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка и анализ эффективных методов и алгоритмов исследования динамики сложных распределенных объектов с помощью МВС на основе теории перколяции.

В соответствии с этим в диссертационной работе были поставлены и решены следующие ОСНОВНЫЕ ЗАДАЧИ:

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

2. Создать технологию формирования перколяционной решетки и провести верификацию построенной модели.

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

4. Разработать метод априорной оценки эффективности нестационарных режимов для предварительного определения оптимального диапазона исследуемых параметров.

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

6. Рекомендовать оптимальные режимы воздействия на объект с заданными характеристиками.

В настоящей работе ОБЪЕКТОМ ИССЛЕДОВАНИЯ являются процессы движения жидкости в нерегулярной пористой среде. Поскольку параметры среды случайны и подвержены изменению во времени, то объект, с одной стороны, является не стационарным, а с другой, распределенным. Физика процессов, происходящих в таких средах, описываются методами, развитыми в теории перколяции.

МЕТОДЫ ИССЛЕДОВАНИЯ

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

НАУЧНАЯ НОВИЗНА

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

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

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

АПРОБАЦИЯ ОСНОВНЫХ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЯ

Основные результаты диссертации докладывались и обсуждались на 3-ем Всероссийском семинаре «Теория сеточных методов для нелинейных краевых задач» (Казань, 2000г.), на 4-ом Всероссийском семинаре «Сеточные методы для краевых задач и приложения» (Казань, 2002г.), на V международном конгрессе по математическому моделированию (Дубна, 2002г.), на 3-ей Всероссийской конференции «Гидродинамическая основа радиотомографии» (Москва, 2004г.).

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ

ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Основные результаты опубликованы в 7 работах, список которых приведен в конце автореферата.

СТРУКТУРА И ОБЪЁМ РАБОТЫ

Работа состоит из введения, четырех глав, заключения, приложений и списка литературы из 112 названий. Объем составляет 118 страниц машинописного текста, включая 32 рисунка и 7 таблиц.

И.ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

- создание технологии формирования перколяционной решетки и технологии верификации построенной модели;

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

В качестве изучаемой модельной задачи в диссертационной работе рассматривается инвазионная перколяция (т.е. перколяция вытеснением) -

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

«V -Д |/>|+Н*°; (1)

р.- и—I

а

1^ = 1; (3)

а«±|,0

г<р, = 2 В - -- (2)

Здесь а - индекс, имеющий следующий смысл: -1 соответствует наличию компаненты1 (например, нефти), 0 - вакансии, 1 соответствует наличию компаненты2 (например, воде).

С1] - давление в узле (у),

случайная величина, принимающая значения 0 (закрыт) или 1 (открыт) канал (у - ¡+р о+б) для протекания,

непрерывная случайная величина со значениями из [0,1], характеризующая пропускную способность канала (у - ¡4^+8).

При конкретном разовом расчете величины и задаются

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

В начальном состоянии решетка (пласт) заполнена компонентами в соответствии с приведенными ниже условиями:

^■=0.9,^=0.1,^=0, С,=0. (6)

В ряде узлов расположены истоки (добывающие скважины) и стоки (нагнетательные скважины). Для этих узлов выполняются следующие условия:

= 1, = О, = 0, в и = 0 - для истоков, (7)

F;1 = 0, F° = 0, Fl = 1, G4 (/) = g(t) - для стоков, (8)

где g(f) - заданная функция времени. В расчетах использовалась импульсная кусочно-постоянная функция, принимающая значения 0 и 1 со скважностью от 1 до 10. Под скважностью понимается отношение периода следования импульсов к длине одного импульса Q = T/t0.

/Для описания трехмерных объектов уравнения аналогичны, но имеют более громоздкую систему индексов. Поэтому, чтобы обобщить запись ^равнений для двумерного и трехмерного случаев, были введены векторные индексы т - координаты узла и т + ут - координаты соседнего узла.

Для численного моделирования использована следующая аппроксимация:

(9)

* У.

=-IaK^^f; - ^.е^;), (ю)

Г У.

где т - шаг по времени; U ,U- значения сеточной функции (CuF) в моменты времени t и t+т, соответственно.

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

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

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

Таблица. 1. Значение порогов перколяции для различных решеток.

Решетка (lattice) Рь (bond) Эксперимент Размер сетки

Квадратная 0,5 0,4999 10 000 х 10 000

Кубическая 0,2488126(5) 0,2475 1 000 х 1 000 х 1 000

Порог перколяции или критическая концентрация открытых ребер разделяет две фазы: в одной фазе существуют только конечные кластеры, а в другой существует один бесконечный кластер. В исследуемой задаче это соответственно наличие запертых кластеров и появление промываемого кластера. Уменьшение отклонения величины порога перколяции от теоретического значения происходит с ростом числа узлов в изучаемой решетке, т.е. с уменьшением влияния её фаниц. Поэтому полное совпадение кривых получено лишь на решетках большого размера - трехмерных (800x800x800, 1000x1000x1000, 1100x1100x1100), которые образуют кривую слева, и двумерных (1000x1000, 10000x10000), которые образуют кривую справа.

экспериментальное определение порога перколяции

- Ряд1 Ряд2 -х- РядЗ -А- Ряд4 -Ж- Ряд51

~ж-ж-

0,3 0,4 0,5 0,6 0,7 доля открытых ребер

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

Другим критерием проверки качества заполнения решетки может служить распределение узлов по числу инцидентных каждому из них открытых ребер. Аналитические значения могут быть получены на основании закона Бернулли:

к, = С'6р'(\ - рУ~', ' = 0,...6 - для трехмерной решетки, (11)

к1 / = 0,...4-для двумерной решетки, (12)

где к - доля узлов, каждому из которых инцидентно в точности / открытых ребер; р - доля открытых ребер.

Приведенные в таблице 2 данные свидетельствуют о хорошем соответствии экспериментально полученного распределения

аналитическому.

Таблица.2. Распределение узлов по степеням, при р = 0.4.

Число открытых ребер Аналитическое значение Эксперимент 1000x1000x1000 Относительная ошибка

0 4.65% 4.52% - 0.03

1 18.62% 18.53% - 0.00

2 31.08% 31.30% 0.01

3 27.68% 27.87% 0.01

4 13.86% 13.80% - 0.00

5 3.70% 3.60% - 0.03

6 0.41% 0.39% - 0.07

На основании проведенного анализа свойств решетки можно сделать следующие выводы:

• генератор псч предоставляет удовлетворительную последовательность;

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

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

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

□

Исток

Рис. 2. Топология решетки специального вида.

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

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

Рюмер маиэаиалыюго кластера размер области промьваемЛ статическим воздействием ■ ПотснииальньА йьмрых от использования несгвдоонарнэго режмвоукйствия

Процент открытых ребер

Рис. 3. Размер кластера, который может быть промыт за бесконечное время.

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

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

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

Таблица.З.Сравнение двух методов декомпозиции сеток.

Координатный метод Иерархический метод

Максимальная степень домена 17 16

Общее число разрезанных ребер 32 324 15 504

Максимальное число разрезанных ребер домена 1 507 1 061

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

Численное моделирование выполнялось в широком диапазоне параметров нефтяного пласта: доля открытых ребер варьировалась от 25% до 55%, период - от 700 до 2000 условных единиц, доля времени активного воздействия на пласт - от 0.3 до 1.

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

доля открытых ребер в котором составляла 34%, максимальный выигрыш достигается при нагнетании в течение примерно трети периода и блокировании скважины в остальное время, т.е. при скважности равной трём.

При уже выбранном режиме нестационарного воздействия проведен анализ зависимости максимального достигнутого выигрыша в доле добытой нефти от процента открытых рёбер (рис. 5). Каждая точка на этом графике соответствует разности между двумя количествами остаточной нефти (при стационарном и нестационарном воздействии) на сетке с заданной долей открытых ребер. Видно, что максимальный выигрыш достигается при разработке нефтяного пласта, в котором примерно 40% пор проницаемы. Выигрыш при этом составляет примерно 18%.

Рис.5.3ависимость эффективности добычи от процента открытых ребер.

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

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

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

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

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

100% < 90% 80% 70% 80% 60% ■ 40% 30% 20% 10% 0%

Ч-—-to----

I

О 1000x1 ООО* 100 » 10 000*12 500

SO 100 150 200 250 300 350 400 450 500 Количество процессоров

Рис.7. Эффективность при увеличении числа процессоров до 500.

При проведении расчетов использовался суперкомпьютер "МВС 1000М" [www.jscc.ru], представляющий собой 768 процессорную систему, пиковая производительность которой составляет 1012 операций с плавающей точкой с двойной точностью в секунду при общем объеме оперативной памяти решающего поля 768 Гбайт.

Ш.ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

• Создан комплекс программно-математических средств, обеспечивающий решение задач оценки динамических параметров сложных объектов на многопроцессорных вычислительных системах, позволяющий использовать более 80% вычислительной мощности большого числа процессоров (от десяти до пятисот).

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Антонова И.И., Головешкин В.А., Якобовский М.В. Дефект импульса при ударе тела о жесткую преграду // 3-ий Всероссийский семинар «Теория сеточных методов для нелинейных краевых задач» - Казань, 2000. -С.15-19.

2. Антонова И.И., Якобовская И. М. Распределенные сети в науке и образовании // Наукоемкие технологии образования: Труды X международной научно-методической конференции. Межвузовский сборник научных трудов под общей ред. Благовещенской М.М. - Таганрог: ТРТУ,2001. - С. 166-168.

3. Антонова И.И., Кессель А.Р., Леванов Е.И. Моделирование процессов фильтрации в перколяционных решетках на многопроцессорных системах с распределенной памятью // 4-ый Всероссийский семинар «Сеточные методы для краевых задач и приложения» - Казань, 2002. - С.11-16.

4. I.I Antonova, A.R.Kessel Simulation of filtration processes in percolation lattices on distributed memory multiprocessor systems // 5 International congress of mathematical modeling. Book of abstracts, V.l // responsibl for volume L.A.Uvarova-M. :"JANUS-K", 2002-266p.

5. I.I Antonova, A.R.Kessel Simulation of filtration processes in percolation lattices on distributed memory multiprocessor systems // Journal of Computational Methods in Sciences and Engineering, vol.3, no.l, 2003, pp.1-8, ISSN 1472-7978, Cambridge International Science Publishing, Cambridge CB1 6AZ, Great Britain.

6.Антонова И.И. Моделирование нестационарных режимов нефтедобычи на многопроцессорных системах с помощью перколяционных решеток. // Математическое моделирование и управление в сложных системах. Сб. научных трудов под общей ред. С.Н.Музыкина, А.П.Хныкина. - Москва: МГАПИ, 2003.- С.6-10.

7.Антонова И.И. Методы повышения эффективности процессов обработки данных эксперимента на многопроцессорных системах. // Материалы 3-ей Всероссийской конференции «Гидродинамическая основа радиотомографии» - Москва, 2004. - С.24-25.

Подписано к печати 11.10.2004 г. Формат 60x84. 1/16 Объем 1,0 п.л. Тираж 100 экз. Заказ № 151

Московская государственная академия приборостроения и информатики

107996, Москва, ул. Стромынка, 20

№19309

РНБ Русский фонд

2005-4 14583

Глава 1. АНАЛИЗ ОСНОВНЫХ НАУЧНЫХ РЕЗУЛЬТАТОВ В ИССЛЕДОВАНИИ

РАСПРЕДЕЛЕННЫХ ОБЪЕКТОВ (на примере нефтедобычи).

1.1.ХАРАКТЕРИСТИКИ ПЛАСТА, ТИПЫ ПЛАСТОВ И МЕТОДЫ ВОЗДЕЙСТВИЯ НА ПЛАСТ.

1.2.КЛАССИЧЕСКИЕ МОДЕЛИ НА ОСНОВЕ ДИСКРЕТИЗАЦИИ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ СПЛОШНОЙ СРЕДЫ.

1.3.МОДИФИЦИРОВАННЫЕ МЕТОДЫ ЧИСЛЕННОГО РЕШЕНИЯ СТОХАСТИЧЕСКИХ МНОГОМЕРНЫХ ЗАДАЧ.

1.4.КЛАССИФИКАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.5. ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ.

Глава 2. МАТЕМАТИЧЕСКОЕ МАДЕЛИРОВАНИЕ РАСПРЕДЕЛЕННЫХ ОБЪЕКТОВ

НА ОСНОВЕ ТЕОРИИ ПЕРКОЛЯЦИИ.

2.1 .ФИЗИЧЕСКАЯ МОДЕЛЬ НА ОСНОВЕ ТЕОРИИ ПЕРКОЛЯЦИИ.

2.2.ДИНАМИЧЕСКАЯ ПЕРКОЛЯЦИОННАЯ МОДЕЛЬ (ДПМ).

2.2.1. КИНЕТИЧЕСКИЕ УРАВНЕНИЯ.

2.2.2. УРАВНЕНИЯ ТРЕХКОМПАНЕНТНОЙ ДПМ.

2.3.МЕТОДЫ РЕШЕНИЯ.

2.4.ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ.

2.4.1. МЕТОДЫ ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ.

2.4.2. ГЕОМЕТРИЧЕСКИЙ ПАРАЛЛЕЛИЗМ.

2.5.ВЫВОДЫ ПО МАТЕРИАЛАМ ГЛАВЫ 2.

Глава 3. МЕТОДЫ СОЗДАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ИССЛЕДОВАНИЯ

СЛОЖНЫХ НЕСТАЦИОНАРНЫХ ОБЪЕКТОВ.

3.1. ФОРМИРОВАНИЕ ПЕРКОЛЯЦИОННОЙ РЕШЕТКИ И ЕЁ ВЕРИФИКАЦИЯ

3.1.1. ГЕНЕРАЦИЯ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, ОПРЕДЕЛЯЮЩИХ ПРОНИЦАЕМОСТЬ РЕБЕР.

3.1.2. АНАЛИЗ СВОЙСТВ СФОРМИРОВАННОЙ РЕШЕТКИ.

3.1.2.1. Анализ решетки специального вида

3.1.2.2. Технология изучения свойств решетки

3.1.2.3. Проверка «качества» сформированной перколяционной решетки

3.1.2.4. Определение количества остаточной нефти (при стационарном воздействии)

3.2. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ИССЛЕДОВАНИЯ НЕСТАЦИОНАРНЫХ

РЕЖИМОВ ВОЗДЕЙСТВИЯ НА ПЛАСТ.

3.2.1. МЕТОДЫ ПРЕОБРАЗОВАНИЯ РЕШЕТКИ.

3.2.2. АЛГОРИТМЫ БАЛАНСИРОВКИ ЗАГРУЗКИ.

3.2.2.1. Декомпозиция сеток

3.2.2.2. Балансировка загрузки и распределенный ввод-вывод 79 З.З.ВЫВОДЫ ПО МАТЕРИАЛАМ ГЛАВЫ 3.

Глава.4. РЕАЛИЗАЦИЯ АЛГОРИТМОВ И РЕЗУЛЬТАТЫ ЧИСЛЕННЫХ

ИССЛЕДОВАНИЙ.

4.1.АРХИТЕКТУРА ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ.

4.2. ТЕХНОЛОГИЯ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ MPI.

4.3. РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ И МОДЕЛИРОВАНИЯ.

4.3.1. РАСЧЕТНЫЕ СЕТКИ.

4.3.2. ЭФФЕКТИВНОСТЬ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ.

4.3.3. УСТОЙЧИВОСТЬ АЛГОРИТМА.

4.3.4. РЕЗУЛЬТАТЫ РАСЧЕТОВ НЕСТАЦИОНАРНЫХ РЕЖИМОВ ВОЗДЕЙСТВИЯ НА ПЛАСТ.

4.3.4.1. Список проведенных расчетов

4.3.4.2. Сравнение различных начальных условий

4.3.4.3. Сравнение различных размеров скважин

4.3.4.4. Увеличение нефтеотдачи за счет импульсного воздействия на пласт

4.3.4.5. Сравнение стационарных и пульсационных режимов 108 Приложение 1.

Формат файлов *.раг.

Актуальность темы. Построение математических моделей технологических объектов, особенно нестационарных и распределенных, представляют сложную задачу. Известные математические модели, развитые в работах академиков Полубариновой-Кочиной П.Я. [1], Басниева К.С. [2] и других [3-11], описываются дифференциальными уравнениями в частных производных, при этом допускают значительную неопределенность в конкретизации модели. Построение таких моделей основано на предположении о стационарности среды и нестационарности процесса. Основанные на таком подходе модели не адекватны реальному положению, и не учитывают, например, наличие случайных микрогеометрических неоднородностей среды, существование порогового давления и т.д.

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

В связи с этим актуальны две ключевые задачи, решаемые в настоящей диссертации:

1. Создание математических моделей распределенных объектов, основанных на перколяционном подходе, когда среда «обитания» объекта является стохастической и ее влияние на объект существенно.

2. Создание алгоритмов и программ реализации разработанных моделей на многопроцессорных вычислительных системах (МВС).

Со времени появления первой публикации в 1957 г. работы Броадбента и Хаммерсли [17] по теории перколяции подавляющее большинство научных работ издано за рубежом. Отечественная научная литература ограничена несколькими переводными фундаментальными изданиями (например Кестен X. «Теория просачивания для математиков» [18] ) , работами Тарасевича Ю.Ю. [19], Эфроса А.Л. [20], Шкловского Б.И. [21], в области теоретических исследований, и отдельных публикаций по приложению теории перколяции к решению различных задач [22,23].

В области разработки параллельных методов для решения задач математической физики уже накоплен значительный опыт [24-28]. Однако применение стандартных и общепринятых способов управления вычислительным процессом и обработкой больших объемов данных для распределенных объектов с перколяционными свойствами не является эффективным.

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

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

В соответствии с этим в диссертационной работе были поставлены следующие основные задачи:

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

2. Создать технологию формирования перколяционной решетки и провести верификацию построенной модели.

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

4. Разработать метод априорной оценки эффективности нестационарных режимов для предварительного определения оптимального диапазона исследуемых параметров.

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

6. Рекомендовать оптимальные режимы воздействия на объект с заданными характеристиками.

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

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

Научная новизна состоит в следующем:

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

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

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

Основные результаты опубликованы в 7 работах [30-36]. Они докладывались и обсуждались на 3-ем Всероссийском семинаре «Теория сеточных методов для нелинейных краевых задач» (Казань, 2000г.), на 4-ом Всероссийском семинаре «Сеточные методы для краевых задач и приложения» (Казань, 2002г.), на V международном конгрессе по математическому моделированию (Дубна, 2002г.), на 3-ей Всероссийской конференции «Гидродинамическая основа радиотомографии» (Москва, 2004г.).

Теоретическая и практическая ценность полученных результатов состоит в следующем:

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

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

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

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

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

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

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

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

- создание технологии формирования перколяционной решетки и технологии верификации построенной модели;

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

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

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

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

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

Автор выражает искреннюю благодарность научному руководителю Ашинянцу P.A. за постоянное внимание и поддержку при выполнении работы; академику Кесселю А.Р. за постановку и полезные обсуждения прикладной задачи нефтедобычи; заведующему кафедрой АСОУ Петрову О.М., к.т.н. Ульянову М.В., к.т.н. Никульчеву Е.В., без помощи и ценных рекомендаций которых, диссертация не имела бы многих положительных моментов; сотрудникам кафедры «Высшей математики» за доброжелательную поддержку во время выполнения работы.

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

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

• Создан комплекс программно-математических средств, обеспечивающий решение задач оценки динамических параметров сложных объектов на многопроцессорных вычислительных системах, позволяющий использовать более 80% вычислительной мощности большого числа процессоров (от десяти до пятисот).

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

3. Максимов М.М., Рыбицкая JI.П. Вычислительные машины и математическое моделирование процессов разроботки нефтяных месторождений. "Нефтяное хозяйство", N 3, 1993.

4. Рябченко В.И. Подземная гидромеханика: Учебное пособие/ Кубан. Гос. Технол. Ун-т. Краснодар: Изд-во КубГТУ, 2001г. 85с.

5. Веригин Н.Н., Васильев С.В., Саркисян B.C., Шержуков Б.С. Гидродиналмические и физико-химические свойства горных пород. М.: Недра, 1977. - 270 с.

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

7. Геология и геохимия нефти и газа: Учебник для вузов / А.А.Бакиров, М.В.Бордовская, В.И.Ермолкин, и др., под ред. В.И.Ермольника -Москва, Недра, 1993,288 е.: ил.

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

9. Цынкова О.Э., Мясникова Н.А., Баишев Б.Т. Гидродинамические методы увеличения нефтеотдачи. Москва, недра, 1993, 160 с.

10. W. Kinzelbach. 1986. Groundwater Modelling. New York: Elsevier.

11. Bacley S.E., Leverett M.C. Mechanizm of fluid displacement in sands. // Transition A.L.M., V. 146,1942.

12. V.G.Bakurov, V.I.Gusev, A.F.Izmailov, A.R.Kessel. Dynamical percolation model of oil displasement by water in the oil reservoir // J. Phys. A: Math. Gen. 23(1990) 2507-2521.

13. Kessel A.R., Berim G.O. Percolation Kinetic Model of Fluid Spreading in Oil Stratum //Prog. Synopsis of VIUNITAR International Conference on Heavy Crude and Tav Sands, Houston Texas, 1995, P. 147

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

15. Myerson A.S., Izmailov A.F., Kessel A.R. // Oil Recovery Simulation for Heterogeneous Reservoirs // Proc. Eastern Regional Conf., Pittsburgh, November 1993, SPE 26105, 709-710.

16. Myerson A.S., Izmailov A.F., Kessel A.R // Kinetic approach to the Oil Heterogeneous Reservoirs // Proc. Eastern Regional Conf., Pittsburgh, November 1993, SPE 26930,385-392.

17. Broadbent S.K., Hammersley J.M. Percolation processes I. Crystals and mazes. //Proc. Camb/Phil. Soc. 53, 629-641 (1957).

18. Kesten H. Percolation Theory for Mathematicians. Boston: Birkhauser, 1982.

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

20. Эфрос A.JI. Физика и геометрия беспорядка. М.: Наука. Глав. Ред. Физ.-мат. Лит., 1982. - 176 с. - (библиотечка «Квант». Вып. 19)

21. Скал А.С., Шкловский Б.И. Топология бесконечного кластера в теории перколяции и её связь с теорией прыжковой проводимости.// Физика и техника полупроводников, 8,1586 (1974).

22. Панфилов М.Б., Панфилова И.В. Осредненные модели фильтрационных процессов с неоднородной внутренней структурой. М.: Наука, 1996. -383 с.

23. Панфилов М.Б., Туваева И.В. Перколяционные модели вытеснения жидкостей в случайно неоднородных средах.// М., 1990. 90с. (Препр./ ИПНГ АН СССР, N12).

24. Кадет В.В., Селяков В.И. Перколяционная модель двухфазной фильтрации.//Изв. АН СССР. МЖГ. 1987г. N1, с.88-95.

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

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

27. Математическое моделирование. Современные проблемы математической физики и вычислительной математики. М.: Наука, 1989г. - 312 с. - ISBN 5-02-000754-4

28. Miranker W.L. A survey of parallelism in numerical analyses // SI AM Rev. -1971. V. 13. - N 4. - p. 524 - 547

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

30. Антонова И.И., Головешкин В.А., Якобовский М.В. Дефект импульса при ударе тела о жесткую преграду // 3-ий Всероссийский семинар «Теория сеточных методов для нелинейных краевых задач» Казань, 2000. - С.15-19.

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

32. Flinn M.J. Some computer organizations and their effectiveness // IEEE Trans. Comput. 1972. - C-21, N 9. - pp. 948-960.

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

34. Lorenz C.D. 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).

35. Ziff R. M., Sapoval B. The efficient determination of the percolation threshold by a frontier generating walk in a gradient // J. Phys. A: Math. Gen. 19 LI 169-L1172 (1986).

36. Wilkinson D., Wlemsen J.F. Invasion percolation: A new from of percolation theory. J Phys. A16, 365-376 (1983).

37. Соколов И.М. Размерности и другие геометрические критические показатели в теории протекания// УФЫ. 1986. Т. 150. С.221.

38. Амбарцумян Р.В., Мекке Й., Штойян Д. Введение в стохастическую геометрию. М.: Наука, 1989. - 400 с.

39. Сб. «Фракталы в физике», Москва «Мир» 1988.

40. Stauffer D. // Introduction to Percollation Theory // Taylor and Francis, London 1985

41. Самарский A.A. Теория разностных схем. Москва, Наука, 1989г., 616 с.

42. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.:БХВ-Петербург, 2002. - 608 с.

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

44. Карцев М.А. Принципы организации параллельных вычислений. Структуры вычислительных систем и их реализация // Кибернетика. -1981.-N2.-c. 68-74.

45. Bowler К.С. Transputer mashines and applications // Phys. Reports (Review Section of Physics Letters). 1991. - V. 207, N 3-5. - pp. 261-289.

46. Hoare C.A.R. Transputer application. Manual. Prentice Hall London, 1984.

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

48. Воеводин Вл.В.Теория и практика исследования параллелизма последовательных программ/ЯТрограммирование. 1992. - №3. - С.38-53.

49. Основы теории вычислительных систем. Под ред. С.А.Майорова. Учеб. пособие для вузов. Москва, Высшая школа, 1978,408 е., ил.

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

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

52. Бакирова М.И., Карпов В.Я., Мищенко Т.В. Решение задач фильтрации с использованием полностью неявного метода. М.: ВЦММ, 1991 - 83 с.

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

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

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

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

57. Оре О. Теория графов. Москва, наука,1980, 336 е., перевод с англ.

58. Басакер Р. Сайта Т. Конечные графы и сети. Москва, наука,1974, 368 е., перевод с англ.

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

60. Hendrickson В. and Leland R. A Multi-Level Algorithm for Partitioning Graphs, Tech. Rep. SAND93-1301, Sandia National Laboratories, Albuquerce, October 1993.

61. Hendrickson B. and Leland R. An Improved Spectral Graph Partitioning Algorithm For Mapping Parallel Computations —SIAM J. Sci. Comput., 1995, vol.16. №2.

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

63. Fiduccia C.M. and Mattheyses R.M. A Linear-Time Heuristic for Improving Network Partitions. 19th Design Automatic Conference 1982. - paper 13.1 -p. 175-181.

64. Адельсон-Вельский Г.М., Ландис E.M. Один алгоритм организыции информации // Докл. АН СССР. 1962. Т. 146, №2. С. 263-266.

65. ГергельВ.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Н.Новгород, ННГУ, 2001.

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

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

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

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

70. Воеводин Вл.В. Статистический анализ и вопросы эффективной реализации программ // Вычислительные процессы и системы. — 1993. -№9.-С.249-301.