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

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

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

1. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

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

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

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

1.1 Классификация вычислительных систем

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

Системы с разделяемой памятью (мультипроцессоры), у которых имеется одна виртуальная память, а все процессоры имеют одинаковый доступ к данным и командам, хранящимся в этой памяти (uniform memory access или UMA). По этому принципу строятся векторные параллельные процессоры (parallel vector processor или PVP) и симметричные мультипроцессоры (symmetric multiprocessor или SMP).

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

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

Исторически наиболее ранней является классификация М. Флинна (1966). Классификация основана на понятии потока, под которым понимается последовательность команд или данных, обрабатываемых процессором. На основе числа потоков команд и потоков данных выделяют четыре класса архитектур:

· SISD (Single Instruction stream/Single Data stream) - один поток команд и один поток данных;

· SIMD (Single Instruction stream/Multiple Data stream) - один поток команд и множество потоков данных;

· MISD (Multiple Instruction stream/Single Data stream) - множество потоков команд и один поток данных;

· MIMD (Multiple Instruction stream/Multiple Data stream) - множество потоков команд и множество потоков данных.

В настоящее время подавляющее число «серьезных» компьютеров реализуется в классе MIMD-архитектур. При этом рассматривают следующие основные подклассы.

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

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

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

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

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

1.2 Стандарты для распараллеливания программ

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

OpenMP (Open specifications for Multi-Processing) стандарт для написания параллельных программ в условиях общей памяти. Программа представляется как набор потоков объединённых общей памятью, где проблема синхронизации решается введением критических секций и приватных переменных;

MPI (Message Passing Interface) стандарт, предназначенный для написания программ в условиях разделённой памяти, данный стандарт описывает параллельную программу как набор нитей, взаимодействующих посредством передачи сообщений.

OpenMP. Стандарт OpenMP был разработан в 1997 году, как API, ориентированный на написание портируемых многопоточных приложений. Сначала он был основан на языке Fortran, но позднее включил в себя и C/C++.

Разработкой стандарта занимается организация OpenMP ARB (ARchitecture Board), в которую вошли представители крупнейших компаний - разработчиков SMP-архитектур и программного обеспечения. Спецификации для языков Fortran и C/C++ появились соответственно в октябре 1997 года и октябре 1998 года. OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах (SSMP, ccNUMA) в модели общей памяти (shared memory model).

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

За счет идеи “частичного распараллеливания” OpenMP идеально подходит для разработчиков, желающих быстро распараллелить свои вычислительные программы с большими параллельными циклами. Разработчик не создает новую параллельную программу, а просто добавляет в текст последовательной программы OpenMP директивы. Предполагается, что OpenMP-программа на однопроцессорной платформе может быть использована в качестве последовательной программы, т.е. нет необходимости одновременно поддерживать последовательную и параллельную версии. Директивы OpenMP просто игнорируются последовательным компилятором, а для вызова процедур OpenMP могут быть подставлены заглушки (stubs), текст которых приведен в спецификациях.

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

Функции OpenMP служат в основном для изменения и получения параметров окружения. Кроме того, OpenMP включает API-функции для поддержки некоторых типов синхронизации. Чтобы задействовать эти функции OpenMP библиотеки периода выполнения (исполняющей среды), в программу нужно включить заголовочный файл omp.h. Если же используется в приложении только OpenMP-директивы pragma, включать этот файл не требуется.

MPI. Стандарт MPI используется в системах с распределенной памятью. Он возник в 1994 году как решение проблемы разнообразия архитектур параллельных вычислительных систем и обеспечение возможности создания мобильных (переносимых между различными компьютерными платформами) программ. Наличие такого стандарта позволило разработать стандартные библиотеки программ (MPI-библиотеки), в которых оказалось возможным скрыть большинство архитектурных особенностей параллельных вычислительных систем и, как результат, существенно упростить проблему создания параллельных программ. Более того, стандартизация базового системного уровня позволила в значительной степени обеспечить мобильность параллельных программ, поскольку в настоящее время реализации MPI-стандарта имеются для большинства компьютерных платформ.

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

Формально MPI-подход основан на включении в программные модули вызовов функций специальной библиотеки (заголовочные и библиотечные файлы для языков С/С++ и Fortran) и загрузчика параллельно исполняемого кода в вычислительные узлы (ВУ). Подобные библиотеки имеются практически для всех платформ, поэтому написанные с использованием технологии MPI взаимодействия ветвей параллельного приложения программы независимы от машинной архитектуры (могут исполняться на однопроцессорных и многопроцессорных c общей или разделяемой памятью ЭВМ), от расположения ветвей (выполнение на одном или разных процессорах) и от API (Application Program Interface) конкретной операционной системы (ОС).

