Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 43
Текст из файла (страница 43)
Глобальные ПГА (технология master-slave)В этом случае существует только одна популяция на masterпроцессоре, как и в последовательном ГА. При этом остальные процессоры (slave-процессоры или workers-процессоры) используются толькодля расчета целевых функций. Метод очень просто реализуется (т.к.фактически используется последовательный ГА) и хорош в тех случаях, когда вычислительная часть задачи доминирует над коммуникационной.
При построении глобальных ПГА не делается никаких предположений об архитектуре параллельного компьютера. Число индивидуумов, приходящихся на один процессор либо константа, либо можетдинамически меняться с целью обеспечения равномерности загрузки(например, в многопользовательской среде).Хотя, как правило, используются синхронные глобальные ПГА, вданной работе рассматривается асинхронный глобальный ПГА. Накомпьютерах с MIMD архитектурой алгоритм, как правило, состоит вразмещении популяции на одном процессоре, рассылки индвидуальностей на workers-процессоры, получение на главном процессоре значений целевой функции и применении генетических операторов для следующего шага.2.
Островная модель (крупно-зернистый ПГА)В рамках этого подхода на каждом процессоре располагается изолированная сабпопуляция, обменивающаяся особями с другими сабпопуляциями за счет миграции, регулируемой рядом параметров. Каждаясабпопуляция невелика по размеру, поэтому скорость сходимостивесьма высока, хотя качество решения оставляет желать лучшего. Существует критическая скорость миграции, позволяющая получить результат, идентичный последовательному ГА.
Один из подходов состоит в том, что на каждом шаге отсылается соседям лучшая особь. Однако в этом случае существует опасность преждевременной сходимости клокальному экстремуму.2133. Клеточная модель (мелко-зернистый ПГА)В этом случае используется большое число очень маленьких сабпопуляций (в пределе - одна особь на процесс), которые интенсивнообмениваются индивидуумами.
Эта модель наиболее хороша для MPPархитектур, но может применяться на любых мультипроцессорах.4. Результаты численных расчетовПроведенные в данной работе исследования показывают, что насистемах с относительно небольшим количеством процессоров прирешении задач функциональной оптимизации (рассматривались некоторые задачи оптимального профилирования) наиболее оправданнымявляется первый подход к построению ПГА. В тоже время, при решении ряда задач интерпретации расчетных и экспериментальных результатов в рамках парадигмы генетического программирования лучшесебя зарекомендовали островная и клеточная модели ПГА.ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯНАПРАВЛЕННЫХ ОТНОШЕНИЙА.М.
ТолокониковМосковский энергетический институт (технический университет)ВведениеТеория направленных отношений [1, 2] является одним из подходов конструктивного построения таких формальных объектов, какфункции, предикаты, программы, семантические сети и т.д. В рамкахэтого подхода каждый из объектов может быть построен из базовыхобъектов путем операций композиции и оператора наименьшей фиксированной точки. На базе теории направленных отношений создан языкфункционально-логического программирования FLOGOL [5] и средаразработки программ, в основе которой графическое представление,разработанное авторами выше указанной теории.По своей сути отношения встречающиеся повседневно в нашейжизни формализованы как Rk ⊆ D1×D2×…×Dk, где Di i =1, 2, …, k –множества элементов относящихся к той или иной проблематике.
Разделив правую часть (Декартово произведение) на две составляющие иназвав одну входом, а другую выходом, установили соответствие, вобщем случае неоднозначное, авторы получили новое понятие, – направленного отношения (НО) R(m,n) : D′1×D′2×…×D′m → D″1×D″2× …214×D″n, где Djl∈{Di | i =1, 2, …, k}, где l ∈ {′,″}, j = 1, 2, …, m(n). Такоепреобразование позволило представить программный продукт в качестве отношения и оперировать с ним как с отношением.Не для кого не секрет, что программа (или программный комплекс) представляет собой отношение, но задать ее в формализме теории множеств задача достаточно трудоемкая и бессмысленная, дляэтой цели за весь период существования вычислительной техники разрабатывались многочисленные языки программирования.
Посмотримна программу или ее часть. Мы видим механизм, устанавливающийсоответствие между исходными и выходными данными6. Тем самымпрограмма это не что иное, как направленное отношение.Далее используем выходы одного НО в качестве входов другого,или объединить в теоретико-множественном смысле, и получим новое,необходимое нам направленное отношение. Для этого были введеныоперации композиции и набор необходимых для построения отношений константных отношений[2]. Остановимся немного на базовых операциях композиции НО.Операции композиции направленных отношенийПусть R1 и R2 – направленные отношения.R1 · R2 ≡ {(α,β) | ∃γ ((α,β)∈R1 & (β,γ)∈R2)}7 – операция последовательной композиции.
Иллюстрация выполнения операции на примередвух отношений представлена на рис. 1. Эта операция позволяет использовать выходы одного отношения в качестве входов другого8. Понятно, что данная операция, на первый взгляд, не обладает свойством,позволяющим параллельно вычислять отношения R1 и R2 в рамках нового НО. Но учитывая то, что R1 и R2 – это не функции, как мы привыкли считать при программировании с помощью процедурно-ориентированных языков, где на сегодняшний день используется функцио6Нельзя исключать случай, когда исходные и/или выходные данные отсутствуют. Например “программа паразит” ничего не получающая в качествеисходных данных, и ничего не возвращающая в качестве результата; просто занимающая ресурсы вычислительной системы.7В силу требовании к оформления к оформлению тезисов использованияшрифта Times New Roman и отсутствия знака «равно по определению»,здесь и далее знаком ≡ будем обозначать термин «равно по определению».8Для использования в качестве аргументов НО разной арности по входами выходам необходимо применение константных НО [2]215нальная или объектная (некоторая модификация функциональной) парадигмы, то в этом случае операция свойству (назовем его свойствомпараллельности операции) при котором R1 и R2 могут вычисляться независимо.
Заметим, что на конкретном наборе входных значений, привычислении (для простоты, можно понимать перечислительную процедуру) мы получим несколько наборов выходных значений и не обязательно конечное. Это свойство направленного отношения дает намне только больше возможностей при написании программ, но и возможность параллельного вычисления, что при функциональном подходе просто не имеет смысла.R1R2R1R2Рис. 1R1#R2 ≡ {(α1α2, β1β2) | (α1, β1)∈ R1 & (α2, β2)∈ R2} – операция параллельной композиции. Иллюстрация выполнения операции на примередвух отношений представлена на рис. 2.
Эта операция позволяет получить новое отношение входами и выходами которого являются входы ивыходы исходных отношений. При выполнении этой операции необходимо учитывать последовательность соединения входов(выходов).Очевидно, что данная операция обладает свойством параллельности,которое заложено в самом определении операции. Операции подобныеприведенным выше используются и в функциональных языках (в томчисле [1]) , позволяя задавать функции конструктивно.R1R1#R2R2Рис. 2R1 ∪R2 ≡ {(α, β) | ((α,β)∈R1 V (β,γ)∈R2)} – операция объединения направленных отношений.
Операция представляет собой объединение втеоретико-множественном смысле. По аналогии с операцией # можносказать, что данная операция обладает свойством параллельности. Онапозволяет нам при программировании задавать неоднозначные соответствия.216Оператор наименьшей фиксированной точки. Пусть задана система в общем случае рекурсивных уравнений:{Xi = τi(X1, X2, ..., Xn, r1, r2, ..., rm), i = 1, 2, ..., n,(1)где Xi – переменные, rj – элементарные НО, а τi – термы построенныеиз символов переменных константных НО и операций композиции.В интерпретации (1) задает первый компонент кортежа НО X1min,minX2 , ..., Xnmin , являющегося минимальной фиксированной точкой длясистемы уравнений (1), т.е.{Ximin = [Xjmin / Xj | j = 1, 2, ..., n]τi, i = 1, 2, ..., nи для всякого другого кортежа НО X′1,X′2, ..., X′n такого что X′i == [Xjmin/Xj | j = 1, 2, ..., n] τi , i = 1, 2, ..., n выполнено Ximin ⊆ X′i, i = 1,2, ..., n.В основе оператора лежит понятие подстановки в терм вместовхождения переменной соответствующего ей терма.
Аналогия с процедурно-ориентированными языками – это понятие процедуры (функции) в языке. Поставили в соответствие набору операторов идентификатор (имя процедуры) и используем это имя в других частях программы.Разница между языками программирования такими, как С или Pascal, без которых не обходится как правило большинство разработокпрограммного обеспечения, и данным, даже не расширенным в сторону общепринятых типов данных, заключается лишь в том, что здесьприсутствуют средства параллельного вычисления, заложенные в самом языке. Нельзя не отметить, что и в С и в языке Pascal были сделаны попытки включить средства распараллеливания, но на сегодняшнийдень программист вынужден использовать средства предоставляемыеоперационными системами (ОС) для задания параллельных вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
