Хардкорный путь к производительности

Известный в обществе термин «производительность процессора» представляет собой объективный, вычисляемый параметр, который меряют во флопах. Впрочем, большинство измеряет его в гигагерцах, по наивности полагая, что это одно и то же. Термин «производительность кода» не знает никто, и сразу объясню почему.

Причина в том, что я его только недавно придумал и пока никому об этом не рассказывал. Однако производительность кода, так же как и производительность процессора, имеет объективные характеристики, которые поддаются измерениям. Эта статья — именно о производительности кода, выполняемого процессорным ядром.

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках ;).

Теперь серьезно. В современных процессорах основными преобразованиями являются действия над 32-битными числами, все остальное по большому счету экзотика. Поэтому учитывать будем главное — операции с 32-битными числами. Как ты думаешь, сколько 32-битных операций одновременно может выполнить ядро современного процессора?

Студент ответит — одну, его преподаватель подумает и скажет, что четыре, профессионал — что пока только двенадцать операций.

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12 RTT-шек. Максимум! Честно признаюсь, такого кода я раньше не писал, но в этой статье попытаюсь сделать над собой усилие.

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно, будет иметь производительность в 1 RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня, и интерпретаторы виртуальных машин. Не нужно считать, что показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1 RTT). В этом случае при 100%-й загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности. Другими словами, когда в диспетчере задач ОС Windows показывается максимальная загрузка процессора, его реальная производительность может варьироваться от 1 до 12 RTT. Увидев в окне производительности 100%-ю загрузку на каком-либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

Единственным критерием косвенной оценки работы процессорного ядра с максимальной производительностью может служить его энергопотребление и, как следствие, шум кулера. Вот если кулер зашумел, тогда да — загрузка пошла по максимуму. Впрочем, пора заканчивать с общими понятиями и переходить к суровой практике.

Традиционная реализация ГОСТ 28147—89

Я не профессионал в области информационной безопасности, но все же знаком с темой шифрования. Заняться конкретно симметричным поточным шифрованием меня подвигли разговоры с профессиональным криптографом, которого я глубоко уважаю. И, занявшись этой темой, я постарался сделать именно хорошо, и не просто хорошо, а еще и быстро, выполняя максимальное число операций за единицу времени. Другими словами, передо мной встала задача написать программный код с максимальным значением RTT. Криптографическое преобразование по ГОСТ 28147—89 используется для поточного шифрования информации в каналах связи и на дисковых накопителях.

В настоящее время повсеместно применяется программная реализация данного ГОСТа на РОН центрального процессора. В известных методах реализации ГОСТа вся секретная информация (ключи шифрования, блоки замен) размещаются в оперативной памяти. Это снижает надежность шифрования, поскольку, имея дамп оперативной памяти, можно полностью выявить все секретные элементы криптопреобразования. Кроме этого, метод имеет ограничения по быстродействию, обусловленные расположением основных объектов криптопреобразования в ОП и неполной загрузкой исполнительных устройств ALU. Современные процессоры, реализуя криптопроцедуру по известному методу, могут обеспечить скорость шифрования на уровне 40–60 мегабайт в секунду. И если уж разбираться до конца, то причиной низкого быстродействия и слабой защищенности криптопреобразования является программная реализация блока подстановок. Описание его в ГОСТе см. на рис. 1.

Рис. 1. Цитата из ГОСТа

По п. 1.2 ГОСТа этот блок реализует тетрадные (по четыре бита) перестановки в 32-битном слове, но архитектура процессора х86/64 и его система команд неспособна эффективно манипулировать тетрадами. Для программной реализации блока подстановок используют специальные таблицы в оперативной памяти, подготавливаемые на этапе инициализации криптофункции. Эти таблицы объединяют узлы замен смежных тетрад в байтовые таблицы размером 88 бит, таким образом, в оперативной памяти размещается четыре 256-байтных таблицы.

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в таблицах дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32-битного слова (следующая операция алгоритма преобразования по ГОСТу). Пример реализации ГОСТа по данному методу показан в приложении 1 (на диске). Информация блока подстановок является секретным компонентом криптофункции (как это сформулировано в ГОСТе, см. на рис. 2).

Рис. 2. Еще одна цитата из ГОСТа

