Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

Глобальный параллелизм

Глобальный параллелизм подразумевает параллельное выполнение

всех операторов генетического алгоритма. При распараллеливании

процесса вычисления fitness-функции проблем не возникает, т.к.

значение функции отдельной хромосомы обычно не зависит от других

хромосом. Некоторую трудность для распараллеливания представляет

оператор селекции.

Параллельные виды операторов селекции построены на основе

последовательных операторов. Следовательно, можно

выделить

следующие виды операторов селекции [2]:

1. пространственный турнирный отбор (англ.: Spatial Tournament

Selection);

2. параллельная пропорциональная селекция (англ.: Parallel

Fitness Proportionate Selection);

3. упорядоченная (разрядная) селекция (англ.: Linear ranking

selection);

4. равновероятный отбор.

Параллельный вариант турнирного отбора носит название

пространственного турнирного отбора (ST-selection), т.к. турниры

проходят в ограниченном пространстве. Ограниченное пространство

определяется соседними процессорами

для каждого процессора.

Данный метод селекции является глобальным, т.к. он сочетает в себе

локальные турниры с перемешиванием всего пространства популяции.

Параллельная пропорциональная селекция выполняется за

несколько шагов. Сначала строится рулетка, т.е. каждый процессор

узнаёт, какую часть рулетки он представляет. Далее каждый процессор

выбирает родительскую хромосому путём генерации случайного

числа. На третьем этапе случайные числа ставятся в соответствие

долям колеса рулетки и определяются соответствующие адреса

процессоров. На последнем шаге хромосомы пересылаются по адресу

процессора, который был определён на предыдущем шаге.

Алгоритм параллельной пропорциональной селекции состоит из

следующих шагов [2]:

1. Вычислить суммы

∑

для i-ой хромосомы и переслать

сумму

всем процессорам.

2. На каждом процессоре j генерировать случайное число

r в

интервале [0,

]

Шаги 3 и 4 необходимы для определения адреса

выбранного

родителя, т.е. если

iji

≤

−1

, то

=i.

