OpenMP на многоядерном процессоре и криптография

Практический пример использования

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

Использование OpenMP должно приводить к увеличению производительности за счет того, что программа (по крайней мере, её параллельные участки) выполняется не на одном процессоре, а на всех доступных. Процесс распределения потоков по процессорам можно контролировать.

В соответствии с законом Амдаля–Уэра (увеличение количества вычислителей приводит к ограничению роста производительности), имея четыре процессора, мы не получим четырёхкратное увеличение производительности. К тому же затраты на синхронизацию и управление потоками сказываются на производительности не лучшим образом. Да и увеличение вычислительной мощности в N раз не приводит к аналогичному росту скорости обращения к памяти.

Я решил проверить, каким будет прирост производительности параллельного шифрования в режиме ECB у алгоритма шифрования ГОСТ 28147—89 на четырёхядерном процессоре.

Операция зашифрования по ГОСТ 28147—89 сама по себе не может быть распараллелена (да и есть ли смысл?). Но так как в режиме ECB операция зашифрования одного блока не зависит от остальных блоков, то процесс можно распараллелить.

Цикл зашифрования выглядит следующим образом (для краткости я не привожу вспомогательные таблицы):

[-]

View Code C

uint_fast32_t gost_data_1[256];
uint_fast32_t gost_data_2[256];
uint_fast32_t gost_data_3[256];
uint_fast32_t gost_data_4[256];

union gostrec_t {
uint8_t x[8];
uint32_t y[2];
};

void do_encode(union gostrec_t* const buf, const uint32_t* const key)
{
const uint32_t* k = key;
uint_fast32_t a = buf->y[0];
uint_fast32_t b = buf->y[1];
uint_fast32_t t;

for (uint_fast32_t i=0; i<=11; ++i) {
if (0 == (i & 3)) k = key;

t = a + k[0];
b ^= gost_data_1[(uint8_t)t] ^ gost_data_2[(uint8_t)(t >> 8)] ^ gost_data_3[(uint8_t)(t >> 16)] ^ gost_data_4[(uint8_t)(t >> 24)];

t = b + k[1];
a ^= gost_data_1[(uint8_t)t] ^ gost_data_2[(uint8_t)(t >> 8)] ^ gost_data_3[(uint8_t)(t >> 16)] ^ gost_data_4[(uint8_t)(t >> 24)];

k += 2;
}

k = key + 8;
for (uint_fast32_t i=0; i<=3; ++i) {
k -= 2;

t = a + k[1];
b ^= gost_data_1[(uint8_t)t] ^ gost_data_2[(uint8_t)(t >> 8)] ^ gost_data_3[(uint8_t)(t >> 16)] ^ gost_data_4[(uint8_t)(t >> 24)];

t = b + k[0];
a ^= gost_data_1[(uint8_t)t] ^ gost_data_2[(uint8_t)(t >> 8)] ^ gost_data_3[(uint8_t)(t >> 16)] ^ gost_data_4[(uint8_t)(t >> 24)];
}

buf->y[0] = (uint32_t)b;
buf->y[1] = (uint32_t)a;
}

Зашифрование в режиме ECB выглядит так:

[-]

View Code C

void encode(uint8_t* buf, uint32_t len, const uint32_t* key)
{
for (int32_t i=0; i<(int32_t)len; i+=sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)(buf+i), key);
}
}

Длина явно приводится к знаковому типу для облегчения переноса на OpenMP (в спецификации есть требование, чтобы счетчики циклов были знаковыми).

Параллельная версия процедуры зашифрования будет выглядеть так:

[-]

View Code C

void encode_omp(uint8_t* buf, uint32_t len, const uint32_t* key)
{
#pragma omp parallel
{
#pragma omp for schedule(static) nowait
for (int32_t i=0; i<(int32_t)len; i+=sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)(buf+i), key);
}
}
}

Makefile:

[-]

View Code GNU make

CC=gcc
CFLAGS=-O3 -fopenmp -march=native -fstrict-aliasing -std=gnu99 -Wall -Wextra -Wno-unused-parameter -Wstrict-aliasing=1 -Wdisabled-optimization
CFLAGS_PGEN=-g3 -pg -fprofile-arcs -ftest-coverage -fprofile-generate
CFLAGS_PUSE=-fomit-frame-pointer -fprofile-use
LDFLAGS=-fopenmp
LDFLAGS_PGEN=-fprofile-generate

all: gost
./gost
$(CC) $(CFLAGS) $(LDFLAGS) $(CFLAGS_PUSE) main.c gost.c -o gost

