Современная «параллельная суета» служит благодатной почвой для разнообразных сказок. Очень уж хочется, чтобы кто-то произнес: «Крибле-крабле-бумс» – и обычная программа вдруг стала бы параллельной! И, ведь, действительно — многоядерные системы, реализующие аппаратно параллелизм, могут ускорить то, что до этого реализовывалось программно. Однако неясно, что ускорить и насколько?
Существующие решения морально устарели, а потому их по-хорошему нужно не реанимировать, а создавать заново. Кардинальных изменений многопоточное программирование, как виртуальный параллелизм, многоядерность и параллелизм реальный, в себе не несут— все они не изменяют существующую модель параллельных вычислений. Все это давние, хорошо известные структурные решения— программные, аппаратные, смешанные, но никак не формальные алгоритмические модели. В этом и корень многих существующих проблем параллельного программирования.
Параллельное программирование нуждается не в единицах процессов и ядер, не в десятках или в лучшем случае сотнях, как обещают в перспективе, а в тысячах и миллионах. Однако, чтобы эффективно управлять таким числом процессов, нужны новые технологии и новые алгоритмические модели. Именно эти цели поставлены в программе DARPA HPCS, объявившей о необходимости создания систем нового поколения, которые, в частности, должны обладать в десять раз более простой системой программирования, чем современные системы и технологии разработки параллельных программ. Однако как посчитать эту «простоту»?
Одного желания мало— вспомним итоги японского проекта по созданию ЭВМ пятого поколения. Не выручит ни мощь процессоров, ни объем и скорость памяти и т.п. Необходимы идеи, нужна питательная почва, на которой могло бы дать всходы нечто, меняющее наше представление о программировании. Рассмотрим «зерна», которые хотелось бы бросить в почву будущих высокопроизводительных систем. Если они не дадут «всходов», то вряд ли имеет смысл говорить о каком-то прогрессе в американской федеральной программе DARPA HPCS, в аналогичных отечественных программах, или в корпоративных инициативах наподобие Intel Advanced Computing Program.
Среди подходов к реализации параллелизма можно выделить три: ручной, автоматический и модельный. При «ручном проектировании» программист берет на себя всю ответственность за структуру и качество параллельного решения. Используя ту или иную библиотеку (MPI, ОреnMP и т.п.) он создает параллельную программу, самостоятельно формируя ее структуру, связи, синхронизацию и т.д. В результате с большой вероятностью можно попасть в ситуацию полной неразберихи. При автоматическом распараллеливании написанная в обычном стиле программа преобразуется в параллельную без участия программиста. Разумеется, за качество распараллеливания отвечает система или среда программирования. Модельный подход отличается тем, что в нем есть та или иная формальная основа— универсальная алгоритмическая модель параллельных вычислений (в первом ее, как правило, нет, во втором она скрыта).
Хочется, однако, успокоить «ручников»— мечта об автоматическом распараллеливании останется таковою до той поры, пока интеллект средств разработки не станет превосходить интеллект программиста. Пока же автоматические решения еще уступают решениям, созданным программистом. Приведем примеры, которые могут подкрепить это утверждение.
Суммирование массива чисел. Простейшее решение сводится к последовательному циклическому суммированию элементов массива, где количество итераций соответствует числу элементов в массиве. Но известно параллельное решение данной задачи— алгоритм сдваивания, когда массив на каждом шаге итерации разбивается на пары, которые параллельно суммируются. Процесс заканчивается, когда остается единственное число— результат. Количество итераций (дискретных шагов алгоритма) здесь меньше или равно log2(N). Но можно ли автоматически из алгоритма циклического суммирования породить алгоритм сдваивания? Это первый «камешек» в огород автоматического распараллеливания.
И проблема не только в автоматическом порождении алгоритма сдваивания. Проблема с его реализацией в рамках существующих систем. Если запрограммировать цикл, вычисляющий последовательно сумму массива, то проблем нет, но в случае алгоритма сдваивания существует проблема выделения нужного числа процессов. Сам по себе алгоритм элементарен, но для массива из 50 млн. чисел на первом шаге параллельной итерации потребуется 25 млн. процессов, а, ведь нужно еще учесть, что они создаются и уничтожаются динамически! А, к примеру, современный суперкомпьютер Cray Red Storm имеет с точки зрения алгоритма сдваивания всего 26 тыс. процессорных ядер при потреблении 2,2 МВт и стоимости порядка 77,5 млн. долл. Мало кто может позволить себе такой «процессор», который к тому же имеет ограничения на реализацию элементарного, но параллельного алгоритма?
Параллельное суммирование обойдется очень дорого, поэтому многие программируют по старинке, последовательно. Продвинутые— последовательно-параллельно, создавая алгоритм под имеющееся число ядер. Правда, это уже не алгоритм сдваивания, а иной алгоритм. И на вычисление будет затрачено большее число дискретных шагов. Справедливости ради заметим, что это не означает, что реальное время работы будет больше— все определяется реальной длительностью самого дискретного шага. Но таково уж нынешнее параллельное программирование, в котором теория и практика существуют сами по себе— параллельно.
Параллельная рекурсия. Пусть необходимо вычисление n-го числа ряда Фибоначчи. Последовательный алгоритм прост— цикл от меньшего числа к заданному. Имеется даже аналитическое решение, сводящее вычисление к одному шагу— по формуле. Но есть и рекурсивный алгоритм. Он привлекателен тем, что легко распараллеливается. Его «прелесть» еще и в том, что уже для малого значения n рекурсивные вызовы порождают огромное число параллельных процессов. И тут еще одна проблема— если для алгоритма сдваивания число процессов известно, то для параллельной рекурсии предсказать их число невозможно (так, в районе 17–20 ряд настольных операционных систем начинает «загибаться»). Но есть и еще проблема— медлительность потоков. Когда ядер не хватает, то они, пожалуй, становятся единственным средством «официального параллелизма», который используется программистом. Польза от такого рекурсивного параллелизма решения пока, пожалуй, одна— тестирование возможностей параллельной системы.
Алгоритм быстрой сортировки. Листинг модуля быстрой сортировки, который легко поддается параллелизму, таков:
void QuickSort(int p, int r){
if (p < r {
int q = Partition(p, r);
QuickSort (p, q-1);
QuickSort (q+1, r); } }
Структура алгоритма удивительным образом напоминает структуру алгоритма вычисления чисел Фибоначчи. И здесь параллелизм сводится к параллельному запуску рекурсивных вызовов. Но, в отличие от задачи Фибоначчи, быстрой сортировке необходимо гораздо меньше процессов в пределах одного дискретного такта работы алгоритма. Для массива случайных чисел со значением n=10 тыс. это примерно 400 процессов, и применение рекурсивного параллелизма вполне оправданно. (Но догадаетесь ли вы об этом, просто сравнивая алгоритмы быстрой сортировки и вычисления чисел Фибоначчи?)
Тестирование показало: если на обычную сортировку уходит 3549549 дискретных тактов, но на эквивалентную параллельную— 567243. Если мы рассмотрим еще один вариант параллельной сортировки— часто приводимый в курсах по параллельному программированию алгоритм четно-нечетной сортировки, то ему понадобится число тактов, примерно равное размерности массива. То есть этот алгоритм потенциально в пять раз быстрее параллельного алгоритма QuickSort. «Потенциально»— в силу разного реального времени единичных тактов (400 потоков на дискретный такт быстрой сортировки будут выполняться значительно быстрее, чем несколько тысяч потоков для алгоритма Фибоначчи).
Рассматривая множество алгоритмов, можно привести множество фактов, цифр и аргументов в пользу теоретического параллельного программирования, которому фактически учат, но которое в реальной ситуации мало востребовано. Причина одна— недостатки и ограничения существующих аппаратно-программных параллельных архитектур.
Рассмотренные простые задачи наглядно отражают проблемы, которые буквально лежат на поверхности в параллельном программировании. Тем не менее, судя по имеющейся информации, они не решены даже в рамках DARPA HPCS. Поэтому можно уверенно утверждать, что параллельный алгоритм вычисления чисел Фибоначчи даже на суперкомпьютере, создаваемом в рамках проекта Cray Cascade, будет не таким уж быстрым, как это могло бы быть теоретически. Просто потому, что подобные архитектуры не рассчитаны на программирование, к примеру, весьма обширного класса так называемых «мелкозернистых» параллельных вычислений.
Пока приходится сталкиваться с тем, что проще, к примеру, объявить параллельный алгоритм вычисления чисел Фибоначчи «неправильным». Однако неправильно объявлять неправильным то, что дает правильный результат. Для теории все алгоритмы, дающие правильный результат,— правильные. Но на практике прекрасная сказка о легком, ясном и красивом параллельном программировании, натолкнувшись на реалии многопоточного и многоядерного программирования, пока остается сказкой. А ведь мы еще не коснулись других, более важных проблем, представляющих (опять же— в теории) хорошо известные классические задачи, решение которых современное параллельное программирование скорее запутывает, а не проясняет. Но, может быть, мечта все же достижима? А HPCS— шажок к ее осуществлению, пусть и небольшой?
Вячеслав Любченко (sllubch@mail.ru ) — сотрудник компании «ПараДип» (Москва).
