WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |   ...   | 24 |

В работе получен конструктивный параллельный алгоритм построения оптимального кусочно-постоянного управления, опирающийся на описанный ранее принцип максимума. Вводятся основные понятия, необходимые при описании и построении параллельных алгоритмов, рассматривается решение данной модельной задачи с привлечением различных вычислительных средств, используемых на кластере PARC: сетевые возможности ОС Linux, средства параллельного программирования, использующие механизмы разделяемой (Pthreads) и распределенной (PVM, MPI) памяти.

Литература 1. PARC – кластер высокопроизводительных компьютеров /Исламов Г.Г., Мельчуков С.А., Клочков М.А., Бабич О.В., Сивков Д.А.

Учебно-методическое пособие. Ижевск: УдГУ, 2001. 66 с.

СТРУКТУРЫ ДАННЫХ ДЛЯ РЕАЛИЗАЦИИ АДАПТИВНЫХ ДИАГОНАЛЬНЫХ КРИВЫХ* Д.Е.Квасов Нижегородский государственный университет им. Н.И.Лобачевского Калабрийский университет, Козенца, Италия Рассматривается классическая задача глобальной оптимизации [1]:

min f(x), xD, (1) D = { xRN | ai xi bi, i=1,…,N}. (2) Предполагается, что функция f(x) может быть недифференцируемой, и в ходе решения (1)-(2) могут быть найдены лишь значения f(x) в точках D, причем вычисление значений f(x) требует больших затрат времени. Задача (1)-(2) является частным случаем задачи минимального описания функции [2].

* Работа поддержана грантом РФФИ № 01-01-00587.

Одним из подходов к решению задачи (1)-(2) является диагональный подход [3], обобщающий характеристические алгоритмы [4] на многомерный случай. Идея данного подхода заключается в последовательном разбиении области поиска D на множество гиперинтервалов Di и вычислении функции f(x) в вершинах главных диагоналей получаемых гиперинтервалов. Для каждого гиперинтервала Di вычисляется его характеристика Ri, отражающая «пригодность» данного гиперинтервала для последующего разбиения. Характеристики выбираются так, что чем больше значение Ri, тем больше вероятность нахождения точки глобального минимума f(x) в Di. На каждой итерации алгоритма очередному разбиению подвергается гиперинтервал Dt с максимальным значением характеристики Rt, т.е.

t = arg max {Ri | 1 i m(k)}, (3) где m(k) есть число гиперинтевалов Di на текущей k-й итерации алгоритма. Разбиение Dt осуществляется гиперплоскостями, параллельными координатным плоскостям и проходящими через некоторую точку главной диагонали Dt.

Традиционно применяемыми стратегиями разбиения являются деление пополам и деление на 2N [3]. Как было показано в [2], при данных стратегиях генерируется множество избыточных точек испытания f(x), что приводит как к замедлению работы алгоритма, так и к увеличению машинной памяти для хранения необходимой информации. Избыточность точек испытания является следствием двух факторов:

1. Каждый гиперинтервал Di содержит более двух точек, в которых вычисляется функция f(x).

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

В работе [2] была предложена новая стратегия, которая преодолевает недостатки традиционных стратегий разбиения области поиска D.

Данная стратегия генерирует последовательность новых непрерывных кривых, заполняющих пространство («space-filling curves»), – адаптивных диагональных кривых (АДК). Обычно в численных алгоритмах используется аппроксимация некоторой кривой (например, кривой Пеано, см. [1]), заполняющей пространство, с заданным порядком разбиения (одинаковым для всей области D). Порядок же разбиения АДК отличается в разных подобластях D: чем больше точность поиска, тем сильнее АДК разбивается в подобластях, предположительно содержащих точки глобального минимума функции f(x). Разбиению области D из (2) на текущем шаге алгоритма соответствует АДК с начальной точкой в вершине a и конечной – в вершине b, которая образована главными диагоналями подобластей Di.

Новая АДК строится путем подразбиения текущей АДК в пределах выбранного гиперинтервала Dt (см. (3)) без изменеия остальных участков кривой, причем Dt разбивается на три гиперинтервала равного объема двумя параллельными гиперплоскостями, проходящими перпендикулярно стороне Dt с наибольшей длиной. Таким образом, АДК остается неразрывной в течение всего процесса разбиения. В силу своего построения АДК является фрактальным объектом.

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

