Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода


Скачать 249.9 Kb.
НазваниеПока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода
страница1/3
Дата публикации06.05.2013
Размер249.9 Kb.
ТипДокументы
userdocs.ru > Информатика > Документы
  1   2   3
«Производительность кода»

(на примере ГОСТ 28147-89 симметричного шифрования)
Наверняка все слышали о термине «Производительность процессора», этот объективный, вычисляемый параметр меряют в Флопах, но большинство измеряет его в Гигагерцах, по наивности полагая что это одно и тоже. Термин «Производительность кода» неизвестен никому, и сразу объясню почему. Причина в том, что я его только недавно придумал и пока никому об этом не рассказывал. Однако «Производительность кода», также как и «Производительность процессора» имеет объективные характеристики, которые поддаются измерениям. Статья именно о производительности кода выполняемого процессорным ядром.

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

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

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

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

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно будет иметь производительность в 1RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня и интерпретаторы виртуальных машин.

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

Другими словами при максимальной загрузке процессора, показываемого например в диспетчере задач ОС Windows, его реальная производительность может варьироваться от 1RTT до 12RTT. Увидев в окне производительности 100% загрузку на каком либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

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

Но хватит общих понятий, как говорится, «короче, Склифасовский».


^ Традиционная реализация ГОСТ 28147-89
Не являясь профессионалом в области информационной безопасности, всё же знаком с темой шифрования. Для меня эта тема близка с точки зрения программиста, который, как и самый первый программист, когда было только слово (информация), после дня (ночи) тяжелого труда, усталый, смотрит на результат своего труда и думает: «это хорошо»….

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

В настоящее время повсеместно применяется программная реализация данного ГОСТ на РОН центрального процессора. В известных методах реализации ГОСТ вся секретная информация (ключи шифрования, блоки замен) размещаются в оперативной памяти.

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

Кроме этого, метод имеет ограничения по быстродействию, обусловленные расположением основных объектов криптопреобразования в ОП и неполной загрузкой исполнительных устройств ALU. Современные процессоры, реализуя криптопроцедуру по известному методу могут обеспечить скорость шифрования на уровне 40-60 мегабайт в секунду.

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

Вот как он описан в официальном документе ГОСТ 28147-89 :

По п. 1.2. ГОСТ этот блок реализует тетрадные (по четыре бита) перестановки в 32битном слове, но архитектура процессора х86/64 и его система команд не способна эффективно манипулировать тетрадами.

Для программной реализации блока подстановок используют специальные таблицы в оперативной памяти подготавливаемые на этапе инициализации криптофункции. Эти таблицы объединяют узлы замен смежных тетрад в байтовые таблицы размером 8х8 бит, таким образом в оперативной памяти размещается четыре 256 байтных таблицы.

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

Пример реализации ГОСТ 28147-89 по данному методу показан в приложении №1.
Информация блока подстановок является секретным компонентом криптофункции, вот как это сформулировано в официальном документе ГОСТ 28147-89:

Размещение этих таблиц с ключами блока подстановок в ОП противоречит требованиям ГОСТ 28147-89 п.1.7., поскольку секретная информация становится доступной для сторонних программ, работающих на вычислительной установке. ФСБ, сертифицирующая в том числе и программные реализации шифрования по ГОСТ 28147-89 на данное нарушение смотрит мягко говоря снисходительно. Если для размещения ключей в ОП ФСБ еще требует наличия «фигового листочка», в виде маскирования ключей операцией XOR, то для блоков замен в ОП ничего не требуется, они хранятся в открытом виде.

ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТ 28147-89 п.1.7..

И это не смотря на общеизвестные методы взлома шифров через съём дампа памяти….

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

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

^ Многопоточная реализация ГОСТ 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, так что можно сравнить их результаты.

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

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

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

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

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

Схема одного из возможных размещений узлов замены на SSE регистрах показана на рисунке:



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

- Ядро процессора переведено в режим Хоста Гипервизора и в нем принудительно отключен блок прерываний (APIC). В этом случае ядро процессора полностью изолировано от ОС и приложений, функционирующих на вычислительной установке.

- Загрузка SSE регистров и изоляция вычислительного ядра производится до начала старта ОС, оптимальным является выполнение этих процедур с модуля доверенной загрузки (МДЗ).

- Программы криптопроцедур по ГОСТ размещаются в немодифицируемой области памяти вычислительной установки (либо БИОС, либо в флеш-памяти МДЗ).
  1   2   3

Похожие:

Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconКурсовая работа По дисциплине «Логистика» на тему: «Штриховые коды:...
«Штриховые коды: понятие, виды, области применения в логистике. Структура и порядок применения штрихового кода ean-13»
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconЗаявка по набору персонала
Совместная корпоративная разработка программного кода, доработка по, поддержка пользователей
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconТретья волна
Невидимый клин Значение рынка Сексуальный раскол Глава Разрушение кода Стандартизация Специализация Синхронизация
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconПо данным научных исследований, употребление кофеинсодержащих напитков...
В результате, производительность труда и работоспособность людей, употребляющих кофе, может значительно снижаться и влиять на эффективность...
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconБарселона – взлом дофаминового кода
Был интересен сам процесс, а главное – интересна сама микроскопическая надежда на то, что «Милан» сможет опровергнуть сложившуюся...
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconСистем
Идентификатором определенного действия микропроцессора является двоичный код-команда. После ввода такого кода в микропроцессор устройство...
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода icon1 Методология процедурно-ориентированного программирования
Выбор платформы и операционной системы, как правило, не являлся серьезной проблемой. А сопровождение программы, хотя и было сопряжено...
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconМатериал: 100 книг культурного кода в современной России Задача материала
Грубо говоря, есть ли у нас общий язык, и из чего он складывается сегодня. Выяснить это мы решили на материале книг, которые этот...
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода iconОсобенности реализации языка uml в case-инструментарии Rational Rose 98/2000
Поддержка возможности автоматической генерации программного кода на основе предварительно разработанной концептуальной схемы оказалась...
Пока диапазон параметра «производительность кода» может варьироваться от 1rtt до 12rtt, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода icon3 Организация памяти в микропроцессорных системах
Информацию в ячейки памяти можно записывать и считывать. Считывание информации из ячейки памяти не нарушает содержимого последней....
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
userdocs.ru
Главная страница