Разработка высокоэффективных алгоритмов для крупномасштабных задач: различия между версиями

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

Другая причина заключается в том, что библиотеки средств коммуникации и среды параллельного программирования (например, MPI [12], OpenMP [16] и высокопроизводительный Фортран [10]), а также пакеты паралельных алгоритмов (например, быстрые преобразования Фурье с использованием FFTW [6] или распараллеленные процедуры линейной алгебры в ScaLAPACK [ ]) нередко демонстрируют совершенно разную эффективность на различных типах параллельных платформ. Если для одной и той же задачи существует несколько пакетов библиотек, пользователь может наблюдать разное время выполнения различных версий библиотеки – даже на одной и той же платформе. Таким образом, анализ времени выполнения должен четко отделять время, затрачиваемое на пользовательский код, от времени, затрачиваемого на различные вызовы библиотечных функций. И в самом деле, если отдельные вызовы библиотечных функций вносят значительный вклад во время выполнения, то количество таких вызовов и время работы для каждого вызова следует фиксироватьи анализировать, тем самым помогая разработчикам библиотек уделять больше внимания наиболее экономически эффективным улучшениям. Например, в простой программе, выполняющей передачу сообщений, можно охарактеризовать проделанную работу при помощи отслеживания последовательного выполнения, объема коммуникаций и количества переданных сообщений. Программа более общего вида, использующая коллективные коммуникационные процедуры библиотеки MPI, могла бы также подсчитать количество вызовов этих процедур. Для инструментовки кодов MPI с целью сбора таких данных доступно несколько пакетов (например, MPICH nupshot [ ], Pablo [17] и Vampir [15]). Эталонный пакет SKaMPI [18] позволяет прогнозировать время работы на основе подобных измерений даже в случае, если целевая машина недоступна для разработки программы. Пакет SKaMPI был разработан для обеспечения надежности, точности, переносимости и эффективности; в частности, он позволяет адаптивно контролировать частоту выполнения измерений, адаптивно уточнять длину сообщения и ширину шага в интересующих точках, способен восстанавливаться после аварийных остановок и автоматически генерировать отчеты.