Содержание к диссертации
Введение
ГЛАВА I. История развития параллельных вычислительных систем 6
1.1. Параллельность в работе компьютера 6
1.2. Управление параллельным компьютером 20
1.3. Архитектура "функциональная арифметика" и геометрическая интерпретация задач43
ГЛАВА II. Геометрическая интерпретация задачи при решении систем линейных алгебраических уравнений 46
2.1. Постановка задачи 46
2.2. Степень отображения 47
2.3. Применение степени отображения для решения системы уравнений 50
2.4. Алгоритм обнаружения неподвижной точки 53
ГЛАВА III Метод геометрической интерпретации для решения систем нелинейных уравнений 57
3.1. Идея метода 57
3.2. Решение системы на многопроцессорном компьютере 59
3.3. Алгоритм решения 60
3.3.1. Решение системы из трех уравнений на персональном компьютере 62
ГЛАВА IV . Компьютерный комплекс на персональном компьютере для решения системы из трёх нелинейных уравнений 64
4.1. Случай квадратных уравнений 64
4.2. Случай произвольных нелинейных уравнений 70
ГЛАВА V. Применения компьютерного комплекса 72
5.1. Определение предельного дебита фонтанирующей скважины при течении двухфазной жидкости 72
5.1.1. Постановка задачи 72
5.1.2. Решение задачи с помощью компьютерной системы 80
5.1.3. Руководство пользователю для решения задачи о фонтанирующей скважине 84
Выводы 91
Литература
- Управление параллельным компьютером
- Применение степени отображения для решения системы уравнений
- Решение системы на многопроцессорном компьютере
- Случай произвольных нелинейных уравнений
Введение к работе
В настоящее время большой интерес представляет собой использование многопроцессорных систем. Однако, уже понятно, что при использовании таких систем камнем преткновения становится возможность так называемого «распараллеливания алгоритмов» для программирования на многопроцессорной структуре. Последовательные алгоритмы, используемые при работе на однопроцессорных компьютерах, не всегда приспособлены для такого распараллеливания.
В последнее время получил распространение метод геометрической интерпретации задач, при котором использование многопроцессорной структуры становится более эффективным.
Истоки этого метода связаны с архитектурой многопроцессорной машины М-10, предназначавшейся для обработки радиолокационной информации. При программировании на этой машине впервые использовался метод геометрической интерпретации задачи.
В настоящей работе предлагаются алгоритмы для решения систем нелинейных (имеются в виду не дифференциальные уравнения) уравнений с использованием геометрической интерпретации задач, рассчитанные на использование в многопроцессорных структурах. На основе этих алгоритмов создан вычислительный комплекс для решения в интерактивном режиме на персональной ЭВМ системы из трех нелинейных уравнений. В работе рассмотрено применение этого комплекса в нефтегазовой отрасли для решения задач с сильной нелинейностью.
Работа состоит из пяти глав.
В первой главе дается обширный обзор применения параллельных вычислений в компьютерах.
Вторая глава посвящена обзору известных применений метода геометрической интерпретации задач.
Третья, четвертая и пятая главы посвящены собственным результатам автора.
Третья глава содержит параллельные алгоритмы решения нелинейных систем.
Четвертая глава посвящена описанию программного комплекса.
В пятой главе подробно описано применение программного комплекса в нефтегазовой отрасли.
Управление параллельным компьютером
Несмотря на явную ограниченность в непосредственных связях даже подобные простые "линейные" топологии хорошо соответствуют многим алгоритмам, в которых необходима связь лишь соседних процессов между собой. В частности, многие одномерные задачи математической физики (да и многомерные с делением области на одномерные) хорошо решаются подобными методами. Для таких задач никаких других топологий придумывать не надо. Но далеко не все задачи такие. Схему сдваивания или блочные методы линейной алгебры на таких топологиях эффективно реализовать не просто, поскольку неправильное размещение процессов по процессорам приведет к потере большей части времени на коммуникации. В идеальной ситуации пользователь не должен думать об этом, у него других проблем хватает, но на практике чудес не бывает. Сегодня по технологическим причинам нельзя сделать большие мультикомпьютерные системы, в которых каждый процессор имел бы непосредственную связь со всеми остальными. А раз так, то и здесь разработчикам вычислительных систем приходится искать компромисс между универсальностью и специализированностью, между сложностью и доступностью. Если класс задач заранее определен, то ситуация сильно облегчается, и результат может быть найден легко. Например, использование схемы распределения работы между параллельными процессами, аналогичной схеме клиент-сервер, при которой один головной процесс раздает задания подчиненным процессам (схема мастер/рабочие, или master/slaves), хорошо соответствует топологии "звезда" (рис. 8, в). Вычислительные узлы, расположенные в лучах звезды, не имеют непосредственной связи между собой. Но это нисколько не мешает эффективному взаимодействию процесса-мастера с подчиненными процессами при условии, что мастер расположен в центральном узле.
Выбор той или иной топологии связи процессоров в конкретной вычислительной системе может быть обусловлен самыми разными причинами. Это могут быть соображения стоимости, технологической реализуемости, простоты сборки и программирования, надежности, минимальности средней длины пути между узлами, минимальности максимального расстояния между узлами и др.
Некоторые варианты показаны на рис. 9. Топология двумерной решетки (рис. 9, а) была использована в начале 90-х годов прошлого века при построении суперкомпьютера Intel Paragon на базе процессоров i860. В соответствии с топологией двумерного тора (рис. 9, 6) могут быть соединены вычислительные узлы кластеров, использующих сеть SCI, предлагаемую компанией Dolphin Interconnect Solutions. Таким образом, в частности, построен один из кластеров НИВЦ МГУ. В настоящее время эта же компания Dolphin предлагает сетевые комплекты, позволяющие объединять узлы в трехмерный тор - чем меньше среднее расстояние между узлами, тем выше надежность. В этом смысле наилучшие показатели имеет топология, в которой каждый процессор имеет непосредственную связь со всеми остальными (рис. 9, в). Но о такой роскоши современный уровень технологии даже мечтать не позволяет: п-1 соединение у каждого узла при общем числе связей п(п — 1)/2.
Иногда находятся исключительно интересные варианты, одним из которых является топология двоичного гиперкуба (рис. 9, г). В w-мерном пространстве рассмотрим лишь вершины единичного «-мерного куба, т. е. точки (xi х , ..., хп), в которых все координаты Xj, могут быть равны либо 0, либо 1. В эти точки мы условно и поместим процессоры системы. Каждый процессор соединим с ближайшим непосредственным соседом вдоль каждого из « измерений. В результате получили «-мерный куб для системы из N=7" процессоров. Двумерный куб соответствует простому квадрату, а четырехмерный вариант условно изображен на рис. 9, г. В гиперкубе каждый процессор связан лишь с log2/V непосредственными соседями, а не с N, как в случае полной связности. Заметим, что при всей кажущейся замысловатости гиперкуб имеет массу полезных свойств. Например, для каждого процессора очень просто определить всех его соседей: они отличаются от него лишь значением какой-либо одной координаты xi Каждая "грань" «-мерного гиперкуба является гиперкубом размерности «- /. Максимальное расстояние между вершинами «-мерного гиперкуба равно «. Гиперкуб симметричен относительно своих узлов; из каждого узла система выглядит одинаковой и не существует узлов, которым необходима специальная обработка. Отметим и то, что многие алгоритмы по своей структуре прекрасно соответствуют такой взаимосвязи между процессорами. В частности неудобная для других топологий схема сдваивания очень хорошо ложится на гиперкуб, используя на каждом шаге алгоритма гиперкуб на единицу меньшей размерности.
Одной из первых реальных многопроцессорных вычислительных систем с архитектурой гиперкуба стал компьютер Cosmic Cube, построенный в 1983 году в Калифорнийском технологическом институте на основе микропроцессоров Intel 8086/8087. В 1985 году фирма Intel выпустила первый промышленный гиперкуб. Это был компьютер iPSC (Intel Personal Supercomputer), в котором в качестве узловых процессоров были использованы микропроцессоры серии 80286/80287. В том же году был объявлен коммерческий гиперкуб NCUBE/ten фирмы NCUBE Corporation, содержащий до 1024 узлов. В некоторых компьютерах гиперкуб использовался в комбинации с другими типами архитектур. В машинах серии Connection Machine фирмы Thinking
Machines использовалось до 216 простых узлов. На одном кристалле этого компьютера находилось 16 узлов, имеющих связь каждый с каждым, а 212 таких кристаллов уже объединялись в 12-мерный гиперкуб. Вернемся к обсуждению особенностей компьютеров с общей и распределенной памятью. Как мы уже видели, оба класса имеют свои достоинства, которые, правда, тут же плавно перетекают в их недостатки. Для компьютеров с общей памятью проще создавать параллельные программы, но их максимальная производительность сильно ограничивается небольшим числом процессоров. А для компьютеров с распределенной памятью все наоборот. Можно ли объединить достоинства, этих двух классов? Одним из возможных направлений является проектирование компьютеров с архитектурой NUMA (Non Uniform Memory Access).
Почему проще писать параллельные программы для компьютеров с общей памятью? Потому что есть единое адресное пространство и пользователю не нужно заниматься организацией пересылок сообщений между процессами для обмена данными. Если создать механизм, который всю совокупную физическую память компьютера позволял бы программам пользователей рассматривать как единую адресуемую память, все стало бы намного проще.
Применение степени отображения для решения системы уравнений
Вернемся теперь к задаче, сформулированной в разделе 2.1. В «-мерном евклидовом пространстве R" задано отображение R — R f(x) = у- Ax + b. Это отображение каждой точке JC ставит в соответствие некоторый вектор %{х), а именно (у-х), т.е. вектор, который выходит из точки х и направлен в точку f[x). Определим теперь гиперповерхность, которую в разделе 2.2 мы называли Q. В нашем случае нам удобно (об этом будет сказано в дальнейшем) в качестве гиперповерхности Q взять границу выпуклого множества К, гомеоморфного п-мерному шару. Имеет место следующее обстоятельство.
Если мы зададим в R" выпуклое множество К, гомеоморфное и-мерному шару с границей Q, то для нашего векторного поля и поверхности Q имеют место два альтернативных варианта. Либо degfi = 0.
Это означает, что неподвижная точка преобразования f\x), а именно точка, соответствующая решению системы находится вне множества . Либо dege = 1.
В этом случае, неподвижная точка преобразования f\x), а именно точка, соответствующая решению системы находится внутри множества К. В этом случае мы поймали решение.
С помощью сказанного выше задачу нахождения приближенного решения системы линейных алгебраических уравнений можно сформулировать следующим образом.
В «-мерном пространстве задается либо «-мерный шар, либо другое и-мерное выпуклое тело, гомеоморфное шару. Это может быть куб, параллелепипед,
симплекс и т.д. С помощью степени отображения можно ответить на вопрос, находится ли точка, координаты которой являются решением системы уравнений, внутри рассматриваемого тела.
Идея использования многопроцессорной структуры для нахождения приближенного решения системы уравнений заключается в том, чтобы разбить п-мерное пространство на подозреваемые области и каждую область обрабатывать на своем процессоре.
Моделирование этого процесса с помощью персональных компьютеров выявило неожиданную трудность. Оказалось, что вычисление степени отображения с помощью интеграла приводит к очень большим ошибкам. Вычисление самого интеграла производилось по приближенным формулам. Получалось, что при системе, состоящей уже из 10 уравнений, мы никакими доступными нам средствами из-за потери точности не могли отличить значение «ноль» от значения «единица».
По этому поводу нам пришлось воспользоваться еще одним обстоятельством. Выберем в качестве тела К выпуклый многогранник в «-мерном пространстве с границей бив качестве векторного поля ь\х) поле, построенное на основе преобразования f(x) = y = Ax + b и рассмотрим вектора Ь\ХІ) В точках ;, являющихся вершинами многогранника. Тогда случай degc = 0 будет соответствовать ситуации, когда все вектора Ь\ХІ) лежат в одном полупространстве, а случай dege = l будет соответствовать ситуации, когда не найдется ни одного полупространства, где бы лежали все вектора . Иначе говоря, если вектора все лежат в каком-либо полупространстве, то это значит, что неподвижная точка преобразования f(x), т.е. точка, координаты которой являются решением уравнения Ах = Ь, не лежит внутри многогранника, в противном случае, эта точка лежит внутри многогранника, т.е. мы найдем решение.
Это последнее обстоятельство послужило отправной точкой для разработки алгоритмов, определяющих, лежит ли точка, соответствующая решению, внутри некоторого «-мерного многогранника.
Решение системы на многопроцессорном компьютере
При разработке газоконденсатных месторождений важна оценка дебитов, которые могут наблюдаться при аварийном фонтанировании скважины.
В случае возникновения аварийных фонтанов фильтрационные характеристики пласта, состояние скважины, состав газожидкостной смеси либо вообще неизвестны, либо известны с очень невысокой степенью точности. Поэтому применение сложных гидромеханических методов для описания аварийного фонтанирования представляется нецелесообразным.
В работе для рассмотрения задачи об определении максимального свободного дебита скважины предлагается следующая гидромеханическая модель: Будем считать поток гомогенным; массовое газосодержание по стволу скважины постоянным и равным некоторому среднему значению; течение изотермическим; жидкую фазу несжимаемой; газ совершенным, т.е. подчиняющимся уравнению Клапейрона.
При гомогенном течении по вертикальной трубе градиент давления может быть представлен в следующем виде dp AvG/2D + Gg/v dz 1-vG/p (1) g где S - ускорение силы тяжести, V - скорость смеси, G - массовая скорость смеси, Я - коэффициент гидравлического сопротивления, Р -давление, vg - приведенная скорость газа, D - диаметр трубы, Z - координата по вертикали. Математическая задача об определении свободного дебита фонтанирующей скважины формулируется следующим образом. При заданных входных параметрах требуется найти так называемые критические значения: РКр - критическое значение давления на выходе из скважины; Мкр- критическое значение массового расхода смеси; Икр- критическое значение объемного расхода, приведенного к атмосферному давлению. При решении задачи мы имеем дело со следующими величинами: М - массовый расход смеси; М 1V1 g - массовый расход газа; Рс - плотность смеси; Pg - плотность газа; Pi - плотность жидкости; F - площадь сечения трубы; X - массовое газосодержание. Массовое газосодержание X определяется как Для решения нашей задачи мы составляем две дополнительные подпрограммы На вход подпрограммы Н\ поступают конкретно заданные значения параметров ркр и рс, а на выходе получаем значение функции для этих параметров. На вход подпрограммы П2 также поступают конкретные значения параметров Ркр и Рс, а на выходе получаем значение функции г г \РС»Ркр ) от ЭТИХ КОНКреТНЫХ Ркр и Рс Обе эти подпрограммы устроены так, что они зависят от многих параметров, входящих в определение функций и Эти параметры следующие: L - глубина скважины; D - диаметр труб; Рт - пластовое давление; - параметры пласта; Рс - плотность конденсата; Pg - плотность газа при атмосферном давлении; Я - коэффициент гидравлического сопротивления; о -температура; х= w- - массовое газосодержание.
При использовании программ Н\ и 2 все параметры, кроме X 5 вводятся в программы заранее в виде констант.
Параметр X - массовое газосодержание нас интересует более подробно. О нем мы расскажем ниже.
В нашей задаче нас интересует значение М кр - максимального массового расхода смеси при критическом истечении, когда происходит запирание потока, а также соответствующий объемный расход \dKp. Эти величины зависят от массового содержания X и от Ркр - критического давления. Они связаны формулами Р F г кр " \[Щ где F - площадь сечения трубы, R - газовая постоянная. В нашем случае I 9 J о =- Рс Наша программа будет вычислять значения кр и (JKp для разных значений параметра X, например, от = 0 до Х = 1 с шагом Лх . Для этого при каждом значении X мы должны определить РКр Оно входит в систему уравнений РІІРОРКРУ вместе с давлением Рс в этот же момент на забое скважины. Решая систему уравнений, находим Ркр , а заодно и Рс. Далее используем Ркр для определения и Укр. По расширенной программе проводились расчеты по задаче, сформулированной выше. Расчеты проводились при следующих значениях входных параметров: глубина скважины - -1 = vooM . диаметр труб - L) — 11 JММ . р=50М7а. пластовое давление - х т параметры пласта
Случай произвольных нелинейных уравнений
При разработке газоконденсатных месторождений важна оценка дебитов, которые могут наблюдаться при аварийном фонтанировании скважины.
В случае возникновения аварийных фонтанов фильтрационные характеристики пласта, состояние скважины, состав газожидкостной смеси либо вообще неизвестны, либо известны с очень невысокой степенью точности. Поэтому применение сложных гидромеханических методов для описания аварийного фонтанирования представляется нецелесообразным.
В работе для рассмотрения задачи об определении максимального свободного дебита скважины предлагается следующая гидромеханическая модель: Будем считать поток гомогенным; массовое газосодержание по стволу скважины постоянным и равным некоторому среднему значению; течение изотермическим; жидкую фазу несжимаемой; газ совершенным, т.е. подчиняющимся уравнению Клапейрона.
Существующие методы решения нелинейных систем основаны на линеаризации системы и фактическом сведении нелинейных систем к линейным. Но линеаризацию системы можно проводить локально. Это имеет успех в тех случаях, когда мы примерно знаем области расположения решения. Если же это не так, то линеаризация может привести к ошибке.
Решение задачи с помощью компьютерной системы Для решения нашей задачи мы составляем две дополнительные подпрограммы На вход подпрограммы Н\ поступают конкретно заданные значения параметров ркр и рс, а на выходе получаем значение функции для этих параметров. На вход подпрограммы П2 также поступают конкретные значения параметров Ркр и Рс, а на выходе получаем значение функции г г \РС»Ркр ) от ЭТИХ КОНКреТНЫХ Ркр и Рс Обе эти подпрограммы устроены так, что они зависят от многих параметров, входящих в определение функций и Эти параметры следующие: L - глубина скважины; D - диаметр труб; Рт - пластовое давление; - параметры пласта; Рс - плотность конденсата; Pg - плотность газа при атмосферном давлении; Я - коэффициент гидравлического сопротивления; о -температура; х= w- - массовое газосодержание. При использовании программ Н\ и 2 все параметры, кроме X 5 вводятся в программы заранее в виде констант.
Параметр X - массовое газосодержание нас интересует более подробно. О нем мы расскажем ниже.
В нашей задаче нас интересует значение М кр - максимального массового расхода смеси при критическом истечении, когда происходит запирание потока, а также соответствующий объемный расход \dKp. Эти величины зависят от массового содержания X и от Ркр - критического давления. Они связаны формулами Р F г кр " \[Щ где F - площадь сечения трубы, R - газовая постоянная. В нашем случае I 9 J о =- Рс Наша программа будет вычислять значения кр и (JKp для разных значений параметра X, например, от = 0 до Х = 1 с шагом Лх . Для этого при каждом значении X мы должны определить РКр Оно входит в систему уравнений РІІРОРКРУ вместе с давлением Рс в этот же момент на забое скважины. Решая систему уравнений, находим Ркр , а заодно и Рс.
