Автоматическое распараллеливание отчасти неэффективно при выполнении программ на кластерах. Кластеры эффективны только для узкого класса слабо связанных задач, при переходе от последовательного компьютера к кластеру в 99% случаев следует менять алгоритм. Если наивный пользователь кластера встретит распараллеливающий компилятор, откомпилирует им свою старую последовательную программу, то потом обнаружит, что программа работает медленнее. А вина за это ляжет на компилятор, поскольку известны случаи, когда вручную для кластеров были написаны эффективные программы. Не всегда даже самый интеллектуальный компилятор сможет в последовательной программе распознать скрытые возможности параллельного выполнения. Но, с другой стороны, далеко не всякий программист способен оптимизировать или распараллелить программу лучше компилятора.
Переподготовка программиста для работы на параллельном компьютере может потребовать многих месяцев. Действительно, программист должен определить, какие операции в каком именно устройстве будут выполняться, при наличии коммутатора составить ему задание на соединение различных элементов вычислительной системы, синхронизировать вычислительные процессы (определяя задержки в буферах и интервал подачи данных для конвейерных систем), решить сложную комбинаторную задачу оптимального размещения данных в параллельной памяти. Поэтому для архитектур с общей памятью — векторных, VLIW, суперскалярных, SMP, многоядерных — разрабатывались и разрабатываются компиляторы с возможностями автоматического распараллеливания. И этот список будет продолжен, поскольку такие компиляторы востребованы.
Спор, что лучше — ручное или автоматическое распараллеливание, такой же несостоятельный, как и выбор между ассемблером и языками высокого уровня — нужно и то и другое. Бесспорно, чем больше автоматизации при создании сложных, в том числе и параллельных, программ — тем лучше. Кроме того, распараллеливание может быть и полуавтоматическим, при котором система предоставляет пользователю сервис в виде автоматического выявления зависимостей, эвристического определения загрузочного баланса и пр.
Развитие автоматического распараллеливания сдерживают два основных фактора. Во-первых, мифы об универсальности высокопроизводительных вычислительных систем, заменяющие четкое и честное описание класса задач, на которых эти системы эффективны. Для компьютеров, ориентированных на узкий класс задач, выбор подходящего алгоритма дает больший эффект, чем автоматическое распараллеливание программной реализации лучшего последовательного алгоритма. Во-вторых, слабое знание системными программистами математической теории преобразования программ.
Автоматическое распараллеливание позволяет:
-
ускорить время разработки параллельных программ;
-
удешевить разработку параллельных программ;
-
снизить требования к квалификации программистов;
-
повысить надежность разрабатываемых программ, поскольку объем исходного текста последовательной программы на порядок меньше, чем параллельной, а ее логическая структура проще;
-
упростить перенос многих разработанных программ с последовательных компьютеров на параллельные;
-
эффективнее проектировать программно-аппаратные комплексы с учетом новых методов распараллеливания.
Средства автоматического распараллеливания можно использовать и при проектировании схем однокристальных параллельных вычислительных устройств.
Рассмотрим теперь некоторые проблемы создания параллельного программного обеспечения и возможности автоматического распараллеливания. Для примера возьмем открытую распараллеливающую систему (ОРС).
Проблемы параллельного программирования
Проблемы параллельного программирования тесно связаны с проблемами подготовки программистов. У человека, который начинает осваивать параллельное программирование, как правило, возникает ряд априорных — обычно неверных — гипотез об этой деятельности.
Гипотеза 1. Если вычислительная система состоит из N параллельно работающих вычислительных устройств, то последовательная программа может быть выполнена в N раз быстрее. Исходя из этой гипотезы и ожидая получения недостижимых результатов, некоторые чиновники могут принять решение о выделении больших средств на создание параллельных компьютеров.
Однако гипотеза легко опровергается на примере задачи, которая под силу школьникам даже не последних классов.
Задача 1. Каждый школьник находит сумму двух чисел за одну минуту. За какое наименьшее время восемь школьников найдут сумму ста чисел? [Ответ: 15 минут.]
Сумму N чисел невозможно вычислить даже всем классом быстрее, чем за log2(N) шагов, причем без учета времени на обмены данными.
Следующая задача иллюстрирует еще более низкий эффект от распараллеливания некоторых алгоритмов.
Задача 2. Предположим, что некоторая задача решается алгоритмом сложности 2n, то есть при количестве данных n алгоритму требуется 2n операций для решения задачи на однопроцессорном компьютере. Если для n=100 однопроцессорный компьютер будет работать один час, то для какого значения n сможет решить задачу за один час двухпроцессорный компьютер? [Ответ: n = 101].
Для достижения быстродействия во многих, в частности NP-полных задачах, в первую очередь следует точные алгоритмы приносить в жертву эвристическим, а затем уже использовать распараллеливание.
Изучение параллельного программирования начинается с параллельных вычислительных архитектур и здесь нельзя обойти SIMD и MIMD. Первая позволяет во всех процессорных элементах выполнять одинаковые вычисления, а вторая — разные. Таким образом, появляется еще одна «очевидная», но ложная гипотеза.
Гипотеза 2. Всякий векторизуемый цикл может быть выполнен асинхронно, в любом порядке.
Однако асинхронное параллельное выполнение цикла
For i = 1 to N do
X[i] = 2*X[i+1]
может дать разные непредсказуемые результаты, например, если вторая итерация завершится до начала первой. При этом векторное выполнение данного цикла равносильно его последовательному выполнению.
Асинхронное параллельное выполнение тоже порождает свою «очевидную» гипотезу.
Гипотеза 3. Пусть программа F представляет собой последовательное выполнение двух фрагментов F1 и F2. Предположим, что последовательное выполнение этих фрагментов в произвольном порядке не влияет на результат. Тогда эти фрагменты можно выполнять асинхронно.
Однако пусть оба фрагмента F1 и F2 одинаковы и имеют вид:
{X = 1; Y = X; X = 2;}
Перестановка местами одинаковых фрагментов — это эквивалентное преобразование, не меняющее программу, но параллельное асинхронное выполнение этих фрагментов некорректно. При последовательном выполнении программы переменная Y будет равна единице, но может сложиться ситуация, при которой операторы в параллельных процессах будут выполняться по такому расписанию, что по окончании работы Y будет равно двум.
Эти гипотезы приводят к выводу, что эвристические соображения всегда следует подкреплять математическими доказательствами, а при преобразовании последовательных программ в параллельные следует анализировать программные зависимости. ОРС как раз и выполняет такой автоматический анализ.
И еще. При подготовке параллельных программистов важно развивать видение многих вариантов (алгоритмов) решения одной задачи и многих вариантов программной реализации алгоритма: для одних архитектур эффективны одни подходы, а для других — другие. Это требование продиктовано разнообразием параллельных архитектур и их быстрой обновляемостью. Приведем еще одну задачу — об обнаружении фальшивых монет — из серии олимпиадных задач для школьников. Задача привлекает внимание учащихся к особенностям параллельного программирования.
Задача 3. Есть двое чашечных весов без гирь и 120 монет (N монет), из которых одна фальшивая. За какое наименьшее одновременное количество взвешиваний можно найти фальшивую монету, если известно, что она легче настоящих? [Ответ: log5N (= 3 взвешивания)].
От распараллеливающего компилятора к распараллеливающей системе
Идеи автоматического распараллеливания появились в начале семидесятых годов прошлого века вскоре после создания первого параллельного суперкомпьютера ILLIAC-IV. В обзорах того времени (см. например, В.В.Вальковский, Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989) упоминалось несколько десятков разработок отечественных экспериментальных распараллеливающих компиляторов. Большинство из них искали шаблонные циклы в тексте последовательной программы и заменяли их параллельными командами. Лучшие из этих компиляторов проводили анализ зависимостей, не всегда отождествляя вхождения переменных X(i+1) и X(1+i). Главная проблема состояла в отсутствии хорошей библиотеки преобразований программ. Видимо, единственный серьезный отечественный распараллеливающий компилятор был создан для компьютера «Эльбрус 3». За рубежом (в США и Японии) эффективные распараллеливающие компиляторы разрабатывались для векторных компьютеров, однако удачными были разработки только для компьютеров с общей памятью. В конце концов стало ясно, что эффективное автоматическое распараллеливание возможно только для архитектур, ориентированных на решение широкого класса универсальных задач. Однако из-за быстрого морального старения компьютеров и разнообразия архитектур появляется потребность в быстрой разработке и обновлении параллельного ПО, в частности распараллеливающих компиляторов. Многолетняя разработка компилятора просто бессмысленна.
Некоторые разработчики компьютеров используют собственные компиляторы, которые заранее модифицируются одновременно с новой аппаратурой. В худшем положении находятся независимые разработчики ПО, они позднее узнают об архитектурах и вынуждены иметь свои заготовки— инструменты для разработки средств автоматического распараллеливания.
В основе распараллеливающей системы лежит внутреннее представление программ и библиотека преобразований, причем изначально подразумевается, что оптимизирующие преобразования для одной архитектуры могут ухудшать код для другой, поэтому возможна лишь частичная переносимость компилятора. Сохраниться при переносе могут, в основном, высокоуровневые преобразования, причем при переносе, возможно, их придется перегруппировать, изменив сферу их применения. Поэтому более эффективен не компилятор, в котором преобразования «плотно пришиты» друг к другу, а распараллеливающая система, в которой преобразования размещены в библиотеке в виде, удобном для вызова и группировок. При этом библиотека открыта для пополнения и модификаций преобразований.
Открытая распараллеливающая система
Открытая распараллеливающая система была задумана как инструмент разработки распараллеливающих конверторов и компиляторов, однако со временем представления о возможностях использования ОРС расширились. Отличительная особенность ОРС— архитектурно-независимая библиотека высокоуровневых преобразований с четкой структурой. Казалось бы, высокоуровневая оптимизация может проиграть низкоуровневой в эффективности. Однако, во-первых, в каждом конкретном случае низкоуровневую оптимизацию можно добавить, во-вторых, чем выше уровень преобразований, тем шире круг возможных целевых архитектур и, следовательно, больше количество приложений. К тому же современные многоядерные процессоры вполне допускают распараллеливание высокоуровневых циклов.
Ситуация аналогична соотношению ассемблера и языков высокого уровня. Разумеется, прикладная программа на ассемблере будет работать быстрее, но разработка займет слишком много времени, не говоря уже о модификации. За это время будет создано новое поколение процессоров, быстродействие которых погасит ассемблерные преимущества в ускорении.
Еще одно преимущество высокого уровня преобразований— пользователь системы может видеть как исходный текст последовательной программы, так и преобразованный, что облегчает верификацию и позволяет автоматизировать тестирование преобразований. В ОРС предполагается собрать все известные разумные высокоуровневые преобразования, для какой бы архитектуры они не предназначались. Почти для каждого преобразования верно то, что, если одно из них улучшает код, то второе ухудшает, и наоборот. Следовательно, для каждой архитектуры хотя бы одно из них будет полезно. Но часто оказываются полезны оба преобразования, просто в разных контекстах. Например, в одних и тех же компиляторах используются такие известные взаимно обратные преобразования, как «подстановка» и «вычисление общих подвыражений». В ОРС разрабатываются оригинальные преобразования циклов с минимизацией вводимых временных массивов, распараллеливающие преобразования рекуррентных циклов, оптимизация линейных участков с учетом баланса минимизации арифметических операций и избыточных обращений к памяти (конфликтующих между собой преобразований) и др. Создана возможность диалогового (полуавтоматического) применения преобразований— пользователь сам определяет последовательность применения преобразований и их целесообразность.
Автоматическое определение параллельно выполняемых циклов
Распараллеливающие компиляторы и распараллеливающие системы автоматически определяют параллельно выполняемые циклы. Однако понятие «параллельно выполняемого» цикла не совсем корректно без уточнения параллельной вычислительной архитектуры. Различные архитектуры в параллельно выполняемых циклах допускают различные программные зависимости. В ОРС, например, автоматически строится граф информационных связей, определяются все типы зависимостей: входные, выходные, истинные и анти-зависимости, а также характеристики зависимостей по отношению к циклам (циклически порожденные и циклически независимые). На основе анализа графа информационных связей для разных архитектур автоматически определяется возможность одновременного (параллельного) выполнения итераций циклов. Если в цикле нет зависимостей, то итерации можно выполнять параллельно на различных архитектурах. Асинхронная архитектура (многоядерные процессоры, кластеры) позволяет распараллеливать циклы любой глубины вложенности. Эти циклы могут содержать условные операторы, но допускают только циклически независимые зависимости. Синхронная архитектура позволяет распараллеливать самые глубоко вложенные циклы и допускает зависимости, которые направлены сверху вниз. Общая память допускает входные зависимости. При распределенной памяти входная зависимость мешает, но ее можно устранить предварительной рассылкой (копированием) данных.
Процесс распознавания в ОРС параллельно выполняемых циклов для различных архитектур приведен на рис. 1. Входная программа показана слева, граф информационных связей— справа. Правое информационное окно сообщает о векторизуемости самого вложенного цикла, нижнее— о возможности независимого выполнения итераций второго цикла сверху. Синяя метка возле описания функции min() обозначает, что данная функция не имеет побочных эффектов, которые могли бы препятствовать распараллеливанию циклов, содержащих вызов этой функции.
Решетчатый граф программы для синхронизации процессов при распараллеливании
Рассмотрим процедуру распараллеливания на два процесса внешнего цикла в следующем фрагменте программы:
for(i=1; i<=N; ++i)
for(j=1; j<=N; ++j)
{ a[i+j] = …
…= … a[i+j-1];
}
Итерации этого цикла не являются независимыми и поэтому параллельно выполняемые процессы должны будут содержать операции синхронизации. Решетчатый граф, построенный с помощью ОРС для данного фрагмента, приведен на рис. 2.
Вершины графа— точки пространства итераций. Дуга соединяет две вершины, если на соответствующих итерациях происходит обращение к одним и тем же ячейкам памяти; направление дуги определяет порядок этого обращения во времени. Зеленые дуги обозначают истинные зависимости, красные— антизависимость, синие— выходную самозависимость. Вертикальная линия разбивает пространство итераций гнезда циклов между двумя процессами. Внутри каждого процесса порядок выполнения итераций сохраняется от последовательного выполнения. Между процессами необходимо согласование по дугам, концы которых принадлежат разным процессам. Выполнение итерации гнезда циклов, которое соответствует концу дуги, должно начинаться только после выполнения итерации, соответствующей началу дуги (которая принадлежит другому процессу).
Решетчатый граф для реальных программ может быть достаточно большим, поэтому внутри ОРС он хранится в виде кусочно-квазилинейных функций и неравенств, описывающих область их определения.
Распараллеливание циклов с зависимыми итерациями существенно расширяет использование автоматического распараллеливания. Следует подчеркнуть, что реализация такого распараллеливания не представляется возможной (кроме простых случаев) на основе традиционного графа зависимостей по данным.
Автоматическая конвейеризация
В ОРС реализован автоматический расчет таких параметров конвейеризации циклов, как задержки и интервал инициализации итераций. По одномерному циклу определяется наличие зависимостей, препятствующих конвейеризации, и, в случае их отсутствия, строится граф вычислений. Имеется возможность визуально проанализировать все эти характеристики. Модуль расчета синхронизации конвейера ориентирован на архитектуру перестраиваемого конвейера, но может быть адаптирован и к любой другой конвейерной архитектуре.
В группе ОРС ведутся исследования в области многоконвейерных вычислительных систем, модель которых допускает выполнение нескольких программных фрагментов на нескольких конвейерах одновременно и при этом между фрагментами допускаются регулярные зависимости.
Каждой операции из цикла в левой части экрана (рис. 3) соответствует вершина в графе вычислений (в правой части экрана), а каждая дуга указывает на передачу информации между соответствующими операциями. Для каждой вершины указана операция, которую она выполняет, а для каждой дуги указана величина задержки (буфера), необходимая для синхронизации передачи данных между соответствующими операциями.
Автоматические оценки погрешностей
В задачах с большим объемом вычислений над вещественными числами, для которых используются параллельные вычисления, возникает проблема накапливающейся погрешности вычислений. В ОРС разработан конвертор обычных вычислительных программ в программы с интервальными вычислениями. У «посмертных» интервальных оценок есть один известный недостаток— они растут очень быстро. Отчасти это происходит из-за многократных использований одних и тех же данных. Например, если переменная X имеет интервал точности [X— d, X + d], то, следуя формулам погрешностей для арифметических операций, выражение X— X будет иметь интервал точности [-2хd, 2хd]. В конверторе ОРС этот эффект учитывается, и интервал точности в данном примере будет нулевым. В конвертор заложен метод, вычисляющий оптимальный интервал точности для широкого класса арифметических выражений, содержащих кратные переменные.
Архитектура и распараллеливающая система
Прежде чем делать новый компьютер, что недешево, надо бы посмотреть, какие программы будут на нем эффективными. Если речь идет не об узкоспециализированном компьютере, а о компьютере, на котором должен эффективно считаться широкий класс программ, то нужен хороший компилятор с языка высокого уровня. В ОРС разрабатываются методы автоматического распараллеливания на синхронные многоконвейерные вычислительные модели. Эти методы позволяют отображать на многоконвейерную модель гнезда циклов с регулярными зависимостями.
Выводы
Сегодня имеется более десятка распараллеливающих систем: POLARIS, SUIF, PIPS, PARAWISE и др. В системе POLARIS (как и во многих других) в ходе всего процесса распараллеливания используется граф зависимостей по данным для всей программы, который модифицируется после каждого преобразования. В ОРС и SUIF граф зависимостей строится только для преобразуемого фрагмента программы, что упрощает разработку преобразований и сокращает время компиляции. Кроме того, в ОРС, в отличие от других распараллеливающих систем, используется решетчатый граф программы, а модификация двух информационных графов отнимет вдвое больше времени на компиляцию и разработку. Система POLARIS работает только с программами на языке Фортран для SMP-архитектур. Система PARAWISE имеет возможность диалога при распараллеливании, но располагает ограниченным набором преобразований. Система SUIF (Stanford University Intermediate Format) акцентируется на внутреннем высокоуровневом представлении— тем самым подчеркивается его важность (и с этим нельзя не согласиться). Система работает с языком Си, а для преобразования программ на Фортран используется конвертор f2c. К многоязыковым системам следует отнести семейство оптимизирующих компиляторов GNU с многоуровневым внутренним представлением. В оптимизирующих компиляторах известных производителей имеются возможности автоматического распараллеливания циклов с независимыми итерациями. Но, чем выше уровень вложенности цикла в гнезде циклов, тем статистически реже его итерации независимы. Чем выше уровень вложенности современных многоядерных процессоров, тем эффективнее распараллеливание. В ОРС, в отличие от других распараллеливающих систем и компиляторов, используется решетчатый граф программы, позволяющий разрабатывать новые приемы распараллеливания с автоматически вставленными синхронизациями для циклов с зависимыми итерациями.
Борис Штейнберг (borsteinb@mail.ru )— профессор Южного федерального университета (г. Ростов-на-Дону).
Среда ОРС
Исследования и разработки по программе ОРС (ops.rsu.ru) ведутся в Южном федеральном университете (г. Ростов-на-Дону) по таким направлениям, как создание новых преобразований программ, средств повышения надежности преобразований и автоматизации оценок точности вычислений, методов распараллеливания и др. На базе ОРС готовится к выпуску в начале 2008 г. «тренажер параллельного программиста». Планируется выпуск нескольких распараллеливающих конверторов и, в перспективе, компиляторов.
В отличие от электронных учебников «тренажер параллельного программиста», кроме традиционной учебной информации, предоставляет возможность пользователям получать визуализации программных зависимостей, вскрывающих причины возможности либо невозможности соответствующих преобразований или распараллеливания с помощью графовых моделей программ. В тренажере имеются граф информационных связей; граф вычислений (автоматическая конвейеризация цикла с синхронизацией); решетчатый граф программы; управляющий граф программы; граф вызовов подпрограмм; SSA-граф.
Тренажер автоматически определяет, какие циклы в программе могут быть выполнены на параллельной, векторной или конвейерной архитектуре при преобразовании последовательной программы к виду, удобному для параллельного исполнения.