Теорема [2]. Существует специальная индексация гиперинтервалов Di, полученных при генерировании АДК на текущей итерации алгоритма, позволяющая по индексу гиперинтервала Di находить координаты его вершин a(i) и b(i), в которых вычисляется f(x).

Информация о функции в конкретной вершине вычисляется только один раз, а затем просто считывается из некоторой базы данных, причем метод в состоянии определить, была ли f(x) уже вычислена в вершинах, сгенерированных на текущей итерации. Так как каждая точка испытания f(x) может принадлежать различным (до 2N) гиперинтервалам, то может возникнуть необходимость считывать 2N раз одну и ту же информацию о значении функции. Поэтому правильная организация данных в связи с фактом существования индексации гиперинтервалов позволяет существенно повысить эффективность процедуры поиска.

Возможно построение различных структур данных для реализации АДК. Например, будем хранить информацию в специализированной базе данных, структура которой приведена на рисунке 1.



Координаты вершин X и соответствующая им информация F(X) (значения функции, градиента и др.) хранятся в записях vi массива вершин. Записи массива вершин образуют (при помощи 2N указателей) двунаправленные линейные списки, каждый из которых соответствует одной из N координат. Информация о гиперинтервалах (значение характеристик Ri, описательная информация INFOi) организуется в виде линейного списка, элементы которого соответствуют данным о каждом из существующих на текущей итерации алгоритма гиперинтервалов. В таком случае гиперинтервалы Di из списка содержат только указатели Ai и Bi на записи из массива вершин и не дублируют информацию о вершинах a(i) и b(i). Например, подобласти с индексами i и k (см. рис.) имеют общую вершину b(i)=b(k): информация о ней хранится в единственной записи vмассива вершин, на которую установлены указатели Bi и Bk соответствующих элементов i и k списка гиперинтервалов.

Рис.1. Структура специализированной базы данных Для обеспечения быстрого доступа к данным необходима эффективная реализация операции вставки новых элементов в список гиперинтервалов с соответствующей настройкой указателей и операции поиска информации о вершинах. Предлагаемая структура данных в связи с процедурой построения АДК отвечает данному требованию.

При параллельной реализации методов [4,5], использующих АДК, на каждой итерации значения характеристик Ri упорядочиваются по невозрастанию и испытания f(x) проводятся одновременно в нескольких гиперинтервалах с наибольшими значениями характеристик, что соответствует одновременному подразбиению АДК в пределах данных гиперинтервалов. Предлагаемая структура данных эффективна также при использовании параллельных методов глобальной оптимизации.

Литература 1. Стронгин Р.Г. Численные методы в многоэкстремальных задачах.

М.: Наука, 1978.

2. Sergeyev Ya.D. An efficient strategy for adaptive partition of Ndimensional intervals in the framework of diagonal algorithms //J.

Optimizat. Theory Appl. 2000. Vol. 107. N 1. P.145–168.

3. Pintr J. Global Optimization in Action. Dordrecht: Kluwer Academic Publishers, 1996.

4. Grishagin V.A., Sergeyev Ya.D., Strongin R.G. Parallel characteristical algorithms for solving problems of global optimization //J. Global Optimizat. 1997. Vol. 10. P. 185–206.

5. Strongin R.G. and Sergeyev Ya.D. Global Optimization with NonConvex Constraints: Sequential and Parallel Algorithms. Dordrecht:

Kluwer Academic Publishers, 2000.

ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО НАЗНАЧЕНИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ НА ГЕТЕРОГЕННЫЙ ВЫЧИСЛИТЕЛЬНЫЙ КЛАСТЕР А.В.Киселев, Е.Л. Зверев Институт криптографии, связи и информатики Академии ФСБ России, Москва В работе рассматриваются вопросы оптимального назначения параллельных задач на вычислительный кластер, образованный путем объединения нескольких мультипроцессорных вычислительных систем.

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

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

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

С каждым вычислительным узлом (ВУ) bi связан описатель – , где l – тип процессора, p – производительность процессора (число команд, выполняемых в единицу времени), zp – текущая загруженность процессора.

