WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

В однородном случае = tw / tc и выражение (6) принимает вид:

p S0 ( p) =. (7) 1+ ( p -1) + p( p -1) N Выражение (6) можно переписать в форме:

S( p) = I / O 1 + ( p -1) + p( p -1) i ki N (8) p p p tw tw 1 i i = ; = i p -1 tc ki p( p -1) tc i=2 k =1 i=i k Здесь, - средние арифметические значения параметра. Следует отметить, что в i ki общем случае, так как они вычисляются усреднением по различным i ki элементам. Таким образом, модель производительности алгоритма на неоднородной вычислительной системе (6) может быть заменена моделью (8) более простой (эквивалентной) системы, в которой пропускная способность сети при рассылке данных не равна пропускной способности сети при сборе данных обратно на узел ввода-вывода.

Если положить = µ, где µ - коэффициент пропорциональности, то можно ki i заменить выражение (8) моделью для однородной вычислительной системы:

~ p S ( p) =. (9) µ 1+ ( p -1) + p( p -1) i i N Таким образом, производительность (6) алгоритма расчета m статистических характеристик на неоднородной системе, эквивалентна производительности алгоритма, передающего на узел ввода-вывода µm статистических характеристик, уже на однородной системе, которая описывается уравнениями (7,9).

Следует отметить, что 1, и можно без модификации использовать p>> ik i формулу (6) для однородной системы со средним значением параметра. Параметры,µ можно получить по результатам тестирования вычислительной системы.

i Можно ли описать производительность в GRID Вычисления в гиперсетях (GRID) печально знамениты тем, что параметры вычислительной среды p, tc i, twi заранее не известны и меняются от запуска к запуску.

Потому для описания производительности следует задать модель их изменчивости. Если предположить, что при каждом запуске приложения на такой системе пользователю -предоставляется p вычислительных узлов производительностью k = tc и временем k обмена tw, которые выбираются из некоторой генеральной совокупности k (статистического ансамбля). Тогда выражение (6) для производительности алгоритма на неоднородной системе должно допускать вероятностное толкование.

Для удобства запишем выражение (6) в виде:

S( p) =. (10) p p I / O p 1+ + 1+ N ii ij N i=2 k =1 i=2, ik Здесь первая сумма соответствует прямым характеристикам взаимодействия узла ввода-вывода с остальными узлами, а вторая сумма – «перекрестным» связям. Пусть (для простоты) k, ki суть случайные величины с математическими ожиданиями v, и дисперсиями D, D соответственно. Следует отметить, что в пределе, но в i ki принципе это разные величины (усреднение K ведется по элементам конкретной системы, а X - по всем системам, входящим в ансамбль). Тогда суммы в знаменателе (10) можно интерпретировать как гауссовы случайные величины, исходя из центральной предельной теоремы. Их характеристики имеют вид:

p ; D[1] = ( p -1)1+ 1 = ; M[1] = ( p -1)1+ D, 1+ N ii N N i= (11) p p 1 = ; M[2 ] = ( p -1)2 ; D[2 ] = ( p -1)2 D.

ij N N k =1 i=2, ik Тогда для оценивания статистических характеристик производительности алгоритма на многопроцессорной системе со случайными параметрами можно применить метод статистической линеаризации.

Математическое ожидание параллельного ускорения будет иметь вид:

p S ( p) =. (12) I / 1+ ( p -1)1+ + ( p -1) N N Таким образом, среднюю производительность приложений на GRID можно рассматривать в приближении однородной MPP-системы), средние характеристики (, ) которой оцениваются по экспериментальным данным. Этот вывод может показаться более грубым, чем выражение (6) для неоднородной системы, в которой все параметры заданы детерминировано. Но, если учесть, что GRID является многопользовательской средой, на получение более четких оценок среднего рассчитывать не приходится (пользователю никогда не известно, какие p вычислительных узлов могут быть доступны в момент запуска).

Дисперсия параллельного ускорения (в предположении, что между характеристиками, нет статистической зависимости) задается выражением:

- p p DS ( p) = D + p D, 1+ A2 ( p)2 I A4 ( p) N I / O / O (13) A( p) = 1+ ( p -1)1+ + ( p -1)2.

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

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

• Характеристики производительности узлов:

= 2.0, = D.5 = 0.5, = 2.0.

I / • Характеристики относительной пропускной способности сети:

= 0.040, = 0.012.

• Характеристики данных: m = 102, N = 105, = 2 103.

На рис. 7(а) приведено математическое ожидание параллельного ускорения и границы соответствующего 99% вероятностного интервала. На рис. 7(б) приведена дисперсия параллельного ускорения, рассчитанная по формуле (13): полное выражение, и первое и второе слагаемые отдельно. Из рисунка видно, что вклад обоих слагаемых различен.

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

Рис. 7. Вероятностные характеристики параллельного ускорения для многопроцессорной системы со случайными параметрами: (а) математическое ожидание (1) и границы 99% вероятностного интервала; (б) дисперсия: общая (1), только первое слагаемое (2), только второе слагаемое (3).

