 |
|
|
|
Низкоуровневая оптимизация производительности на примере функции хэширования по ГОСТ Р 34.11-2012
Низкоуровневая оптимизация производительности В статье исследуются возможности низкоуровневой оптимизации производительности для архитектуры x86 на примере хеш-функции по ГОСТ Р 34.11-2012. Проанализированы результаты применения таких способов оптимизации, как использование оптимизирующих компиляторов, встроенных функций и ассемблерных вставок на распространенных микроархитектурах процессорах Intel и AMD. Показана существенная зависимость достигнутого с применением методов низкоуровневой оптимизации увеличения производительности от особенностей процессорной микроархитектуры. На основе полученных в ходе исследования результатов выделены характеристики оптимизируемых программ, которые необходимо учитывать при выполнении низкоуровневой оптимизации, охарактеризованы ее общие возможности и перспективы применения 1. Введение Несмотря на практическую актуальность, тематика низкоуровневой оптимизации зачастую вызывает дискуссионные вопросы: насколько оправданы усилия, затраченные наоптимизацию производительности в каждом конкретном случае? От чего зависит эффективность применения тех или иных методик и инструментов? Существует ли универсальная стратегия оптимизации? Ответ на первый вопрос сравнительно прост: минимальный уровень увеличения производительности, при котором усилия, затраченные на осуществление низкоуровневой оптимизации, имеют смысл, нельзя рассматривать отдельно от сферы применения разрабатываемого программного продукта. В качестве примера специализированных областей, в которых низкоуровневая оптимизация наиболее востребована, можно привести криптографические приложения, где область использования может варьироваться от встраиваемых систем (например, криптомаршрутизатор, одной из основных характеристик которого является скорость передачи шифрованного трафика) до криптографических библиотек и криптопровайдеров, используемых в пользовательских приложениях на различных процессорах в 32- или 64-битных режимах. Ответы на последующие вопросы невозможны без ознакомления с наиболее распространенными способами низкоуровневой оптимизации (использование оптимизирующего компилятора, применение встроенных функций компилятора – intrinsics, методика оптимизации «горячих точек» [17], использование ассемблерных вставок [4], реализация наассемблере). Вместе с тем разнообразие существующих методов оптимизации приводит к усложнению поиска оптимального способа (или их комбинации), необходимых для достижения наилучшего практического результата. Работы в области методологии низкоуровневой оптимизации позволяют сократить временные и финансовые затраты путем выбора способов увеличения производительности, соответствующих специфике оптимизируемого алгоритма. Целью статьи является рассмотрение методики осуществления низкоуровневой оптимизации с учетом предлагаемых в работе характеристик оптимизируемой программы наконкретном практическом примере – реализация хеш-функции по ГОСТ Р 34.11-2012 для архитектуры x86. В разделах 2-4 приводятся теоретические аспекты низкоуровневой оптимизации, формулируются классификационные критерии оптимизируемых программ и их связь сраспространенными методами оптимизации. В разделах 5-7 рассматривается пример низкоуровневой оптимизации хеш-функции с учетом выделенных классификационных критериев, описывается методика тестирования производительности и получения результатов, демонстрации и обсуждению которых посвящен раздел 8. 2. Декомпозиция общей задачи низкоуровневой оптимизации Классическим подходом к решению задач низкоуровневой оптимизации является выделение «горячих точек» – то есть наиболее ресурсоемких фрагментов программы – и ихдальнейшая оптимизация путем указания специальных директив компилятора или замена на фрагменты кода с применением встроенных функций компилятора или ассемблерные вставки. Однако само понятие «горячей точки» довольно условно – для вычислительного приложения таковыми могут являться лишь несколько отдельных циклов, а для объемного приложения с графическим интерфейсом пользователя, выполняющего, например, хеширование данных по ГОСТ Р 34.11-2012 в качестве «горячей точки» может рассматриваться весь алгоритм хеш-функции. Сформулируем более строгое определение оптимизируемого участка программы, на которое будем ссылаться в дальнейшем. Будем называть оптимизируемый участок кода программы, в котором локализована наибольшая часть вычислений, функциональным фрагментом (под ним может подразумеваться функция или процедура на языке высокого уровня, цикл или только его внутренняя часть). Функциональный фрагмент можно рассматривать как синоним устоявшегося впрограммировании и теории компиляторов понятия «базовый блок» [2]. Таким образом, при оптимизации с использованием техники ассемблерных вставок программисту приходится выполнять рутинные задачи компилятора по выделению базовых блоков, поскольку сам компилятор при выполнении оптимизации всего остального кода не анализирует содержимое ассемблерных вставок, что может нивелировать результат их применения. Теперь задача оптимизации производительности программного кода может быть декомпозирована следующим образом:
Решение первой задачи «ручным» способом затруднительно ввиду большого объема высокоуровневого исходного кода, который требуется проанализировать. Даже при ее успешном выполнении полученный код может потерять в гибкости модернизации и переносимости, а затраты на подобную оптимизацию (фактически «переписывание» кода на ассемблере) велики. Решение второй задачи вполне осуществимо для эксперта, что обусловлено сравнительно небольшим объемом высокоуровневого исходного кода, оптимальное отображение которого в эквивалентную последовательность машинных инструкций требуется найти. Как показывает практика, современные компиляторы достаточно эффективно справляются с данной задачей, однако возможность улучшения полученных компилятором решений все же существует [4]. Методы типа стохастической оптимизации позволяют увеличить производительность отдельных функциональных фрагментов на величину порядка десятков процентов [9]. Своеобразным компромиссом при решении обеих задач можно назвать использование встроенных функций компилятора (intrinsics). С одной стороны, их применение позволяет эксперту использовать наиболее оптимальные последовательности машинных инструкций для функциональных фрагментов, с другой стороны, за эффективное осуществление обмена данными между ними отвечает компилятор. 3. Оптимизация функциональных фрагментов Ускорение выполнения программы осуществляется современными процессорами в том числе за счет параллелизма на уровне команд и векторизации. Помимо распространенных векторных расширений команд MMX, SSE и SSE2, существуют и те, которые поддерживаются только некоторыми процессорами или определенными производителями (причем часть инструкций в них доступна лишь в 64-битном режиме). Вместе с тем с точки зрения удобства низкоуровневой оптимизации и повышения переносимости получаемых программ рекомендуется использование в функциональных фрагментах наиболее распространенных векторных расширений. Таким образом, при оптимизации функциональных фрагментов необходимо стремиться к сбалансированному выполнению следующих требований, заключающихся в минимизации:
Так как современные процессоры x86-64 используют довольно сложный набор команд, каждый оптимизированный функциональный фрагмент может быть записан на машинном языке многими способами. Предпочтение необходимо отдавать тем способам, которые более успешны с точки зрения динамического планирования и конвейеризации. На этапе оптимизации функциональных фрагментов становится возможным задействование микроархитектурных ресурсов увеличения производительности. Адаптацию функциональных фрагментов к микроархитектурным особенностям конкретного процессора можно осуществить, анализируя механизм выполнения команд на конкретной микроархитектуре [4], путем использования статических анализаторов или профилировщиков (Intel Architecture Code Analyzer, Intel VTune Amplifier, AMD CodeXL). Другой подход– тестирование имеющихся вариантов реализации оптимизированного функционального фрагмента и выбора наиболее производительного. Как правило, оптимизация функциональных фрагментов, удовлетворяющая приведенным выше четырем условиям, уже дает увеличение производительности на широком спектре микроархитектур. Но, как показано далее, такое утверждение верно не для всех программ. В ходе выполнения оптимизации возникает задача измерения скорости выполнения оптимизируемого функционального фрагмента программы, а также достигнутого уровня быстродействия для всего приложения в целом. С учетом внеочередного выполнения команд, состояния кэшей, взаимовлияния вычислительных ядер многоядерного процессора ивлияния сторонних приложений решение данной задачи нетривиально. Подход, в котором для сглаживания негативных последствий указанных факторов используется многократный вызов функционального фрагмента на исполнение, а для измерения производительности используется инструкция считывания счетчика тактов процессора, назовем микротестированием производительности [6]. В этом случае наблюдается пропускная способность участка машинного кода на полностью кэшированных данных. Микротестирование может быть выполнено с помощью статического анализатора. Длянаиболее распространенных архитектур Intel доступен Intel Architecture Code Analyzer, который не только оценивает ресурсоемкость участка кода в тактах, но и предоставляет аналитическую информацию (загрузку исполнительных блоков и граф выполнения). Назовем макротестированием производительности измерение увеличения времени быстродействия всей программы в секундах после модификации функционального фрагмента. Вданном случае имеют место высокая достоверность результата (так как функциональный фрагмент выполняется в реальных условиях), сравнительно высокие сложность ивременные затраты. При работе с функциональными фрагментами удобнее иметь дело с микротестированием – но как только будут получены данные об увеличении производительности, они должны быть подтверждены макротестированием. Оптимизируемые функциональные фрагменты могут быть классифицированы как «преимущественно векторизуемые» и «преимущественно конвейеризируемые». Для последних микроархитектурные особенности конкретного процессора имеют гораздо большее влияние на производительность, нежели поддерживаемый процессором набор расширений, особенно если выполняются условия:
Таким образом, для низкоуровневой оптимизации, эффективной на различных процессорах, в ряде случаев необходим подход, основанный на анализе микроархитектуры используемого процессора в целях последующего запуска соответствующих специализированных версий функциональных фрагментов. В качестве имеющихся средств можно привести функцию __builtin_cpu_is() компилятора GCC. Практику ускорения вычислений путем анализа имеющихся векторных расширений и запуска специализированных версий программы для наиболее функциональной изприсутствующих наборов инструкций можно считать уже устоявшейся и имеющей поддержку даже на уровне компилятора. Примером использования данного подхода являются следующие возможности современных компиляторов: опция /Qax компилятора ICL (генерация специальных версий машинного кода программы для указанных расширений и встраивание диспетчера, управляющего их запуском), функция __builtin_cpu_supports() компилятора GCC (определение имеющихся векторных расширений) и атрибут ifunc (динамическое «переопределение» вызываемой функции). Следует помнить, что данная стратегия эффективна для программы, подавляющее большинство функциональных фрагментов которой относится к «преимущественно векторизуемым». Как правило, это программы, выполняющие математические операции над вещественными числами. 4. Оптимизация обмена данными между функциональными фрагментами С точки зрения характеристик обмена данными между функциональными фрагментами и их свойств можно выделить указанные далее условные классы программ. По распределению удельного веса времени выполнения функциональных фрагментов в общем времени выполнения программы можно характеризовать как содержащие несколько функциональных фрагментов, на которые приходится основная доля вычислений, или как состоящие из большого числа функциональных фрагментов, примерно одинаковых повремени выполнения. Последние, очевидно, менее удобны для оптимизации посредством использования ассемблерных вставок и других аналогичных техник. По характеру активности функциональных фрагментов можно выделить программы с постоянной активностью функциональных фрагментов (например, алгоритмы, обрабатывающие однотипные блоки данных) и изменчивой активностью, то есть существенно зависящей от обрабатываемых данных – как правило, подобные программы чувствительны к техникам оптимизации типа Profile-guided optimization. С точки зрения локализации вычислений в пределах функциональных фрагментов можно выделить два класса программ, называемых далее «поточными» и «сегментированными». В поточной программе большинство вычислений осуществляется в функциональных фрагментах, время вычисления которых сопоставимо со временем на их вызов. Как правило, такая ситуация характерна для программ, в которых преобладают функции, выполняющие сравнительно быстрые однопроходные операции с данными (например, логические, атакже операции с памятью). При этом время «полезных» вычислений сопоставимо со временем накладных расходов на вызов самой функции (передача аргументов, выполнение пролога и эпилога функции и другие). Таким образом, для «поточной» программы оптимизация обмена данными между функциональными фрагментами становится существенным фактором увеличения быстродействия. Для сегментированной программы ситуация прямо противоположна – практически все вычисления локализованы в функциональных фрагментах, а затраты на их вызов несущественны по сравнению с общим временем выполнения. Примером алгоритма первого класса является рассматриваемая в настоящей работе хеш-функция (при первоначальном выделении функциональных фрагментов, см. раздел 6), примером второго – электронная подпись по ГОСТ Р 34.10-2012 (при выделении в качестве функциональных фрагментов операций целочисленной арифметики). Выполнение таких функциональных фрагментов, как умножение чисел величиной 256-1024 бит, занимает значительно больше тактов, чем «накладные расходы» на вызов функции с несколькими аргументами-указателями. Можно заметить, что множеству алгоритмов поточных с точки зрения низкоуровневой оптимизации условно соответствует множество потоковых алгоритмов в общепринятом смысле (потоковым называется алгоритм обработки данных, в котором входные данные представляют собой последовательность элементов, каждый из которых необходимо рассмотреть за малое число проходов). Хотя потоковые алгоритмы изначально проектируются с высокими требованиями к быстродействию, не стоит забывать, что актуальность низкоуровневой оптимизации в конечном счете определяется именно в контексте практического использования. Поскольку высокоуровневая структура программы (функции, циклы и другие функциональные фрагменты) в результате выполнения компилятором межпроцедурной оптимизации может не соответствовать фактической на языке машинных команд, то в качестве практического критерия отнесения программы к одному из указанных классов может выступать сравнение быстродействия двух версий анализируемой программы (функциональные фрагменты в которой вычленены в отдельные функции на языке высокого уровня), компилируемой с высоким уровнем оптимизации и принудительной подстановкой всех функций или подстановкой на усмотрение компилятора. Если быстродействие первой версии существенно меньше, чем второй, то это говорит о преимущественно поточном характере алгоритма. В сущности, поточные алгоритмы не являются удобными для низкоуровневой оптимизации, поскольку значительно ускорить их быстродействие «точечным» применением ассемблера не удастся. Для успешного выполнения низкоуровневой оптимизации поточный алгоритм необходимо сделать сегментированным путем выделения новых функциональных фрагментов, представляющих более крупные объединения уже существующих, что продемонстрировано далее на примере рассматриваемой хеш-функции. Выделенные классы названы выше условными, поскольку путем изменения разбиения программы на функциональные фрагменты можно варьировать ее характеристики в рамках предложенных классификационных критериев. Вместе с тем данные критерии позволяют указать такое направление структурных преобразований программы, которое позволит повысить эффективность ее оптимизации с помощью ассемблерных вставок и иных аналогичных методов. Существенным недостатком рассмотренных способов низкоуровневой оптимизации (за исключением применения оптимизирующих компиляторов) является их слабая степень автоматизации. Перспективные подходы, например метод двухэтапной компиляции, позволяют задействовать микроархитектурный ресурс повышения производительности безснижения степени автоматизации, однако для их применения требуется использование специальной информационной инфраструктуры [11, 13]. 5. Программные средства Наиболее удобный и распространенный способ низкоуровневой оптимизации – использование оптимизирующего компилятора. Заметим, что практически все современные компиляторы являются оптимизирующими и в общем случае выдают эффективный с точки зрения производительности код, поэтому оптимизацию выделенных функциональных фрагментов легче производить, «отталкиваясь» именно от решений, сгенерированных компилятором. В качестве оптимизирующих компиляторов использовались: компилятор языка С из GNU Compiler Collection 4.9.2 – далее компилятор GCC [10] и Intel C++ Compiler из набора Intel Parallel Studio XE 2015 – далее компилятор ICL [5]. Оба компилятора поддерживают создание программ как с универсальной оптимизацией (то есть исполняемых на любых процессорах x86), так и с оптимизацией для набора расширений конкретного процессора (опции –march=native для GCC и /QxHost для ICL). Для возможности выполнения компилятором интенсивной межмодульной оптимизации все функции помещались в один файл исходного кода на языке Си (опции -fwhole-program и/Qipo для компиляторов GCC и ICL соответственно). Выбор алгоритма хеширования по ГОСТ Р 34.11-2012 обусловлен тем, что вопросы его высокоуровневой оптимизации достаточно полно раскрыты в существующих работах [14], кроме того, имеются эффективные низкоуровневые реализации, с которыми можно проводить сравнение: в качестве примера использования встроенных функций компилятора была рассмотрена доступная по BSD-подобной лицензии реализация хеш-функции [3] (основанная на использовании встроенных функций компилятора – intrinsics – далее версия INT), ав качестве примера полностью ассемблерной реализации использованы данные работы [14]. Первоначально была разработана тестовая версия для проверки корректности реализации, в которой все функциональные фрагменты остаются реализованными на языке высокого уровня (далее SRC-версия), а затем версии с их реализацией в виде ассемблерных вставок с инструкциями архитектуры x86 и использованием векторных регистров и команд невыше уровня MMX или SSE (далее MMX и SSE разновидности версии inline – далее INL). Данная версия является результатом практического применения описанного выше подхода и подробно рассматривается в следующем разделе. Для SRC-версии были осуществлены два варианта компиляции: с встраиванием функций на усмотрение компилятора и полным встраиванием – спецификаторы static __attribute__ ((always_inline)) и __forceinline для компиляторов GCC и ICL соответственно. 6. Низкоуровневая оптимизация функции хеширования ГОСТ Р 34.11-2012 В соответствии с разделом 8 ГОСТ Р 34.11-2012 реализация хеш-функции предполагает три основных этапа: инициализация, многократное выполнение функции сжатия, дополнение оставшегося вектора исходных данных и финальные вычисления. Первоначально выделенные в программной реализации хеш-функции функциональные фрагменты представляли собой наиболее часто используемые функции второго этапа, такие как операция lps-преобразования из упомянутого выше стандарта, операция исключающего ИЛИ над 512-битными векторами – xor() и т.п. Данные функциональные фрагменты используются в высокоуровневых функциях сжатия и функции вычисления хеш-суммы. В INL-версии каждая ассемблерная вставка, реализующая соответствующий функциональный фрагмент, оформлялась в виде одноименной void-функции. Исследуемая хеш-функция обладает сравнительно небольшим числом «высоконагруженных» функциональных фрагментов и относится к блочным алгоритмам (постоянная активность функциональных фрагментов) и с этой точки зрения удобна для низкоуровневой оптимизации. С другой стороны, тестирование производительности согласно [6] показывает, что для большинства функциональных фрагментов, например xor(), количество тактов, требуемых длявызова функции (помещения аргументов в стек, выполнения пролога и эпилога функции), сравнимо или даже превышает время выполнения самой функции. В связи с этим становится понятным, почему при первоначальном выделении функциональных фрагментов отношение скоростей хеширования для SRC-версии, скомпилированной спринудительным полным встраиванием и подстановкой функций на усмотрение компилятора, оказывается существенно меньше единицы – 0,28 (процессор Intel Core2 Duo E5500, компилятор ICL, уровень оптимизации /O2). Эти факты, а также преобладание в выделенных функциональных фрагментах логических операций и операций загрузки значений из памяти, свидетельствуют о «потоковом» характере самой программы и «преимущественно конвейеризируемом» характере функциональных фрагментов. Первое указывает на необходимость выделения новых функциональных фрагментов на основе существующих, а второе – на необходимость рассмотрения различных вариантов их реализации для осуществления эффективной оптимизации на разных микроархитектурах. Для рассматриваемой хеш-функции найти оптимальное «совмещение» функциональных фрагментов не составляет особого труда. «Узким местом» является функция сжатия, содержащая 24 последовательных lps-преобразования. После выделения функции сжатия в качестве нового самостоятельного функционального фрагмента и изменения соответствующих атрибутов встраивания функций в пробной SRC-версии отношение скоростей хеширования, скомпилированное с полным встраиванием функций и встраиванием на усмотрение компилятора, оказывается близким к единице – 0,9. Оптимизируемая программа стала носить характер «сегментированной», то есть функциональные фрагменты выделены надлежащим образом, и теперь стоит переходить к их оптимизации, анализируя ассемблерный вывод компиляторов. Поиск опций компиляции для компилятора GCC, прикоторых максимально эффективны векторизация и внеочередное выполнение для наиболее ресурсоемкой функции lps-преобразования, не увенчался успехом, поскольку данный компилятор не смог задействовать векторные регистры при генерации машинного кода, и все его решения остались в рамках использования регистров общего назначения. Компилятор ICL смог сгенерировать решение, использующее векторные регистры. Лучшее решение, которое удалось обнаружить, имеет место при настройках компиляции суровнем оптимизации по умолчанию и архитектурным ограничением использования инструкций не выше SSE2. Но векторизация как таковая здесь не наблюдается, поскольку задействованы только младшие 64 бита 128-битных регистров XMM. Таким образом, останется возможность «ручной» доводки ассемблерной реализации, в результате которой, согласно данным Intel Architecture Code Analyzer, имеет место более равномерная загрузка портов, а также четырехкратное увеличение пропускной способности. Подробное рассмотрение этой оптимизации выходит за пределы задач настоящей статьи. Стоит заметить, что для ускорения вычислений применяют YMM-регистры и специализированные команды AVX [8]. Однако при реализации хеш-функции переход к регистрам YMM даже на уровне функциональных фрагментов типа xor() и использование специализированных команд табличной подстановки, например таких, как vpgatherqq в lps-функции, не приводит к увеличению производительности – данная команда требует восстановления регистра-маски и связывает одновременно три разных регистра YMM при выполнении. Поэтому реализация с использованием AVX-регистров в тестировании не использовалась. Множество вариантов реализации функциональных фрагментов хеш-функции можно ограничить рассмотренными версиями тестовых реализаций, поскольку существуют лишь два «принципиально» разных способа извлечения байтов в наиболее ресурсоемкой функции lps-подстановки – расширение 8-битных регистров посредством команды movzx (MMX иSSE разновидности версии INL) или использование инструкций pextrw (pextrd) – указанные далее версии INT. Оптимальная реализация на языке машинных команд остальных функциональных фрагментов не представляет особой сложности ввиду их простоты и опускается из рассмотрения. 7. Тестирование производительности В процессе тестирования были изучены реализации хеш-функции, полученные:
Целью включения данных реализаций в тестирование является демонстрация уровня производительности, которого можно достигнуть с помощью одного лишь оптимизирующего компилятора без использования иных способов низкоуровневой оптимизации;
Данные реализации включены в тестирование в целях демонстрации уровня производительности, которого можно достигнуть с применением методик использования встроенных функций компилятора и ассемблерных вставок соответственно. Применение компилятора GCC для версий INL и INT, так же как и уровень оптимизаций O0, не случайно – прииспользовании компилятора ICL и высоких уровней оптимизации наблюдается снижение характеристик производительности. Объяснение заключается в том, что попытки «помочь» оптимизирующему компилятору (особенно при использовании ассемблерных вставок) усложняют анализ программы последним и приводят к прямо противоположному результату. В силу специфики рассматриваемой хеш-функции (отсутствие команд условного перехода в выделенных функциональных фрагментах, работа с блоками данных постоянной длины512 бит) применение технологии Profile-guided optimization для обоих компиляторов не привело к увеличению производительности на величину более 2%. Итоговое тестирование проводилось путем измерения скорости хеширования случайного массива данных (усредненной по многим испытаниям таким образом, что абсолютная погрешность составляет порядка 1%). В большинстве случаев тестирование производилось на 64-разрядных операционных системах Windows 7. Поскольку размер данных существенным образом влияет на скорость хеширования, на первом этапе проводилось вычисление хеш-функции от всего объема тестовых данных – 8Мб, затем от его половины и т.д. – до размера блока. С уменьшением размера хешируемых данных скорость снижается, поскольку начиная с границы 4096-2048 бит в общем времени выполнения хеш-функции повышается удельный вес наименее оптимизированных процедур инициализации, дополнения вектора данных и финальных вычислений (представленных во всех версиях стандартными функциями memset и memcpy, а также кодом на языке высокого уровня). 8. Результаты тестирования на микроархитектурах Intel и AMD Рассмотренные решения (SRC, INT и INL) протестированы на процессорах микроархитектур Intel (Atom, NetBurst, Nehalem, Core, Sandy Bridge, Haswell, Skylake) и AMD (K8, K10, K10.5, Bulldozer, Piledriver). Устаревшие архитектуры были задействованы для того, чтобы максимально расширить «временную шкалу», необходимую для анализа динамики эффективности низкоуровневой оптимизации. Тестирование проводилось на процессорах для рабочих станций, серверов (Xeon) и портативных (с литерами B, M, P, U в названиях). Данные о спецификации микропроцессоров иподдерживаемых наборах векторных расширений команд получены с помощью утилиты CPU-Z. Представленные далее на рис. 1-3 результаты тестирования продемонстрированы вцелях ответа на следующие последовательные вопросы:
Конечно, исследуемая хеш-функция не претендует на роль «эталонного теста производительности», позволяющего дать исчерпывающие ответы на поставленные вопросы (хотя иоснована на использовании наиболее универсальных операций работы с памятью и логических операций), но вместе с тем она является удачным примером (или, соответственно, контр-примером) при поиске ответов на поставленные вопросы. На рис. 1 представлены графики скорости хеширования для тестовых реализаций на процессорах Intel микроархитектуры Nehalem.
Рисунок 1. Скорость хеширования на процессорах микроархитектуры Nehalem Близость графиков друг к другу позволяет сделать вывод: несмотря на различия в типе процессоров, рабочих частотах, размерах кэшей и других характеристиках, именно особенности организации конвейера, присущие конкретной микроархитектуре, являются наиболее существенным фактором, определяющим соотношение эффективности тестируемых способов низкоуровневой оптимизации (для рассмотренных микроархитектур Intel ситуация аналогична). Применительно к полученным данным для процессоров, выпускаемых компанией AMD, заметим, что процессоры AMD в целом демонстрируют еще большее «однообразие». Рассмотрим скорости хеширования для 32-битных реализаций, базирующихся на использовании разных наборов векторных инструкций (для каждой из четырех категорий выбраны наиболее производительные решения, если одна и та же группа расширений используется для разных тестовых программ – например, ICL-SSE2 или INL-SSE). Данные представлены на рис. 2.
Рисунок 2. Производительность реализаций хеш-функции на основе использования разных векторных расширений (по возрастанию значений категории SSE, SSE2) Тестирование показывает, что производительность хеш-функции «не пропорциональна» версии используемых векторных расширений команд (что является следствием еепринадлежности к классу «преимущественно конвейеризируемых» программ). Решения SSE2 или SSE в целом наиболее оптимальны. Более того, версии SSE3 или SSSE3, запускаемые тестовой программой ICL-Qax, демонстрируют в ряде случаев существенное снижение производительности. Решения INT и INL формально являются «кросс-микроархитектурными» поскольку используют универсальные приемы низкоуровневой оптимизации. Поэтому преимущество одного метода над другим на разных процессорах обусловлено особенностями микроархитектуры последних. Не углубляясь в особенности микроархитектуры, которыми обусловлены различия производительности тестируемых версий, заметим, что в ряде случаев процессоры AMD уступают по характеристикам быстродействия сопоставимым процессорам Intel, несмотря на более высокую тактовую частоту. Одна из основных причин заключается в более низкой ассоциативности кэша процессора (например, AMD FX-8320 – 4-way по сравнению с Intel i5-4440 – 8-way), что приводит к снижению эффективности кэширования, поскольку одни и те же кэш-линейки вынуждены попеременно замещать свое содержимое данными из разных участков памяти [4]. На рис. 3 показаны приросты производительности (обозначим α) в процентах (относительно лучшего из решений компиляторов: GCC, ICL-SSE2 и ICL-Qax) для методов ассемблерных вставок и использования встроенных функций. Для каждой микроархитектуры выбран наиболее производительный процессор из участвовавших в тестировании. Из приведенных данных следует, что фактор зависимости от особенностей микроархитектуры является существенным. Потери в случае использования программы, «неподходящей» для конкретной микроархитектуры, могут достигать порядка 25% для процессоров Intel и 61% для AMD (от максимального наблюдаемого уровня производительности на данной микроархитектуре; архитектуры NetBurst и K8 на рис. 3).
Рисунок 3. Процентные приросты производительности INL- и INT-решений относительно лучшего из SRC-решений для процессоров Intel (a) и AMD (b) в 32-битном режиме При этом усредненный по всем рассмотренным микроархитектурам прирост производительности (относительно решений компиляторов) для INL-версий составил в среднем 40%, для INT-версий – 12%. Комбинация этих методов дает прирост около 44% и позволяет избежать потерь в указанных выше пределах для отдельных микроархитектур. Отставание метода вставок на архитектурах Atom, Core и Nehalem компенсируется более существенным выигрышем на иных архитектурах, в особенности AMD. Практическая значимость проведенного сопоставления несколько условна, поскольку в анализе не учитывается реальное количество используемых на сегодняшний день процессоров указанных микроархитектур. Вместе с тем сравнение с применением усредненного по рассмотренным микроархитектурам прироста производительности вполне приемлемо для общей оценки качества реализаций. На рис. 4 представлена динамика эффективности низкоуровневой оптимизации, выраженной как отношение производительности лучшего из INL- или INT-решений к лучшему изрешений компиляторов (обозначим β), по мере появления новых микроархитектур.
Рисунок 4. Эффективность низкоуровневой оптимизации для процессоров Intel (a) и AMD (b) в 32-битном режиме Линейные тренды показывают уменьшение эффективности оптимизации по мере развития микроархитектур. Это может быть объяснено повышением эффективности динамического планирования и иных технологий увеличения производительности и большей «взаимной адаптацией» новых процессоров и современных компиляторов. Таким образом, для поколений процессоров Intel старше Skylake можно прогнозировать прирост быстродействия от техник «ручной» низкоуровневой оптимизации (методы, аналогичные INL) менее 20%. Это меньше порогового значения, при котором усилия, потраченные на оптимизацию, имеют смысл согласно [12]. Более высокие значения показателя эффективности низкоуровневой оптимизации для процессоров AMD могут быть объяснены тем, что в отличие от процессоров Intel, для которых был использован компилятор ICL, при вычислении данного показателя использованы решения компилятора GCC. Применение специализированных компиляторов, поддерживающих оптимизацию для данных микроархитектур, например AMD Open64, может снизить данный показатель, но вряд ли изменит тенденцию. Ответ на вопрос о том, почему даже в пределах одной архитектуры ускорение вычислений, полученное в результате низкоуровневой оптимизации, варьируется в столь широких пределах (от 1,16 до 3,15 раза), заключается в самом их устройстве – CISC-процессоры x86 начиная с Intel486DX производятся с использованием RISC-ядра, таким образом, непосредственно перед исполнением сложные CISC-инструкции преобразуются в более простой набор внутренних инструкций RISC [16]. Исходя из этого можно объяснить, почему разные наборы высокоуровневых инструкций, выполняющих, по сути, одни и те же операции, обладают различной производительностью– последняя зависит от успешности упомянутого выше преобразования CISC-инструкций, которое, в свою очередь, влияет на успешность динамического планирования иконвейеризации. Очевидно, что у современных процессоров рассмотренный механизм более совершенен, отсюда и наблюдаемое уменьшение эффективности низкоуровневой оптимизации по мере появления новых микроархитектур. Также следует заметить, что при публикации данных, посвященных вопросам низкоуровневой оптимизации, необходимо осуществлять контроль зависимости достигнутого увеличения производительности от особенностей микроархитектуры конкретного процессора. Например, вопрос о том, насколько переносимы на другие процессоры оптимизационные решения, полученные в работах [1, 7], остается открытым. Для полноты картины необходимо ознакомиться с результатами в 64-битном режиме – быть может, при его использовании будет наблюдаться столь высокая производительность, чторабота по оптимизации для архитектуры x86 покажется напрасной? На рис. 5 приведено сравнение характеристик производительности для лучших из 64-битных решений INT-SSE2 или INT-SSE4.1 и лучшего из 32-битных решений SRC или INL (данные упорядочены по возрастанию значений категории х64).
Рисунок 5. Сравнение наиболее производительных реализаций для 64- и 32-битного режимов Существенным преимуществом в производительности 64-битные решения по сравнению с 32-битными не обладают, хотя и являются наиболее эффективными из рассмотренных длямногих процессоров. Вместе с тем количество регистров общего назначения, SSE и AVX, для архитектуры x86-64 в два раза больше (16 вместо 8) по сравнению с 32-разрядной архитектурой x86. Благодаря этому на первой достигается большее быстродействие – поэтому тесты производительности коммерческих программ [15] и оригинальных ассемблерных решений [14], какправило, даются именно для нее. Отдельного упоминания заслуживает реализация, приведенная в работе [14], отмеченная на рис. 5 треугольным значком (94 Мб/с) для процессора Intel Core i7 920. Ее можно рассматривать как пример низкоуровневой оптимизации, использующей экстремальный прием повышения производительности – почти все константные и промежуточные значения находятся в регистровом файле, обмен с памятью минимален. Подобные решения наиболее актуальны для встраиваемых и иных, требовательных к производительности систем, ноони возможны не для всех оптимизируемых алгоритмов. 9. Заключение Низкоуровневая оптимизация все еще является актуальным инструментом повышения производительности программ. Для ряда специализированных алгоритмов (аналогичных рассмотренной хеш-функции) ускорение от ее применения даже для современных процессоров может составлять более 20% по сравнению с уровнем производительности решений, сгенерированных оптимизирующим компилятором. Вместе с тем наблюдается тенденция уменьшения эффекта от низкоуровневой оптимизации для новых процессоров. Их алгоритмы динамического планирования имикроархитектура способствуют улучшению производительности в том числе и неоптимального машинного кода. Таким образом, наибольшего эффекта от низкоуровневой оптимизации следует ожидать именно для встраиваемых систем, поскольку процессоры для них обладают, как правило, не самой последней микроархитектурой. Немаловажным аспектом применения низкоуровневой оптимизации является зависимость достигнутого увеличения производительности от особенностей микроархитектуры конкретного процессора (до 60% от максимального наблюдаемого уровня производительности на данной микроархитектуре). С одной стороны, это может рассматриваться как негативное явление, способное нивелировать усилия, потраченные на низкоуровневую оптимизацию для отдельных микроархитектур, с другой – как своеобразный ресурс увеличения производительности, если требуется повышение характеристик быстродействия для широкого спектра микроархитектур ценой «точечной» адаптации оптимизируемого алгоритма для каждой из них. Поскольку для многих микроархитектур инструменты типа Intel Architecture Code Analyzer отсутствуют, для анализа быстродействия преимущественно конвейеризируемых алгоритмов можно выполнить тестирование нескольких вариантов реализации оптимизированных функциональных фрагментов – по результатам настоящей статьи вполне достаточно одного процессора для каждой учитываемой микроархитектуры. Более того, для стабильного прироста производительности вовсе не обязательно иметь столько же версий оптимизированной программы, сколько и учитываемых микроархитектур – длярассматриваемой хеш-функции оказалось достаточным использование всего двух версий INL-SEE и INT-SSE2. В общем случае при выполнении низкоуровневой оптимизации необходимо контролировать специфику программы (состоит ли она из преимущественно конвейеризируемых иливекторизуемых функциональных фрагментов и т.д.) и применять соответствующую стратегию увеличения производительности. Подводя итог обзору методов низкоуровневой оптимизации, можно сказать, что техника оптимизации с использованием ассемблерных вставок хотя и обладает большими возможностями использования различных машинных команд по сравнению с методом применения встроенных функций компилятора, но вместе с тем для своей эффективности требует структурных преобразований оптимизируемой программы в соответствии с выделенными классификационными критериями. Низкоуровневая оптимизация с полностью ассемблерной реализацией сохраняет свою актуальность для тех программ, в которых возможны экстремальные методы увеличения производительности, основанные на специфике конкретного алгоритма. Одним из актуальных направлений повышения эффективности решений современных оптимизирующих компиляторов по результатам проведенных исследований видится поддержка реализации «кросс-микроархитектурных» решений для программ, состоящих из преимущественно конвейеризируемых функциональных фрагментов – по аналогии с тем, как это уже реализовано для приложений, быстродействие которых зависит преимущественно от функциональности доступных векторных расширений (например, опция /Qax компилятора ICL).
Ключевые слова: оптимизация, ускорение вычислений, ассемблер, микроархитектура процессора, компиляция. The low-level performance optimization on the example of the hash function GOST R 34.11-2012 Severin P.A., graduate student of Radio Physics and Electronics of the Syktyvkar State University named after P. Sorokin., Syktyvkar, pav9687@yandex.ru Golchevskiy Yu.V., Ph.D., associate professor of the department of information security behalf of the Syktyvkar State University named after P. Sorokin., yurygol@mail.ru Abstract: The article concerns the possibilities of a low-level performance optimization for x86 architecture on the example of the GOST R 34.11-2012 hash function. The results of applying optimization methods such as optimizing compilers using, built-in functions and assembler code inserts on the common microarchitectures for Intel and AMD processors were analyzed. The article contents a demonstration of the achieved performance increase using a low-level optimization techniques significant dependence from the processor microarchitecture features. On the basis of results obtained in the study the optimized programs characteristics that needed to be considered when performing a low-level optimization were determined, its general features and application prospects were described. Keywords: Optimization, computational acceleration, assembler, processor micro-architecture, compilation. |
СЕВЕРИН П.А., аспирант кафедры радиофизики и электроники Сыктывкарского государственного университета имени Питирима Сорокина, г. Сыктывкар, 
Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
