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

== Применение ==

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

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

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

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

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