Коммуникационная подсистема рассматривается на физическом и логическом уровнях:

• на физическом уровне – как граф Gf = (B,F), где B={bi}– множество ВУ, а F – множество соединяющих вершины физических каналов связи. С каждым каналом связан описатель , где s – пропускная способность канала, а zs – текущая загруженность канала. Топология коммуникационной подсистемы задается матрицей смежности S=|| sij || графа Gf ;

• на логическом уровне – система рассматривается как полный граф Gb, вершинами которого являются ВУ, а ребрами – логические каналы связи. Под логическим каналом понимается путь между вершинами bi и bj графа Gf, обладающий максимальной пропускной способностью. С каждым логическим каналом связан описатель , где c – пропускная способность логического канала, определяемая как минимальная из пропускных способностей физических каналов, образующих данный логический канал, а zc – текущая загруженность логического канала.

Параллельная задача представляется в виде графа Ga = (А,D), где A={Аi}- совокупность взаимодействующих процессов, c каждым из которых связан вектор a=. al определяет вычислительную сложность Ai в числе команд процессора l-типа. D= {Di} – множество дуг – описывает взаимодействия процесса: каждой дуге соответствует число dj, характеризующее передаваемый объем данных.





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

Отличную от 0 загруженность процессора (канала) можно интерпретировать как уменьшение его производительности (пропускной способности). В этом случае будем говорить о приведенной производительности p' (пропускной способности c'): p' = (1–zp)p; c'=(1–zc)c.

Оценить изменение производительности процессора и пропускной способности канала в случае назначения на ВУ процесса A можно по формулам:

di p ci aс2 (i) c с' ; p p' ;

di dp + aс a + p ci (i) Пересчет приведенной пропускной способности осуществляется для всех логических каналов, включающих в свой состав физический канал, используемый процессом Ai для передачи данных.

Обозначим : A B, (N = |A|, M = |B|) отображение информационного графа параллельной задачи Ga на структуру вычислительной системы, заданной графом Gb и представим его матрицей X = { Xij:

i A, j B }, где Xij = 1, если (i) = j, и Xij = 0, если (i) j. Оптимальное отображение доставляет минимум функционалу F(X) = F1 (X) + F2 (X), N N M ai i=где F1(X) = (X ai - p'k )2 ;

ik M i=1k =1 p' j=1 j M M N N F2(X) = pk dij c' X X.

pi kj i=1 j=1p=1k =F1 (X) оценивает равномерность загрузки процессоров, а F2(X) оценивает загрузку коммуникационной подсистемы.

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

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

РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРОВ* В.А. Крюков Институт прикладной математики им. М.В. Келдыша РАН, г.Москва 1. Введение Последние годы во всем мире происходит бурное внедрение вычислительных кластеров. Это вызвано тем, что кластеры стали общедоступными и дешевыми аппаратными платформами для высокопроизводительных вычислений. Поскольку единого определения вычислительного кластера не существует, для упрощения дальнейшего изложения введем некоторую классификацию, которая будет отражать свойства программно-аппаратной платформы, существенные с точки зрения разработки прикладных параллельных программ.

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

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

* Работа поддержана Российским фондом фундаментальных исследований, грант № 99-01-Если на вычислительном кластере аппаратно или программноаппаратно реализована DSM (Distributed Shared Memory – распределенная общая память), позволяющая выполняющимся на разных узлах программам (любым, даже ассемблерным) взаимодействовать через общие переменные, то такой кластер будем называть DSMкластер. Если такая DSM отсутствует, и прикладные программы взаимодействуют посредством передачи сообщений, то вычислительный кластер будем называть DM-кластер (DM – Distributed Memory).

Если все входящие в состав вычислительного кластера узлы имеют одну и ту же архитектуру и производительность, то мы имеем дело с однородным вычислительным кластером. Иначе – с неоднородным.

Неоднородность же вносит следующие серьезные проблемы.

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

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

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

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

За прошедший с тех пор период предложено много различных подходов к разработке параллельных программ, созданы десятки различных языков параллельного программирования и множество различных инструментальных средств. Среди них можно отметить следующие интересные отечественные разработки – Норма, ФортранGNS, Фортран-DVM, mpC, Т-система.

Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |   ...   | 24 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.