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

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

311

поток получает на выполнение одну задачу – формирует одну

точку выходного изображения;

2. поток получает набор задач – формирует несколько точек

выходного изображения.

В качестве набора задач рассматривались строка, столбец или

блочная строка выходного изображения.

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

в частности, рассматривались следующие варианты строчной

декомпозиции:

Строки распределяются между потоками статически, то есть

при обращении освободившегося потока за очередной задачей

(строкой для обработки) он получает строку с номером вида

*kni+

, где k – номер потока, n – общее количество потоков, i

– количество задач, выполненное этим потоком. На каждом

шаге обработки (при каждом положении окна) производится

считывание информации обо всех отсчетах, попавших в это

окно.

Строки распределяются между потоками статически, но на

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

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

последнем передвижении (столбец).

Строки распределяются между потоками динамически, т.е.

при обращении освободившегося потока за очередной задачей

он получает строку с номером, следующим за номером

последней взятой строки. На каждом шаге обработки

производится считывание очередного столбца.

Кроме указанных выше способов исследовался также вариант со

статическим распределением столбцов. Особенность такого варианта

состоит в том, что

при передвижении по столбцу (при сдвиге окна

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

как при построчной обработке. Влияние направления движения

определяется способом хранения изображения, т.е. временем,

затрачиваемым на доступ к элементам.

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

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

система

какое-то время не выделяет квантов времени для работы, этот поток

завершит свою работу позже остальных. То есть при определенных

312

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

очень эффективно. Однако по сравнению с блочным разбиением нет

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

этапе работы программы.

Основные результаты

Рассмотрим полученные зависимости общего времени обработки

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

Из рисунка 2 можно заметить, что для малого размера окна

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

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

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

окон линейная фильтрация становится более

выигрышной, но разница

в производительности для разного рода процессоров остается такой

же.

Рис. 2. Время обработки изображения окном 3x3 и 9x9, где MT_med и MT_fir -

медианная и линейная фильтрации на мультитредовом, DUO_med и DUO_fir –

на двухъядерном, XEON_med и XEON_fir – на восьмиядерном компьютере.

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

На рисунке 3 представлены графики, иллюстрирующие

соответствующие кривые для трех вариантов разбиения изображения.

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

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

случае – для расчета строки. В третьем случае входное изображение

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

до начала обработки

Из графиков видно, что наибольшее время занимает обработка

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

задачей. Этот факт объясняется наличием синхронизации в модуле

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

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

времени ожидают своей очереди при получении задачи.

313

Рис. 3. Время обработки изображения окном 3x3 и 9x9, где Single_MT,

String_MT и Block_MT – позадачная, построчная и блочная декомпозиции на

мультитредовом, Single_DUO, String_DUO и Block_DUO – на двухъядерном,

Single_XEON, String_XEON и Block_XEON – на восьмиядерном процессоре

Построчное распределение практически не уступает блочному. То

есть при построении многопоточных приложений в случае

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

декомпозицию по данным нельзя) следует воспользоваться построчной

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

позадачной декомпозицией и практически не проигрывает по

сравнению с блочной. Отметим также, что при

увеличении размера

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

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

На рисунке 4 приведены графики зависимости времени обработки

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

строчной декомпозиции.

Рис. 4. Время обработки изображения на одноядерном мультитредовом и

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

(считывается все окно), 2 - статическое распределение строк (считывается

столбец), 3 - статическое распределение столбцов (считывается строка), 4 -

динамическое распределение строк, 5 - динамическое распределение задач, 6 -

блочное распределение

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

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

временным затратам близко к распределению задач.

Статическое распределение столбцов, как видно из графика, так же

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

314

факт можно объяснить особенностями используемого формата

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

оказываются большими, чем затраты на считывание столбца.

Заключение

Преимущество многоядерных процессоров над одноядерными (в

том числе мультитредовыми) особенно сильно проявляется в

следующих случаях:

изображение подверглось сильным динамическим

искажениям, и требуется его обработка фильтром с большой

опорной областью,

изображение имеет большие размеры,

изображение можно заранее разбить на блоки и распределить

их между процессами, занимающимися обработкой.

