| 采用交叉访问方式，一个由n个存储体构成的主存储器，它的速度实际上并不能提高n倍，其根本原因是存在有访问冲突。产生访问冲突的根源主要有两个，一是程序中有转移指令，二是数据的随机性。从上面的分析结果看，后一个问题更为严重。 下面，介绍一维和二维数组的无冲突访问存储器。 先举一个一维数组的例子。如果采用交叉访问方式的并行存储器有4个存储体，交叉存放一维数组a0，a1，a2，……，如图4.16所示。 |
||||||||||||||||||||||||||||||
| 图4.16 一维数组的存储方案 | ||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
| 如果每次都按连续地址访问，就没有冲突问题，一个存储周期可以读出4个操作数。若一个存储周期需要读出更多的操作数，只要增加存储体的个数就可以了。如果要求按位移量为2的变址方式访问并行存储器（访问下标为奇数或偶数的操作数），则存储器的频带宽度就要降低一半，即可能有一半地址是冲突的。在并行递归算法中，典型的访问模式是向量子集的各个元素逐次按2的整数幂相间访问。例如，先按地址连续访问，然后按位移量为2的变址方式访问，再按位移量为4的变址方式访问等。对于这类算法，一般的交叉访问存储器就显得不能适应了。 只要认真分析造成访问冲突的原因，不难发现传统的交叉访问存储器的存储体个数n为2的整数幂，因此变址位移量正好是n的约数。解决这一问题的方法很简单，只要把存储体的个数n选为质数，变址位移量就必然与n互质，一维数组的访问冲突自然也就不存在了。 许多以向量计算为主要任务的大型计算机系统，其主存储器的存储体个数一般都是质数。例如，美国Burroughs公司研制的巨型科学处理机BSP，它的存储体个数为17，我国研制的银河巨型计算机，存储体的个数为31。 对于多维数组，需要考虑的问题就复杂得多，为简单起见，下面仅讨论二维数组，讨论过程中所得出得的结论也可以推广到多维数组中。 |
||||||||||||||||||||||||||||||
| 4.17 按列访问有冲突的存储方案 | ||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||