Пример: расчет ковариационной функции В качестве практического примера количественного анализа производительности рассмотрим задачу расчета ковариационной функции случайного пространственновременного поля. С вычислительной точки зрения она сводится к расчету ковариационной матрицы n-мерной случайной величиныk11 k1n m n (k ) ) = {i} ; K = O, ki, j = (k, i, j =1,n. (14) i j i= m -k = knn kn(k ) Здесь верхний индекс нумерует элементы выборки. Следует отметить, что такое (матричное) представление с алгоритмической точки зрения является наиболее общим. В соответствии с принципами декомпозиции, возможны, как минимум, два варианта построения метамодели. Первый, самый простой, соответствует простой декомпозиции по ансамблю:

n,m (k • Матрица данных {i )} разбивается по индексу k на p подматриц размерностью i=1,k =p nml, = m, каждая из которых отсылается на свою ПВ (узел или процессор, в ml l=зависимости от архитектуры системы).

• На каждой ПВ параллельно производится вычисление треугольной (за счет ml * (k ) симметрии) корреляционной матрицы kij = (k ) (блок «В»).

i j k =• Результаты расчета ( n(n +1) / 2 элементов треугольной матрицы) со всех ПВ передаются на ГПВ, где они суммируются и нормируются на (m -1).

Второй способ основывается на функциональной (functional) декомпозиции, которая, в отличие от декомпозиции по данным, ориентирована на выделение в алгоритме параллельно выполняемых задач. Для вычисления (14) параллельное представление В данном случае рассматриваются центрированные случайные величины сводится к независимому вычислению элементов ковариационной матрицы kij, i, j = 1, n на каждом вычислительном узле (с точки зрения естественной парадигмы это соответствует декомпозиции по индексирующей переменной). Алгоритм формулируется следующим образом (алгоритм «Б»):

n,m (k • Исходная матрица {i )} данных отсылается на свою ПВ, т.е. происходит i=1,k=100(p-1)% дублирование данных.

n • Треугольная матрица K = {kij} разбивается по индексам i, j на p i, j=p неструктурированных групп элементов размерностью ql, = n(n +1) / 2, и на ql l=каждом из p ПВ производится вычисление элементов своей группы – оценок m * (k ) ковариаций kij = (k ) «В».

i j k=• Результаты расчета (по ql значений оценок ковариаций) со всех ПВ передаются на ГПВ, и заполняют исходную ковариационную матрицу K.

Для однородной вычислительной системы с параметрами tc,tw,ts (где последний параметр характеризует время задержки (startup) при передаче данных), количественный анализ производительности параллельных алгоритмов «А» и «Б», выражаемой, приведен в табл. 2.

Таблица Количественный анализ производительности алгоритмов вычисления ковариационной матрицы.

Алгоритм «А» Алгоритм «Б» Операция (по ансамблю) (по индексу) mn (p -1)ts + tw (p -1)[ts + tw mn] Рассылка данных с ГПВ на ПВ p mn(n + 1) mn(n +1) Вычисление значений tc tc ковариации на ПВ 2 p 2 p n(n +1) s t + tw 2 + n(n +1) (p Сбор и обработка данных на ГПВ -1) (p -1)ts + tw 2 p n(n +1) + µ 2 tc Примечание: ГПВ – главная параллельная ветвь, ПВ – параллельная ветвь (в том случае, если число процессов не соответствует числу процессоров).

Здесь параметр µ > 1 учитывает отличия операций при сборе данных на ГПВ, от вычислительных операций на других ПВ. Из табл. 2 видно, что общее время параллельных вычислений значений ковариационной матрицы на p узлах для алгоритмов «А» и «Б» остается одинаково; основные отличия возникают только при рассылке данных на ПВ и обратно. Выражения для параллельного ускорения имеют следующий вид.

Для алгоритма «А» (параллельность по данным):

p S =. (15) p p( p -1) 2 1 tw p( p -1) ts 1 + µ + p( p -1) + + m p(n +1) m tc mn(n + 1) tc Для алгоритма «Б» (параллельность по задачам):

p S =. (16) p 2 1 tw p( p -1) ts 1+ p( p -1) + + (n +1) pm tc mn(n +1) tc На рис. 8 приведены результаты измерений параллельного ускорения при расчетах на 8-процессорном кластере ( 4 2, PIII-500, FastEthernet), а также – аппроксимативные кривые (15,16) с параметрами, восстановленными по исходным данным.

Рис. 8. Ускорение параллельных алгоритмов «А» (1) и «Б» (2) расчета ковариационной матрицы: 3 – зависимости (15,16), 4 – идеальное ускорение.

Значения параметров: (а): m=100, n=2000, (б) m=5000, n=500.

ОСНОВНЫЕ ИДЕИ РАЗДЕЛА Проблема отображения параллельного алгоритма на многопроцессорную вычислительную архитектуру в статической постановке сводится к парному сопоставлению и ранжированию возможных алгоритмов на основе разных естественных принципов для заданных значений характеристик массива данных и характеристик многопроцессорной системы.

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

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

Статическая оптимизация и принцип конкуренции Из рис. 8 видно, что при различных характеристиках исходных данных большую производительность имеет или алгоритм «А», или алгоритм «Б» расчета ковариационной функции. Следовательно, для создания эффективных параллельных программ необходима предварительная оптимизация параллельного алгоритма с целью достижения его наилучшего отображения на соответствующую многопроцессорную архитектуру. В качестве целевой функции для критерия оптимальности алгоритма рассмотрим его параллельное ускорение S( p), представленное в форме (6). Поиск алгоритма с наибольшей производительностью можно интерпретировать как решение задачи оптимального управления многопроцессорной вычислительной системой. Оно сводится к определению способа отображения графа параллельного статистического алгоритма на граф,С, исходя из максимизации параллельного ускорения S( p) при заданном числе вычислительных узлов p. В рамках естественного подхода, рассмотренного в предыдущем разделе, проблема построения оптимального графа параллельного алгоритма сводится к задаче дискретной оптимизации, что соответствует различным комбинациям естественных принципов распараллеливания. Следовательно, взамен сложного аппарата оптимизации на графах, эта проблема может быть легко решена путем попарного сравнения и ранжирования всех алгоритмов по значению S( p) для заданных значений характеристик массива данных и характеристик многопроцессорной системы,C.

Если модель вычислительной системы,C заменяется моделью однородной системы, эквивалентной ей с точки зрения производительности и характеризуемой безразмерной величиной, см. формулы (7,9), то становится возможным получить аналитическое решение задачи поиска оптимального алгоритма. Оно строится путем сопоставления параметрических моделей производительности (6) в форме уравнений изоэффективности параллельных алгоритмов (например, двух - «А» и «Б»):

SA(, p,) = SБ (, p,). (17) При фиксации характеристик вычислительной системы выражение (17) описывает поверхность в пространстве (p, ), которая служит разделом между областями преимущества одного из алгоритмов.

Для различных способов представления параллельного алгоритма мы можем сформулировать принцип конкуренции: при заданных характеристиках исходных данных (размерность, объем и пр.) и значениях ( p,) выполнению подлежит алгоритм с максимальной производительностью S( p).

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

Следует отметить, что такой прием независимо был предложен коллективом авторов под руководством J. J. Dongarra для реализации параллельной библиотеки линейной алгебры [Chen et al., 2003].

Для задачи расчета ковариационной функции, описанной в предыдущем разделе, подстановка (15) и (16) в (17) дает:

2 1 2 1 µ = + +. (18) (n +1) + pm p(n +1) m m В зависимости от сочетания ( p, ) выражение (18) задает семейство кривых на плоскости (n, m). Для определения оптимального соотношения этих величин будем полагать:

m = n. Тогда коэффициент пропорциональности, обеспечивающий изоэффективность:

1 p(1+ -1µ) - =. (19) 2 p -Выражение (19) определяет границы применимости алгоритмов «А» и «Б» в зависимости от числа вычислительных узлов (процессоров) и безразмерного коэффициента = tw / tc. В случае -1 << 1 (tc << tw ) коэффициент 1 2. Это означает, что для слабосвязанной вычислительной системы (например, при реализации распределенных вычислений в GRID) алгоритм «А» распараллеливания по матричным блокам будет эффективнее алгоритма «Б» только при m > n 2. На рис. 8(а,б) приведены примеры оценок ускорения параллельных алгоритмов для различных соотношений параметров (n, m) по результатам расчетов на 8-процессорном кластере ( 4 2, PIII-500, FastEthernet), ( 3.0 ). Из рис. 8 видно экспериментальное подтверждение (19).

Динамическая оптимизация. Балансировка нагрузки Статическая оптимизация на основе принципа конкуренции (17) полностью решает задачу выбора наилучшего алгоритма в том случае, если параметры вычислительной системы в момент их определения путем тестирования, и в момент запуска расчетного приложения одни и те же. Однако на практике возникает, как минимум, три ситуации, в которых это условие не выполняется:

• Эволюционное изменение характеристик вычислительной системы ( p, ) в процессе эксплуатации (характерно для неоднородных многопользовательских вычислительных сетей, например, GRID). В этом случае статическая модель производительности «в среднем» не справедлива, поскольку характерный масштаб изменчивости может быть сопоставим со временем работы приложения.

• Перенос программного обеспечения на большие вычислительные системы MPPархитектуры с прототипов с небольшим количеством вычислительных узлов. В этом случае не учитывается ситуация, когда происходит передача данных между вычислительными узлами через два или более коммуникаторов в MPP-системе, что физически приводит к ее неоднородности. Следовательно, истинные оценки будут смещены относительно значений, полученных по прототипу.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |






















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

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