Работа выполнена при поддержке РФФИ (гранты № 06-08-01024 и

№ 07-07-00210), а также гранта исследовательского конкурса

компании «Интел» по многоядерным технологиям.

Литература

1. Калышенко А.А. Обзор четыхядерного процессора Intel,

http://samara.pragma.ru/files/reviews/intel_quad.html?shop=1ec58

f3b952fa19af12d6229423a7139, 2006 г.

R.G. Gonzales, R.E. Woods. Digital Image Processing. Addison-

Wesley, 1992.

Методы компьютерной обработки изображений / Под ред.

Сойфера В.А. Москва: Физматлит, 2003.

ВЛИЯНИЕ СИНХРОННЫХ И АСИНХРОННЫХ

ВЗАИМОДЕЙСТВИЙ НА ПРОИЗВОДИТЕЛЬНОСТЬ

ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ.

Д.И. Харитонов, Д.С. Шиян

Институт автоматики и процессов управления ДВО РАН,

Владивосток

В настоящей статье предлагается сравнение эффективности

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

315

параллельной программе, моделирующей двумерное нестационарное

движение газа через пористый тепловыделяющий элемент.

Введение

Эффективность работы параллельной программы обычно

оценивается как отношение времени работы однопроцессорной версии

программы ко времени работы программы на многопроцессорной

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

количества используемых процессоров. Идеальным вариантом

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

процессоров. На практике же величина ускорения программы имеет

верхний предел, который объясняется

законом Амдала, то есть долей

последовательных операций в программе. На графике времени работы

программы этот эффект проявляется как предел, к которому стремится

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

Довольно часто этот предел наблюдается уже при количестве

используемых процессоров порядка 10, что заставляет задумываться

об альтернативных объяснениях этого явления, в частности

о степени

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

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

В 2007 году в ИАПУ ДВО РАН была произведена адаптация

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

решения системы дифференциальных уравнений, к исполнению на

многопроцессорной вычислительной системе. При оценке

эффективности работы программы на многопроцессорном

вычислительном комплексе МВС15000 (42 узла по 2 процессора IBM

PowerPC 970+, объединённых сетью Myrinet), был получен

график

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

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

процессов к асинхронному. Далее в статье приводятся сравнительные

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

типа взаимодействия.

Описание программы

Рассматриваемая в настоящей статье программа реализует

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

нестационарное движение газа через пористый тепловыделяющий

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

программе [1,2], следует отметить некоторые особенности её

реализации. Входные и выходные данные хранятся в шести

316

трехмерных статических массивах, каждый из которых отвечает за

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

плотности газа, температуры твердой фазы, горизонтальной и

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

массивов отвечают за размерность сетки вычислений, а третья за

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

вычислений. Сетка имеет прямоугольную форму, внутри

которой

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

имеет т-образную форму. Размерность сетки вычислений и количество

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

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

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

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

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

условий, которые определяются в

начале программы.

Рис. 1. Шаблон вычислений

В реализованном в программе численном методе расчет значений

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

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

каждой итерации слои меняются местами. Для вычисления значений в

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

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

серым цветом

помечена ячейка с вычисляемыми значениями. Шаблон

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

вертикальной скоростей фильтрации представлен на рис. 1а, для

вычисления значений температуры твердой фазы - на рис. 1б. Порядок

обхода ячеек узлов сетки изображён на рисунке 1в.

317

Рис. 2. Взаимодействие между процессами параллельной программы

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

подходит для параллельной реализации. При этом сетка вычислений

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

своими соседями. На рис. 2 представлена схема взаимодействия для j-

го процессора. Каждая расчетная область состоит из: внутренней

области (I), для вычисления значений которой не требуются значения

из других областей; граничных значений (II), для

вычисления которых

необходимы значения из соседних расчетных областей; теневой

области (III), значениями которой являются граничные значения

соседней области, т.е. они не вычисляются на рассматриваемом узле.

На каждой итерации процессы обмениваются с соседями, передавая им

свои граничные и принимая от них теневые области. Таким образом,

основной параллельный вычислительный процесс можно разбить

на 2

стадии. Первая стадия – вычисление значений расчетной области,

вторая стадия – синхронный обмен граничными областями

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

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

многопроцессорный вычислительный комплекс МВС15000. Объем

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

