又一个看似简单的问题

发表于 2012-5-16 20:39

二维数组的转置问题，简单描述如下
BYTE ms[x][y];
BYTE md[y][x];
int i,j;
for(i=0;i<x;i++)
for(j=0;j<y;j++)
md[j][i]=ms[i][j];
就是这么简单的一个问题，却存在严重的瓶颈。
当x*y的大小远远超出CPU的CACHE时，这种转置将变得很慢。
在嵌入式中，CACHE较小，会变得更慢。
不信，你试试看。

发表于 2012-5-16 21:30

不太明白

发表于 2012-5-16 23:33

是不是时间局部性的问题

发表于 2012-5-17 13:28

我信，而且不旦要保证不超CACHE大小，还应保证不超缓存行的大小，这样才保证不会发起慢得多的内存访问。可你想证明什么呢？
超过一个缓存行的大小后，如果目标地址没有命中，则直接访问内存。而且对于嵌入式系统而言又大多用SDRAM，CPU一般会重新启动一个爆发读命令，读入一个缓存行，而非仅仅你要的那一个安节。
明白了？

发表于 2012-5-17 13:30

是不是时间局部性的问题
zjgtan 发表于 2012-5-16 23:33

对，CACHE是因为有时间局部性原则才有意义。离开时间局部性原则，CACHE就变成废物了。

发表于 2012-5-22 12:51

没考虑过时间

发表于 2012-5-22 13:25

思路简单运算慢，思路复杂运算慢快。有时不能想得太复杂，有时又不能想得太简单。

又一个看似简单的问题

相关帖子

浏览过的版块

无冕之王奖章

沉静之湖泊

十世金身

技术导师奖章

社区建设奖章

欢快之小溪

常驻人口

技术高手奖章

晶莹之水滴

以坛为家

精华达人奖章

湍急之河流

伴坛终老

技术奇才奖章