Размещение этих таблиц с ключами блока подстановок в ОП противоречит требованиям ГОСТа (п. 1.7), поскольку секретная информация становится доступной для сторонних программ, работающих на вычислительной установке. Регулирующие органы, сертифицирующие в том числе и программные реализации шифрования по ГОСТу, на данное нарушение смотрят, мягко говоря, снисходительно. Если для размещения ключей в ОП еще требуется наличия «фигового листочка» — маскирования ключей операцией XOR, то для блоков замен в ОП ничего не требуется, они хранятся в открытом виде. Короче говоря, регулирующие органы пропускают такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТу (п. 1.7). И это несмотря на общеизвестные методы взлома шифров через съем дампа памяти… К вопросу хранения ключей и блоков замен во внутренних регистрах процессора мы вернемся чуть позже (есть красивое и быстрое решение), а пока мы будем хранить в ММХ-регистрах только ключи шифрования, это надежнее.

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1 RTT-шку. Теперь напишем код с производительностью 2 RTT-шки.

Многопоточная реализация ГОСТ 28147—89

Единственной возможностью ускорить криптопроцедуры в известном алгоритме является введение многопоточности. Смысл такого изменения реализации алгоритма заключается в том, чтобы обсчитывать сразу несколько блоков данных параллельно.

Большинство программистов подразумевает под параллельной обработкой исключительно работу нескольких процессорных ядер, синхронизированных через прерывания и семафоры в памяти. Однако существует и иной вариант параллельной обработки данных на одном-единственном ядре процессора. Поясню эту неочевидную мысль.

Современные процессоры имеют в своем составе как минимум два, а то и три-шесть арифметико-логических устройств. Эти АЛУ (FPU, блоки адресной арифметики и так далее) могут работать независимо друг от друга, единственное условие их параллельной работы — непересекающиеся программные объекты, которыми они оперируют. Другими словами, в командах, которые одновременно выполняют АЛУ, адреса памяти и номера регистров должны быть разными. Либо в общие регистры и адреса памяти, к которым обращаются различные исполнительные устройства процессора, не должно выполняться операций записи.

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра — планировщик, который просматривает исполняемый код форвардно, на глубину до 32–64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены. Большинство программных последовательностей, генерируемых автоматически (компиляторами), не могут загрузить все АЛУ и FPU, находящиеся в ядре процессора. В этом случае оборудование процессора простаивает, что значительно снижает его результирующую производительность. Разработчики процессоров это понимают и вводят режимы увеличения частоты ядра, когда оборудование используется не полностью. Также для этого предназначены системы гипертрейдинга, и эту систему я буду использовать для «прессования» кода по максимуму в дальнейшем.

Компиляторы, даже самые оптимизированные, и тем более — движки виртуальных машин, не могут формировать оптимизированный код с точки зрения быстродействия. Только программист с инженерными знаниями может написать такой оптимизированный код, причем инструментом для его написания является исключительно ассемблер.

Характерной иллюстрацией возможности выполнения нескольких независимых программных потоков на одном ядре процессора служит реализация ГОСТа, выполняемая в два потока на единственном ядре процессора. Идея кода проста: имеется два блока данных для шифрации/дешифрации, но одно ядро процессора, которое будет выполнять преобразование. Можно выполнить для этих двух блоков данных преобразование последовательно, так и делается до настоящего времени. В этом случае время, требуемое на выполнение преобразований, удваивается.

Но можно поступить и иначе: чередовать команды, относящиеся к обработке разных блоков данных. Графически эти варианты представлены на рис. 3.

Рис. 3. Чередование команд

На рисунке верхний пример показывает обычный порядок выполнения обработки двух независимых блоков данных. Сначала обрабатывается первый блок, затем процессор переходит к обработке второго блока. Естественно, результирующее время равно удвоенному времени, которое необходимо для обработки одного блока, а исполнительные устройства ядра процессора загружены не полностью.

Далее показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве. Чтобы такой программный код работал без простоев АЛУ, необходимо, чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX-регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков. Это, конечно, очень упрощенное объяснение принципа параллельного выполнения программных потоков на единственном ядре, реально все гораздо сложнее. На практике нужно учитывать конвейерную архитектуру исполнительных устройств, ограничения на одновременный доступ в кеш и блок регистров РОН, наличие узлов адресной арифметики, коммутаторов и много еще чего… Так что это — тема для профессионалов, которых можно пересчитать по пальцам… одной руки.

