WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 3 | 4 || 6 |

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

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

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

Традиционно проблема балансировки вычислительной нагрузки характерна для сложных вычислительных задач, в которых характеристики массива данных на разных узлах могут меняться в процессе вычислений [Hendrickson & Devine, 2000]. Для задач статистических измерений, связанных с пересылками больших объемов данных, на первое место выходит коммуникационный дисбаланс. Причина его возникновения в том, что из-за различий между тестовыми и истинными значениями вычислительные узлы заканчивают работу не одновременно и простаивают, ожидая завершения последнего параллельного процесса.

На рис. 9 приведена диаграмма общего времени загрузки процессоров 8процессорноого кластера ( 4 2, PIII-500, FastEthernet) на примере задачи статистического оценивания ковариационной матрицы (n=20) по выборке m=2105 элементов. Даже при p=8 процессоров практический дисбаланс для теоретически сбалансированного алгоритма может составлять более 10%. Для неоднородной системы ситуация еще более усугубляется. На рис. 9 также приведено время загрузки процессоров для неоднородной системы (моделируемой вмешательством пользователя с равным приоритетом на одном из узлов). Видно, что дисбаланс достигает 35-40%.

Рис. 10. Зависимость эффективности E Рис. 9. Время загрузки процессоров для параллельного алгоритма от числа параллельного алгоритма статистического разбиений m в процедуре динамической оценивания корреляционной матрицы.

балансировки нагрузки.

(1) – однородная система; (2) – неоднородная система Рассмотрим некоторые технологии динамической балансировки нагрузки, которые позволяют оптимизировать ускорение для ряда типовых алгоритмов обработки и моделирования информации, в частности, статистического оценивания случайных величин и функций, а также – стохастического воспроизведения ансамблей реализаций случайных величин, временных рядов и случайных полей методом Монте-Карло. Для неоднородных вычислительных сред, а так же в случае частичной загрузки одного или нескольких вычислительных узлов однородной вычислительной среды фоновым (например, системным) приложением, можно предложить алгоритм разделения исходных данных или участков моделирования на блоки, внутри которых динамически вводится дробная неравномерность, соответствующая частоте k = L-1 моделирования или k обработки данных вычислительным узлом. В случае изменения загрузочной конъюнктуры, очередной блок должен динамически скорректировать перераспределение данных между узлами, что должно привести к оптимизации загрузки всех вычислительных узлов суперкомпьютера и, как следствие, к уменьшению суммарного времени вычислений.

В простейшем случае, для декомпозиции по ансамблю, каждому блоку ставится в соответствие оптимальный план загрузки процессоров, которые характеризуются p набором коэффициентов qk, = 1, определяющих долю выборочных данных, qk k =обрабатываемых на каждом процессоре. На каждом шаге m вычислительной процедуры k -* (k ) производится уточнение коэффициентов qk =, где k = (Lk + Tcomm) – полное p 1 + K + время загрузки каждого процессора на предыдущем шаге (включая время передачи данных на узел). Следует отметить, что такая технология является достаточно эффективной. Например, для однородной вычислительной системы с большим количеством процессоров, свободной от других приложений, теоретически она уже при m=2 позволяет достичь существенного увеличения производительности за счёт уменьшения коммуникационного дисбаланса. Для систем, загрузка процессоров которых меняется во времени, устойчивых оценок коэффициентов q* получить, по-видимому, не k удается. В качестве альтернативы можно предложить более простой, но не менее эффективный алгоритм балансировки нагрузки на основе “банка задач”. Основная идея этого алгоритма состоит в том, что декомпозиция исходных данных производится на равные блоки (“банк задач”), число которых в несколько раз превышает число процессоров, при этом вычислительные узлы конкурируют между собой, стремясь обработать как можно большее число таких блоков. Подобный подход к балансировке нагрузки весьма близок к традиционному подходу “клиент-сервер” для бизнес– приложений.

Производительность алгоритма балансировки существенно зависит от числа разбиений m.

На рис. 10 приведены зависимости эффективности параллельного алгоритма E = S / p от m для задачи оценивания корреляционной p матрицы многомерной случайной величины (см. рис. 9), по вычислениям, проводимым на 4 и 8 процессорах 8-процессорноого кластера ( 4 2, PIII500, FastEthernet).