MPI является (довольно) низкоуровневым инструментом программиста; c помощью MPI созданы рассчитанные на численные методы специализированные библиотеки (например, включающая решение систем линейных уравнений, обращение матриц, ортогональные преобразования, поиск собственных значений и т.п. библиотеки ScaLAPACK и AZTEC для плотнозаполненных и разреженных матриц соответственно). MPI не обеспечивает механизмов задания начального размещения процессов по вычислительным узлам (процессорам); это должен явно задать программист или воспользоваться неким сторонним механизмом.

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

Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP Single Programm Multiple Processes). Данный программный код, представленный в виде исполняемой программы, должен быть доступен в момент запуска параллельной программы на всех используемых процессорах. Исходный программный код для исполняемой программы разрабатывается на алгоритмических языках C или Fortran с использованием той или иной реализации библиотеки MPI.

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

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

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

Hypre - библиотека высокопроизводительных предобуславливателей и решателей для больших разреженных линейных систем. Акцент делается на современные масштабируемые предобуславливатели. Разрабатывается в Ливерморской национальной лаборатории (Lawrence Livermore National Laboratory)

Trilinos - проект, направленный на развитие параллельных алгоритмов и библиотек в рамках объектно ориентированного подхода. Данный пакет предназначен для применения к задачам науки и прикладного моделирования, требующие решения сложных и крупномасштабных задач математической физики. Разрабатывается в Сандийской национальной лаборатории (Sandia National Laboratories).

PETSc - библиотека, состоящая из процедур и структур данных для параллельного решения научных задач с моделями, описываемыми в виде дифференциальных уравнений с частными производными. Библиотека основана на использовании MPI, BLAS и LAPACK [2].

1.3 Описание схемы параллельного выполнения алгоритма

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

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

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

, (1.1)

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

1., т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени,

2., т.е. к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены [1].

Определение времени выполнения параллельного алгоритма

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

(1.2)

Для выбранной схемы вычислений желательно использование расписания, обеспечивающего минимальное время исполнения алгоритма

(1.3)



Уменьшение времени выполнения может быть обеспечено и путем подбора наилучшей вычислительной схемы

(1.4)

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

(1.5)

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

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

(1.6)

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



(1.7)

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

(1.8)

(эффективный параллельный алгоритм может не совпадать с наилучшим последовательным методом при исполнении на одном процессоре) [8].

Показатели эффективности параллельного алгоритма

Ускорение, получаемое при использовании параллельного алгоритма для процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется

(1.9)

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

Эффективность использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:



(1.10)

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

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

Кроме этого, существует понятие «парадокса параллелизма» - достижение ускорения и эффективности параллельного алгоритма, превышающих значения и , соответственно. Говоря другими словами, «парадокс параллелизма» - это более чем линейный рост производительности параллельной ВС с увеличением числа её вычислителей [1].

2. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

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

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

2.1 Генетический алгоритм и его особенности

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

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

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

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

Функционирование генетического алгоритма можно описать следующими шагами:

Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k-особей.

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

1. Выбрать особь из популяции;

2. С определенной вероятностью (вероятностью кроссовера) выбрать вторую особь из популяции и произвести оператор кроссовера;

3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации;

4. С определенной вероятностью (вероятностью инверсии) выполнить оператор инверсии;

5. Поместить полученную хромосому в новую популяцию;

6. Выполнить операции, начиная с пункта 3, k-раз;

7. Увеличить номер текущей эпохи t=t+1;

8. Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2;

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

Тем не менее, генетические алгоритмы довольно широко и успешно используются для решения задач (7).

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

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

Существует три температурных режима метаногенеза: психрофильный, мезофильный и термофильный. На практике широкое распространение получили мезофильный и термофильный режимы. Оптимальная температура для мезофильного (термофильного) режима составляет 37°С (56°С), а период полной ферментации - 25 суток (12 суток).

Математическая модель метаногенеза имеет вид:

(1)

с дополнительными соотношениями



(2)

и начальными условиями

(3)

где X - концентрация бактерий, кг/м³; L - концентрация питательных веществ, усваиваемых бактериями, кг/м³; V - выход биогаза, м³; и - относительные скорости соответственно прироста и отмирания бактерий, сут.^-1; и - максимально возможные относительные скорости соответственно прироста и отмирания бактерий, сут.^-1; в - безразмерный коэффициент усвоения субстрата; p - относительная скорость поступления субстрата, сут.^-1; г - коэффициент, характеризующий скорость преобразования питательных веществ субстрата в биогаз, м³/(сут.кг/м³); и - эмпирические коэффициенты, м³/кг.

Особенностью системы (1) является отсутствие переменной V в правой части. Поэтому третье уравнение можно рассматривать независимо от остальных. Удобно ввести величину скорости выхода биогаза:

