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

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

ЗАООЛЬ Иззедин

КОМПЛЕКС ПРОГРАММ, РЕАЛИЗУЮЩИЙ ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

МОСКВА 2006

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

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

Елена Валерьевна

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

Юрий Петрович;

кандидат технических наук Демьянов Валерий Лукьянович

Ведущая организация - НИИ вычислительных комплексов им.М.А.Карцева

Защита состоится «_»_2006 года в _ часов _ минут на

заседании диссертационного совета Д 212.200.14 при Российском государственном университете нефти и газа им. И.М.Губкина. Ленинский проспект, 65, Москва, ГСП-1, 119991, Россия.

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

Автореферат разослан « »_2006 года.

Ученый секретарь

диссертационного совета Д 212.200.14, д.т.н., доцент

А.В.Егоров

Актуальность темы

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

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

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

Многопроцессорная машина М-10 была создана в СССР в 70-х годах прошлого столетия. К этому моменту на западе уже были созданы такие многопроцессорные системы как JLIAK и SOLOMON.

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

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

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

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

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

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

Цель работы заключается в создании математического обеспечения и на его основе вычислительного комплекса, обеспечивающего решение системы

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

Основные задачи исследования

1. Переформулировка задачи о решении системы нелинейных уравнений в терминах геометрической интерпретации.

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

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

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

Научная новнчна полученных результатов

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

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

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

Практическая ценность работы

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

2. Построенная компьютерная система позволяет решать конкретные практические задачи.

3. С помощью компьютерной системы решена задача о фонтанирующей скважине при нефтедобыче.

Положения, выносимые на защиту

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

2. Алгоритмы решения нелинейных систем методом геометрической интерпретации.

3. Программный комплекс для решения нелинейных систем в интерактивном режиме.

Апробация работы

Результаты работы догадывались:

1. на конференции «И Международная научно-техническая конференция»;

2. на конференции «VI Всероссийская конференция молодых ученых, специалистов и студентов по проблемам газовой промышленности России».

Публикации

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

Структура и объем работы

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

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

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

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

Начиная с третьей главы и далее содержатся собственные результаты автора.

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

Идея метода Рассмотрим пример.

Пусть задана система, состоящая из двух квадратных уравнений

\ахх2 + ву + С^у + А* + Еху + Я, = 0,