Из рис. видно, что уже при m=816 эффективность (а, следовательно, ускорение) становится максимальным (причем процедура балансировки позволила увеличить ускорение более чем на 24% для p=8, и около 30% – для p=4 при исходном дисбалансе порядка 45%, что является результатом, близким к оптимальному). При этом видно, что при значительном увеличении m происходит падение производительности. Это, повидимому, связано с уменьшением зернистости отдельных вычислительных блоков за счет накладных расходов (латентности) на организацию пересылок данных.

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

1. Измеряются параметры вычислительной системы,C путем тестирования всех доступных узлов, и вычисляется параметр, единый для заданного набора алгоритмов «А», «B», «C» и пр. Эти алгоритмы выполняют одну и ту же процедуру статистических измерений (расчет моментов, квантилей, спектральных характеристик и пр.), но используют разные способы декомпозиции.

2. Выполняется статическая оптимизация: выбирается наиболее производительный параллельный алгоритм, используя уравнение изоэффективности (17).

3. Определяется план загрузки процессоров, исходя из сбалансированности времени их работы (если система неоднородна), и производится рассылка данных, в соответствии с принятым алгоритмом.

4. Параллельно выполняется обработка данных на каждом вычислительном узле, в соответствии с принятым алгоритмом.

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

6. С учетом текущего значения по уравнению изоэффективности (17) выносится решение о необходимости замены параллельного алгоритма для обработки следующего фрагмента данных.

7. Переход к пункту 4.

Рис. 11. Общая схема оптимизации параллельных вычислений в задаче статистической обработки данных Адаптация параллельного математического обеспечения под особенности программно-аппаратных комплексов Основное требование к производительности параллельного МО (см. раздел 1) может быть сформулировано в форме тройки (,,C,T), где характеризует объем обрабатываемых данных, T - время, за которое выполняется обработка с целью выполнения измерений, а,C задает архитектуру вычислительной системы в составе информационно-измерительного комплекса. Учитывая, что при фиксированном уровне методической погрешности величины T, связаны функционально, задача адаптации параллельного МО для условий эксплуатации в составе конкретной информационноизмерительной системы может формулироваться двояко:

• Настройка параллельного МО, обеспечивающего выполнение статистических * измерений за время T ~ f (,,C ) на конкретной вычислительной системе в составе измерительного комплекса (далее – задача «А»).

• Выбор архитектуры вычислительной системы,C ~ g(T, ), необходимой для выполнения статистических измерений по данным заданного объема за * ограниченное время T (далее – задача «Б»).

На рис. 12 приведена схема принятия решений, которая отражает последовательность действий для настройки параллельного МО под требования конкретного информационно-измерительного комплекса. В зависимости от постановки задачи адаптации, неизменными остаются только теоретические основы (Т.1-Т.3), а некоторые другие элементы схемы имеют разное содержание и могут опускаться.

Например, в задаче «А» ключевой элемент P.3 состоит в выборе самого простого (и потому дешевого с точки зрения программной реализации алгоритма), выполняемого за * время, меньшее T, сразу на всех p узлах системы. Это условие основывается на экономических соображениях – в системе не должно быть узлов, работающих * «вхолостую», даже если и без них алгоритм выполняется за время, меньшее T.

Единственным ограничением на число используемых узлов p* является достижение максимума параллельной производительности (элемент Р.2), так как при p > p* общее время выполнения параллельного приложения будет снижаться. В рамках задачи «Б» (подбор архитектуры под конкретную задачу статистических измерений) данный вопрос вообще не встает, поскольку заранее принимается p = p* для заданного алгоритма. Однако в этом случае неоднозначную интерпретацию имеет элемент P.1. Если для задачи «А» оценки времени выполнения базовых операций можно получить экспериментальным путем (непосредственным тестированием имеющейся вычислительной системы), то для «Б», когда такая система еще только выбирается, следует использовать данные прототипов (например, двухузловых макетов для вычислительных систем, имеющих в составе только один коммутатор). Кроме того, учитывая, что эти данные нужны не для точной количественной оценки производительности, а лишь для ее сопоставления в рамках P.3, допустимо использовать оценки времени выполнения базовых операций на системах похожей архитектуры, пусть даже совершенно разной производительности.

