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

Ключевые слова и синонимы

Экспериментальная алгоритмика

Постановка задачи

Под разработкой алгоритмов понимается процесс, в результате которого нарисованная на бумаге блок-схема преобразуется в надежную, эффективную, тщательно протестированную и удобную для использования реализацию. Таким образом, она охватывает ряд тем, от моделирования поведения кэша до принципов проектирования хорошего ПО; однако ее главным направлением является эксперимент. В этом смысле ее можно связать с недавно опубликованной книгой по экспериментальной алгоритмике [14], посвященной разработке методов, инструментов и практик для оценки и совершенствования алгоритмов посредством экспериментов. Этому направлению посвящен Журнал экспериментальной алгоритмики ACM (ACM Journal of Experimental Algorithmics, JEA), доступный на сайте http://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 [4]) нередко демонстрируют совершенно разную эффективность на различных типах параллельных платформ. Если для одной и той же задачи существует несколько пакетов библиотек, пользователь может наблюдать разное время выполнения различных версий библиотеки – даже на одной и той же платформе. Таким образом, анализ времени выполнения должен четко отделять время, затрачиваемое на пользовательский код, от времени, затрачиваемого на вызовы библиотечных функций. И в самом деле, если отдельные вызовы библиотечных функций вносят значительный вклад во время выполнения, то количество таких вызовов и время выполнения каждого вызова следует фиксировать и анализировать, тем самым помогая разработчикам библиотек уделять больше внимания наиболее экономически эффективным улучшениям. Например, в простой программе для передачи сообщений можно охарактеризовать проделанную работу при помощи отслеживания последовательного выполнения, объема коммуникаций и количества переданных сообщений. Программа более общего вида, использующая коллективные коммуникационные процедуры библиотеки MPI, могла бы также подсчитать количество вызовов этих процедур. Для инструментовки кодов MPI с целью сбора таких данных доступно несколько пакетов (например, MPICH nupshot [8], Pablo [17] и Vampir [15]). Эталонный пакет SKaMPI [18] позволяет прогнозировать время работы на основе подобных измерений даже в случае, если целевая машина недоступна для разработки программы. Пакет SKaMPI был разработан для обеспечения надежности, точности, переносимости и эффективности; в частности, он позволяет адаптивно контролировать частоту выполнения измерений, адаптивно уточнять длину сообщения и ширину шага в интересующих точках, а также способен восстанавливаться после аварийных остановок и автоматически генерировать отчеты.

Применение

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

