Увеличение производительности компьютерных систем осуществляется сегодня, как правило, за счет физического параллелизма — по этому пути идут Intel, AMD, ARM, а также nVidia, последние модели графических процессоров которой имеют сотни ядер, а платформа Tesla образована из набора графических карт, объединенных параллельно и подключаемых к управляющему компьютеру как отдельный вычислительный блок. Компания Intel тоже решилась испытать судьбу после неудачной попытки выхода на рынок графических процессоров и предложила новую архитектуру со множеством простых ядер (Many Integrated Core, MIC). Такова общая тенденция, согласно которой в индустрии считается, что производительность проще нарастить путем увеличения количества, нежели усовершенствуя отдельно взятые исполнительные блоки. Графические процессоры nVidia и AMD характеризуются не только узкой специализацией, но и простотой компоновкой, что позволяет во множестве размещать их на одной подложке. Ядра процессора для проекта MIC имеют архитектуру x86, причем сильно упрощены по сравнению с ядрами других процессоров компании Intel, в частности из них удалены все векторные инструкции, а исполнение в рамках ядра происходит строго последовательно. Однако для увеличения параллелизма по данным были разработаны 512-битные векторные инструкции SIMD, что в четыре раза выше, чем в стандартных процессорах.
Еще одна тенденция — рост популярности гетерогенных вычислений; например, IBM оснастила свои новейшие серверы, помимо обычных процессоров, еще и графическими от nVidia, а Intel анонсировала встраивание графического ядра на одну подложку с обычным процессором.
Вместе с тем на этом фоне грандиозных достижений в области оборудования высокопроизводительных исполнительных устройств сфера разработки программ буксует — создание действительно параллельных приложений требует специальной подготовки, особого образа мышления и высокой квалификации программистов. Поэтому чрезвычайно значимой становится задача создания инструментария для автоматической оптимизации и распараллеливания программ. Поскольку все программы так или иначе должны быть скомпилированы на язык исполнительного устройства, то много усилий таких производителей, как Intel, Microsoft и сообщества Open Source, тратится именно на доработку компиляторов.
Интрига
В качестве единой меры оценки качества оптимизации программ и производительности процессоров принят набор тестов SPEC cpu2006, в состав которого входят исходные коды наиболее известных трудоемких приложений. Уже много лет между Intel и AMD ведется ожесточенная борьба за лидерство по показателям этого теста: в то время как 8-ядерный процессор Intel Xeon X3470 установил рекорд в категории SPEC BASE (все тестовые программы набора компилируются с одними и теми же опциями компилятора), в категории SPEC PEAK (допускается оптимизация параметров компилятора) он проигрывает AMD Opteron 2356 (табл. 1). Сейчас также вводится сравнение производительности на единицу электроэнергии, при котором влияние компилятора еще более усиливается.
| Xeon X3470 | 8 ядер | Base 81,7 | Peak 85,5 |
|---|---|---|---|
| Opteron 2356 | 8 ядер | Base 79,6 | Peak 87,2 |
Оптимизация параметров компилятора строится, в частности, на технологии итеративной оптимизации, позволяющей исследовать пространство оптимизирующих преобразований, количество которых весьма велико, а архитектуры процессоров весьма сложны для моделирования. Итеративная оптимизация позволяет улучшить производительность скомпилированного приложения, например задача перемножения двух матриц может быть ускорена в несколько раз.
|
Кризис параллельного мира
Рост тактовой частоты прекращается, вычислительная мощность растет за счет увеличения числа ядер в процессорах, производительность последовательных вычислений теперь не повышается, однако концепция параллельного программирования, возникшая более 40 лет назад, представляет собой существенную проблему. |
Для автоматической подстройки компиляторов применяется, например, машинное обучение, реализованное с помощью ряда подходов. Построение дерева решений эффективно для подстройки алгоритмов развертывания циклов на разных архитектурах, однако для решения более широкой задачи, включающей большее число алгоритмов, может потребоваться слишком много ресурсов. Генетическое программирование позволяет создавать программы, способные автоматически подстраивать свое поведение под входные условия в соответствии с некоторой заданной функцией. Основной идеей является использование операторов скрещивания и случайных мутаций, производящих по ходу работы все новые решения из уже найденных; однако такой метод требует довольно большого количества ресурсов, а также собственной нетривиальной настройки. Данный метод используется, например, в инструментарии Meta optimization, в котором рассмотрены три оптимизации: формирование гиперблока, предвыборка данных и распределение регистров. Обучение ограничено 50 поколениями, но в некоторых случаях удается достигнуть хорошего результата уже через 2-5 поколений.
Машинное обучение – хорошее подспорье при поиске оптимальных параметров компилятора, однако для достижения заметных результатов требуется сбор большого числа различных данных, приведение их к единому представлению и статистическая обработка. Для того чтобы обучение дало действительно оптимальную для общего случая эвристическую функцию, необходим тщательно подобранный набор обучающих приложений, покрывающий большой спектр разнообразных случаев.
Отбор опций
Сегодня имеется множество алгоритмов отбора опций компиляторов, часть которых приведена в табл. 2.
| Алгоритм | Описание |
|---|---|
| Алгоритм полного перебора (Exhaustive Search) | Использует каждый из допустимых наборов опций компиляции — строит полное пространство решений, и найденный минимум целевой функции всегда является глобальным. Однако вычислительная сложность данного алгоритма равна O(M), где n – число опций компиляции, а M – число возможных значений опций. Такая сложность считается неприемлемой, поскольку время поиска растет экспоненциально с ростом числа опций, поэтому на практике предпочтение отдается различным модификациям, например алгоритму полного перебора с приоритетом. Каждой опции и ее значению на основе экспертной оценки приписывается некоторый вес, и в зависимости от него в процессе формирования очередного тестового набора те или иные опции получают более высокий приоритет. В результате при завершении итераций задолго до окончания полного перебора уже будут опробованы наиболее значимые комбинации опций и их параметров. |
| Алгоритм группового исключения (Batch Elimination) | Идея в том, чтобы определить опции, которые вызывают увеличение времени исполнения тестируемой программы, и не использовать их в дальнейшем поиске оптимального набора опций. Реализация данного алгоритма позволяет добиться хорошей производительности, только если влияние опций друг на друга незначительно. Для определения эффекта использования какой-либо опции применяется относительная процентная доля улучшения (Relative Improvement Percentage, далее RIP), показывающая относительную разницу времени исполнения тестируемой программы, скомпилированной в двух вариантах: с выключенной опцией и со всеми включенными опциями. Если полученная величина отрицательна, данный алгоритм исключает из набора исследуемую опцию, получая таким образом, оптимальный набор. |
| Алгоритм итеративного исключения (Iterative Elimination) | В отличие от алгоритма группового исключения, данный алгоритм последовательно исключает из стартового набора опции, которые увеличивают время исполнения тестируемой программы наибольшим образом. Стартовый набор для данного алгоритма ничем не отличается от стартового набора для алгоритма группового исключения, то есть все опции включены. После вычисления RIP для каждой из них удаляется та, что дала наибольший негативный эффект. Этот процесс повторяется со всеми оставшимися опциями до тех пор, пока ни одна из оставшихся не перестанет давать отрицательных результатов. |
| Алгоритм комбинированного исключения (Combined Elimination) | Совмещает в себе идеи алгоритмов группового и итеративного исключения. Если опции компиляции слабо влияют друг на друга, данный алгоритм исключает опции с отрицательным значением, как алгоритм группового исключения, в противном случае он исключает их в течение итеративного процесса, как алгоритм итеративного исключения. Этот алгоритм показал средний прирост производительности 4%, что лучше, чем предыдущие. По нормализованному времени работы алгоритм комбинированного исключения лучше других в 1,5 – 6 раз, однако при увеличении количества опций подход становится слишком требовательным ко времени. |
| Генетический алгоритм (Genetic) | Позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров. При этом используются механизмы, напоминающие биологическую эволюцию, в процессе которой выживают наиболее приспособленные особи, а наименее приспособленные погибают. Алгоритм начинает свою работу с формирования начальной популяции – конечного набора допустимых решений задачи. Эти решения выбираются случайным образом. На каждом шаге эволюции с помощью вероятностного оператора селекции выбираются два решения – родители. Оператор скрещивания по выбранным решениям строит новое, которое подвергается небольшим случайным модификациям – мутациям. Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции. |
| Алгоритм статистического выбора (Statistical Selection) | Использует статистику вывода (Inferential Statistics). Вводятся экспериментальная и начальная гипотезы, которые противоречат друг другу. Для проверки гипотез определяют контрольную (опция выключена) и экспериментальную (опция включена) группы для каждой из опций. Поскольку для их проверки требуется значительное число запусков тестируемой программы с различными наборами опций, то создается только одна контрольная и одна экспериментальная группа. В данных группах значения опций распределены случайным образом с использованием ортогональных массивов, к которым применяется тест Манна-Уитни для расчета влияния той или иной опции на время работы программы. Согласно этому тесту, для определения влияния некоторой опции на время исполнения тестируемой программы информация о времени исполнения распределяется на две групп — экспериментальную и контрольную. Затем, используя информацию экспериментальной группы, вычисляется тестовая статистика и на ее основе при помощи вероятностной функции определяется, попадает ли опция с данным значением в оптимальный набор. |
| Жадный конструктивный алгоритм (Greedy Constructive Algorithm) | Пространство поиска представляется как направленный ацикличный граф, корнем которого является пустое множество. В пространстве с n оптимизаций корень содержит n детей, представляющих множества размером в один элемент. Каждый последующий узел содержит 2n детей, которые представляют добавление отличающейся оптимизации к той, что находится в родительском узле. Конструктивный алгоритм спускается от корня, выбирая на каждом шаге узел с наилучшим значением производительности до тех пор, пока не сконструирует множество заданной длины. Применение жадных алгоритмов дает хорошие результаты при решении многих сложных проблем. |
| Алгоритм случайного поиска (Randomized algorithm) | Применяет степень произвольности как часть своей логики, обычно использует генератор равномерно случайных величин как вспомогательный вход, регулирующий его работу, в надежде добиться хороших результатов «в среднем» среди всех возможных выборов произвольных величин. Формально, его производительность — это случайная величина, определяемая случайными величинами, поэтому и время и результат его работы тоже являются случайными величинами. |
| Нетерпеливые алгоритмы | Идея похожа на алгоритм случайного поиска, за тем исключением, что для каждой новой случайно выбранной точки пространства совершается локальный спуск по некоторому заданному количеству точек вокруг нее. Сам спуск может совершаться различными способами, в частности, это может быть случайный перебор внутри некоторого радиуса. |
Алгоритмы из табл. 2 влияют на время работы (количество итераций), а также на конечные результаты, однако испытания показали небольшую разницу между найденными решениями (исключая полный перебор), в пределах 10% по времени работы приложения, поэтому были разработаны системы поиска оптимальных опций (табл. 3).
| Система | Описание |
|---|---|
| PathOpt2 — система для итеративного поиска лучшей оптимизации | Особенности системы: XML-формат описания конфигурации и параметров поиска, возможность использовать компилятор как черный ящик, гибкая форма задания параметров поиска, а также возможность при сборке приложения во время итерации компилировать только выбранные файлы. Недостатки: возможность работы только на уровне всего приложения или файлов, а не отдельных функций или более маленьких структур, отсутствие каких-либо способов ускорения поиска. |
| ACME (Adaptive Compilation Made Efficient) — инструмент итеративного поиска лучшей оптимизации | Сравнение различных вариантов скомпилированного кода занимает половину всего времени при итеративном поиске вариантов, а данный инструмент вместо запуска программы для оценки производительности использует виртуальное выполнение. Без запуска программы подсчитывается количество инструкций, которые выполнились бы при запуске, и оценивается, насколько оптимизация меняет производительность. Виртуальное исполнение накладывает ограничения на оптимизацию: так как оценивается только количество инструкций, то в инструменте не используются трансформации, которые напрямую влияют на производительность работы с памятью. Утверждаемая точность виртуального исполнения достаточно высока — в среднем 98,6% оценок оказывается точными с погрешностью в 3%. Использование виртуального выполнения позволяет сократить время эксперимента в 2-5 раз. |
В системе использовались четыре алгоритма поиска: жадный конструктивный алгоритм, генетический алгоритм, алгоритм поиска экстремума и алгоритм поиска по пространству с помощью случайных испытаний, а также 16 трансформаций. К сожалению, система может работать только с приложением целиком, не выделяя в нем наиболее часто исполняемые части.
Усредненные данные
Большинство вычислительных приложений для своей работы используют набор входных данных, поэтому ряд исследований по поиску оптимальных опций компилятора был посвящен вопросу поиска такой оптимизации, при которой достигались бы хорошие результаты с любым набором данных. Такие компромиссные оптимизации (табл. 4) принято называть уровнями оптимизации, результаты применения каждого из них должны удовлетворять тем или иным специфицированным требованиям.
| Система | Описание |
|---|---|
| Фреймворк Compiler Optimization Level Exploration (COLE) | Автоматическое нахождение оптимальных уровней оптимизации для компилятора GCC 4.1.2. С помощью генетического алгоритма COLE ищет наборы опций компилятора, которые дают парето-оптимальные результаты для нескольких целевых функций. Рассматриваются 60 опций, входящих в наборы -О1, -О2, -О3 и -Оs, и две целевые функции: функция производительности и функция времени компиляции. Функции измеряют сумму времени работы тестов и суммарное время компиляции всех тестов соответственно. В результате экспериментов COLE смог найти уровни оптимизации, которые превосходят стандартные -О1, -О2, -О3 и по производительности (на 3,1% лучше, чем -О3), и по времени компиляции (на 37,6% быстрее, чем -О3). При этом полученные уровни задействуют только 15 опций из 60 используемых в уровнях GCC. Однако COLE нашел эти уровни только для определенного набора программ и только для одной архитектуры, поэтому их нельзя назвать универсальными. |
| Статистика непараметрического вывода | Для получения множества оптимизационных конфигураций можно использовать ортогональные массивы, а для определения степени влияния опции на оптимизацию приложения – тест Манна-Уитни. В результате получаются следующие данные: для поиска в пространстве из 45 опций требуется не более 10 итераций (каждая итерация содержит от 24 до 100 циклов компиляции-запуска-измерения производительности). Полученные для каждого тестируемого приложения оптимальные наборы опций всегда показывают результат лучше, чем опции -O1, -O2, -O3 компилятора GCC 3.3.1. К недостаткам данного подхода можно отнести большое количество циклов оптимизации-запуска-измерения (от 72 до 1 тыс.). |
Исследование пространства поиска
На практике невозможно совершить полный перебор всех возможных комбинаций значений опций компилятора, более того, из-за чрезвычайной сложности современных архитектур невыполним даже теоретический расчет потенциального минимума времени работы программы. Это не позволяет определить максимально достижимые величины оптимизации, сформулировать критерии остановки поиска и даже оценить потенциал такого поиска. Однако имеются исследования для некоторых выбранных опций, позволяющих получить неплохие результаты. Например, было изучено подпространство оптимизаций (последовательности длиной 10 разных оптимизаций) и качество работы нескольких алгоритмов поиска оптимума (генетический алгоритм, алгоритм поиска экстремума и жадный конструктивный алгоритм, а также их модификации) в большем пространстве
В нашем исследовании использовался собственный компилятор, и оптимизации было возможно запускать в произвольном порядке, в результате исследования подпространства оптимизаций был выявлен набор свойств подпространства. Сравнение алгоритмов показало, что лучшие результаты демонстрирует генетический алгоритм, однако он требует больше ресурсов, чем другие. По соотношению результат/время работы лучше всех оказались нетерпеливые алгоритмы поиска экстремума, исследующие до 10% ближайших соседей текущей точки и пытающиеся 10 и 50 раз начать поиск в случайных точках пространства.
Полный перебор всех возможных комбинаций для 15 опций оптимизатора Very Portable Optimizer (VPO) произвольной длины применительно к 111 функциям позволил определить достижимый предел оптимизации. Чтобы сделать такой перебор возможным, для хранения получаемой информации использовался направленный ациклический граф, узлами которого были экземпляры оптимизированной функции, а ребрами — оптимизации. Если очередная оптимизация не могла быть применена к функции, она не сохранялась. Для каждого экземпляра функции вычислялся хеш-код. Процесс перебора продолжался до тех пор, пока система могла создать отличающийся экземпляр
Вфункции. В результате был проведен анализ взаимодействия разных оптимизаций и произведено улучшение VPO, как следствие, размер кода увеличился на 1,5%, производительность упала на 0,5%, время компиляции уменьшилось до 29,7% от первоначального времени.
Новые пути
В своей работе мы исследовали все 1593 опции компилятора Intel Compiler 11.1. Было выявлено, что на тестах SPEC CPU2000 некоторые отдельно взятые опции могут существенно влиять на время исполнения (87 дали прирост больше 5%), в основном они отвечают за оптимизацию циклов, векторизацию и выравнивание данных в памяти.
|
Многоядерные процессоры и программирование
Сегодняшнее программирование разделено на две практически непересекающиеся области: программирование высокоскоростных вычислений и создание программ общего назначения. До недавнего времени они мирно сосуществовали. Гром грянул, когда ведущие ИТ-поставщики объявили о планах производства микросхем с сотнями ядер на одной подложке. Как это повлияет на программирование? |
Обычно мало внимания уделяется тому факту, что 20% кода выполняют 80% работы, а разные участки кода требуют индивидуального подхода к оптимизации. Мы организовали оптимизацию отдельных наиболее часто исполняющихся блоков код и остановились на наиболее стабильном варианте независимой оптимизации часто исполняющихся процедур приложения. Такая оптимизация на тестах SPEC CPU2000 показала прирост производительности на 8 тестах из 22 при 100 итерациях — наилучший результат состоял в шестикратном ускорении теста 173.applu.
Системы поиска чрезвычайно сложны в использовании, и мы пошли по пути создания Web-сервиса, предоставляющего графический вывод всех найденных данных, позволяющий запускать и управлять множеством параллельных поисков. Его ядром стала распределенная децентрализованная система на множестве разнородных машин, использующая очереди планирования.
В рамках работы был разработан инструмент настройки компиляторов и библиотек. Так, например, в приложении к двум функциям работы с разреженными матрицами математической библиотеки MKL удалось получить 18- и 60-проентный прирост производительности в продукте. А с помощью оптимизации векторизатора удалось повысить производительность тестов CPU2000 и CPU2006 на 10 и 40% соответственно.
***
Исследование способов оптимизации параметров компилятора чрезвычайно важно, учитывая распространение многоядерных микропроцессоров, предъявляющих все больше требований к и без того очень сложным современным компиляторам. Обнаруженная связь между свойствами выходного кода и применяемыми оптимизациями сулит большой потенциал повышения производительности. Выбор наиболее значимых оптимизаций позволяет сократить поиск, зато показывает, как выбор стратегии оптимизации влияет на результат компилирования, в частности на повышение производительности тестов CPU2000 и CPU2006.
Леонид Брусенцов (leonid.brusencov@intel.com) – аспирант Института автоматики и электрометрии СО РАН (Новосибирск).
