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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РЕШЕНИЕ ЗАДАЧИ МЕТАНОГЕНЕЗА С ИСПОЛЬЗОВАНИЕМ ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (пояснительная записка к курсовой работе по дисциплине «Параллельное и распределенное программирование»)Одним из примеров задач многокритериальной оптимизации может служить задача метаногенеза, которая относится к классу вычислительно сложных. При представлении процесса метаногенеза необходимо учитывать достаточно большое количество критериев, назначаемая степень важности которых оказывает существенное влияние, как на процесс, так и на качество составляемой модели.В последнее время, чтобы получить возможность задействовать на практике ту дополнительную вычислительную мощность, которую дает закон Мура, стало необходимо задействовать параллельные вычисления. На протяжении многих лет, производители процессоров постоянно увеличивали тактовую частоту и параллелизм на уровне инструкций, так что на новых процессорах старые однопоточные приложения исполнялись быстрее без каких либо изменений в программном коде.В зависимости от организации подсистем оперативной памяти параллельные компьютеры можно разделить на следующие два класса. Системы с разделяемой памятью (мультипроцессоры), у которых имеется одна виртуальная память, а все процессоры имеют одинаковый доступ к данным и командам, хранящимся в этой памяти (uniform memory access или UMA). Системы с распределенной памятью (мультикомпьютеры), у которых каждый процессор имеет свою локальную оперативную память, а у других процессоров доступ к этой памяти отсутствует. При работе на компьютере с распределенной памятью необходимо создавать копии исходных данных на каждом процессоре. На основе числа потоков команд и потоков данных выделяют четыре класса архитектур: SISD (Single Instruction stream/Single Data stream) - один поток команд и один поток данных;В качестве средства для написания параллельных программ для многопроцессорных систем чаще всего используют 2 стандарта: OPENMP (Open specifications for Multi-Processing) - стандарт для написания параллельных программ в условиях общей памяти. Программа представляется как набор потоков объединенных общей памятью, где проблема синхронизации решается введением критических секций и приватных переменных; MPI (Message Passing Interface) - стандарт, предназначенный для написания программ в условиях разделенной памяти, данный стандарт описывает параллельную программу как набор нитей, взаимодействующих посредством передачи сообщений. OPENMP задуман как стандарт для программирования на масштабируемых SMP-системах (SSMP, CCNUMA) в модели общей памяти (shared memory model). Предполагается, что OPENMP-программа на однопроцессорной платформе может быть использована в качестве последовательной программы, т.е. нет необходимости одновременно поддерживать последовательную и параллельную версии.При разработке параллельных алгоритмов решения задач вычислительной математики принципиальным моментом является анализ эффективности использования параллелизма, состоящий обычно в оценке получаемого ускорения процесса вычисления (сокращения времени решения задачи). Другой важный подход может состоять в построении оценок максимально возможного ускорения процесса получения решения задачи конкретного типа (оценка эффективности параллельного способа решения задачи). , (1.1) в котором для каждой операции указывается номер используемого для выполнения операции процессора и время начала выполнения операции Для того, чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества : 1. Время выполнения параллельного алгоритма определяется максимальным значением времени, используемым в расписании Оценка определяет время выполнения алгоритма при использовании одного процессора и представляет, тем самым, время выполнения последовательного варианта алгоритма решения задачи.Генетические алгоритмы в настоящее время широко используются для интеллектуальной обработки данных и решения задач оптимизации и поиска.Генетические алгоритмы возникли в результате наблюдения и попыток копирования естественных процессов, происходящих в мире живых организмов, в частности, эволюции и связанной с ней селекции (естественного отбора) популяций живых существ. Он заинтересовался свойствами процессов естественной эволюции, в том числе фактом, что эволюционируют хромосомы, а не сами живые существа. Так же, как и в природе, генетические алгоритмы осуществляли поиск "хороших" хромосом без использования какой-либо информации о характере решаемой задачи. На каждом поколении генетическим алгоритмом реализуется отбор пропорционально приспособленности, кроссовер и мутация. Схематичное описание функционирования генетического алгоритма представлено на рисунке 2.1: Рисунок 2.

Содержание

Введение

1. Параллельные вычислительные системы

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

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

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

2. Генетические алгоритмы

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

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

3. Результаты экспериментальных исследований и испытаний

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

3.2 Наложение текстуры на объекты

Заключение

Список литературы генетический метаногенез текстура наложение