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

• Автор: Ващенко, Геннадий Васильевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Красноярск
• Количество страниц: 132 с. : ил.

Содержание
Введение
Глава 1. Контроль точности и устойчивости. Последовательный и параллельный алгоритмы
1.1 Основные определения
1.2 Контроль точности вычислений
1.3 Контроль устойчивости
1.4 Реализация методов с контролем точности и устойчивости
1.5 Параллельные вычислительные системы и параллельные вычисления
1.6 Оценки эффективности параллельных алгоритмов
1.7. Параллельный вариант явного метода с контролем точности
вычислений и устойчивости численной схемы
1.8 Заключение к главе
Глава 2. Параллельная реализация явных методов с контролем точности и устойчивости
2.1. Явные т-стадийные методы типа Рунге-Кутты
2.2. Одностадийный метод
2.3. Двухстадийный метод
2.4. Трехстадийный метод
2.5. Заключение к главе
Глава 3. Параллельная реализация Т-устойчивого метода
3.1. Класс (т,к)-методов
3.2. Алгоритм постоянного шага на основе (2,1)-метода
3.3. Параллельный алгоритм переменного шага
3.4. Анализ эффективности
3.5. Заключение к главе
Глава 4. Комплекс параллельных программ и результаты численного моделирования
4.1. Комплекс параллельных программ
4.2. Численное моделирование генной сети
4.3. Численное моделирование проникновения антител в ткань живого организма
Заключение
Литература

Введение
Численное решение обыкновенных дифференциальных уравнений вида
/ = О)
где у и /- вещественные Л'-мерные вектор-функции, I - скалярная величина является одной из наиболее часто встречающихся задач научно-технических исследований в химической кинетики, биологии, радиоэлектроники и в других практических приложениях. Во многих случаях задача усложняется жесткостью и большой размерностью системы (1). В результате возможностей обычных последовательных вычислительных машин уже оказывается недостаточным. Поэтому актуальной проблемой является создание алгоритмов интегрирования на современных параллельных вычислительных машинах с распределенной памятью. Для этого необходимо разработать параллельный алгоритм разбиения данных на блоки, каждый из которых обрабатывается отдельным процессором, а так же организовать межпроцессорные взаимодействия с учетом архитектуры и программного обеспечения многопроцессорной вычислительной машины.
При численном решении систем дифференциальных уравнений одношаговыми методами на основе схем типа Рунге-Кутты и /.-устойчивых методов возникает необходимость построения численных формул с автоматическим выбором величины шага интегрирования, обеспечивающего требуемую точность вычислений. Критерии выбора шага основываются на оценках локальной или глобальной погрешности, а для явных методов дополнительно требуется контролировать устойчивость численной схемы. Поэтому разработка параллельных явных методов переменного шага с выбором величины шага по точности и устойчивости является актуальной задачей. При построении параллельных алгоритмов и программ интегрирования требуется разрешить ряд вопросов, которым посвящена данная работа. Сначала нужно выбрать методы, которые соответствовали бы классу решаемых задач. Здесь в основу алгоритмов интегрирования

положены одношаговые безытерационные численные схемы вида
Упл=У«+ЪФА*п>Уп>Ь)> (2)
которые обладают определенными преимуществами перед многошаговыми. В частности, многошаговые формулы приводят в некотором смысле к осреднению решения (срезание экстремумов), что при моделировании некоторых динамических объектов делает их неприемлемыми. Кроме того, если правая часть дифференциальной задачи разрывная, то применение многошаговых методов является малоэффективным. Достаточно полный обзор работ по многошаговым методам содержится в [1-5], и поэтому ниже на этом вопросе останавливаться не будем.
Требование безытерационности (2) позволяет оценить затраты на шаг интегрирования до проведения расчетов и упрощает программную реализацию как последовательных, так и параллельных алгоритмов интегрирования. Важность указанных задач породила за последнее время огромное количество методов интегрирования жестких и не жестких систем. Однако для того, чтобы от идеи метода перейти к его алгоритмической реализации, необходимо решить проблему изменения величины шага интегрирования и оценки точности получаемых численных результатов, что и делает метод экономичным и надежным. Современные способы управления шагом основаны, как правило, на контроле точности численной схемы. Такой подход представляется наиболее естественным, поскольку основным критерием при проведении практических расчетов является точность нахождения решения. Многие алгоритмы интегрирования для выбора величины шага используют оценку локальной ошибки (погрешности аппроксимации). Это оправдано тем, что если на каждом шаге контролировать некоторый минимальный уровень локальной ошибки, то глобальная ошибка будет ограничена. В настоящее время можно выделить три практических способа оценки данной ошибки [1,с.59-65]. Классическим способом оценки локальной ошибки является экстраполяция Ричардсона [10—
11]. Его иногда еще называют правилом Рунге, и он заключается в

системам кластерной архитектуры. Очевидно, это связано с резким сниже нием отношения "цена / производительность" при переходе к кластерам рабочих станций и с относительной недоступностью специализированных суперкомпьютеров типа Cray для широкого круга пользователей. Заметим, что и в этом случае вопрос о выборе подходящих параллельных алгоритмов для решения вычислительных задач остается актуальным. Здесь наряду с достаточной степенью параллелизма, алгоритм должен иметь большие блоки вычислений, которые могут выполняться параллельно. Иными словами, алгоритм должен быть "крупнозернистым" (coarse grained structure), чтобы процессоры были загружены вычислениями постоянно. Количество межпроцессорных обменов должно быть минимальным с использованием относительно больших пакетов данных.
Оценка коммуникационных затрат может быть получена с помощью формулы [13,28,30] tcomm = ц + V- l/у, где /л - латентность (время инициализации обмена) сети передачи данных (сек), / - время передачи одного байта, у- пропускная способность сети передачи данных (байт/сек), V - объем в байтах, количество слов, подлежащих пересылке для рассматриваемого обмена.
1.7. Параллельный вариант явного метода с контролем точности вычислений и устойчивости численной схемы
Ниже речь пойдет о параллельной реализации явного метода (1.5) с контролем точности вычислений и устойчивости численной схемы. Начнем со случая, когда вычисления выполняются без контроля точности и устойчивости, затем получим параллельные алгоритмы с реализацией приведенных оценок погрешности на шаге и условий устойчивости численной схемы. Параллельные вычисления основываются на парадигмах распределенной и общей памяти. Ниже, при построении параллельных алгоритмов, будем рассматривать первую из них, которая технически реализуется в многопроцессорных вычислительных системах кластерной