{А2х2 + В2у2+С2ху + В2х + Е2у + Н2 = 0 (1)

Рассмотрим две функции от двух переменных

г = Е{ (.г, у) = А,х2 + ву + С,ху + + Е{у + Н{, г - Е2{х,у) = А2х2 + В2у2 + С2ху + И2х + Е2у + Н2.

Уравнения системы (1) определяют линии уровня для функций

и , где соответствующие функции равны нулю.

Решения этой системы будут координатами точек, являющихся пересечением линий уровня (рис. I).

Рассмотрим поведение функций 2~^\{Х'У), 2 ~ ^2\х'У) в

окрестности их линий уровня (см. рис. 1). Пусть функция 2 = больше

нуля вне эллипса, а меньше нуля внутри его. Это значит, что в окрестности

эллипса, где найдутся как точки где-^(*>>')> О, так и точки

Рис. 1. ГI^метрическая интерпретация решения систем нелинейных уравнении

Аналогично для функции ^ — . Пусть вне второго эллипса она

меньше нуля, а внутри его - больше нуля. Это значит, что в окрестности второго

эллипса, где^2(-*».У)= 0, найдутся как точки где ^"гС*'у)^, так и точки где

Рассмотрим точки пересечения эллипсов, т.е. те точки, координаты которых являются решениями системы (1).

В окрестности этих точек найдутся точки четырех типов:

О,

1 тип: точки, где (х> >>) > 0 •

2тип: точки, где у)<0 .

Г/ф.дОсО,

3 тип: точки, где ^(х>у)>0>

Шх,у)< О,

4 тип: точки, где ^ (х> у) < 0 .

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

Метод геометрической интерпретации состоит в отыскании точек-решений по этому признаку.

Решение системы на многопроцессорном компьютере

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

На плоскости (х,у) построится набор точек, с координатами (•*•; 'У)), i,j = h■^,N , Это будут узлы некоторой сетки. В каждом узле вычисляются значения функций Р\ > У^ ) и ^г (•*,■ > У} ).

Это вычисление на многопроцессорной машине делается

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

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

№(х„У))>0,

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

Если при этом наборе узлов такое не случится, то строим набор узлов в другом месте.

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

Алгоритм решения

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

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

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

Случай квадратных уравнений

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

На плоскости построим набор точек, с координатами

^>J , Это будут узлы некоторой сетки. В каждом узле вычисляются

значения функции 4 -"и 4 ''.

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

последовательно вычисляются значения ^(^¡».Уу»2*,), »У/ >2к ) и

^(^»»^у»2*), — 1,.., N. Интерфейс позволяет вводить исходную

систему уравнений с экрана (см. рис 3).

На рис. 2 изображена блок — схема работы компьютерной системы.

1'ис. 2. Блок - схема программы для решения системы квадратных уравнении.

На рис. 3 изображен интерфейс программы

Ш II 1111 ——1......мши ......

- .. г • / .. \ . .. :• ■ •> -

\ \

\ \ \ ' ' \ •

Рис. 3. Интерфейс программы

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

Рис. 4

Для построения графика функции, в окне "options" (рис. 4) необходимо ввести:

• размеры осей;

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

Примечание:

Для изображения "ячеек" (Рис.5), размер какой-либо оси следует сделать меньше шага по ней.

• радиус "точки", который определяет точность решений;

• дистанция, с которой будут наблюдаться графики; . • коэффициенты функций.

Все перечисленные выше параметры можно загрузить или сохранить через мешо.

Рис. 5

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

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

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

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

В комплекс вводятся три. программы 111,112,113, осуществляющие вычисления функций П (х,у,2), Р2(х,у,г), Р3(х,у,г), для определения значений х.у.г.

Вычисление функций П, Р2, РЗ по этим подпрограммам осуществляется в каждом из узлов сетки.

Блок - схема работы комплекса в случае произвольных нелинейностей изображено на рис. 6.

Выбор области осмотра

Выбор шага

П1

П2

ПЗ

Изменение шага

Представление системы в виде

•

/^(лг.д'.г^О.

Вычисление функций:

« Щ =Рг(х>У>2\

Последовательно в каадой узле

массиве.

Выделение области, где каждая из функций М),, ш,, и)1 имеет как отрицательные, так и положительные значения.

Рис. 6. Шок — схема работы комплекса в случае произвольных нелинейностей изображено.

В пятой главе рассматривается применение компьютерного комплекса.

Определение предельного дебита фонтанирующей скважины при течении двухфазной жидкости

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

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

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

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

Будем считать

• поток гомогенным;

• массовое гс^тсодержание по стволу скважины постоянным и равным некоторому среднему значению;

• течение изотермическим;

• жидкую фазу несжимаемой;

• газ совершенным, т.е. подчиняющимся уравнению Клапейрона.

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

сЬ~ \~vfijp ' <>>

где ¿Г - ускорение силы тяжести, V - скорость смеси,

С - массовая скорость смеси, Я - коэффициент гидравлического сопротивления, Р - давление,

^ - приведенная скорость газа,

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

При заданных входных параметрах требуется найти так называемые критические значения:

Ркр - критическое значение давления на выходе из скважины;

Мкр - критическое значение массового расхода смеси;

критическое значение объемного расхода, приведенного к атмосферному давлению.

При решении задачи мы имеем дело со следующими величинами: М - массовый расход смеси;

^а - массовый расход газа;

Рс - плотность смеси;

Р% - плотность газа;

Р\ - плотность жидкости;

У** - площадь сечения трубы;

X - массовое газосодержание.

Массовое газосодержание * определяется как

Плотность смеси Рс записывается через массовое газосодержание следующим образом:

1 = * 1-х

Рс Рц Р1

Используем следующие известные соотношения:

п М „ _ Мк МКЯТ0 хМТаИ

рр* ' ят0 ■

Здесь То - температура, Я -газовая постоянная. Из (4) и (5) имеем:

~ 2 М2 = Р^

Г . \

X 1-х

— +-

V X

{Ре Р1

1-х

— +-

Ре Р1

М2хКТп „ М

Iг2

Ь р

- = с

р2 •

с=хЯГ0

Подставляя (6), (7), (8) в уравнение (1), получим:

Л м2

Ыг

х 1-х

— +-

Р8 Р1

У«

£

(3)

(4)

Х/Р8+(1~Х)/Р,

СМ2

(5)

(6) (7)

(8) (9)

(!«)

Будем считать, что в условиях критического истечения флюида из скважины при 2 = 0 градиент давления растёт до бесконечности, т. е. знаменатель выражения (10) обращается в ноль. А значит в этом случае с учётом

(9) можно найти связь между ^кр и Ркр, которые ещё нам неизвестны. Эта связь выглядит следующим образом:

1--^ = 0

Р*р

и р - Ркр

где Мкр и ркр _ соответственно массовый расход и давление на выходе из скважины.

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

Уравнение (10) в случае истечения с критическим расходом записывается

в виде:

{ . 1 Л

Л „2 ■л

1 1-х

+ -

ф(г)_ 2РИк\р{?) хИТьР,) лгЛГ0/р(г)+(1-х)/р,

8

& , р* (12)

1

В этом уравнении

Ркр - неизвестная величина, равная конкретному значению, пока нам неизвестному, а р{?) - это давление, зависящее от 2 .

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

р1-Рс=А0 + В(>2 , 03)

где О - объемный расход, приведенный к атмосферному давлению, А

и В - параметры пласта, Рт - пластовое давление, а Ре - давление на забое скважины.

При критическом истечении

Л/

в =

(14)

ГДС Рсат - плотность смеси при атмосферном давлении.

Используя соотношения (11) и (14), уравнение (13) можно представить в

виде

р1-р1=нРкр+Ер1Р.

Здесь

Л2

4-1*

В

Ш*

А и В - параметры, зависящие от свойств пласта. Перепишем уравнение (12) в виде

<к

1-

р:Р

(15)

(16)

ф _Я_ 2 ( 1 1 — л: ^ g

2Э Нр{г) + хКТйр, J + хЛГо/Иг)+0-х)/А

где р(2) - это функция, обратная функции 2(р).

Решение уравнения (17), а именно будет

интегралом:

1-

р1рл

Ф

1 1-х ^

20 РЛр + хЯТ0р, J + хИТ0/р + (1 -х)/р,

8

(18)

Вычислив этот интеграл в пределах скважины, т.е. от Р — Рс , до Р — Ркр, получим длину скважины Ь .

Таким образом

( „П

рч.

1-

/V

ф

Л-

2£

1 1-х

+

Р хЯТ0р,

&

. 09)

х/гг0/Р+(1-х)/р(

Произведя интегрирование в формуле (19), получим соотношение,

связывающее Ркр и Рс с заданными параметрами задачи, а именно соотношение (20).

где

1л . \ 2 а{хус4в1{х)ркр

агсЩ

вХх)+а2(хЫр+а^Гс4

л/С4В,(х)

ФУ

(

— arctg

рс(в1(х)+а2(х)С4р;р) ^ /~С4

Ч 1 КР г

+

V

Р^СЛ{х) вХх)-а2(х)С4р1

+ а

1

\

«р

+

г^ОО+аЧ*)^ 2С4 X (5, {х)+а2{х)С4р1)+ 2 а{х)С4р1р + С4р2кр }-- 1п{р2 (Вх(х) + а2(х)С4р2р)+ 2а{х)С4р;рРс + С4р]р }|-1

при этом

1

рсКТйх рЯТ0 •

Сл =■

хЯТ»

ю-

Итак, мы имеем два уравнения для определения параметров Ркр и Рс •

Первое соотношение - это уравнение (15). Его можно представить в виде

(рс>ркр)= с. -Рс р1р,

у!х х '

в

I п

„ 2 с -. Л ^^_ г -—ь.

— 71 2) ,

