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

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

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

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

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

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра - планировщик, который просматривает исполняемый код форвардно, на глубину до 32-64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

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

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

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

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

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

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

Чтобы такой программный код работал без простоев АЛУ, необходимо чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

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

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

Ясно, что данная реализация ГОСТа имеет производительность кода 2RTT-шки, а теперь посмотрим, как это сказывается на времени выполнения.

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

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

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

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

Дата добавления: 2015-07-08