Компьютерная отрасль переживает сегодня переход от последовательного программирования к параллельному, и, как всякий переход, он полон сомнений, предрассудков, заблуждений и обещаний, которые раздают создатели очередных супервычислителей. Без четких критериев оценки реального уровня параллелизма усилия по созданию в стране пула суперкомпьютерных ресурсов могут оказаться бесполезны. В подобной ситуации важно иметь некую отправную точку, плацдарм, который можно было бы использовать для анализа происходящих событий. Для программирования таким плацдармом является теория параллельных вычислений, позволяющая выработать критерии определения «кто есть кто».
В основе теории вычислений лежит понятие абстрактных машин, и одной из них является машина Поста, под которую фактически и была «заточена» архитектура нынешних процессоров. Точкой отсчета здесь принято считать определение «логической конструкции электронной вычислительной машины» из отчета фон Неймана и его коллег из Принстонского института по проекту ENIAC в июне 1946 года. Однако при попытках распараллелить вычислительный процесс ситуация меняется – оказывается, что и с архитектурой машин что-то не то, да и с языком выражения «параллельных мыслей» – алгоритмов?– не все гладко. В результате отношения с параллельным программированием напоминают сегодня отношения с любимыми животными – мы вроде бы понимаем друг друга, но полноценному контакту мешает отсутствие языка общения.
Сегодня теория и практика параллельного программирования существуют сами по себе. Тут либо теория не верна, либо практика не соответствует положениям теории. Модернизация параллельного программирования нужна и, что тут скрывать, давно назрела. Но правильно ли мы ее проводим и тем ли путем идем?
Может быть, ситуация излишне драматизируется – ведь имеются примеры, когда достижения параллельного подхода не подвергаются сомнению? Но это «рекорды», число которых мало. Много ли вы знаете программистов, которых заботят проблемы расположения программ в памяти и их производительность с учетом объема кэша или попадания в него? А кто из них озабочен понятиями латентности системы и когерентности памяти? Программирование «высоких достижений» было, есть и будет, но надо ли всем к нему стремиться? Может, и о параллельном программировании пока еще даже мечтать рано, тем более что поставщики платформ описывают, как легко сделать программу параллельной, например расставив вызовы OpenMP и сразу получив огромный прирост производительности?
Не надейтесь легко распараллелить уже существующие программы – скорее всего, для этого потребуется создание новых алгоритмов и преобразование структур данных и механизмов работы с ними. Но как отличить действительно параллельное программирование от поименованного таковым? Только тестированием, однако что понимать под параллелизмом? В одноядерном процессоре достаточно функционирующих параллельно узлов, но это еще не повод считать его параллельным. Но почему многие легко соглашаются считать его таким, если на одном чипе разместить несколько ядер? Ведь сколько ни собирай автомобили в одну кучу, они самолетом не станут.
Обратимся к теории алгоритмов, вспомнив, к примеру, понятие вычислительной сложности. Оно распространяется на любой тип алгоритмов, связывая условное время работы алгоритма с его входными данными. Необходимо найти алгоритмы, вид которых, последовательный или параллельный, качественным образом влияет на их вычислительную сложность. Тогда, рассматривая объект как «черный ящик», мы, сняв его характеристики, можем отличить последовательную реализацию объекта от параллельной. Мы уже рассматривали алгоритм вычисления чисел ряда Фибоначчи. Последовательная рекурсивная форма данного алгоритма имеет ярко выраженную экспоненциальную, а аналогичная параллельная – линейную вычислительную сложность.
Но сначала одно важное замечание. В теории анализ алгоритмов выполняется в так называемом условном времени. В рамках последовательной парадигмы программирования им может быть реальное время работы алгоритма. Для этого достаточно знать коэффициент пропорциональности между реальным и условным временем исполнения единичной инструкции алгоритма – инструкции, ко времени которой приводится время работы остальных инструкций. Учитывая это, просто построить график вычислительной сложности последовательного алгоритма Фибоначчи, фиксируя реальное время получения результата для некоторого интервала номеров чисел ряда.
В параллельном алгоритме инструкциям (процессам, потокам, ядрам и т.п.) разрешено выполнятся одновременно, а поскольку формально нет ограничений на их количество, то для его выполнения часто не хватает даже ресурсов суперкомпьютеров. Поэтому в параллельном программировании мы сталкиваемся с необходимостью моделировать параллелизм. В такой ситуации реальное время сложно приравнять условному и нужно обязательно говорить об условном времени и различать абстрактную вычислительную сложность – ту, о которой говорится в теории, и реальную, которую мы наблюдаем. А уж чем они ближе друг к другу, тем ощутимее выгода от параллельного программирования и тем больше оснований говорить об истинном параллельном программировании.
Теория оперирует абстрактной вычислительной сложностью, которую можно, а иногда и нужно «вычислить», исследуя работу реальной параллельной программы. Так мы сможем убедиться, что теория соответствует практике, а практика не опровергает теорию. Абстрактная вычислительная сложность параллельного рекурсивного алгоритма Фибоначчи имеет линейный характер. Реально к этому можно лишь стремиться, так как фактически невозможно найти систему, которая предоставила бы необходимое число параллельных процессов. Поэтому, реализуя данный алгоритм, мы гарантированно столкнемся с необходимостью моделировать параллелизм. Но это даже хорошо, поскольку невозможно или, как минимум, сложно будет обмануть заказчиков суперкомпьютерных систем, выдавая обычный объект за параллельный.
Итак, если система порождает нужное алгоритму число процессов (хотя бы в некотором диапазоне входных данных), то реальная вычислительная сложность должна соответствовать абстрактной. Если же ресурсов недостаточно, то, зная соответствие между условным временем вычислительной модели и реальным временем ее работы, мы также сможем оценить вычислительную сложность алгоритма. Но, чтобы исключить любые недоразумения, анализ алгоритма лучше сразу вести в условном времени. Ответ же на вопрос, что ему соответствует, нужно искать, анализируя свойства системы – многопоточной, многоядерной и т.п. – или вычислительной модели, реализованной на их базе. Для большинства известных и наиболее популярных подходов в программировании единицу условного времени можно связать с числом выполненных параллельно инструкций – реально или в режиме моделирования.
С результатами сравнительных экспериментов по выполнению различных последовательных и параллельных алгоритмов вычисления чисел Фибоначчи, созданных в рамках разных вычислительных моделей, можно познакомиться на сайте Intel Software Network (software.intel.com/ru-ru/blogs/2009/11/06/2002442). Из рассмотренных моделей лишь подход на базе автоматов подтверждает выводы теории о линейном характере вычислительной сложности параллельного рекурсивного алгоритма. Рассматривая же параллельные решения на базе библиотеки Intel TBB (Threading Building Blocks) и языка MC#, можно прийти к ложному выводу о свойствах параллельного алгоритма (в реальном времени сложность имеет экспоненциальную зависимость). Отсюда – или «время» не то, или реализация параллельных алгоритмов не параллельна.
Из сравнения работы однопоточного и двухпоточного вариантов параллельного алгоритма на TBB следует, что, например, при двух ядрах мы имеем линейное ускорение в два раза. Но что это меняет, если вычислительная сложность алгоритма имеет все ту же экспоненциальную зависимость? В такой ситуации о параллелизме как вычислительной модели речи нет. Или, может, нужна, как в случае с автоматной моделью, другая шкала времени? Иначе создается впечатление, что TBB реализует некое подобие «ручки скорости», увеличивающей скорость работы процессора. И, казалось бы, – жми да жми! Но тут самое время вспомнить о времени реальном – решение с TBB на одном потоке сначала уменьшает скорость выполнения в шестьдесят шесть раз, а затем увеличивает в два раза. В итоге имеем замедление, когда для достижения даже исходной скорости нам нужен процессор, как минимум, с тридцатью тремя ядрами. А будет ли «ручка» и дальше работать по линейному закону? А вычислительная сложность? Если она останется экспоненциальной, то легко будут «съедены» все ядра и любая скорость.
Для кого-то табун лошадей – лучше, чем один конь. Но даже огромный табун не пробежит быстрее автомобиля из Москвы в Санкт-Петербург. Может, между многоядерным процессором и соответственно многопоточным программированием – с одной стороны, и параллельным программированием – с другой, такая же качественная пропасть, как между лошадью и автомобилем? На этот вопрос еще только предстоит узнать ответ из доказательств «линейности» параллельных алгоритмов Фибоначчи на TBB или на MC#.
***
Интрига текущей ситуации в том, что разговоров о параллельном программировании больше, чем его самого, и потому-то в параллельном программировании «куда ни кинь – всюду клин». Кто нас «убаюкивает» и под чью «дудочку» мы мечтаем о том, чего еще фактически нет и, возможно, не будет, не так уж и важно, но настораживает сложившийся в программировании «теоретический нигилизм», игнорирующий даже имеющуюся доказательную базу. Слепоглухонемая к теории практика программирования способна завести только в тупик, выход из которого найти намного сложнее, чем вход.
Вячеслав Любченко, Юрий Тяжлов (sllubch/armaguard@mail.ru) – сотрудники компании «ПараДип» (Москва).
Квадратура параллелизма
Параллельное программирование нуждается не в единицах процессов и ядер, а в тысячах и миллионах, однако, чтобы эффективно управлять таким числом процессов, нужны новые технологии и алгоритмические модели.
