Значение "Чисел Фибоначчи" в истории параллельного программирования

28 Дек 2009

Автор: Андрей Карпов

Чи́сла Фибона́ччи - элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, ... в которой каждое последующее число равно сумме двух предыдущих чисел. Числа Фибоначчи мы можем заметить во многих объектах природы, в соотношении пропорций туловища или увидеть реализацию спирали Фибоначчи в раковине моллюска.

С недавнего времени мне не дают покоя эти самые числа Фибоначчи! С какими бы материалами по параллельному программированию я не знакомился, я всюду встречаю эти числа. Возникает ощущение, что все параллельное программирование связано исключительно с проблемой вычислений чисел Фибоначчи.

Вычисление чисел Фибоначчи приводится во множестве печатных и электронных статей. Даже Wikipedia-статья о Parallel computing содержит пример их вычисления.

Какой пример любят приводить разработчики Cilk? Конечно, вычисление чисел Фибоначчи. Числа Фибоначчи в проекте Cilk "Parallelism for the Masses". Числа Фибоначчи в описании Cilkview. Про Фибонначи идет речь в "Cilk Reference Manual". Проще говоря, везде.

Числа Фибоначчи используются для демонстрации средства автоматического динамического распараллеливания "Т-система", разработанного в рамках суперкомпьютерной программы "СКИФ" Союзного государства России и Беларуси.

Этот список можно продолжать и продолжать. Фибомания какая-то. :) Собственно такое частое упоминание Фибоначчи понятно. Простой и наглядный пример, демонстрирующий принципы распараллеливания, но приводимый излишне часто. Есть, конечно, и другие примеры, демонстрирующие распараллеливание алгоритмов. Но все они чаще всего являются решением какой-то математической задачи. Это плохо, и я остановлюсь на этом моменте подробнее.

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

Примеры с числами Фибоначчи, вместо того, чтобы продемонстрировать как легко и эффективно можно распараллелить программу, оставляют у программиста-прикладника ощущение, что к его программам это никакого отношения не имеет. Он мыслит не в математических алгоритмах, а в форме работы с GUI, в терминах "файлы" и "здесь мне нужно очистить массив". Возможно, у него есть потребность в ускорении программного комплекса. Но это никак не связывается с параллельностью, так как он не видит в своем проекте тех алгоритмов для распараллеливания, про которые пишут в статьях и книгах.

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

Одним из этапов развития нашего инструмента PVS-Studio было использование возможностей многоядерной системы. Статический анализ кода больших проектов может занимать часы, и скорость обработки является важной характеристикой таких инструментов.

Мы начали обсуждение, как распараллелить нашу систему и сразу ушли в неверном направлении, совершенно этого не заметив. Причина этому - мышление в рамках информационных ресурсов по параллельности, сосредоточенных на технологиях и методиках распараллеливания различных алгоритмов. Первые мысли были направлены на то, выбрать ли OpenMP или иную технологию, как распараллелить обход синтаксического дерева. И на прочие глупости в этом роде. А решение лежало на поверхности, было элегантным и простым в реализации.

Хорошо, что распараллеливание алгоритмов статического анализа явилось сложной задачей и в ходе размышлений мы поднялись на более высокий уровень абстракции. Нам незачем быстро обрабатывать один файл с исходным кодом. Он обрабатывается и так достаточно быстро. Проблема в обработке множества файлов. Так будем обрабатывать эти файлы параллельно! Просто запустим параллельно несколько анализаторов (создадим несколько процессов) и соберем выдаваемую ими информацию. Не надо OpenMP, не надо думать над синхронизациями, не нужно искать узкие места и проверять эффективность распараллеливания.

Описанное решение было реализовано и отлично работает. Такое решение кажется очевидным? Безусловно. Не буду врать, что нам понадобилось много времени, чтобы прийти к нему. Но в других задачах все может быть не так очевидно. Легко можно увлечься выискиванием неэффективных участков в программе, их распараллеливанием, затем выявлением в них ошибок. Очень легко забыть взглянуть на задачу с более высоких уровней. Рассмотрение примеров типа Фибоначчи как раз способствуют такой забывчивости. Программирование параллельных систем намного более многогранный вопрос. Но осветить эту многогранность часто незаслуженно забывают, сосредотачиваясь на определенной технологии или методике распараллеливания.

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