Разработка высокоэффективных алгоритмов для крупномасштабных задач
Ключевые слова и синонимы
Экспериментальная алгоритмика
Постановка задачи
Под разработкой алгоритмов понимается процесс, в результате которого нарисованная на бумаге блок-схема преобразуется в надежную, эффективную, тщательно протестированную и удобную для использования реализацию. Таким образом, она охватывает ряд тем, от моделирования поведения кэша до принципов проектирования хорошего ПО; однако ее главным направлением является эксперимент. В этом смысле ее можно связать с недавним ростом экспериментальной алгоритмики [ ], посвященной разработке методов, инструментов и практик для оценки и совершенствования алгоритмов посредством экспериментов. Этому направлению посвящен Журнал экспериментальной алгоритмики ACM (ACM Journal of Experimental Algorithmics, JEA), доступный на сайте www.jea.acm.org.
Разработка высокоэффективных алгоритмов [2] ориентирована на один из множества аспектов разработки алгоритмов – скорость работы. Высокая эффективность необязательно подразумевает распараллеливание; на деле в любой задаче с выкосой степенью параллелизма максимум прироста эффективности достигается при совершенствовании последовательной части кода.
Термин «разработка алгоритмов» был впервые использован в этом контексте в 1997 году в процессе организации первого семинара по разработке алгоритмов (Workshop on Algorithm Engineering, WAE 97). С тех пор этот семинар проводится в разных странах Европы ежегодно. Семинар по разработке и экспериментальному выполнению алгоритмов 1998 года (Workshop on Algorithms and Experiments, ALEX98), проходивший в Италии, включал дискуссионный форум для исследователей и специалистов-практиков, интересующихся разработкой, анализом и экспериментальной проверкой точных и эвристических алгоритмов. Родственный семинар начал работу в США в 1999 году: семинар по разработке и экспериментальному выполнению алгоритмов (Workshop on Algorithm Engineering and Experiments, ALENEX99) проводится каждую зиму совместно с симпозиумом ACM/SIAM по дискретным алгоритмам (ACM/SIAM Symposium on Discrete Algorithms, SODA).
Основные результаты
Параллельные вычисления применяются по двум основным причинам, тесно связанным друг с другом. Во-первых, имея больше оперативной и дисковой памяти, чем одиночная рабочая станция, параллельный компьютер может решать более объемные экземпляры той же задачи. Это повышение емкости позволяет выполнять моделирование с высокой точностью, обрабатывать увеличенные массивы информации с помощщью приложений для обработки больших объемов данных, а также отвечать на большее число запросов к корпоративным базам данных. Во-вторых, имея больше процессоров и более крупные агрегированные подсистемы памяти, чем у одиночной рабочей станции, параллельный компьютер зачастую может решать задачи быстрее. Повышение скорости также может обеспечить перечисленные выше преимущества, но его главным достоинством, возможно, является длительность цикла обработки. Именно этот параметр является критичным в ситуациях, когда вычисления являются одним из компонентов практической системы – например, при формировании прогноза погоды, принятии решений об инвестициях либо в системах слежения и наведения. Менее очевидным следствием сокращения длительности цикла обработки является рост качества: если вычислительный эксперимент занимает менее часа, исследователь может позволить себе роскошь углубленного изучения с запуском нескольких разных сценариев для получения более полного представления об изучаемом феномене.
Целью процесса разработки алгоритмов является представление при помощи экспериментов воспроизводимых результатов, применимых к более широкому классу компьютеров, чем конкретная марка компьютерной системы, используемой в ходе эксперимента. Для последовательных вычислений эмпирические результаты нередко оказываются машинно-независимыми. Несмотря на то, что такие характеристики компьютеров, как размер слова, кэш и объем оперативной памяти, а также скорость процессора и шины, различаются, сравнения на различных однопроцессорных машинах демонстрируют одни и те же тенденции. В частности, количество обращений к памяти и операций с процессором оказывается достаточно постоянным (возможно, с поправкой на небольшой константный коэффициент). С другой стороны, приразработке высокоэффективных алгоритмов с параллельными компьютерами подобная переносимость обычно отсутствует: каждый компьютер и каждая среда представляют собой особый случай. Одной из очевидных причин является значительное различие в оборудовании, влияющее на баланс затрат на коммуникации и вычисления: машина с истинной разделяемой памятью демонстрирует поведение, очень сильно отличающееся от поведения кластера, основанного на сетях с массовой обработкой.
Другая причина заключается в том, что библиотеки средств коммуникации и среды параллельного программирования (например, MPI [12], OpenMP [16] и высокопроизводительный Фортран [10]), а также пакеты паралельных алгоритмов (например, быстрые преобразования Фурье с использованием FFTW [6] или распараллеленные процедуры линейной алгебры в ScaLAPACK [ ]) нередко демонстрируют совершенно разную эффективность на различных типах параллельных платформ. Если для одной и той же задачи существует несколько пакетов библиотек, пользователь может наблюдать разное время выполнения различных версий библиотеки – даже на одной и той же платформе. Таким образом, анализ времени выполнения должен четко отделять время, затрачиваемое на пользовательский код, от времени, затрачиваемого на различные вызовы библиотечных функций. И в самом деле, если отдельные вызовы библиотечных функций вносят значительный вклад во время выполнения, то количество таких вызовов и время работы для каждого вызова следует фиксироватьи анализировать, тем самым помогая разработчикам библиотек уделять больше внимания наиболее экономически эффективным улучшениям. Например, в простой программе, выполняющей передачу сообщений, можно охарактеризовать проделанную работу при помощи отслеживания последовательного выполнения, объема коммуникаций и количества переданных сообщений. Программа более общего вида, использующая коллективные коммуникационные процедуры библиотеки MPI, могла бы также подсчитать количество вызовов этих процедур. Для инструментовки кодов MPI с целью сбора таких данных доступно несколько пакетов (например, MPICH nupshot [ ], Pablo [17] и Vampir [15]). Эталонный пакет SKaMPI [18] позволяет прогнозировать время работы на основе подобных измерений даже в случае, если целевая машина недоступна для разработки программы. Пакет SKaMPI был разработан для обеспечения надежности, точности, переносимости и эффективности; в частности, он позволяет адаптивно контролировать частоту выполнения измерений, адаптивно уточнять длину сообщения и ширину шага в интересующих точках, способен восстанавливаться после аварийных остановок и автоматически генерировать отчеты.