3. Соединить две последовательности

),...,(

1 N

),...,(

1 N

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

два числа (необходимо использование пары

),( jr

вместо

r ,

т.к. индекс j (адрес выбираемого процессора) потребуется

позже).

4. Вычислить количество

, которые меньше чем

r .

Результатом данного вычисления является

последовательность

),...,(

1 N

cc Если

r является k-ым r-

элементом сортированной последовательности (шаг 3), то

является адресом процессора, хранящего родителя,

выбранного процессором j, т.е.

Шаги 5-9 осуществляют пересылку выбранных родителей

процессорам, которым они необходимы.

5. Сортировать пары

),( j

в змеевидном порядке (по первому

элементу). Результатом является последовательность

),(

,…

),(

NjN

6. Если

jkjk

ππ

≠

−1

, то процессор k посылает свой адрес (k)

процессору

7. Если процессор i получает адрес k на шаге 6, он посылает

свою хромосому

x процессору k.

8. Если процессор k получает хромосому x на шаге 7, он

пересылает её всем процессорам k’, для которых

'jkjk

После этого каждый процессор содержит хромосому x и пару

),( j

9. Каждый процессор пересылает свою хромосому x процессору

После этого каждый процессор получил хромосому, согласно

случайно сгенерированному числу на шаге 2.

Скрещивание:

Каждый процессор получает родительскую хромосому из соседнего

процессора.

Нечётные процессоры получают хромосому слева, чётные - справа.

Выполнить скрещивание на родительских хромосомах для получения

потомства.

В случае параллельной упорядоченной селекции,

разряд каждой

хромосомы легко может быть получен с помощью параллельной

сортировки (шаг 1). Определение разряда выбранной хромосомы не

составляет труда, т.к. вероятность выбора той или иной хромосомы

только косвенно зависит от значения fitness-функции.

Алгоритм параллельной упорядоченной селекции можно

представить следующими шагами[2]:

Пусть

- значение fitness-функции хромосомы на i-ом

процессоре. Сортировать пары вида

()

по первому значению.

Таким образом, каждый процессор j содержит пару

(

)

такую, что

хромосома i имеет разряд j, т.е. процессор j имеет указатель

на

процессор, на котором располагается хромосома с разрядом j.

Каждый процессор генерирует случайным образом число в

диапазоне

]1)1(

,0[ −−NN

и вычисляет разряд

⎥

⎦

⎥

⎢

⎣

⎢

++=

Сортировать отобранные разряды

в змеевидном

(синусоидальном) порядке. Результатом является последовательность

),...,(

21 NSS

Если

≠

−1

, то процессор k посылает свой адрес (k) процессору

Если процессор l получил адрес k на шаге 4, он посылает указатель

обратно процессору k.

Если процессор k получил указатель

на шаге 5, он посылает

свой адрес (k) процессору

Если процессор i получает адрес k на шаге 6, он посылает свою

хромосому

x процессору k.

Если процессор k получил хромосому x на шаге 7, он передаёт

хромосому x всем процессорам

, для которых

'kk

После этого

шага каждый процессор содержит хромосому x и пару

),( j

Хромосома x была необходима процессору j.

Каждый процессор посылает свою хромосому x процессору j.

Скрещивание:

Каждый процессор: принять второго родителя (хромосому) от

соседнего процессора. Нечётные процессоры принимают хромосомы

слева, чётные - слева.

Выполнить оператор скрещивания для формирования потомства.

Миграционная (островная) модель

Основная идея данного вида параллелизма заключается в

разделении общей популяции

на отдельные подпопуляции,

эволюционное моделирование которых осуществляется на отдельных

процессорах [1]. Определяется размер подпопулюций, топология и

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

материалом между подпопуляциями. В случае, если обмен

хромосомами происходит только между соседними вычислителями –

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

любыми подпопуляциями – это островная модель вычислений.

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

основанные на миграционная модели

включают следующие шаги [3]:

1. Определить подходящее представление задачи; случайным

образом генерировать начальную популяцию и разделить её

на N подзадач; определить структуру соседей субпопуляции.

2. Для каждой субпопуляции Sp

(i=1,…,N) выполнить

шаги 3 и 4.

3. Для Nm поколений каждой субпопуляции Sp

выполнить

генетические операторы (селекцию, скрещивание, локальную

оптимизацию (local hill-climbing),рекомбинацию).

4. Отправить лучшую хромосому субпопуляции n “соседям” и

получить лучшие хромосомы от “соседей”, удалить из

субпопуляции n хромосом (наихудших по значению

fitness-функции; родственных; случайно выбранных).

5. Если не конец, то на шаг 2.

Применение того или иного варианта миграционной модели

зависит от архитектуры параллельного вычислителя (сетевая или

кольцевая). Частота миграции определяется размерами

подпопуляций.

При высокой частоте подпопуляция может быстро потерять

гетерогенность. Наоборот, при слабой интенсивности миграции и

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

скольких хороших решений, однако сходимость генетического

алгоритма замедляется.

Клеточная модель

В клеточной модели работа ведётся с одной единственной

популяцией. Каждая хромосома в данном случае расположена в

отдельной ячейке

плоской сетки. Селекцию и скрещивание возможно

применять только в отношении хромосом, находящихся в соседних

ячейках.

Генетические алгоритмы, основанные на клеточной модели,

состоят из следующих шагов [3]:

1. Случайным образом генерировать начальную популяцию;

назначить каждую хромосому определённой ячейке решётки;

для всех хромосом определить значение fitness-функции.

2. Для каждой текущей ячейки с

выполнить шаги 3, 4, 5 и 6.

3. Выбрать новую хромосому среди соседей ячейки с, чтобы

занять ячейку с.

4. Случайным образом выбрать хромосому из соседей ячейки с,

и повторно объединить (рекомбинировать) её с хромосомой в

ячейке с с вероятностью

p ; назначить одного из потомков

на ячейку с.

5. Выполнить мутацию хромосомы, ячейки с с вероятностью

p .

6. Вычислить значение fitness-функции для новой хромосомы в

ячейке с.

7. Если не конец, то на шаг 2.

Диффузионная модель

Третья разновидность параллелизма [1] - диффузионная модель. В

этом случае общая популяция разделяется на большое количество

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

селекции применяются лишь в ограниченной области, определяемой

отношением соседства. Это приводит к тому, что хорошие решения

очень медленно распространяются в популяции (диффузия) и про-

блема попадания в "локальную

яму" становится менее острой.

Выводы

В работе дана классификация генетических алгоритмов,

основанных на параллельных вычислениях; описаны общие стратегии

каждого вида параллелизма. Использование параллельных вычислений

при решении задач с помощью генетических алгоритмов позволяет

увеличить вероятность сходимости алгоритма в точке глобального

экстремума (данное преимущество относится к диффузионной и

миграционной/островной моделям), уменьшить общее

время

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

Литература

1. Родзин С.И. Формы реализации и границы применения

эволюционных алгоритмов // Перспективные

информационные технологии и интеллектуальные системы/

2002. №1.

2. Branke J., Andersen H.Ch., Schmeck H. Global Selection Methods

for SIMD Computers// Forschungsbericht Xo. 333, Institute AIFB,

University of Karlsruhe, Germany,Abstract.

3. Lin G., Xin Yao. Parallel Genetic algorithm on PVM //

Computational Intelligence Group, Department of Computer

Science. University College, The University of New South Wales.

РАЗВИТИЕ МЕЖФАКУЛЬТЕТСКОЙ МАГИСТРАТУРЫ

ПО СИСТЕМНОМУ И ПРИКЛАДНОМУ

ПРОГРАММИРОВАНИЮ ДЛЯ МНОГОЯДЕРНЫХ

КОМПЬЮТЕРНЫХ СИСТЕМ:

ОПЫТ НИЖЕГОРОДСКОГО УНИВЕРСИТЕТА

В.П. Гергель, В.А. Гришагин

Нижегородский государственный университет

В области современных компьютерных технологий качественное

изменение ситуации связано с появлением и прогнозируемым

широким распространением многоядерных платформ (до 70% рынка в

2006 г.). Как результат, потребность эффективного использования

параллельных структур становится массовой как со стороны

системного, так со стороны прикладного параллельного

программирования. Динамика изменения ситуации и острота

проблемы ставит сложную задачу оперативной подготовки

высококвалифицированных кадров, что представляет собой

определенный вызов для системы высшего университетского

образования. Для самой университетской среды возникает

комплексная проблема поиска новых и переподготовки существующих

преподавательских

кадров, развития учебных планов, разработки

новых и расширения уже имеющихся учебных курсов, создания новых

лабораторных практикумов. Осознавая все это, Нижегородский

госуниверситет ведет целенаправленную активную работу, связанную

с созданием новых форм и методов подготовки кадров в области

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

области критических суперкомпьютерных технологий. В

связи с

переходом на многоуровневую систему образования важнейшее

значение приобретает развитие магистратуры как базовой формы

подготовки кадров высокого научного потенциала.

В области параллельных вычислений Нижегородский

госуниверситет инициировал новаторскую форму подготовки

специалистов - межфакультетскую магистратуру по системному и

прикладному программированию для многоядерных компьютерных

систем, организованную при поддержке компании Intel.

Данная магистратура содержит интегрированную

систему учебных

курсов, обеспечивающую комплексный подход к подготовке

специалистов по параллельным компьютерным технологиям,

включающий в себя:

 расширение фундаментальной подготовки (модели и методы

решения сложных вычислительных задач),

 изучение передовых архитектур и системных программных

средств параллельных высокопроизводительных вычислений

(архитектуры многопроцессорных компьютерных систем и

многоядерных процессоров, технологии и инструменты

параллельного программирования, сети и Grid-технологии,

параллельные базы данных),

 параллельные

вычисления в прикладных областях (обработка

изображений, параллельные методы в физике и радиофизике,

принятии решений, химии, биологии, научная графика).

Ключевым принципом магистратуры является

междисциплинарный подход к образованию, реализующий

возможность получения знаний по параллельному программированию

специалистами из разных проблемных областей и одновременно

преодолевающий ограниченность узкоспециализированной

подготовки.

Магистратура создавалась на базе существующей в

Нижегородском университете межфакультетской магистерской

программы "Математические модели, методы и программное

обеспечение современных компьютерных технологий" для

существенного расширения подготовки высококвалифицированных

специалистов как в области системного программирования для новых

многоядерных компьютерных систем, так и области прикладного

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

направлений науки и техники (механики, физики, химии, биологии и

др.).

В рамках

магистратуры созданы две подпрограммы

(специализации):

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

многоядерных компьютерных систем,

 Прикладное параллельное программирование для

многоядерных компьютерных систем.

Обеспечение межфакультетского характера осуществляется на

ассоциативной основе – интеграция факультетских программ

магистратуры обеспечивается при помощи введения общих учебных

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

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

эффективному применению и использованию многоядерных

компьютерных платформ.

Структура магистерской программы состоит в следующем. Общее

количество курсов, планируемых к включению в магистратуру – 22. В

состав курсов вошли три курса,

уже разработанных и апробированных

ранее, для 5 дисциплин был обеспечен определенный уровень

доработки, используются 2 учебных курса из других университетов

(при развитии магистратуры количество таких курсов планируется

расширить). Планируется разработка 12 новых учебных курсов (4

курса из цикла системного параллельного программирования и 8

курсов из цикла прикладного параллельного программирования), из

которых 7 курсов готовы к использованию.

В состав общих курсов, которые являются обязательными для

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

Данные курсы посвящены базовым проблемам

высокопроизводительных вычислений, в их число входят следующие

курсы:

 Анализ и разработка алгоритмов.

 Введение в параллельное программирование.

 Архитектура вычислительных систем.

 Операционные системы.

 Компьютерные сети.

Вторая группа

курсов является обязательной для подпрограммы

"Системное программирование" и представляет собой курсы по

выбору для подпрограммы "Прикладное программирование". Данные

дисциплины расширяют спектр вопросов, изученных в разделе общих

курсов, ориентируясь на углубление знаний по конкретным

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

 Технологии программирования.

 Технологии построения и

использования кластерных систем.

 Алгоритмические языки и библиотеки параллельного

программирования.

 Технологии разработки параллельных программ.

 Введение в технологии GRID.

 Анализ требований и проектирование программных систем.

100

 Параллельные системы баз данных (данный курс разработан

профессором Южно-Уральского университета

Л.Б.Соколинским и внедряется в рамках магистратуры).

Третья группа дисциплин состоит из 10 курсов, которые являются

дисциплинами по выбору для обеих подпрограмм, но студенты

подпрограммы "Прикладное программирование" обязаны выбрать два

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

группы посвящены специализированным прикладным вопросам

параллельных вычислений.

Подготовка по новому учебному плану магистратуры начата с 1

сентября 2006 г. Общее количество обучаемых в магистратуре –

человек.

Существенная часть работ проекта состоит в расширении

взаимодействия факультетов ННГУ в рамках межфакультетской

магистратуры. В рамках проекта проводятся работы по

тиражированию курсов в университетах г. Нижнего Новгорода

(Технического и Архитектурно-строительного университетов) и

других городов России и стран СНГ (Саровский физико-технический

институт, Казанский университет, Самарский аэрокосмический

университет и

др.). Общее количество обучаемых в магистратуре

должно возрасти до 40-50 человек.

Данная магистерская программа рассматривается как опытный

полигон по созданию новых форм подготовки квалифицированных

специалистов по высокопроизводительным параллельным

вычислениям и многоядерным архитектурам. В дальнейшем

планируется осуществить трансфер отдельных курсов, разделов

курсов, лабораторных работ в программы начального уровня высшего

образования – бакалавриата – с целью

реализации массовости

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

параллельных вычислений.

В настоящий момент реализуется разработка учебно-

методического комплекса магистратуры в рамках гранта компании

Intel по разработке и внедрению учебно-методических комплексов в

области параллельных компьютерных технологий и

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

Intel Multicore Curriculum Program, которая является частью Intel®

Higher Education Program.