Второе соотношение - это

Мы имеем систему из двух нелинейных уравнений

Решение задачи с помощью компьютерной системы

Для решения нашей задачи мы составляем две дополнительные подпрограммы П\ и П2.

На вход подпрограммы поступают конкретно заданные значения

параметров Р^ и рс, а на выходе получаем значение функции [рс > Ркр ) для этих параметров.

На вход подпрограммы П2 также поступают конкретные значения параметров Ркр и Рс, а на выходе получаем значение функции ^г \Рс > Ркр ) от

ЭТИХ КОНКреТНЫХ Ркр и Рс.

Обе эти подпрограммы устроены так, что они зависят от многих

параметров, входящих в определение функций и Рг • Эти параметры следующие: Ь - глубина скважины; О - диаметр труб; Рт - пластовое давление; Ли В - параметры пласта; Рс - плотность конденсата; Ре - плотность газа при атмосферном давлении; Л - коэффициент гидравлического сопротивления; То - температура;

К

- массовое газосодержание.

При использовании программ Пх и П2 все параметры, кроме X, вводятся в программы заранее в виде констант.

Параметр X - массовое газосодержание нас интересует более подробно. О нем мы расскажем ниже.

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

массового содержания * и от Ркр - критического давления. Они связаны формулами

где Р - площадь сечения трубы, Я - газовая постоянная.