gost: main.o gost.o
$(CC) $(LDFLAGS) $(LDFLAGS_PGEN) $^ -o $@

main.o: main.c gost.h
$(CC) $(CFLAGS) $(CFLAGS_PGEN) -c $*.c

gost.o: gost.c gost.h
$(CC) $(CFLAGS) $(CFLAGS_PGEN) -c $*.c

clean:
-rm -f *.o gost *.gcda *.gcno

.PHONY: all clean

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

~~Получились весьма интересные результаты:~~

	Min	Max	Avg
Parallel	1.43	1.46	1.44
Serial	1.39	1.42	1.41

Параллельная версия алгоритма не только не даёт прироста в производительности, но еще и проигрывает последовательной версии!

Так бы и считал, если бы во время тестирования альтернативной версии не заметил, что параллельная версия выполняется быстрее. Мораль: читайте маны.

Дело в том, что время измерялось следующим образом:

[-]

View Code C

start = clock();
func(buf, n, key);
stop = clock();
x = (double)(stop - start) / CLOCKS_PER_SEC;

Но CLOCKS_PER_SEC не учитывает, что у нас четыре ядра, а не одно. Или как раз-таки учитывает. И вообще хз. Я так понял, что на выходе я получаю время, которое понадобилось бы процессору на выполнение задачи, если бы он был один. Тёмный лес.

UPD: POSIX requires that CLOCKS_PER_SEC equals 1000000 independent of the actual resolution.

Как правильно:

[-]

View Code C

gettimeofday(&start, NULL);
func(buf, n, key);
gettimeofday(&stop, NULL);
x = (1000000.0f*(stop.tv_sec - start.tv_sec) + (stop.tv_usec - start.tv_usec))/1000000;

Итак, что получилось на четырёх ядрах:

	Min	Max	Avg
Parallel	0.365861	0.408662	0.371971
Serial	1.406327	1.418306	1.412239

Что характерно, в случае с одним процессором оба способа измерения времени работают примерно одинаково, так что будем считать, что в статье "Практическая польза fast-типов" я не сильно наврал со скоростью.

Когда я неудачно измерял время выполнения кода, я думал, что причина неудачи в том, что кэш процессора не резиновый: как-никак буфер для зашифрования 100 мебибайт, потоки берут код из совершенно разных участков памяти, процедура зашифрования активно использует 4 кибибайта таблиц…

Тогда я написал такую процедуру зашифрования, рассчитанную на четыре ядра:

[-]

View Code C

void encode_omp(uint8_t* buf, uint32_t len, const uint32_t* key)
{
#pragma omp parallel sections shared(buf, key, len)
{
#pragma omp section
for (int32_t i=0; i<(int32_t)len; i+=4*sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)&buf[i], key);
}

#pragma omp section
for (int32_t i=sizeof(union gostrec_t); i<(int32_t)len; i+=4*sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)&buf[i], key);
}

#pragma omp section
for (int32_t i=2*sizeof(union gostrec_t); i<(int32_t)len; i+=4*sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)&buf[i], key);
}

#pragma omp section
for (int32_t i=3*sizeof(union gostrec_t); i<(int32_t)len; i+=4*sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)&buf[i], key);
}
}
}

Идея в том, что если потоки выполняются с примерно одинаковой скоростью, возможно улучшить локальность данных в кэше процессора (код, скорее, представлял proof of concept, ибо не учитывает целый ряд факторов).

	Min	Max	Avg
Parallel Sections	0.375868	0.404222	0.384918

Результат с использованием секций получился чуть-чуть хуже.

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

Автор: Vladimir; опубликовано в: OpenMP; метки: benchmark, C/C++, ECB, OpenMP, криптография, производительность, шифрование

4
Апр
2009

Комментарии к статье «OpenMP на многоядерном процессоре и криптография» (13) »

Konstantyn

Апрель 16, 2009 в 01:04

С замером времени тож самое было)) пропарился как говориться…..Аналогично считал что распаралеленная версия медленнее однопоточной

Ответить
slovn

Январь 19, 2010 в 20:32

хаха, у меня лапа с иедленная спользованием OpenMP самая медленная по сравнению с pthread и однопоточний… Интернесно, почему так

Ответить
- Vladimir
  
  Январь 20, 2010 в 02:35
  
  Вообще странно — OpenMP в Linux использует pthreads.
  
  А процессор многоядерный? И ключ -fopenmp использовался при компиляции?
  
  Ответить
Максим

Январь 21, 2010 в 16:47

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

