Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 15
Текст из файла (страница 15)
1(6). С. 124–130.5. Дудник А.В., Кибец А.И., Кибец Ю.И. Конечно-элементная методикарешения трехмерной нестационарной задачи динамики дискретно армированных конструкций // Проблемы прочности и пластичности: Межвуз. сб. /Н.Новгород: Изд-во ННГУ. – 2003 – Вып.65. – С.92–96.6. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. БХВПетербург, 2002. 609 с.7. Копысов С.П., Красноперов И.В., Рычков В.Н. Объектноориентированный метод декомпозиции области.
Вычислительные методыи программирование. 2003. Т. 4. с. 1–18ОЦЕНКА ТРУДОЕМКОСТИ АЛГОРИТМОВ КОЛЛЕКТИВНЫХОПЕРАЦИЙ MPI ДЛЯ КЛАСТЕРОВ МНОГОУРОВНЕВОЙАРХИТЕКТУРЫА.В. Гришагин, А.Л. Курылев, А.В. ЛиневъНижегородский государственный университет им. Н.И ЛобачевскогоВведениеКоллективные операции являются важным и часто используемымкомпонентом MPI, и в настоящее время различные исследовательскиеколлективы выполняют разработки, связанные с повышением их производительности.
Однако в большинстве случаев при оценке стоимости операций предполагается, что расположение процессов на узлахсети не имеет значение, а число одновременно взаимодействующихпар процессов можно учесть в виде дополнительного слагаемого и вдальнейшем не учитывать его изменение. Проведенные нами исследование показывают, что в кластерах из машин с большим числом процессоров данные параметры вносят существенный вклад в результатоценки стоимости. Например, при изменении нумерации процессов вкоммуникаторе время выполнения одного и того же алгоритма операции bcast может отличаться на 30%.Кластер многоуровневой архитектурыВ качестве примера кластера с многоуровневой архитектурой рассмотрим кластер, построенный на базе POWER5-систем.
Он имеет иерархическую архитектуру и содержит следующие уровни:71• сеть (network, cluster);• узел (node);• книга (book);• сборка (multi-chip module);• чип (chip);• ядро (core);• виртуальный процессор (virtual processor).Каждому уровню соответствует свой способ взаимодействия процессов, выполняющихся в пределах одного объекта данного уровня(сетевое взаимодействие, общая память, общий кэш L3 или L2 и т.д.).Соответственно, время передачи сообщения существенно зависит оттого, механизм какого уровня используется взаимодействующимипроцессами.В настоящий момент мы ограничиваем рассмотрение двумя уровнями архитектуры:• передача данных внутри SMP-узла через общую память;• передача данных между SMP-узлами через сеть.Можно принимать во внимание нижележащие уровни, но в современных операционных системах существует миграция процессов внутри SMP-узла, например, в Linux с ядрами семейства 2.6, реализованыспециализированные алгоритмы, контролирующие перемещение процессов в рамках узла с учетом неоднородной архитектуры SMPсистемы.Измерение стоимости операций точка-точкаДля оценки стоимости коллективных операций мы предлагаемпредварительно измерить стоимость операций точка-точка.
В дальнейших рассуждениях мы рассматриваем однородный кластер (то естькластер, состоящий из одинаковых узлов, единообразно подключенныхк сети), и исходим из следующих гипотез:• одновременная передача и прием сообщений через одно подключение к сети не изменяют время приема и передачи, так как современные сетевые компоненты функционируют в полнодуплексном режиме;• одновременная передача и прием сообщений через общую память снижают скорость приема и передачи;• при выполнении операции доставки сообщения время, вкладопераций передачи и приема в общее время выполнения считается равным.72При принятии перечисленных гипотез для оценки времени выполнения элементарных операций на конкретном кластере необходимовыполнить следующие эксперименты:• определение зависимости времени передачи сообщения черезсеть от размера сообщения и числа передающих процессов на SMPузле.
В ходе эксперимента производится передача сообщений различного размера между парами процессов, при этом процессы каждой пары расположены на различных узлах;• определение зависимости времени передачи сообщения черезобщую память от размера сообщения и числа взаимодействующихпроцессов на SMP-узле.
В ходе эксперимента производится передачасообщений различного размера между несколькими процессами, расположенными на одном узле.По результатам экспериментов мы можем оценить зависимостьстоимости операций точка-точка от следующих параметров:• длина сообщения;• число процессов на SMP-узле, одновременно выполняющихприем/передачу через сетевое соединение;• число процессов на SMP-узле, одновременно выполняющихприем/передачу через общую память.Оценка стоимости коллективных операцийРасчет стоимости алгоритма коллективной операции выполняетсядля некоторого конкретного случая размещения процессов на узлахсети. Оценка выполняется следующим образом:• определяется число шагов, требуемых алгоритму коллективнойоперации;• для каждого шага алгоритма определяется:− какие процессы передают и принимают сообщения и размерэтих сообщений,− какие процессы совместно используют подключение к сетидля приема или передачи, и какие процессы совместно используют общую память,− рассчитывается время выполнения шага для каждого процесса;• трудоемкость алгоритма принимается как сумма максимальныхзначений, полученных на каждом шаге.Результаты исследований показывают, что применение предлагаемого подхода позволяет получить оценки стоимости алгоритмов кол73лективных операций, качественно повторяющие экспериментальныеданные и позволяющие проводить сравнение производительности алгоритмов.ЗаключениеПроведенные исследования показывают существенную зависимость стоимости алгоритмов коллективных операций от размещенияпроцессов на узлах сети и различия в стоимости операций точка-точкачерез разделяемую память и сетевое соединение.
Очевидна необходимость разработки специализированных алгоритмов коллективных операций для таких кластеров. Предлагаемый подход к оценке стоимостиалгоритмов коллективных операций учитывает многоуровневую архитектуру кластера и может быть использован как для реализации динамического выбора оптимального алгоритма при вызове коллективнойоперации, так и для оценки производительности новых алгоритмов.Работа выполнена при поддержке IBM Faculty Awards for Innovation Program.ПАРАЛЛЕЛЬНЫЙ МЕТОД РЕШЕНИЯ МНОГОМЕРНЫХМНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ С НЕВЫПУКЛЫМИОГРАНИЧЕНИЯМИВ.А.ГришагинНижегородский государственный университет им.
Н.И.ЛобачевскогоЯ.Д. СергеевКалабрийский университет, ИталияРассмотрим конечномерную задачу оптимизации (задачу нелинейного программирования)f ( y ) → min, y ∈ Q ⊆ R N(1)Q = { y ∈ D : g j ( y ) ≤ 0, 1 ≤ j ≤ m}(2)D = { y ∈ R N : yi ∈ [ai , bi ], 1 ≤ i ≤ N } ,(3)т.е. задачу отыскания экстремальных значений целевой (минимизируемой) функции f (y) в области Q, задаваемой координатными (3) ифункциональными (2) ограничениями на выбор допустимых точек (векторов) y = (y1, y2, …, yN), принадлежащих N-мерному евклидову пространству RN.74Предметом рассмотрения настоящей статьи являются многоэкстремальные задачи оптимизации, т.е. задачи, в которых целевая функция f (y) имеет в допустимой области Q несколько локальных экстремумов, а ограничения gj(y) из (2) также могут быть многоэкстремальными.
Будем далее предполагать, что функции gj(y), 1 ≤ j ≤ m удовлетворяют условию Липшица каждое со своей константой Lj, а целеваяфункция f (y) также является липшицевой с константой Lm+1.Важнейшими факторами, определяющими сложность исследования задач данного класса, являются размерность N и структура допустимой области Q. В силу того, что глобальный экстремум является нелокальной, а интегральной характеристикой минимизируемой функции, т.е. для его определения необходимо сопоставить значение в точкеглобального минимума со значениями функции в остальных точкахобласти поиска, поисковый метод многоэкстремальной оптимизациивынужден строить некоторую сетку испытаний, покрывающую допустимую область. Вследствие этого для рассматриваемого класса задачимеет место так называемое «проклятие размерности», состоящее вэкспоненциальном росте вычислительных затрат при увеличении размерности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
