OpenMP — это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с разделяемой памятью. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой главный поток создает набор подчиненных потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами.
Использование OpenMP должно приводить к увеличению производительности за счет того, что программа (по крайней мере, её параллельные участки) выполняется не на одном процессоре, а на всех доступных. Процесс распределения потоков по процессорам можно контролировать.
В соответствии с законом Амдаля–Уэра (увеличение количества вычислителей приводит к ограничению роста производительности), имея четыре процессора, мы не получим четырёхкратное увеличение производительности. К тому же затраты на синхронизацию и управление потоками сказываются на производительности не лучшим образом. Да и увеличение вычислительной мощности в N раз не приводит к аналогичному росту скорости обращения к памяти.
Я решил проверить, каким будет прирост производительности параллельного шифрования в режиме ECB у алгоритма шифрования ГОСТ 28147—89 на четырёхядерном процессоре.
Операция зашифрования по ГОСТ 28147—89 сама по себе не может быть распараллелена (да и есть ли смысл?). Но так как в режиме ECB операция зашифрования одного блока не зависит от остальных блоков, то процесс можно распараллелить.
Цикл зашифрования выглядит следующим образом (для краткости я не привожу вспомогательные таблицы):
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[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[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[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[t >> 24];
}
buf->y[0] = (uint32_t)b;
buf->y[1] = (uint32_t)a;
}
Зашифрование в режиме ECB выглядит так:
{
for (int32_t i=0; i<(int32_t)len; i+=sizeof(union gostrec_t)) {
do_encode((union gostrec_t* const)(buf+i), key);
}
}
Длина явно приводится к знаковому типу для облегчения переноса на OpenMP (в спецификации есть требование, чтобы счетчики циклов были знаковыми).
Параллельная версия процедуры зашифрования будет выглядеть так:
{
#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:
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 |
Параллельная версия алгоритма не только не даёт прироста в производительности, но еще и проигрывает последовательной версии!
Так бы и считал, если бы во время тестирования альтернативной версии не заметил, что параллельная версия выполняется быстрее. Мораль: читайте маны.
Дело в том, что время измерялось следующим образом:
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
.
Как правильно:
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 кибибайта таблиц…
Тогда я написал такую процедуру зашифрования, рассчитанную на четыре ядра:
{
#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% — не так уж и плохо (особенно если считать, что основной целью статьи было показать, что параллельность — это не всегда хорошо).
Меня зовут Владимир, я программист-фрилансер, специализирующийся на Web-программировании и програмировании под Linux.
По совместительству занимаюсь администрированием LAMP/LNMP-серверов и техническим переводом.
С замером времени тож самое было)) пропарился как говориться…..Аналогично считал что распаралеленная версия медленнее однопоточной