04 марта 2016г.
Одной из проблем разработки программного обеспечения для реализации криптографических алгоритмов является повышение их быстродействия. Актуальность программной оптимизации не вызывает сомнений в таких областях, как создание криптографических библиотек, разработка средств защиты информации и других подобных.
Оптимизация производительности кода может быть рассмотрена с точки зрения баланса времени разработки программы и скорости ее выполнения. Увеличение времени разработки необходимо для получения программ с большим быстродействием и наоборот. Поэтому наиболее эффективным представляется подход, который состоит в оптимизации лишь тех участков кода, на которые приходится наибольшая часть вычислений. Будем называть такой участок кода функциональным фрагментом – под ним может подразумеваться функция или процедура на языке высокого уровня, цикл или только его внутренняя часть.
Задача трансляции программы, составленной на исходном языке высокого уровня, в соответствующую программу на низкоуровневом языке (машинный код) на современном этапе развития вычислительных технологий решается с помощью компиляторов.
Несмотря на множество прогрессивных технологий, используемых компиляторами для кодогенерации, функциональная сложность современных процессоров, большое количество машинных инструкций и т.д. приводит к тому, что детерминированные (то есть такие, последовательность действий в которых однозначно определена) алгоритмы кодогенерации не в состоянии проанализировать все варианты ускорения программы в ходе ее трансляции в машинный код. Альтернативой является использование случайности в процессе поиска наиболее эффективного отображения высокоуровневого кода в эквивалентную последовательность машинных кодов, что может быть охарактеризовано общим термином «стохастическая оптимизация».
В популяризации данного термина значительную роль сыграла работа [4]. Необходимо заметить, что под оптимизацией в данной статье понимается именно оптимизация кодогенерации (то есть создания такого же эффективного кода на ассемблере, как и разработанного экспертом со знанием инструкций целевой платформы), а не оптимизация, как процесс поиска оптимума (максимума или минимума) исследуемой функции.
«Случайность» может быть использована на различных этапах компиляции. Обзор современных работ по данной тематике [2-4] позволяет классифицировать имеющиеся результаты по уровню абстрагирования от высокоуровневого кода, на котором имеет место применение стохастических приемов:
1) Исходный высокоуровневый код [2];
2) Язык внутреннего представления компилятора [1, 3];
3) Машинный код (ассемблер) [4].
В первом случае эффект оптимизации достигается путем изменения последовательности выполнения однотипных операций на языке высокого уровня (например, меняется порядок вычисления группы зависимых друг от друга выражений, а также порядок выполнения арифметических действий в них, происходит добавление или удаление промежуточных переменных и т.д., при этом данные преобразования не нарушают корректности расчетов). Для изменения исходного кода и поиска его оптимального преобразования в [2] использовались генетические алгоритмы.
Практически каждый новый набор операций на языке высокого уровня заставляет компилятор по-новому выполнять размещение переменных в регистрах, изменять последовательность машинных инструкций (что оказывает влияние на конвейеризацию вычислений). В конечном счете, может быть обнаружена такая последовательность операций на языке высокого уровня, которая при компиляции покажет существенно большую эффективность для конкретной архитектуры процессора по сравнению с первоначальной версией исходного кода.
Наиболее узким местом данного подхода является сложность автоматизации генерации версий высокоуровневого исходного кода. Вполне возможно, что не для каждой практической задачи подобная автоматизация осуществима. Приведенные в [2] примеры показывают увеличение производительности от единиц до нескольких десятков процентов на отдельных процессорных архитектурах.
Во втором случае эффект оптимизации достигается в большей мере за счет преобразований кода на языке внутреннего представления компилятора (например, Register Transfer Language для компилятора GCC). Повлиять на этот процесс можно путем изменения опций компиляции, количество которых может составлять от нескольких десятков до нескольких сотен. При этом имеет место следующая тенденция: чем более качественный код генерирует компилятор, тем меньше опций доступно для изменения пользователю, так как компилятор осуществляет их настройку самостоятельно. В работе [3] использовался компилятор 4.7.3-1ubuntu1, в качестве тестовых программ для оптимизации использовались быстрое преобразование Фурье, умножение матриц и т.п., локализованные в отдельных файлах. Увеличение производительности составило от 15% до 282%.
В последнем случае исходный высокоуровневый код используется главным образом для проверки алгоритмической корректности последовательно (каждый достигнутый результат в определенной степени зависит от предыдущего) генерируемого прямо на языке машинных команд кода. Генерация кода осуществляется случайным образом, что дает возможность открывать алгоритмически совершенно новые решения, соответствующие высокоуровневому исходному коду. Это единственный из описанных методов, который теоретически способен найти оптимальное решение с учетом всех инструкций конкретной платформы. Использован оптимизационный алгоритм Markov Chain Monte Carlo (MCMC). Максимальное увеличение производительности порядка нескольких десятков процентов по сравнению с результатами оптимизирующих компиляторов.
Сравнительными недостатками данного метода являются сложность его реализации, высокие требования к вычислительным ресурсам (для генерации тестовых вариантов использован кластер из 40 двухъядерных AMD Operton 1,8 ГГц), а также применимость только к небольшим не содержащим циклов функциональным фрагментам программы.
Метод, приведенный в [3], обладает наиболее интересным соотношением достигнутого уровня увеличения производительности и сложности реализации. Вместе с тем при данном подходе имеют место некоторые моменты, негативно влияющие на оптимизацию кодогенерации:
1) Опции кодогенерации применяются ко всему файлу высокоуровневого исходного года (всем содержащимся в нем процедурам и циклам), хотя разные функциональные фрагменты могут требовать разных опций для наибольшей производительности (например, одни циклы должны быть развернуты полностью, а другие всего на 2 итерации).
2) Размер пространства опций компилятора хоть и значителен, но не сопоставим с числом возможных вариантов отображения высокоуровневого исходного кода в эквивалентную совокупность машинных кодов.
Для преодоления приведенных затруднений предложен и исследован следующий подход:
1) Опции кодогенерации применяются к функциональным фрагментам программы, оформленным в одну единицу трансляции (функцию) и содержащим не более нескольких вложенных циклов;
2) Для увеличения пространства поиска использованы не только опции оптимизации, но и опции кодогенерации со значениями, как большими, так и меньшими рекомендуемых – при меньших значениях, как правило, генерируется худший с точки зрения производительности код, однако совокупность побочных эффектов от отдельных «недостаточно оптимизированных» частей кода может привести к обратному результату.
Ввиду того, что в работе рассматриваются криптографические вычисления (работа с целыми числами), опции компилятора, ответственные за использование вещественных чисел, из рассмотрения исключались.
Предложенные выше улучшения, необходимость поддержки современных компиляторов Intel C++ Compiler из набора Intel Parallel Studio XE 2015 (далее компилятор ICL), GNU Compiler Collection 4.9.2 (далее компилятор GCC) и актуальных процессорных архитектур, а также специфика исследуемой предметной области (криптографические вычисления) побудили авторов статьи к разработке собственного решения для использования техники стохастической оптимизации на уровне языка внутреннего представления компилятора применительно к исследованию комплексного подхода к ускорению криптографических вычислений [6] – Программный комплекс оптимизации кодогенерации компиляторов, далее Комплекс (свидетельство о регистрации программного продукта ЦИТиС №61507167008, 16.07.2015).
Комплекс использует алгоритм глобальной оптимизации «метод имитации отжига». Исследуемые функциональные фрагменты помещались в специальную функцию в файл исходного кода на языке С, компилировались с помощью составленной с применением алгоритма отжига строки опций в объектный файл, который затем линковался в исполняемый файл, содержащий код для тестирования производительности.
Для исследования возможного прироста быстродействия были выбраны функциональные фрагменты кода, реализующие следующие операции:
1) Двоичное исключающие ИЛИ для двух аргументов 512 бит;
2) Двоичное исключающие ИЛИ для двух аргументов 512 бит с записью результата в третий аргумент;
3) Функция, реализующая арифметический примитив для 512-битных чисел s = s – bd, где d – 32-битное число;
4) Умножение двух 512-битных чисел;
5) Возведение в квадрат 512-битного числа.
Первые два функциональных фрагмента тривиальны и включены в рассмотрение в целях тестирования, поскольку оптимальные для выполнения данных операции последовательности SSE инструкций очевидны. Компилятор ICL находит оптимальный набор SSE инструкций для данного случая уже при стандартных опциях компиляции, компилятор GCC также оказался способен найти оптимальные решения в ходе работы Комплекса.
Для последующих функциональных фрагментов оба компилятора не смогли найти решений с использованием регистров SSE.
По сравнению со стандартными опциями оптимизации, для компилятора GCC увеличение уровня производительности при решении задач 3)-5) составляло до 25%. Однако и в этом случае быстродействие было существенно меньше, чем у компилятора ICL c опциями оптимизации по умолчанию. Решения данного компилятора удавалось улучшить с помощью работы Комплекса лишь на несколько процентов.
Для алгоритма умножения компилятор ICL смог найти оригинальную перестановку 32-битных слов в одном из множителей, что привело к увеличению быстродействия практически на треть по сравнению с лучшим решением GCC.
Алгоритмы возведения в квадрат могут быть выполнены за практически вдвое меньшее время за счет замены половины операций умножения операциями сдвига и уменьшения количества обращений к памяти. Однако оба компилятора данных оптимизаций не произвели, быстродействие оказалось таким же, как и перемножение двух произвольных чисел.
Можно сделать вывод, что на данный момент применение технологии стохастической оптимизации уровня языка внутреннего представления компилятора для функциональных фрагментов не дает результатов, существенно превышающих значение минимального порога, при котором затраты на оптимизацию кода имеют смысл – 20% согласно [5].
Для улучшения результатов оптимизации для увеличения производительности имеет смысл воспользоваться более специализированными компиляторами (например, AMD Open64 4.5.2), или осуществлять стохастическую оптимизацию используя технологии, условно расположенные между 2 и 3 уровнем в приведенной выше классификации.
Список литературы
1. ACOVEA (Analysis of Compiler Optimizations via an Evolutionary Algorithm) [Электронный ресурс] URL: https://directory.fsf.org/wiki/Acovea (дата обращения: 27.08.2015).
2. Andrew Kensler, Peter Shirley. Optimizing Ray-Triangle Intersection via Automated Search [Электронный ресурс] URL: http://www.cs.utah.edu/ ~aek/research/triangle.pdf (дата обращения: 27.08.2015).
3. J. Ansel. OpenTuner: An Extensible Framework for Program Autotuning / J. Ansel, Sh. Kamil, K. Veeramachaneni, J. Ragan-Kelley, J. Bosboom, Una-May O'Reilly, S. Amarasinghe [Электронный ресурс] URL: .http://opentuner.org/ publications (дата обращения: 27.08.2015).
4. Schkufza E. Stochastic Superoptimization. / Eric Schkufza, Rahul Sharma, Alex Aiken [Электронный ресурс] URL: http://arxiv.org/abs/1211.0557 (дата обращения 27.08.2015).
5. Касперски К. Техника оптимизации программ. Эффективное использование памяти. – СПб.: БХВ- Петербург, 2003. – 464 с
6. Северин П.А., Гольчевский Ю.В. Комплексный подход к ускорению криптографических вычислений // Информационные технологии в управлении и экономике [Электронный ресурс] URL: http://itue.ru/?p=286 (дата обращения 27.08.2015).