В нашем случае I 2

л

Рс ■

Наша программа будет вычислять значения Мкр и ()кр для разных значений параметра ДГ , например, от = 0 до ДГ = 1 с шагом Л* . Для этого при каждом значении X мы должны определить Ркр , Оно входит в систему уравнений

вместе с давлением Рс в этот же момент на забое скважины.

Решая систему уравнений находим Ркр, а заодно и Рс •

Далее используем Ркр для определения Мкр и ()кр _ По расширенной программе проводились расчеты по задаче, сформулированной выше.

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

• глубина скважины - ^ = 3688л/.

• диаметр труб . ^ = 115 мм .

рт = 50 МПа

• пластовое давление - г т ;

• параметры пласта -

А = 0Л1МПа>.сут тыс ■ м '

2

В = 8,б-юЧМ/7а-СН

^ тыс • м )

плотность конденсата ■

р,=1 зо4

м ■

/».=0.73^-

• плотность газа при атмосферном давлении - м ;

1 _ X | 1-х

р Р^ Р Р,

• плотность смеси с записывается ' а' ' ' ;

X — 0 02

• коэффициент гидравлического сопротивления - ' ;

Т0 — 321Л"

• температура - и ;

Р-9Й7/—

• газовая постоянная - Л

кг К

массовое газосодержание X изменялось от 0 до 1.

Вычисление Сг, С3, С4 через параметры-константы

О

х = * + Ах

* * 1

ж = 1

Вычисление «О) и

ВЫХОД

Вычисляем поле ^|(Рс>Ркр)

Вычисляем поле ^(Рс>Ркр)

Находим точки (Ре, Ркр), где

^.Срс,ркр) = 0 „

^(РоРкр)^

Л,

М

Ищем кР

X

Ищем

О =—^

Хкр

Рис. 7. Блок - схема расширенной программы 29

—л* Гр«»«<» Стюц Гчвми^мЦ ДтиГртр^КЦ

Пяае>етмм*<м»РЧ

А: |0И