Ответить
- Vladimir
  
  Январь 21, 2010 в 19:46
  
  Я с S-box извратился.
  
  Там как-то так это выглядит:
  
  [-]
  
  View Code C
  
  int i = 0;
  for (uint8_t a=0; a<16; ++a) {
  ax = sbox[1][a] << 15;
  bx = sbox[3][a] << 23;
  cx = sbox[5][a];
  cx = (cx >> 1) | (cx << 31);
  dx = sbox[7][a] << 7;
  
  gost_sbox_1[i] = ax | (sbox[0][0] << 11);
  gost_sbox_2[i] = bx | (sbox[2][0] << 19);
  gost_sbox_3[i] = cx | (sbox[4][0] << 27);
  gost_sbox_4[i] = dx | (sbox[6][0] << 3);
  ++i;
  
  gost_sbox_1[i] = ax | (sbox[0][1] << 11);
  gost_sbox_2[i] = bx | (sbox[2][1] << 19);
  gost_sbox_3[i] = cx | (sbox[4][1] << 27);
  gost_sbox_4[i] = dx | (sbox[6][1] << 3);
  ++i;
  
  // ...
  }
  
  Тесты такая реализация точно проходила.
  
  Ответить
  - Vladimir
    
    Январь 21, 2010 в 19:47
    
    PS — называется это всё S-box precomputation.
    
    Ответить
    - Максим
      
      Январь 21, 2010 в 19:53
      
      Спасибо большое, по ключевой фразе S-box precomputation нарыл кое что в гугле. У меня было немного попроще с precompution’ом, там все равное нужно было сдвиг делать каждый раз
Максим

Январь 21, 2010 в 17:09

и кстати у меня наложение маски почему то работает быстрее чем приведение типа

Ответить
- Vladimir
  
  Январь 21, 2010 в 19:33
  
  А это от компилятора, вероятно, зависит. Нужно смотреть, какой код генерируется в одном и в другом случае.
  
  Ответить
  - Максим
    
    Январь 21, 2010 в 19:47
    
    Не могли бы вы показать код инициализации таблиц замен, мне интересна эта оптимизация.
    
    Ответить
    - Vladimir
      
      Январь 21, 2010 в 20:22
      
      Код такой, как в комментарии, только по всем индексам (от 0 до 15).
      
      [-]
      
      View Code C
      
      int i = 0;
      for (uint8_t a=0; a<16; ++a) {
      ax = sbox[1][a] << 15;
      bx = sbox[3][a] << 23;
      cx = sbox[5][a];
      cx = (cx >> 1) | (cx << 31);
      dx = sbox[7][a] << 7;
      
      for (uint8_t j=0; j<16; ++j) {
      gost_sbox_1[i] = ax | (sbox[0][j] << 11);
      gost_sbox_2[i] = bx | (sbox[2][j] << 19);
      gost_sbox_3[i] = cx | (sbox[4][j] << 27);
      gost_sbox_4[i] = dx | (sbox[6][j] << 3);
      ++i;
      }
      }
      
      Как-то так.
Максим

Январь 22, 2010 в 13:39

Не знаю проверяли вы или нет этот код на 64 битной платформе, но на ней uint_fast32_t t – будет почти наверное 64 битной, и тогда t = * + * – может выйти за границы 32 бит, и тогда gost_data_4[t >> 24] – может выйти за границы массива (у меня лично выходит ), так что тут видимо тоже надо приводить тип.

Кстати у меня примерно такой же код (я немного циклы развернул) шифрует со скоростью ~ 366,3 МБит/сек (не параллельная реализация)
Процессор: AMD Athlon(tm) X2 Dual-Core QL-60 1.9 Гц

Попробуйте еще флаги: -funroll-loops / -funroll-all-loops
флаг -ftree-parallelize-loops=число, почему то у меня ничего не ускоряет.

Я вообще хотел еще оптимизировать хеш функцию, но её распараллелить видимо нереально…

Ответить
- Vladimir
  
  Январь 26, 2010 в 04:14
  
  gost_data_4[t >> 24] – может выйти за границы массива
  
  Вы абсолютно правы, спасибо, сейчас поправлю.
  
  Кстати у меня примерно такой же код (я немного циклы развернул) шифрует со скоростью ~ 366,3 МБит/сек
  
  Здорово. Впечатляет.
  
  Я вообще хотел еще оптимизировать хеш функцию, но её распараллелить видимо нереально…
  
  Если честно, я не знаю ни одной хэш-функции, вычислять которую можно параллельно. В принципе, в этом есть свой плюс: подбор хэша тоже не особо распараллелишь.
  
  Ответить