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[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 выглядит так:

[-]
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 (Unknown Language)
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% — не так уж и плохо (особенно если считать, что основной целью статьи было показать, что параллельность — это не всегда хорошо).

Добавить в закладки

Связанные записи

4
Апр
2009

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

  1. Konstantyn says:

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

Подписаться на RSS-ленту комментариев к статье «OpenMP на многоядерном процессоре и криптография» Trackback URL: http://blog.sjinks.org.ua/openmp/522-openmp-on-multicore-cpu-and-cryptography/trackback/

Оставить комментарий к записи «OpenMP на многоядерном процессоре и криптография»

Вы можете использовать данные тэги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Оставляя комментарий, Вы выражаете своё согласие с Правилами комментирования.

Подписаться, не комментируя