Метод параллельного шифрования эффективно реализуется только для 64-битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТа по данному методу показан в приложении 2 (на диске). Ясно, что данная реализация ГОСТа имеет производительность кода 2 RTT-шки. А теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение 1) составляет 352 такта, и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТа (приложение 2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6 ГГц.

Интересная получается картина: код содержит ровно в два раза больше команд, а выполняется всего на 15% дольше, но, думаю, читатели уже поняли причину этого феномена…

Теоретически код из второго примера должен выполняться за такое же количество тактов, что и код из первого примера, но узел планировщика разрабатывают хоть и инженеры фирмы Intel, но тоже люди, а мы все далеки от совершенства. Так что имеется возможность оценить эффективность их творения. Этот код будет работать и на процессоре AMD, и можно сравнить их результаты.

Если кто мне не верит на слово, то для таких неверующих на диске прилагаются тестовые программы с счетчиками тактов. Программы в исходных кодах, естественно на ассемблере, так что есть возможность проверить мои слова, а заодно и подсмотреть некоторые хитрости профессионального кодинга.

Использование SSE-регистров и AVX-команд современных процессоров для реализации ГОСТ 28147—89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТа на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE-регистрах.

На одном SSE-регистре можно разместить сразу две таблицы из 16 строк. Таким образом, четыре SSE-регистра позволят полностью разместить все таблицы замен. Единственным условием такого размещения является требование чередования, согласно которому тетрады одного байта должны помещаться в разные SSE-регистры. Кроме этого, целесообразно размещать младшие и старшие тетрады входных байтов соответственно в младших и старших тетрадах байтов SSE-регистров.

Эти требования обуславливаются оптимизацией под имеющийся набор AVX-команд.

Таким образом, каждый байт SSE-регистра будет содержать две тетрады, относящиеся к разным байтам входного регистра блока подстановок, при этом позиция байта на SSE-регистре однозначно соответствует индексу в таблице замены блока подстановки. Схема одного из возможных размещений узлов замены на SSE-регистрах показана на рис. 4.

Рис. 4. Схема одного из возможных размещений узлов замены на SSE-регистрах

Размещение секретной информации узлов замен на SSE-регистрах повышает защищенность криптопроцедуры, но полная изоляция этой секретной информации возможна при соблюдении следующих условий:

• Ядро процессора переведено в режим хоста гипервизора, и в нем принудительно отключен блок прерываний (APIC). В этом случае ядро процессора полностью изолировано от ОС и приложений, функционирующих на вычислительной установке.
• Загрузка SSE-регистров и изоляция вычислительного ядра производится до начала старта ОС, оптимальным является выполнение этих процедур с модуля доверенной загрузки (МДЗ).
• Программы криптопроцедур по ГОСТу размещаются в немодифицируемой области памяти вычислительной установки (либо БИОС, либо в флеш-памяти МДЗ).

Выполнение этих требований позволит гарантировать полную изоляцию и неизменность программного кода криптопроцедур и используемой в них секретной информации.

Для эффективной выборки из SSE-регистров тетрад используются имеющиеся в составе блоков FPU многовходовые байтовые коммутаторы. Эти коммутаторы позволяют осуществлять пересылки из любого байта источника в любой байт приемника, по индексам, находящимся в специальном индексном SSE-регистре. Причем параллельно выполняется пересылка для всех 16 байт SSE-регистра-приемника.

Имея узлы хранения подстановок на SSE-регистрах и многовходовый коммутатор в блоках FPU, можно организовать следующее преобразование в блоке подстановок (рис. 5).

Рис. 5. Преобразование в блоке подстановок

В этой схеме входной регистр в каждой тетраде задает адрес для соответствующего коммутатора, который по шине данных передает из накопителей узлов замены информацию в выходной регистр. Такую схему можно организовать тремя способами: • Создать соответствующий дизайн чипа, но это для нас фантастика. • Перепрограммировать микрокод и создать собственную процессорную команду для реализации этой функции на существующих процессорах — это уже не фантастика, но, к сожалению, нереально в нынешних условиях. • Написать программу на официальных командах AVX. Вариант пускай и не очень эффективный, но зато осуществим «здесь и сейчас». Так что этим и займемся далее.

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Ее первый операнд является приемником информации из коммутаторов, второй — источником, к которому подключены входы коммутаторов. Третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором; значение в нем задает номер направления, с которого коммутатор считывает информацию. Описание этой команды из официальной документации Intel см. на рис. 6.

Рис. 6. Цитата из официальной документации Intel

На рис. 7 приведена схема работы этой команды — изображена только половина SSE-регистров, для второй половины все аналогично.

Рис. 7. Схема команды

Коммутатор использует только младшие четыре бита для определения направления коммутации, последний бит в каждом байте используется для принудительного обнуления соответствующего байта приемника, но эта функция коммутатора в нашем случае пока не востребована.

Программа с выборкой тетрад через коммутаторы FPU была написана, но я даже не стал помещать ее в приложение — слишком убого. Иметь регистр размером 128 бит и использовать в нем только 32 бита — непрофессионально.

Как говорится, «Наш финиш — горизонт», поэтому выжимать так выжимать... будем прессовать и складывать в пакеты!

Это не игра слов, а суровая FPUшная реальность — регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка Р — пакет, которая ставится перед мнемоникой команды, и не менее магические буковки Q, D, W, B, которые ставятся в конце и объявляют, на какие части разбиты в этой команде регистры SSE.

Нас интересует пакетный режим с разбивкой SSE-регистра на четыре 32-битных блока; соответственно, все команды будут иметь префикс «P», а в конце — символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, то есть в параллель рассчитывать четыре блока данных.

Программа, реализующая этот метод, имеется в приложении 3, там же — все пояснения. Впрочем, прессовать так прессовать! В современных процессорах имеется как минимум два блока FPU, и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных. Такая программка была написана, и ее можно посмотреть в приложении 4, только смотреть нужно осторожно — можно слететь с катушек. Это, что называется, «код не для всех...».

Цена вопроса

Использование SSE-регистров для хранения узлов замены понятно — оно дает некую гарантию изоляции секретной информации, а вот смысл расчета самой криптофункции на FPU неочевиден. Поэтому были проведены замеры времени выполнения стандартных процедур по методу прямой замены в соответствии с ГОСТом для четырех и для восьми потоков.

Для четырех потоков была получена скорость выполнения 472 процессорных такта. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков со скоростью 392 мегабайта в секунду.

Как может заметить читатель, код в примере № 3 имеет производительность 4 RTT, а код в примере № 4 имеет производительность 8 RTT. В этих примерах на SSE-регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20%-е увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены с использованием универсальных AVX-команд, имеющихся как в процессорах Intel, так и в процессорах AMD. Если выполнить оптимизацию под процессор AMD, результат будет значительно лучше. Звучит поперек тренда, но тем не менее это правда, и вот почему: процессоры AMD имеют дополнительный набор команд, так называемое XOP-расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТа.

Имеются в виду команды логического пакетного сдвига байтов и пакетного циклического сдвига двойных слов. В примерах, приведенных в приложениях 3 и 4, используются последовательности универсальных команд, реализующих необходимое преобразование: в первом случае одна «лишняя» команда, а в другом случае сразу четыре лишних команды. Так что резервы оптимизации есть, и немалые.

Если речь зашла о дальнейшей оптимизации, нелишне помнить о наличии 256-битных регистров (YMM-регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только перспектива, на данный момент процессоры очень сильно замедляются, когда выполняют 256-битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM-регистрах выигрыша не дает. Но это только пока, на новых моделях процессоров, несомненно, будет увеличено быстродействие 256-битных команд, и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600–700 мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16 RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

Будем прессовать дальше. Наша цель — получить 12 RTT-шек, это можно сделать, выполняя команды одновременно на всех имеющихся в ядре процессора FPU. Их у Intel три штуки, мы же пока задействовали только два, так что вперед!

Опять встает вопрос количества регистров, их не хватает, чтобы раскрутить такой алгоритм. Но нам поможет режим гипертрейдинга. У процессорного ядра имеется второй набор регистров, доступных в режиме логических процессоров. Поэтому будем выполнять один и тот же код сразу на двух логических процессорах. В этом режиме исполнительных устройств у нас, конечно, не прибавится, но за счет чередования можно получить полную загрузку всех исполнительных устройств.

Рассчитывать на прибавку в 50% здесь не приходится, узким местом становится кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8 RTT), но он имеется в программных файлах. Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Intel, у AMD только два блока FPU на два процессорных модуля (аналог режима гипертрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать. Можно загнать процессорные модули «Бульдозера» в режим, аналогичный режиму гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE-регистрах и получить те же 12 RTT. Этот вариант я не проверял, но, думаю, на AMD код в 12 RTT будет работать более эффективно. Желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно?

Серьезный вопрос, но с простым ответом — это нужно всем. Скоро все мы подсядем на облака, будем там хранить и данные и программы, а там ой как хочется обустроить свой собственный, приватный уголок. Для этого придется шифровать трафик, и скорость криптопреобразования будет главным определяющим фактором комфортной работы в облаке. Выбор алгоритма шифрования у нас невелик — либо ГОСТ, либо AES. Причем, как это ни странно, встроенное в процессоры шифрование по AES-алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100–150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Проблема заключается в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь в виду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3–6 RTT практически нет, компиляторы вообще генерят код на уровне 1–2,5 RTT, а основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний что ассемблер, что какой-нибудь там Си-шарп — без разницы. Но не все так печально: в «сухом остатке» после недели бессонных ночей имеется новый алгоритм реализации ГОСТа, который грех не запатентовать. И заявки на патенты (целых три) уже оформлены и поданы, так что, господа коммерсанты, выстраивайтесь в очередь — женщинам и детям скидка.

• Комментарии