Boolean function absolute nonlinearity calculation on GPU.pdf Для криптографических приложений представляют интерес функции с высоки-ми показателями «нелинейности», потому что они труднее поддаются анализу. Суще-ствует несколько характеристик нелинейности функции, одна из них - совершеннаянелинейность [1], которая показывает, насколько функция удалена от класса функ-ций с линейной структурой. Разработан алгоритм вычисления совершенной нелиней-ности произвольной булевой функции для параллельной реализации на видеокартахNVIDIA, поддерживающих технологию CUDA [2].Обозначим через P2 (n) множество всех булевых функций от n ^ 1 переменных иX - область их определения, X = {0,1}n.Определение 1. Для функции / Е P2(n) и набора а Е X функция / (x) == / ( x ) Ф / ( x ф а) называется производной функции / по направлению а.Определение 2. Говорят, что булева функция / имеет линейную структуру,если существует вектор а Е X \ {0n} , что / = const, т.е. / = / либо -/ = /.Множество всех функций в P2(n), имеющих линейную структуру, обозначается LS(n).Определение 3. Число CNf = d ( / , LS(n)) = min d(/, g) называется совершен- gGLS(ra)ной нелинейностью функции /. Здесь d(/, g) -расстояние между функциями / и g,равное количеству наборов, на которых они различаются.Существует ряд способов вычисления CNf; наиболее подходящим для параллель-ной реализации оказался следующий:CN = min гmin(w(/:), 2n - w ( / ) ) / 2 ,где w(.) - вес булевой функции. Основную трудность здесь представляет вычислениефункции / ( x ф а). Проблема состоит в том, что CUDA предполагает запуск боль-шого числа нитей параллельно [3], но их совокупная память ограничена (3 Гб дляTesla C2050), поэтому невозможно хранить значения / ( x ф а) для каждой нити, и веспроизводной вычисляется «по частям» (алгоритм 1).Вектор значений булевой функции от n переменных представляется в памяти мас-сивом 2n-битных ячеек - элементов базового типа языка C/C+-+ (в реализации ис-пользуется 32-битный тип long int, N = 5). Количество ячеек определяется по фор-муле m = 2n-N. Далее будем обозначать i-ю ячейку функции / через /j.Алгоритм 1. Алгоритм вычисления w ( / )Вход: /, aВ ы х о д : w ( / )w - 0Для i = 0 , . . . , m - 1w - w + weight(/i(x) ф / i (x ф a))В еРнУт ь w = w ( / )Данный алгоритм не требует вычисления / ( x ф a) в явном виде, но надо уметьполучать i-ю ячейку функции / ( x ф a ) . Заметим, что вектор значений / ( x ф a ) получа-ется из вектора значений функции / ( x ) перестановкой бит по определённому закону.Например, если a1 = 1, то меняются местами половины вектора значений исходнойфункции, иначе ничего не меняется; если a2 = 1, то меняются между собой половинывнутри половин всего вектора, иначе они не меняются, и т. д. рекурсивно.Алгоритм 2 принимает на вход вектор a и номер i, а на выходе выдает номер jячейки / ( x ) , который соответствует ячейке с номером i в / ( x ф a).Алгоритм 2. Алгоритм вычисления номера ячейки для функции / ( x ф a) Е P2(n)Вход: i, a = a1 . . . an, m - количество ячеекВыход: j, такой, что / j ( x ) = / (x ф a) (без учета перестановки бит внутри ячейки)l - 0 // инициализация левой границы интервалаj - iiw - m >> 1 // половина длины текущего интервалаДля k = 1 , . . . , nЕсли i < l + iw, тоЕсли ak = 1, тоj - j + i wиначеl l + iwЕсли ak = 1, тоj - j - i wiw iw > > 1Конец цикла.ВернУть jПерестановка бит внутри ячеек происходит по такому же закону, но в реализациииспользуется более быстрый способ на основе битовых операций.Ниже приведены результаты экспериментов по вычислению CNf при разной сте-пени распараллеливания. Испытания проводились на компьютере Intel(R) Core(TM)2Quad Q6700 2,66 ГГц с установленной видеокартой NVIDIA Tesla C2050. На CPU алго-ритм реализован в двух вариантах - последовательном и с использованием библиотекиOpenMP, которая позволяет задействовать все ядра центрального процессора (в на-шем случае 4 ядра). В таблице показано время работы (в секундах) соответствующихреализаций.CPU GPUn Посл. алг. OpenMP CUDA15 1,02 0,25 0,0116 4,13 1,03 0,0417 16,9 4,22 0,1518 69,9 17,4 0,65Таким образом, реализация для видеокарты с использованием технологии CUDA ока-залась быстрее, чем последовательный алгоритм, примерно в 106 раз, а в сравнениис параллельной реализацией на центральном процессоре - примерно в 26,5 раз.

Скачать электронную версию публикации