. (4)

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

3. РЕЗУЛЬТАТЫ ЭКСПЕРЕМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ И ИСПЫТАНИЙ

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

3.1 Параллельные вычисления в решении задач составления расписания

Основным средством организации параллельных вычислений в многопроцессорных системах с общей памятью являются потоки (threads). Основными методами работы с потоками являются: создание, удаление, приостановка, запуск на выполнение. Если оформить процедуру оценки особи в виде потокового класса, то приведённый выше фрагмент будет выглядеть следующим образом.

ОценитьПопуляцию(Популяция, ЧислоОсобей)

{

for( i=0 ; i<ЧислоОсобей ; i++ )

{

ОценитьОсобь->СоздатьПоток(Популяция[i], Последовательность);

ОценитьОсобь->Выполнить();

ОценитьОсобь->ЖдатьЗавершения();

ОценитьОсобь->УдалитьПоток();

}



Организация такого процесса будет состоять в том, чтобы создать одновременно несколько экземпляров потокового класса «ОценитьОсобь», запустить их на выполнение, передав индивидуальные входные параметры, и далее ожидать окончания выполнения для каждого экземпляра класса. Число особей в реализации параллельного генетического алгоритма по такой схеме обычно гораздо больше числа вычислительных процессоров в системе (4-6 в текущих маркетинговых процессорах Intel, до 64 в специализированных системах). Поскольку мы предполагаем, что один вычислительный поток будет загружать один процессор (одно ядро) в системе, то необходимо одновременно выполнять такое число потоков, которое равно числу процессоров. Таким образом, в коде выше появится дополнительный вложенный цикл. Псевдокод параллельной реализации в терминах потоков приведён ниже.

ОценитьПопуляцию(Популяция, ЧислоОсобей)

{

for( int i=0 ; i<ЧислоОсобей/ЧислоПотоков ; i++ )

{

j=i*ЧислоПотоков;

выполнять_параллельно_для j, j+1, … , j+ЧислоПотоков-1

{

ОценитьОсобь->СоздатьПоток(Популяция[j], Последовательность);

ОценитьОсобь->Выполнить();

}

ЖдатьОкончанияПотоков j, j+1, … , j+ЧислоПотоков-1;

УдалитьПотоки();

}

}



Здесь переменная «ЧислоПотоков» показывает, сколько вычислительных потоков будет выполняться одновременно. Обычно для многоядерных систем рекомендуется выбирать число потоков равное числу вычислительных ядер системы.

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

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

Испытания распределенного приложения на основе описанного алгоритма были проведены на двухъядерном процессоре с частотой 1,9 ГГц и 4 Гб оперативной памяти. Распараллеливание велось по количеству особей популяции. Время выполнения последовательного алгоритма - . Время выполнения параллельного алгоритма - . Ускорение - определялось по формуле:



.

Выигрыш -

[1]

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

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

В зависимости от количества ядер компьютера масштабируемость алгоритма изменяется с увеличением ядер. Ускорение алгоритма практически не изменяется, теоретически существует тенденция к увеличению ускорения с увеличением количества ядер.

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

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



ЗАКЛЮЧЕНИЕ

В работе рассматривается один из подходов к построению параллельного алгоритма метаногенеза. Параллельная программа использует библиотеку MPI.

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

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



СПИСОК ЛИТЕРАТУРЫ

1. Гергель В.П. Лекции по параллельным вычислениям: учеб. пособие / В.П. Гергель,В.А.Фурсов. - Самара: Изд-во Самар. гос. аэрокосм. ун-та, 2009. - 164 с.

2. Гришагин В.А., Свистунов. А.Н. Параллельное программирование на основе MPI. Нижний Новгород, 2005.

3. Корнеев В.Д. Параллельное программированием в MPI. Новосибирск: СО РАН, 2002. 215 с.

4. Каширина И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида. // Вестник ВГУ, Серия физика, математика. 2003. №1. С. 128-131.

5.Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. -- 2-е изд.. -- М: Физматлит, 2006. --320 с.

6. Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. -- М: Физматлит, 2006. -- 272 с.

7. Ефимов С.С. «Обзор методов распараллеливания алгоритмов решения некоторых задач вычислительной дискретной математики», Математические структуры и моделирование 2001, вып.17, с. 72-93.

8. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. Учебное пособие. - М.: Дрофа, 2004.

9. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. - М.: Физматлит, 2003. - 432 с.

10. Дворецкий Д. С., Дворецкий С. И., Муратова Е. И., Ермаков А. А. Компьютерное моделирование биотехнологических процессов и систем. - Тамбов: Издательство ТГТУ, 2005. - 80 c.

Размещено на Allbest.ru

...