Geum.ru

Исследование эффективности реализации численных методов на кластерах персональных ЭВМ

Вид материалаИсследование

Содержание


2.1. Эффективность параллельных алгоритмов
Подобный материал:
1   2   3   4   5   6   7   8

2.1. Эффективность параллельных алгоритмов



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

Другим подходом к разработке параллельных программ является использование модели программирования с распараллеливанием данных (data-parallel programming model), когда в последовательный код вставляются директивы компилятору и распараллеливание происходит на автоматическом уровне. Если программа логически простая и обладает ресурсом параллелизма, этот подход может дать хорошие результаты. Однако рекордных результатов удается получить только при использовании знаний программиста о структуре алгоритма и управлении вручную потоком данных. Это достигается при использовании стиля программирования с передачей сообщений (message passing style) [5].

Одной из основных характеристик параллельного алгоритма является ускорение S (Speedup), которое определяется как отношение общего времени прохождения программы для последовательного алгоритма ко времени работы параллельного алгоритма с использованием Р процессоров.

Другой важной характеристикой алгоритма является параллельная эффективность E, которая определяется как отношение ускорения к числу процессоров, то есть E =S / P.

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

Возможные причины потери параллельной эффективности следующие:
  1. стартовое время инициализации параллельной программы (startup),
  2. дисбаланс загрузки процессоров (load imbalance),
  3. коммуникационные затраты (communication costs),
  4. наличие последовательных частей кода (serial part of the code).


Стартовое время инициализации параллельных программ.

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

Сбалансированность загрузки процессоров.

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

Коммуникационные затраты.

Как правило, процессоры вынуждены обмениваться данными в процессе решения задачи. Часто соседние процессоры обмениваются значениями в своих приграничных ячейках. Наиболее распространенными конфигурациями процессоров являются линейное расположение (pipeline) и двумерная решетка (mesh). Предположим, что расчетная область состоит из N2 узлов и задача решается на P=n2 процессорах. Тогда при линейном расположении процессоров объем пересылаемых данных будет пропорционален N (все P=n2 процессоров передают данные одновременно). В случае двумерной решетки объем пересылаемых данных будет пропорционален 2N/n, что почти всегда меньше, чем N. Эта простая оценка показывает, что двумерная решетка процессоров является более выгодной с точки зрения минимизации коммуникационных затрат. В то же время использование трехмерной решетки процессоров является еще более эффективным с точки зрения отношения вычислительных затрат к коммуникационным, хотя и усложняет логику программы и увеличивает объем программирования.

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

Латентность продолжает играть существенную роль при средней длине сообщения (обычно 1000 байтов). В случае решетки процессоров за один цикл процессор выполняет вычислительную работу за время aN2/(n2X) (a – количество арифметических операций, необходимое для расчета одного узла), обмен данными происходит за время 2bN(nY)(-1) (b − количество переменных, которыми происходит обмен). Отношение времени обмена данными к времени вычислений оказывается 2bNX(aNY)(-1).

Минимизация коммуникационных затрат может быть достигнута за счет использования встречных обменов данными и асинхронной передачи данных. Как правило, проблема формулируется так, что процессор посылает данные соседнему и сам принимает от него данные. Аппаратные средства большинства параллельных систем и программные средства MРI допускают использование встречных обменов, когда данные передаются одновременно в обе стороны. Это позволяет добиться почти двойного уменьшения времени обмена данными по сравнению с однонаправленными обменами.

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

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