Если на этапе Р.3 был найден алгоритм, удовлетворяющий всем условиям * (T T, p p* ), то выполняется его программная реализация (например, с использованием готовых библиотек), применяя те же инструментальные средства, что и для средств тестирования в Р.1. Если же все алгоритмы, сопоставляемые в рамках Р.3, * выполняются за время T > T, то программной реализации подлежит алгоритм с наибольшей производительностью. Несмотря на то, что формальные требования по * предельному времени T не выполнены, имеется ряд возможностей их удовлетворить: за счет резервов самого алгоритма (У), за счет модификации системного ПО (П) и за счет модификации аппаратного уровня (А).

Элемент У.1 предполагает дополнительную разработку системы динамической балансировки вычислительной нагрузки; она позволяет не только повысить производительность, но даже привести к изменению p*. Однако такая разработка может быть более дорогостоящей, чем сам программная реализация самого алгоритма.

Сущность мероприятий П.1-П.2 состоит в том, что определение характеристик многопроцессорной архитектуры в рамках (6), как базовых статистических операций, отражает особенности не только аппаратной части, но и управляющего ей системного ПО. Именно потому в ряде случаев конфигурирование ПО под конкретную вычислительную задачу (например, выбор оптимальной комбинации директив компилятора), или даже инсталляция нового ПО системного уровня позволяют изменить * характеристики,C системы таким образом, чтобы условие T T, p p* в P.удовлетворялось хотя бы для одного из конкурирующих алгоритмов.

Мероприятия А.1-А.2 более очевидны – они состоят в увеличении количества вычислительных узлов при p < p* и увеличении их собственной производительности. В рамках задачи «Б» мероприятия группы А играют ключевую роль, однако их возможности ограничиваются как доступным на сегодняшний день ассортиментом элементной базы, так и экономическими соображениями. Зная характеристики функциональных устройств, можно приближенно оценить изменения параметров вычислительной системы еще до повторного проведения Р.1, и тем самым обосновать целесообразность такого шага.

Начало Теоретические основы Т.1. Конструирование параллельных методов выполнения статистических измерений Т.2. Параллельная декомпозиция, связывание и агломерация алгоритмов на основе естественных способов распараллеливания Т.3. Разработка теоретических моделей параллельной производительности алгоритмов в рамках представления (6) Принятие решения Р.1. Определение времени выполнения базовых статистических операций (общих для всех параллельных алгоритмов) Р.2. Определение количества вычислительных узлов, дающего наибольшее параллельное ускорение для каждого из алгоритмов Р.3. Выбор параллельного алгоритма, оптимального с точки зрения параллельной производительности, стоимости реализации и загрузки узлов вычислительной системы Увеличение производительности за счет резервов алгоритма У.1. Анализ динамического распределения нагрузки в системе.

Разработка и включение в алгоритм процедуры балансировки нагрузки Модификации программного уровня Модификации аппаратного уровня П.1. Конфигурирование системного А.1. Добавление в систему новых ПО под вычислительную задачу. вычислительных узлов П.2. Инсталляция нового, более А.2. Замена элементной базы эффективного системного ПО. (вычислительных узлов и (или) коммуникационной сети) П.3. Инсталляция нового системного А.3. Использование вычислительной ПО, поддерживающего другую системы другой архитектуры архитектуру управления системой.

Рис. 12. Схема принятия решений для адаптации параллельного МО для эксплуатации в составе конкретного информационно-измерительного комплекса.

Отдельно следует рассматривать мероприятия А.3 и П.3, которые сводятся к смене самой архитектуры вычислительной системы – или программно, или аппаратно. Следует отметить, что для них, в отличие от А.1-А.2, нельзя apriori оценить степень целесообразности. Вместе с тем, большие, по сравнению с другими мероприятиями, затраты на реализацию заставляют рассматривать их как исключительный шаг.

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

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

Pages:     | 1 |   ...   | 3 | 4 || 6 |






















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

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