В данной работе рассмотрено распараллеливание вычислительного процесса для решения обратных задач химической кинетики на трех уровнях: распараллеливание по экспериментальной базе; использование внутреннего параллелизма задачи; декомпозиция алгоритма решения обратной задачи. Ключевые слова: обратные задачи, кинетические константы, физическая химия, многопроцессорные системы, MPI.
Анализ методов решения обратных задач химической кинетики с применением параллельных вычислений кинетических моделей сложных реакций металлокомплексного катализа представляет собой многоуровневый, многократно вложенный, последовательно-параллельный процесс.
Существуют разные способы организации параллельных вычислений. Основная последовательность действий для определения эффективных способов организации параллельных вычислений состоит в следующем: 1) анализ исследуемого объекта на внутренний параллелизм; 2) анализ экспериментальной информации, проектирование баз данных и реализация параллельного доступа к ним;
3) анализ используемых вычислительных схем и осуществление их разделения (декомпозиции) на части (подзадачи), которые могут быть реализованы в значительной степени независимо друг от друга;
4) выделение для выделенного набора подзадач информационных взаимодействий, которые должны осуществляться в ходе решения исходной поставленной задачи;
5) распределение выделенного набора подзадач между процессорами используемой вычислительной системы.
Очевидно, объем вычислений для каждого используемого процессора должен быть примерно одинаковым, что позволит обеспечить равномерную вычислительную загрузку процессоров, а распределение подзадач между процессорами должно быть выполнено таким образом, чтобы количество информационных взаимодействий между подзадачами было минимальным. Также обязательными требованиями являются целостность, универсальность и гибкость разрабатываемых баз данных.
Наиболее простым способом организации параллельных вычислений является распараллеливание по экспериментальной базе, т.е. распределение однотипных вычислений для разных наборов начальных данных. Лучше всего подходят для распараллеливания задачи, обладающие внутренним параллелизмом, например, включающие протекающие параллельно процессы. Наиболее эффективным, но и трудоемким способом распараллеливания является распараллеливание численных методов и алгоритмов решения задач. Рассматриваемые задачи химической кинетики относятся к классу задач, решение обратной задачи в которых осуществляется на основе решения серии прямых задач с минимизацией выбранного критерия отклонения расчетных данных от экспериментальных. Это создает основу для эффективного распараллеливания вычислительного процесса с использованием принципа геометрического параллелизма. Таким образом, распараллеливание вычислительного процесса может быть осуществлено на трех уровнях: 1) распараллеливание по экспериментальной базе; 2) использование внутреннего параллелизма задачи; 3) декомпозиция алгоритма решения обратной задачи.
Имеется трехуровневая модель распараллеливания, сочетающая все эти подходы (рис.1)
[
параллелизма задачи Распараллеливание алгоритма решения задачи Решение одной и той же
задачи для разных наборов начальных данных Детализация задачи
при каждом наборе начальных данных Выявление подзадач в методе и разделение их между процессорами МВС Рис.1. Трехуровневая модель распараллеливания вычислительного процесса при решении обратной задачи 2. Трехуровневая модель распараллеливания вычислительного процесса при решении обратной задачи 2.1 Распараллеливание по экспериментальной базе
Решение многопараметрических задач, таких как задача идентификации кинетической модели сложных химических реакций, состоит в циклическом чередовании натурного и вычислительного экспериментов. Натурный эксперимент требует больших материальных и энергетических затрат, особенно для сложных реакций, и его информативность напрямую зависит от качества и скорости проведения вычислительного эксперимента. Объем данных вычислительного эксперимента зависит от следующих факторов: 1) для каждой реакции необходимо обработать несколько предполагаемых схем химических превращений, чтобы выбрать лучшую схему; 2) для каждой реакции проводится ряд натурных экспериментов при разных условиях; при обработке опытных данных выбираются несколько лучших, по которым расчетные значения имеют наименьшее отклонение от экспериментальных данных; 3) недостаточная информативность эксперимента, что является одной из причин неоднозначного определения кинетических параметров.
Поскольку размерность систем обыкновенных дифференциальных уравнений (ОДУ) достигает 30 уравнений, при решении обратной задачи необходимо решать более 3 миллионов систем нелинейных ОДУ (рис. 2), что определяет целесообразность использования технологии параллельных вычислений.
Рис. 2. Число решаемых прямых задач при построении кинетической модели реакции
гидроалюминирования олефинов
Таким образом, на первом уровне все множество процессоров многопроцессорной
вычислительной системы разбивается на подмножества для решения обратной задачи при
конкретном наборе начальных данных. При этом организация взаимодействия с базой данных
осуществляется по принципу master-slave, при котором выбирается один главный процессор,
имеющий доступ к базе данных и выполняющий распределение данных между всеми
подчиненными процессорами [
На втором уровне распараллеливания каждое подмножество процессоров относят к различным коммуникаторам в соответствии с внутренним параллелизмом задачи, который для рассматриваемой задачи заключается в возможности независимого решения задачи для выделенных, частных, детализированных и общих реакций. Распараллеливание на основе использования внутреннего параллелизма задачи при построении кинетической модели реакции гидроалюминирования олефинов с алюминий-органическими соединениями (АОС) иллюстрирует рис. 3.
Рис. 3. Второй уровень распараллеливания решения обратной задачи химической кинетики 2.3 Распараллеливание алгоритма решения задачи
Третий уровень распараллеливания включает декомпозицию алгоритма решения обратной задачи по числу процессоров, входящих в созданные процессорные коммуникаторы. 2.3.1 Генетический алгоритм решения обратной задачи
Для параллельного решения обратной задачи химической кинетики наиболее эффективным
является генетический алгоритм, основу которого составляет заимствованная из биологии идея
селекции, то есть преимущественного размножения наиболее приспособленных особей [
На первом шаге алгоритма случайным образом создается начальная популяция, состоящая из N особей (N точек в пространстве кинетических параметров, каждая точка имеет m координат – значений параметров). На этапе мутации особи популяции изменяются в соответствии с заранее определенной операцией мутации, в качестве которой был взят покоординатный/параболический спуск из точек пространства.
На этапе селекции из всей популяции выбирается определенная ее доля, которая останется «в живых» на этом этапе эволюции. Вероятность выживания особи зависит от значения функции приспособленности для этой особи; в качестве функции приспособленности выступает функционал невязки. Доля выживших s является параметром генетического алгоритма, и по итогам отбора из N особей популяции в итоговую популяцию войдут sN особей. В рассматриваемом случае s=1/2.
При формировании нового поколения используется скрещивание – чтобы произвести потомка, нужны два родителя. Для формирования новой точки в пространстве параметров в качестве родителей выбирается одна точка из «выживших» и одна из «погибающих», и скрещивание производится путем выбора m/2 координат от первой точки и оставшихся – от второй; при этом потомок наследует черты обоих родителей. Особи для размножения выбираются из всей популяции, а не из выживших на первом шаге элементов с целью исключения возможности деградации популяции.
Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма, в качестве которого выступает любое из условий: 1) нахождение глобального либо субоптимального решения; 2) исчерпание числа поколений, отпущенных на эволюцию; 3) исчерпание времени, отпущенного на эволюцию.
Распараллеливание вычислительного процесса производится на стадии начального заполнения, когда заданные псевдослучайно точки в пространстве параметров равномерно распределяются по процессам МВС. Мутация осуществляется каждым процессом независимо; обмен данными производится на этапе селекции. При этом время автономной работы процессов значительно превышает время межпроцессорных взаимодействий, что обусловливает эффективность данного алгоритма.
Оценка эффективности распараллеливания при тестировании программы на вычислительном кластере Башкирского государственного университета и суперкомпьютера МВС-100К показала, что параллельная программа работает достаточно эффективно при увеличении числа процессов. При решении обратной задачи для реакции гидроалюминирования олефинов по всем экспериментальным данным общее время расчета составило: на персональном компьютере – 360 часов, на суперкомпьютере МВС-100К (с использованием 120 процессоров) – 15 минут. 2.3.2 Геометрический параллелизм по кинетическим параметрам
Принцип геометрического параллелизма предполагает декомпозицию расчетной области пространства кинетических параметров на подобласти соответственно числу процессоров МВС. Для двух констант строится двумерная плоскость (для n констант – соответственно, nмерная). Далее эта область делится на подобласти по числу процессоров, и каждый процессор решает обратную задачу только в своей подобласти.
Определив наборы констант, соответствующие минимальному значению функционала в
заданной подобласти, каждый процессор передает найденные значения серверу. Сервер
исключает подобласти, в которых функционал имеет наибольшие значения, и из полученной области
снова формирует подобласти по количеству процессоров. Данный циклический процесс
продолжается до тех пор, пока не будут определены константы, описывающие эксперимент с
заданной точностью. При этом каждый процессор минимизирует невязку в своей области
методом покоординатного или параболического спуска (рис. 4). Здесь L – количество подобластей
[
Выявлен и рассмотрен внутренний параллелизм задачи на примере реакции гидроалюминирования олефинов, заключающийся в том, что общая схема реакции включает протекающие параллельно стадии, некоторые из них совпадают для реакций с алюминийорганическими соединениями и олефинами. При осуществлении вычислительного процесса решение обратной задачи осуществляется независимо для параллельно протекающих стадий, что позволяет существенно сократить время расчета.
Для организации вычислительного процесса рассмотрена трехуровневая модель распараллеливания, объединяющая распараллеливание по экспериментальной базе, в соответствии с внутренним параллелизмом задачи и на основе декомпозиции метода решения обратной задачи.
Программный комплекс, реализующий расчеты по этой модели, тестирован на вычислительном кластере Башкирского государственного университета и на суперкомпьютере МВС100К Межведомственного суперкомпьютерного центра РАН. При решении обратной задачи для реакции гидроалюминирования олефинов по всем экспериментальным данным на основе генетического алгоритма общее время расчета на суперкомпьютере МВС-100К (с использованием 120 процессоров) составило 15 минут против 360 часов на персональном компьютере с использованием стандартных алгоритмов. Литература 4. Линд Ю.Б., Губайдуллин И.М., Мулюков Р.А. Методология параллельных вычислений для решения задач химической кинетики и буровой технологии // Системы управления и информационные технологии. 2009. №2/36. С. 44–49. Analysis of methods for solving inverse problems of chemical kinetics with the use of parallel computing
I.V. Akhmetov1,2, I.M. Gubaydullin1,2 In this paper we consider parallelization of the computational process for solving inverse problems of chemical kinetics on three levels: parallelization on experimental basis; the use of internal concurrency problems; de-composition algorithm solving the inverse problem.