1. Ранние публикации Бадера (см. [2] и http://www.cc.gatech.edu/~bader) включают различные эмпирические исследования параллельных алгоритмов для таких комбинаторных задач, как сортировка, выбор, алгоритмы на графах и обработка изображений.

2. В процессе демонстрации возможностей технологий разработки высокоэффективных алгоритмов ускорение в миллион раз было достигнуто при помощи сочетания ускорения последовательного выполнения кода в 2 тысячи раз и ускорения в 512 раз благодаря распараллеливанию (притом вторая составляющая ускорения может быть масштабирована на любое число процессоров) [13]. (При последующей демонстрации процесса разработки алгоритма внесенные в стратегии поиска и ограничений улучшения позволили ускорить выполнение последовательной части кода еще в 1000 раз, а общее ускорение в результате превысило 2 миллиарда раз).

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

4. В работе [3] Блеллок и др. при помощи анализа и реализации сравнивают три алгоритма сортировки на компьютерах Thinking Machines CM-2. Несмотря на использование устаревшей (и в настоящее время уже недоступной) платформы, эта статья превосходна сама по себе и должна быть настольным документом каждого разработчика параллельных алгоритмов. В одном из первых исследований подобного рода авторы оценивают время выполнения четырех машинных примитивов, а затем анализируют этапы трех алгоритмов сортировки в терминах указанных параметров. Экспериментальные измерения эффективности нормализованы для получения четкого сравнения масштабируемости алгоритмов по мере роста размера входных данных на компьютере CM-2 с 32 тысячами процессоров.

5. Виттер и коллеги предоставили каноническую теоретическую базу для экспериментальных алгоритмов с большим объемом операций ввода-вывода, использующих внешние параллельные диски (см., например, [1, 19, 20]). Для демонстрации работы модели с параллельными дисками использовались такие примеры, как сортировка, быстрое преобразование Фурье, перестановка и транспонирование матриц.

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

7. Модель LogP, разработанная Каллером и коллегами [5], оказывается вполне практичной для разработки параллельных алгоритмов для платформ пересылки сообщений. Продемонстрировано ее применение для ряда задач, включая сортировку.

8. Несколько групп исследователей выполнили обширную разработку алгоритмов для высокопроизводительных численных вычислений. Один из самых перспективных проектов был выполнен под руководством Донгарры для ScaLAPACK [4] – масштабируемой библиотеки для решения задач линейной алгебры на параллельных компьютерах. ScaLAPACK инкапсулирует значительную часть процесса разработки высокопроизводительных алгоритмов, что имеет важное значение для пользователей, которым требуются эффективные параллельные версии процедур линейной алгебры для обработки матриц. Новые подходы к автоматической настройке последовательных библиотек (например, LAPACK) теперь доступны в виде пакета ATLAS [21].

Открытые вопросы

Все инструменты и техники разработки алгоритмов, созданные в последние годы, применимы к разработке высокоэффективных алгоритмов. Однако многие из этих инструментов требуют дальнейшей доработки. К примеру, техники программирования, обеспечивающие высокую эффективность использования кэша, являются ключом к высокой производительности, однако конкретные пути реализации пока не вполне ясны – главным образом из-за сложных машинно-зависимых проблем, таких как ограниченная ассоциативность, преобразование виртуальных адресов и все более многоуровневые иерархии высокопроизводительных компьютеров. Основной вопрос заключается в том, можно ли найти простые модели в качестве основы для разработки алгоритмов. К примеру, в теории алгоритмы без явного задания параметров кэша [7] эффективны на всех уровнях иерархии памяти, но на практике лишь немногие из них работают хорошо. Или, скажем, профилирование уже выполняемой программы представляет серьезную проблему в последовательной среде (любой инструмент профилирования меняет поведение наблюдаемого процесса), однако эти проблемы меркнут в сравнении с аналогичными проблемами, возникающими в параллельной или распределенной среде (к примеру, измерение аппаратных ограничений пропускной способности может потребовать обратной связи от сетевых переключателей или по меньшей мере их перепрограммирования, что, безусловно, изменит их поведение). Разработка эффективных и переносимых алгоритмов для серийно выпускаемых многоядерных и многократноядерных процессоров представляет собой нерешенную проблему.

См. также

• Анализ неудачных обращений к кэшу
• B-деревья без явного задания параметров кэша
• Модель без явного задания параметров кэша
• Сортировка без явного задания параметров кэша
• Разработка алгоритмов для вычислительной биологии
• Разработка алгоритмов для применения в больших сетях
• Разработка геометрических алгоритмов
• Экспериментальные методы анализа алгоритмов
• Внешние сортировка и перестановка
• Конкурс по реализации алгоритмов поиска кратчайших путей
• Конкурс по реализации эвристик для задачи коммивояжера
• Модель ввода-вывода
• Техники визуализации при разработке алгоритмов

Литература

1. Aggarwal, A., Vitter, J.: The input/output complexity of sorting and related problems. Commun.ACM 31,1116-1127 (1988)

2. Bader, D.A., Moret, B.M.E., Sanders, P.: Algorithm engineering for parallel computation. In: Fleischer, R., Meineche-Schmidt, E., Moret, B.M.E. (ed) Experimental Algorithmics. Lecture Notes in Computer Science, vol. 2547, pp. 1-23. Springer, Berlin (2002)

3. Blelloch, G.E., Leiserson, C.E., Maggs, B.M., Plaxton, C.G., Smith, S.J., Zagha, M.: An experimental analysis of parallel sorting algorithms. Theor. Comput. Syst. 31 (2), 135-167 (1998)

4. Choi, J., Dongarra, J.J., Pozo, R., Walker, D.W.: ScaLAPACK: A scalable linear algebra library for distributed memory concurrent computers. In: The 4th Symp. the Frontiers of Massively Parallel Computations, pp. 120-127, McLean, VA (1992)

5. Culler, D.E., Karp, R.M., Patterson, D.A., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., von Eicken,T.: LogP: Towards a realistic model of parallel computation. In: 4th Symp. Principles and Practice of Parallel Programming, pp. 1-12. ACM SIGPLAN (1993)

6. Frigo, M., Johnson, S. G.: FFTW: An adaptive software architecture for the FFT. In: Proc. IEEE Int'l Conf. Acoustics, Speech, and Signal Processing, vol. 3, pp. 1381-1384, Seattle, WA (1998)

7. Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. 40th Ann. Symp. Foundations of Computer Science (FOCS-99), pp. 285-297, New York, NY, 1999. IEEE Press

8. Gropp, W., Lusk, E., Doss, N., Skjellum, A.: A high-performance, portable implementation of the MPI message passing interface standard. Technical report, Argonne National Laboratory, Argonne, IL, (1996) http://www.mcs.anl.gov/mpi/mpich/

9. Helman, D.R., JaJa, J.: Sorting on clusters of SMP's. In: Proc. 12th Int'l Parallel Processing Symp., pp. 1-7, Orlando, FL, March/April 1998

10. High Performance Fortran Forum. High Performance Fortran Language Specification, 1.0 edition, May 1993

11. Juurlink, B.H.H., Wijshoff, H.A.G.: A quantitative comparison of parallel computation models. ACM Trans. Comput. Syst. 13(3), 271-318(1998)

12. Message Passing Interface Forum. MPI: A message-passing interface standard. Technical report, University of Tennessee, Knoxville, TN, June 1995. Version 1.1

13. Moret, B.M.E., Bader, D.A., Warnow, T.: High-performance algorithm engineering for computational phylogenetics. J. Supercomput. 22, 99-111 (2002) Special issue on the best papers from ICCS'01

14. Moret, B.M.E., Shapiro, H.D.: Algorithms and experiments: The new (and old) methodology. J. Univers. Comput. Sci. 7(5), 434^46(2001)

15. Nagel, W.E., Arnold, A., Weber, M., Hoppe, H.C., Solchenbach, K.: VAMPIR: visualization and analysis of MPI resources. Supercomputer 63. 12(1),69-80 (1996)

16. OpenMP Architecture Review Board. OpenMP: A proposed industry standard API for shared memory programming. http://www.openmp.org, October 1997

17. Reed, D.A., Aydt, R.A., Noe, R.J., Roth, P.C., Shields, K.A., Schwartz, B., Tavera, L.F.: Scalable performance analysis: The Pablo performance analysis environment. In: Skjellum, A., (ed) Proc. Scalable Parallel Libraries Conf., pp. 104-113, Mississippi State University, October 1993. IEEE Computer Society Press

18. Reussner, R., Sanders, P., Traff, J.: SKaMPI: A comprehensive benchmark for public benchmarking of MPI. Scientific Programming, 2001. accepted, conference version with Prechelt, L, MCiller, M. In: Proc. EuroPVM/MPI (1998)

19. Vitter, J. S., Shriver, E.A.M.: Algorithms for parallel memory. I: Two-level memories. Algorithmica. 12(2/3), 110-147 (1994)

20. Vitter, J. S., Shriver, E.A.M.: Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica 12(2/3), 148-169(1994)

21. Whaley, R., Dongarra, J.: Automatically tuned linear algebra software (ATLAS). In: Proc. Supercomputing 98, Orlando, FL, November 1998. http://www.netlib.org/utk/people/JackDongarra/PAPERS/atlas-sc98.ps