c - 如何优化KASUMI算法的S盒？

Question

非常感谢，我正在尝试优化用C编写的Kasumi算法。FI函数中有S-box用于加密数据，S7-box有127个元素，S9-box有512个元素。 FI 函数代码如下:

static u16 FI(u16 in, u16 subkey)
{
    static u16 s7[] = {...};
    static u16 s9[] = {...};

    nine = (u16)(in>>7);
    seven = (u16)(in&0x7F);
    /* Now run the various operations */
    nine = (u16)(S9[nine] ^ seven);
    seven = (u16)(S7[seven] ^ (nine & 0x7F));
    seven ^= (subkey>>9);
    nine ^= (subkey&0x1FF);
    nine = (u16)(S9[nine] ^ seven);
    seven = (u16)(S7[seven] ^ (nine & 0x7F));
    in = (u16)((seven<<9) + nine);
    return( in );
}

u16代表unsigned short。

通过一些转换。我将S7-box和S9-box合并到S16-box，我用avx指令让16个数据并行。 FI函数的代码如下:

static u16 FI(__m256i in, u16 subkey)
{
    u16 arr[16];        
    _mm256_store_si256((__m256i*)arr, in);
    u8 i;           
    for(i = 0; i < 16; i++)
    {
        arr[i] = (u16)(s16[arr[i]] ^ subkey);
        arr[i] = (arr[i] << 7) | (arr[i] >> 9);
        arr[i] = s16[arr[i]];
    }
    in = _mm256_load_si256((__m256i*)arr);
}

S16-box 有 65536 个元素，所以可能会发生一些缓存未命中。我还使用收集指令，如:

inline static __m256i FI( __m256i in, u16 subkey )
{
    __m256i _tmp = _mm256_set1_epi32(0xffff);
    __m256i even_sequence = _mm256_and_si256(in, _tmp);
    __m256i odd_sequence = _mm256_srli_epi32(in, 16);
    even_sequence = _mm256_i32gather_epi32((int const*)s16, even_sequence, 2); 
    __m256i _subkey = _mm256_set1_epi16(subkey);
    even_sequence = _mm256_xor_si256(even_sequence, _subkey);
    even_sequence = _mm256_and_si256(even_sequence, _tmp);
    odd_sequence = _mm256_i32gather_epi32((int const*)s16, odd_sequence, 2); 
    odd_sequence = _mm256_xor_si256(odd_sequence, _subkey);
    odd_sequence = _mm256_and_si256(odd_sequence, _tmp);
    // rotate
    __m256i hi = _mm256_slli_epi16(even_sequence, 7); 
    __m256i lo = _mm256_srli_epi16(even_sequence, 9); 
    even_sequence = _mm256_or_si256(hi, lo);
    //same for odd
    hi = _mm256_slli_epi16(odd_sequence, 7); 
    lo = _mm256_srli_epi16(odd_sequence, 9); 
    odd_sequence = _mm256_or_si256(hi, lo);
    even_sequence = _mm256_i32gather_epi32((int const*)s16, even_sequence, 2); 
    odd_sequence = _mm256_i32gather_epi32((int const*)s16, odd_sequence, 2); 
    even_sequence = _mm256_and_si256(even_sequence, _tmp);
    odd_sequence = _mm256_slli_epi32(odd_sequence, 16);
    in = _mm256_or_si256(even_sequence, odd_sequence);  

    return in; 
}

但是性能达不到要求，我也在考虑bit-slice。我读了一篇可以并行处理 128 个数据但需要一些硬件支持的论文。我认为位转置操作很耗时，而且有很多约束。

非常感谢!

Answer 1

这段代码可能会解释性能问题以及您在其下方的评论。

static u16 FI(__m256i in, u16 subkey) {
    u16 arr[16];        
    _mm256_store_si256((__m256i*)arr, in);
    u8 i;           
    for(i = 0; i < 16; i++)
    {
        arr[i] = (u16)(s16[arr[i]] ^ subkey);
        arr[i] = (arr[i] << 7) | (arr[i] >> 9);
        arr[i] = s16[arr[i]];
    }
    in = _mm256_load_si256((__m256i*)arr);
}

S16-box has 65536 elements, so maybe some cache miss will happen.

平均 x64 处理器只有 32KB 的 L1(AMD 的有时有 64K，但现在让我们忽略它)。

这意味着如果没有其他数据结构使用任何 L1 并且您没有运行 hypertrhreading，您的 64K 阵列将获得 32KB/64KB * 100% = 50% 的缓存命中率另一个线程。

让我们将其简化为您只有 64KB 中的 16KB，每次访问都有 75% 的失误几率。所以你的循环在每一行之间都有数据依赖性，即。下一个语句不能在上一个语句完成之前开始。幸运的是，每次迭代都是独立于其他迭代的数据。

arr[i] = (u16)(s16[arr[i]] ^ subkey);
arr[i] = (arr[i] << 7) | (arr[i] >> 9);
arr[i] = s16[arr[i]];

arr此时几乎肯定会在L1缓存中，只产生4个周期的启动成本，每次访问s16平均成本为0.25*4+0.75*12 = 1+9 = 10 个周期。这给出了每个语句的以下近似延迟成本(忽略 arr[i] 的存储和重新加载的成本，假设 arr[i] 存储在寄存器中)

arr[i] = (u16)(s16[arr[i]] ^ subkey); // arr: 4 + S16: 10 + ^:1
arr[i] = (arr[i] << 7) | (arr[i] >> 9); // << : 1 + |: 1
arr[i] = s16[arr[i]]; // s16 : 10 + store arr : 4

每次迭代有 31 个周期延迟，幸运的是每次迭代之间没有数据依赖性。每次迭代大约需要 3 个周期来发布，因此最后一次将在 ~3*16+31=79 个周期内完成，假设完美的分支预测并忽略最后分配 in 的数据风险。

我认为您的下一个代码是这个重写为 AVX2 的循环将具有许多相同的加载依赖性和完全相同的缓存未命中，循环开销将消失但一些更长的延迟 AVX 指令可能会增加时间。平均时间仍然是大约 31 个周期的延迟 + 一些 AVX 延迟 + 16 个负载/(每个周期最多 2 个负载)，比方说 40 个周期。

如果您没有合并 S7 和 S9，它们将只占用 (128+512)*2 个字节，并且当您运行更长的编码时，它们几乎肯定总是在 L1 缓存中。然后，循环延迟将减半，代价是负载数量翻倍，您的完整 AVX 达到大约 15 + 32 负载/每个周期 2，比方说 30 个周期。

好消息是每个 16 字节的迭代似乎都独立于前一个，因此它们可以在时间上重叠。但是您最终会受到加载和存储数量的限制，一次初始加载，来自 s7+s9 的 32 次加载和一次存储，最多 2 次存储或加载将最佳吞吐量限制为 16 字节/((1+32+ 1)/2) 周期。

这是在做出很多乐观的假设，只有对 2 种不同代码(s16 vs s7+s9)的实际测量才能决定什么是最好的。