Планов*» г«м [0 73

|оог •»•01 [иГ" »ГУ(355"

1X1 • -----

. (I »>«249.507 I • ЦЭЧЯ6Э "

(100(00

Точка пересечение ркр*ьвият Рс» 440.51 бет«

»62.395 *л>сут Окг « 0.624 м*3/су!

1 чоо сео I «я осе I вое

(Гвтвм

»У-1 Нй«аи и ... I <!) , | а^... | ^.... |

В'!« К ЛИ

Рис. 8. Пример построения графиков.

На рис.8 приведен пример решения системы для задачи о фонтанирующей скважине.

ЗАКЛЮЧЕНИЕ

В работе получены следующие результаты:

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

2. Разработан алгоритм решения нелинейных систем с помощью многопроцессорного компьютера.

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

■ Режим А: решение систем квадратных уравнений;

■ Режим Б: решение нелинейных систем с использованием специализированных подпрограмм.

4. С помощью компьютерной системы решена задача о фонтанирующей скважине.

Основное содержание диссертационной работы отражено в следующих публикациях:

1. Тезисы доклада «Применение многопроцессорных компьютеров для решения уравнений балансов» на конференции «II Международная научно-техническая конференция».

2. Тезисы доклада «Использование геометрической интерпретации для решения нелинейных уравнений» на конференции «VI Всероссийская конференция молодых ученых, специалистов и студентов по проблемам газовой промышленности России».

3. Гливенко Е.В., Заооль И. Использование персональных компьютеров для анализа параллельных алгоритмов геометрической интерпретации задач. Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 1. - 2005.

4. Гливенко Е.В., Заооль И. Параллельные алгоритмы решения систем нелинейных уравнений методом геометрической интерпретации.

5. Гливенко Е.В. Заооль. И. Параллельный алгоритм решения уравнений баланс. Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 1. - 2005.

6. Заооль И. Программный комплекс для решении систем нелинейных уравнений.

Подписано в печать 3. Н.06 Формат 60x90/16

Объем " Тираж {00

Заказ 70г

119991, Москва, Ленинский просп. ,65 Отдел оперативной полиграфии РГУ нефти и газа им. И.М. Губкина

ВВЕДЕНИЕ.

ГЛАВА I. ИСТОРИЯ РАЗВИТИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

§1.1. Параллельность в работе компьютера.

§1.2. Управление параллельным компьютером.

§1.3. Архитектура "функциональная арифметика" и геометрическая интерпретация задач

ГЛАВА II. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ПРИ РЕШЕНИИ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ.

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

§2.2. Степень отображения.

§2.3. Применение степени отображения для решения системы уравнений.

§2.4. Алгоритм обнаружения неподвижной точки.

ГЛАВА III МЕТОД ГЕОМЕТРИЧЕСКОЙ ИНТЕРПРЕТАЦИИ ДЛЯ РЕШЕНИЯ СИСТЕМ

НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

§ 3.1. Идея метода.

§ 3.2. Решение системы на многопроцессорном компьютере.

§ 3.3. Алгоритм решения.

§ 3.3.1. Решение системы из трех уравнений на персональном компьютере.

ГЛАВА IV. КОМПЬЮТЕРНЫЙ КОМПЛЕКС НА ПЕРСОНАЛЬНОМ КОМПЬЮТЕРЕ ДЛЯ

РЕШЕНИЯ СИСТЕМЫ ИЗ ТРЁХ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

§4.1. Случай квадратных уравнений.

§4.2. Случай произвольных нелинейных уравнений.

ГЛАВА V. ПРИМЕНЕНИЯ КОМПЬЮТЕРНОГО КОМПЛЕКСА.

§ 5.1. Определение предельного дебита фонтанирующей скважины при течении двухфазной жидкости.

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

§ 5.1.2. Решение задачи с помощью компьютерной системы.

§5.1.3. Руководство пользователю для решения задачи о фонтанирующей скважине.

ВЫВОДЫ.

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

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

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

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

Работа состоит из пяти глав.

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

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

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

Третья глава содержит параллельные алгоритмы решения нелинейных систем.

Четвертая глава посвящена описанию программного комплекса.

В пятой главе подробно описано применение программного комплекса в нефтегазовой отрасли.

выводы

1. Дан подробный обзор параллелизма в компьютерной системе.

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

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

4. Разработан алгоритм решения нелинейных систем с помощью многопроцессорного компьютера.

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

Режим А: решение систем квадратных уравнений;

Режим Б: решение нелинейных систем с использованием специализированных подпрограмм.

6. С помощью компьютерной системы решена задача о фонтанирующей скважине.

1. Андреев А. Н., Воеводин Вл. В., Жуматий С А. Кластеры и суперкомпьютеры — близнецы или братья? // Открытые системы. — 2000 — № 5- 6. - С. 9 -14.

2. Андрианов А. Н., Бугеря А. Б., Ефимкин К. Н., Звдыхайло И. Б. Норма. Описание языка. Рабочий стандарт / Препринт ИПМ им. М. В. Келдыша РАН. 1995. -№ 120. —50 с.

3. Антонов А. С, Воеводин Вл. В. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных супер-ЭВМ // Программирование. — 1996. —№ 4. — С. 37—51.

4. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1988. —430 с.

5. Воеводин В. В. Вычислительные основы линейной алгебры. — М.: Наука, 1977. —304 с.

6. Воеводин В. В. Информационная структура алгоритмов. — М.: МГУ, 1997. -139 с.

7. Воеводин В. В. Компьютерная революция и вычислительная математика // Математика и кибернетика. — М.: Знание. — 1988. — Вып. 3. — 47 с

8. Воеводин В. В. Массивный параллелизм и декомпозиция алгоритмов // ЖВМ и МФ. 1995,- Т. 35. № 6. - С. 988-996.

9. Воеводин В. В. Математические модели и методы в параллельных процессах, — М.: Наука, 1986. —296 с

10. Воеводин В. В. Математические основы параллельных вычислений.— М.: МГУ, 1991 -345 с.

11. Воеводин В. В. Параллельные структуры алгоритмов и программ. — М.: ОВМ АН СССР. 1987. 148 с.

12. Воеводин В. В. Полиномиальное оценивание сложности алгоритмов // ЖВМ и МФ. 1999. - Т. 39, № 6. - С. 1032-1040.

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

14. Воеводин В. В. Точное описание входных и выходных данных программ // Вестн. Моск. ун-та. Сер. 15, Вычислительная математика и кибернетика. — 1997.— № 1. — С. 41—44.

15. Воеводин В. В. Численные методы алгебры (теория и алгоритмы). — М.: Наука, 1966. 248 с.

16. Воеводин В. В., Капитонова А. П. Методы описания и классификации архитектур вычислительных систем. — М.: МГУ. 1994. — 79 с.

17. Воеводин В. В., Краснов С А. Математические вопросы проектирования систолических массивов / Препринт ОВМ АН СССР. 1985.— № 80. —26 с.

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

19. Гливенко Е.В. Заооль. И. Параллельный алгоритм решения уравнений баланс. Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 1. 2005.

20. Гливенко Е.В. О взаимосвязи архитектуры многопроцессорных систем и параллельных алгоритмов. Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 2. - 2003.

21. Гливенко Е.В. Параллельный процессор первичной обработки информации. М: Радио и связь. - 1992.

22. Гливенко Е.В., Заооль И. Использование персональных компьютеров для анализа параллельных алгоритмов геометрической интерпретации задач. Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 1. 2005.

23. Гливенко Е.В., Заооль И. Параллельные алгоритмы решения систем нелинейных уравнений методом геометрической интерпретации.

24. Гливенко Е.В., Саблина С.М. Многопроцессорные системы и геометрическая интерпретация задач. - Информационные технологии №3.-1996.

25. Гливенко Е.В., Саблина С.М. Методы геометрической интерпретации задач. Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 1. 1997.

26. Головкин Б. А. Параллельные вычислительные системы. — М.: Наука, 1980. -520 с.

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

28. Дубровин Б.А., Новиков С.П., Фоменко А.Т. Современна геометрия. -М: Наука. 1979.

29. Дымников В П. Современные проблемы моделирования отклика климатической системы на малые внешние воздействия // Труды межд. теор. конф. "Проблемы гидрометеорологии и окружающей среды на пороге XXI века". -М.: Гидрометеоиздат, 2000. С. 14-34.

30. Ершов А. П. Современное состояние теории схем программ // Проблемы кибернетики. 1973. - № 27. - С. 87-110.

31. Заооль И. Программный комплекс для решении систем нелинейных уравнений.

32. Красносельский М.А. Векторные поля на плоскости. М: ФИЗМАТГИЗ. -1963.

33. Уоллис Г. Одномерные двухфазные течения. М: Мир, 1972. - 440 с.

34. Фаддеева В. Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре // Кибернетика. — 1977. — №6. С. 28 — 40; 1982. — № 3. С. 18 — 31, 44.

35. Чен-Син Э.П., Панюшева JI.H. Методические указания к лабораторным работам по курсу «Компьютерное моделирование». Учебное пособие. РГУ нефти и газа им. И.М.Губкина, Кафедра прикладной математики и компьютерного моделирования. М: 2004. - 93 с.