О проекте

Вл.В.Воеводин

AlgoWiki - это открытая энциклопедия в сети Интернет по свойствам алгоритмов и особенностям их реализации на различных программно-аппаратных платформах с возможностью коллективной работы всего мирового вычислительного сообщества.

---

Компьютеры быстро меняются. За последние сорок лет сменилось, по крайней мере, шесть поколений архитектур, вызвавших необходимость кардинальных изменений в программном обеспечении. Векторные компьютеры, векторно-параллельные, массивно-параллельные, компьютеры с общей памятью, кластеры из машин с общей памятью, компьютеры с ускорителями... Вычислительное сообщество через это прошло, но каждый раз все программное обеспечение нужно было, по сути, переписывать заново: очередное поколение машин требовало выделения новых свойств в алгоритмах, что отражалось и в программах.

Увы, но нет никаких оснований надеяться, что ситуация в будущем изменится к лучшему. Уже сейчас рассматриваются перспективные варианты архитектур, где будут использованы легкие и/или тяжелые вычислительные ядра, ускорители разного типа, идеи SIMD и data-flow обработки. В такой ситуации, для полного использования потенциала будущих компьютеров нужно будет опять переписывать код. Бесконечный процесс, который оптимизма у разработчиков программного обеспечения не вызывает.

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

В такой ситуации для нас важны два факта: сами алгоритмы меняются мало, и их свойства никак не зависят от вычислительных систем. Это значит, что описав свойства алгоритмов один раз, этими сведениями можно будет пользоваться многократно для любых компьютерных платформ, существующих сейчас или будущих. Каждый раз, когда будет возникать задача эффективной реализации алгоритма на некотором компьютере, ответ на вопрос о потенциальных возможностях самого алгоритма можно будет найти в этом описании.

Идея глубокого априорного анализа свойств алгоритмов и их реализаций легла в основу проекта AlgoWiki, начатого в НИВЦ МГУ. Основная задача проекта – составить такое описание фундаментальных свойств алгоритмов, которое даст полное понимание как их теоретического потенциала, так и особенностей их реализации на различных классах параллельных вычислительных систем. Описание всех алгоритмов в AlgoWiki строится из двух частей. В первой части описываются собственно алгоритмы и их свойства. Вторая часть посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на две части сделано для того, чтобы машинно-независимые свойства алгоритмов, определяющие их потенциал и качество реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.

Цель AlgoWiki - дать исчерпывающее описание алгоритма, которое поможет оценить его потенциал применительно к конкретной параллельной вычислительной платформе. Кроме классических свойств алгоритмов, например, последовательной сложности, в AlgoWiki должен быть представлен и целый набор дополнительных сведений, составляющих в совокупности полную картину об алгоритме: параллельная сложность, параллельная структура, детерминированность, оценки локальности данных, эффективности и масштабируемости, коммуникационный профиль конкретных реализаций и многие другие.

В AlgoWiki очень важны детали. Классические базовые алгоритмы должны быть дополнены важными на практике модификациями. В некоторых случаях для описания модификаций достаточно одного небольшого комментария со ссылкой на базовый вариант алгоритма, поясняющего идею его модификации и получаемый эффект. Иногда же изменения алгоритма значительны и требуют полноценного самостоятельного описания. Так в AlgoWiki есть описание базового точечного вещественного варианта разложения Холецкого для плотной симметричной положительно-определенной матрицы. Но на практике не менее важны модификации алгоритма: блочный вариант, вариант для плотной комплексно-симметричной матрицы (как точечный, так и блочный), варианты алгоритма для разреженных матриц, важны соображения относительно использования разложения Холецкого в итерационных методах и т.д.

Точно также важны и детали, касающиеся особенностей реализации алгоритмов на конкретных параллельных вычислительных платформах: многоядерных процессорах, SMP, кластерах, разного рода ускорителях, с использованием векторной обработки. Во многих случаях нужно спускаться еще на уровень ниже, описывая особенности реализации алгоритма не просто для ускорителя, а выделяя отдельно важные частные случаи, например, GPU и Xeon Phi. Полезными являются и данные вычислительных экспериментов на похожих платформах, различающихся, например, разными объемами кэш-памяти, деталями реализации векторной обработки или латентностью коммуникационной сети. При этом, приводя данные о времени выполнения, эффективности и масштабируемости, мы не только даем некоторые ориентиры возможного качества реализации алгоритма на конкретном компьютере, но и формируем базу для сравнительного анализа различных компьютерных платформ на алгоритмах, представленных в AlgoWiki.

Результатом проекта AlgoWiki является открытая энциклопедия по свойствам алгоритмов и особенностям их реализации на различных компьютерах. В реализации сразу была сделана ориентация на использование wiki-технологий с возможностью коллективной работы над энциклопедией всего вычислительного сообщества. На первом этапе проекта основное внимание уделялось отработке именно структуры описания алгоритмов. В настоящее время энциклопедия активно расширяется за счет описаний алгоритмов, составленных внешними экспертами, а также создается многоязычная версия, которая затем и станет основной.

Работа поддержана грантом Российского научного фонда (проект N14-11-00190).