已知内存读写是某个程序最慢的操作，如何减少内存读写？

safedead

某程序有一个内置数组，大小为256字节
经分析，此程序超过一半的时间消耗在读取这个数组上
现在想优化，该怎么做

static unsigned char sbox[256];

使用此数组的完整代码：
uint32_t apply_sbox(uint32_t  a)
{
    uint32_t  b;
    b = (sbox[a >> 24] << 24)                       \
        ^ (sbox[(a >> 16) & 0xFF] << 16)             \
        ^ (sbox[(a >> 8) & 0xFF] << 8)              \
        ^ sbox[a & 0xFF];
    return b;
}
每计算一次b，就要访问四次数组sbox[]，而且大多是非对齐访问，导致此程序超过一半的时间消耗在读取这个数组上
这个sbox数组就是对称密码体系里常说的"S盒"，上面的C代码运算模式叫“4路并行S盒”，用FPGA实现比较高效，可以真正做到“4路并行运算”
但是x64下就没这么便利了

首先说明，这个sbox不存在64个系数以下的多项式解，不像AES的sbox是二元扩域椭圆曲线乘法矩阵

linux_c_py_php

看起来像是想优化算法的样子.

函数inline, O3优化.{:3_190:}

hanxin83

请问咋分析出"超过一半的时间消耗在读取这个数组"的啊?
或者是这个函数开销占了一半时间? 理解的像这样频繁访问的内存数据块一般会被cache住啊.

safedead

hanxin83 发表于 2013-03-01 13:51
请问咋分析出"超过一半的时间消耗在读取这个数组"的啊?
或者是这个函数开销占了一半时间? 理解的像这样频繁 ...

典型的x64系统
CACHE命中的内存读取大概20个cycle的样子
不在CACHE的内存读取至少100个cycle

3个cycle可以完成一个64bit x 64bit = 128bit乘法
144个cycle可以完成一个X87浮点除法

实际上这个函数是不存在的，整个程序是汇编写的，访问sbox的部分反编译成C代码才是我贴出的函数的样子
整个程序就一个函数，sbox放在BSS段

cjaizss

safedead 发表于 2013-03-01 13:26
某程序有一个内置数组，大小为256字节
经分析，此程序超过一半的时间消耗在读取这个数组上
现在想优化，该 ...

FPGA也无法跨越硬件的障碍，4路访问还是得有先有后。
哦，明白了你的意思，你不用RAM,只是4个选择器电路

safedead

cjaizss 发表于 2013-03-01 14:37
FPGA也无法跨越硬件的障碍，4路访问还是得有先有后。
哦，明白了你的意思，你不用RAM,只是4个选择器电路

我的笔记本CPU主频2.4G，用x64编程，单进程处理速度440Mbps
同事用ALTERA的FPGA编写专用处理器，50MHz，4级流水线实现，处理速度接近1600Mbps

cjaizss

safedead 发表于 2013-03-01 14:52
我的笔记本CPU主频2.4G，用x64编程，单进程处理速度440Mbps
同事用ALTERA的FPGA编写专用处理器，50MHz ...

猜测做法是整个公式做成组合电路，然后该组合电路有好多份

safedead

回复 7# cjaizss


   

是的，组合电路消耗的逻辑资源越多速度越快

noword2k

把
static unsigned char sbox[256]
改成
static unsigned int sbox[256]
就能对齐访问了……

pprpg

非对齐访问，会导致CACHE无效?
那么按照楼上的思路:

1. typedef struct {
   
2.   unsigned char use;
   
3.   unsigned char nouse1;
   
4.   unsigned char nouse2;
   
5.   unsigned char nouse3;
   
6. } Cell ;
   
7. 
   
8. Cell sbox[256];

复制代码

按4个字节对齐就能够使cache生效?