зависисмости от размера сетки, а объем пересылаемых сообщений

возрастает в линейной зависимости от размера сетки. Таким образом, с

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

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

настоящем

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

при различном количестве итераций и размерностей сетки

вычислений.

Для анализа эффективности взаимодействий последовательно

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

время вычислений с синхронным обменом – первоначальное

время работы программы;

318

время, затрачиваемое на синхронный обмен без вычислений –

для оценки быстродействия MPI среды;

3. время, затрачиваемое на асинхронный обмен данными без

вычисления – для оценки влияния процедуры синхронизации;

время непосредственно вычисления без учёта обмена

сообщениями;

время вычислений с асинхронным обменом данными.

В процессе исполнения программы на многопроцессороном

вычислительном кластере получили графики (рис. 3), где на оси

абсцисс использовалась логарифмическая шкала по степени 2.

При использовании асинхронного типа обмена между

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

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

между процессорами, что заметно быстрее,

чем при использовании

синхронного взаимодействия. На графиках видно, что время,

затрачиваемое на осуществление синхронного обмена между

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

без осуществления вычислений, а время асинхронного обмена не

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

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

взаимодействий при увеличении количества процессоров заметно

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

, причем на примере

использования 16 процессоров время синхронизации обмена занимает

практически пятую часть от всего времени работы программы.

319

1000

11000

21000

31000

41000

51000

61000

71000

01234

сек

Синхронный обмен с вычислениями

Асинхронный обм е н с вычислениями

Вычисления без обмена

Рис.1. Зависимость времени работы

программы от количества

процессоров (логарифмическая

шкала).

500

1000

1500

2000

2500

3000

3500

01234

сек

Синхронный обмен А синхронный обмен

Рис.2. Зависимость времени

синхронных и асинхронных типов

обменов от количества процессоров

без вычислений (логарифмическая

шкала

)

Рис. 3

Заключение

Производительность коммуникационной среды существенно

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

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

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

слабовзаимодействующих процессов. Переход к быстрой

коммуникационной среде, например от Ethernet к Myrinet, позволяет

увеличить пропускную способность канала и уменьшить латентность,

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

параллельной программы

. Как было отмечено ранее, применение

синхронных взаимодействий может во много раз понизить

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

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

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

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

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

процессоров, вызванного ожиданием. Даже в лекционных

курсах

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

предпочтительнее синхронных [4]. Однако на практике

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

простым. Например, а статье [5] отмечается, что точечные операции

взаимодействия Send/Recv являются источниками ошибок. Между тем,

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

только при помощи точечных операций. Таким образом, в настоящее

время у разработчиков

программного обеспечения есть непростой

320

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

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

взаимодействий, ограничивающих общую эффективность

параллельных программ.

Литература

1. Левин В.А., Луценко Н.А. Течение газа через пористую

тепловыделяющую среду при учете температурной

зависимости вязкости газа // Инженерно-физический журнал.

2006. Т.79, №1. С.35-40.

Левин В.А., Луценко Н.А. Численное моделирование

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

тепловыделяющие элементы // Вычислительные технологии.

Т.11, №6. С.44-58.

Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. -

СПб.: БХБ-Петербург. 2002. 608с.

Group W., Lusk E., Skjellum A

Using MPI — 2nd Edition: Portable Parallel Programming with

the Message Passing Interface (Scientific and Engineering

Computation). MIT Press, 1999

S.Gorlatch. Send-Recv Considered Harmful? Myths and Truths

about Parallel Programming, in: Parallel Computing Technologies,

ed. V.Malyshkin (Springer, 2001), P.243-257.

ПРОГРАММНОЕ СРЕДСТВО ЦЕНТРАЛИЗОВАННОГО

УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМИ ВЫЧИСЛЕНИЯМИ

А.А. Чащин

Вятский государственный университет, Киров

Введение

При решении научных задач, требующих больших

вычислительных расчетов, таких как моделирование сложных

процессов, статистический анализ и др., научно-исследовательские

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

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

задачи на отдельные потоки, обрабатываемые параллельно. Главный

недостаток кластерных систем: системы дорогие и довольно быстро

стареют. Одной из перспективных

технологий параллельных