Аннотация:
В модели параллельных вычислений LogP построено аналитическое выражение времени выполнения алгоритма $k$ параллельных цепочек для реализации корневой редукции на распределенных вычислительных системах (ВС). По построенной функциональной зависимости найдено оптимальное значение числа $k$ параллельных цепочек, при котором алгоритм характеризуется минимальным в модели LogP временем выполнения. На основе этого создан алгоритм с оптимальным числом параллельных цепочек. Для сокращения времени ожидания корневым процессом результатов частичных редукций разработан алгоритм с адаптивным числом параллельных цепочек. Зависимость времени выполнения созданных алгоритмов от числа процессов имеет порядок роста $O(\sqrt{P})$, что эффективнее по сравнению с линейным $\Omega(P)$ временем выполнения исходного алгоритма. Алгоритмы реализованы в стандарте MPI и исследованы на вычислительных кластерах с сетями связи стандарта InfiniBand QDR.
Ключевые слова:
корневая редукция, модель передачи сообщений, параллельное программирование, распределенные вычислительные системы.
Полный текст:
PDF файл (329 kB)