现代计算机系统以存储器为中心3.1存储系统原理3课件.ppt

1、现代计算机系统以存储器为中心现代计算机系统以存储器为中心 3.1 存储系统原理存储系统原理 3.2 虚拟存储器虚拟存储器 3.3 高速缓冲存储器高速缓冲存储器(Cache) 3.4 三级存储系统三级存储系统第第3章章 存储系统存储系统 3.1 3.1 存储系统原理存储系统原理3.1.1 存储系统的定义存储系统的定义3.1.2 存储系统的层次结构存储系统的层次结构3.1.3 存储系统的频带平衡存储系统的频带平衡3.1.4 并行访问存储器并行访问存储器 3.1.5 交叉访问存储器交叉访问存储器 3.1.6 无冲突访问存储器无冲突访问存储器3.1.1 3.1.1 存储系统的定义存储系统的定义 在一台

2、计算机中，通常有多种存储器在一台计算机中，通常有多种存储器种类：种类：主存储器、主存储器、Cache、通用寄存器、缓冲存、通用寄存器、缓冲存储器、磁盘存储器、磁带存储器、光盘存储器储器、磁盘存储器、磁带存储器、光盘存储器等等材料工艺：材料工艺：ECL、TTL、MOS、磁表面、激光，、磁表面、激光，SRAM，DRAM访问方式：访问方式：随机访问、直接译码、先进先出、随机访问、直接译码、先进先出、 相联访问、相联访问、 块传送、文件组块传送、文件组 存储器的主要性能：存储器的主要性能：速度、容量、价格速度、容量、价格 速度速度用存储器的访问周期、读出时间、频带宽度等表示。 容量容量用字节B、千字节

3、KB、兆字节MB和千兆字节GB等单位表示。 价格价格用单位容量的价格表示，例如：$C/bit。 组成存储系统的关键：组成存储系统的关键：把速度、容量和价格不同的把速度、容量和价格不同的多个物理存储器组织成一个存储器，这个存储器的速多个物理存储器组织成一个存储器，这个存储器的速度最快，存储容量最大，单位容量的价格最便宜。度最快，存储容量最大，单位容量的价格最便宜。1. 1. 存储系统的定义存储系统的定义 两个或两个以上速度、容量和价格各不相同的存两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储

4、系统。这个存储系统对应用程序员是透来成为一个存储系统。这个存储系统对应用程序员是透明的，并且，从应用程序员看，它是一个存储器，这个明的，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。宜的那个存储器。虚拟存储器系统：对应用程序员透明（通过操作系统虚拟存储器系统：对应用程序员透明（通过操作系统的存储管理系统调度）的存储管理系统调度）Cache存储系统：对系统程序员及以上均透明（全部存储系统：对系统

5、程序员及以上均透明（全部用硬件调度）用硬件调度） 从从外外部部看看 T Tm mi in n（T T1 1，T T2 2，T Tn n） ，用用存存储储周周期期表表示示 S Sm ma ax x（S S1 1，S S2 2，S Sn n） ，用用M MB B或或G GB B表表示示 C Cm mi in n（C C1 1，C C2 2，C Cn n） ，用用每每位位的的价价格格表表示示1 1( (T T1 1, ,S S1 1, ,C C1 1) )2 2( (T T2 2, ,S S2 2, ,C C2 2) )n n( (T Tn n, ,S Sn n, ,C Cn n) )由多个存储器构

6、成的存储系统由多个存储器构成的存储系统 系系 统统 程程 序序 员员 看看 ： 速速 度度 接接 近近 C Ca ac ch he e 的的 速速 度度 ， 存存 储储 容容 量量 是是 主主 存存 的的 容容 量量 ， 每每 位位 价价 格格 接接 近近 主主 存存 储储 器器 。C Ca ac ch he e 存存 储储 系系 统统C Ca ac ch he e主主 存存 储储 器器n 在一般计算机系统中，有两种存储系统：在一般计算机系统中，有两种存储系统：CacheCache存储系统：由存储系统：由CacheCache和主存储器构成和主存储器构成 主要目的：提高存储器速度主要目的：提高存

7、储器速度 应应用用程程序序员员看看： 速速度度接接近近主主存存储储器器的的速速度度， 存存储储容容量量是是虚虚拟拟地地址址空空间间， 每每位位价价格格接接近近磁磁盘盘存存储储器器。虚虚拟拟存存储储系系统统主主存存储储器器磁磁盘盘存存储储器器虚拟存储系统：由主存储器和硬盘构成虚拟存储系统：由主存储器和硬盘构成 主要目的：扩大存储器容量主要目的：扩大存储器容量2.2.存储系统的容量存储系统的容量对存储系统进行编址的要求：对存储系统进行编址的要求：提供尽可能大的地址空间提供尽可能大的地址空间能够随机访问能够随机访问方法有两种：方法有两种：只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部

8、编址或不编址 CacheCache存储系统存储系统另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中 虚拟存储系统虚拟存储系统3.3.存储系统的价格存储系统的价格计算公式：当S2S1时，CC2 S2与S1不能相差太大 （S S，C C，T T）由由两两个个存存储储器器构构成成的的存存储储系系统统M1（S1，C1，T1）M2（S2，C2，T2）CC SC SSS1122124. 4. 存储系统的速度存储系统的速度表示方法：表示方法：访问周期、存取周期、存储周期、存取时间等命中率定义：命中率定义：在在M1存储器中访问到的概率存储器中访问到的概率 其中：N1是对M1存储器的访问次数

9、 N2是对M2存储器的访问次数访问周期与命中率的关系：访问周期与命中率的关系： THT1(1H)T2 当命中率H1时，TT1HNNN112存储系统的访问效率：存储系统的访问效率：访问效率主要与命中率和两级存储器的速度之比有关访问效率主要与命中率和两级存储器的速度之比有关例例3.13.1：假设T2T，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：解：eTTTH TH THHf HTTTT11111122121()()(,)当当H H0.90.9时，时，e e1 11 1(0.9(0.95(15(10.9)0.9)0.720.72当当H H0.990.99时，时，e e2

10、 21 1(0.99(0.995(15(10.99)0.99)0.960.96提高存储系统速度的两条途径：提高存储系统速度的两条途径：一是提高命中率一是提高命中率H H，二是两个存储器的速度不要相差太大二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提高命中率依靠提高命中率例例3.23.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2105 T。如果要使访问效率到达e0.9，问需要有多高的命中率？解：解：0.9H90000(1-H)189999.1 H89999计算得：计算得： H0.999998888877777 0.9999990 911

11、1 05.()HH5. 采用预取技术提高命中率采用预取技术提高命中率 方法：方法：不命中时，把不命中时，把M2存储器中相邻多个单存储器中相邻多个单元组成的一个数据块取出来送入元组成的一个数据块取出来送入M1存储器中。存储器中。 计算公式：计算公式： 其中：H是采用预取技术之后的命中率 H是原来的命中率 n为数据块大小与数据重复使用次数的乘积HHnn1例例3.33.3：在一个Cache存储系统中， T25T1。当Cache的块大小为一个字时，命中率H0.8。假设数据的重复利用率为5，Cache块大小为个字，Cache存储系统的命中率？并分别计算访问效率。99. 0201208 . 01 2nnH

12、H0.558 .1/10.8)5(1(0.81e10.8H:Cache访问效率为：，块大小为一个字时当0.9604. 1/10.99)5(1(0.991e2 0.99H:4Cache2访问效率为：，个字时块大小为当解：解：n4520， 采用预取技术之后，命中率提高到：)2.(.4096140968 .0 )1.(.105) 1 ( 19 .0mmHHH例例3.43.4：在一个虚拟存储系统中，T2105 T，原来的命中率只有0.8，如果访问磁盘存储器的数据块大小为4K字，并要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至少为多少？解：解：假设数据在主存储器中的重复利用率为m，根据前面

13、给出的关系，有如下方程组：解方程组：解方程组： 由方程(1)得到：0.9H+90000-90000H=1)3.(.1 .8999989999:解这个方程得H次。复利用率至少为数据在主存储器中的重44mm4096140968 .0 1 .8999989999:)2()3(得到代入把2 . 01 .8999940961 .89999409689999mm82.179996 .409m3.1.2 3.1.2 存储系统的层次结构存储系统的层次结构多个层次的存储器多个层次的存储器： 第第1层：层：Register Files(寄存器堆寄存器堆) 第第2层：层： Buffers(Lookahead)(先行

14、缓冲站先行缓冲站) 第第3层：层： Cache(高速缓冲存储器高速缓冲存储器) 第第4层：层： Main Memory(主存储器主存储器) 第第5层：层： Online Storage(联机存储器联机存储器) 第第6层：层： Off-line Storage(脱机存储器脱机存储器)用用i表示层数，表示层数，则有：工作周期工作周期TiTi+1， 存储容量：存储容量：SiSi+1，单位，单位价格：价格：CiCi+1 第第 1 层层 第第 2 层层 第第 3 层层 第第 4 层层 第第 5 层层 第第 6 层层CPU内内部部通通用用寄寄存存器器堆堆联联机机外外部部存存储储器器（磁磁盘盘存存储储器器等

15、等）脱脱机机外外部部存存储储器器（磁磁带带，光光盘盘存存储储器器等等）指指令令和和数数据据缓缓冲冲栈栈C Ca ac ch he e（静静态态随随机机存存储储器器）SRAM）主主存存储储器器（动动态态随随机机存存储储器器 DRAM）存存储储容容量量越越来来越越大大每每位位的的价价格格越越来来越越便便宜宜访访问问速速度度越越来来越越快快各级存储器的主要主要性能特性各级存储器的主要主要性能特性 CPUCPU与主存储器的速度差距越来越大与主存储器的速度差距越来越大 目前相差目前相差两个数量级 今后今后CPUCPU与主存储器的速度差距会更大与主存储器的速度差距会更大存存储储器器层层次次 通通用用寄寄存

16、存器器 缓缓冲冲栈栈 C Ca ac ch he e 主主存存储储器器 磁磁盘盘存存储储器器 脱脱机机存存储储器器 存存储储周周期期 1 10 0n ns s 1 10 0n ns s 1 10 06 60 0n ns s 6 60 03 30 00 0n ns s 1 10 03 30 0m ms s 2 22 20 0m mi in n 存存储储容容量量 5 51 12 2B B 5 51 12 2B B 8 8K KB B2 2M MB B 3 32 2M MB B1 1G GB B 1 1G GB B1 1T TB B 5 5G GB B1 10 0T TB B 价价格格$ $C C/

17、 /K KB B 1 12 20 00 0 8 80 0 3 3. .2 2 0 0. .3 36 6 0 0. .0 01 1 0 0. .0 00 00 01 1 访访问问方方式式 直直接接译译码码 先先进进先先出出 相相联联访访问问 随随机机访访问问 块块访访问问 文文件件组组 材材料料工工艺艺 E EC CL L E EC CL L S SR RA AM M D DR RA AM M 磁磁表表面面 磁磁、光光等等 分分配配管管理理 编编译译器器分分配配 硬硬件件调调度度 硬硬件件调调度度 操操作作系系统统 系系统统/ /用用户户 系系统统/ /用用户户 带带宽宽( (M MB B/ /

18、S S) ) 4 40 00 08 80 00 00 0 4 40 00 01 12 20 00 0 2 20 00 08 80 00 0 8 80 01 16 60 0 1 10 01 10 00 0 0 0. .2 20 0. .6 6 3.1.3 3.1.3 存储系统的频带平衡存储系统的频带平衡例例3.5：Pentium4的指令执行速度为8GIPS，CPU取指令8GW/s，访问数据16GW/s，各种输入输出设备访问存储器1GW/s，三项相加，要求存储器的频带宽度不低于25GW/s。 如果采用PC133内存，主存与CPU速度差188倍 如果采用PC266内存，主存与CPU速度差94倍解决存

19、储器频带平衡方法解决存储器频带平衡方法 (1)多个存储器并行工作（本节下面介绍）多个存储器并行工作（本节下面介绍） (2)设置各种缓冲存储器（第五章介绍）设置各种缓冲存储器（第五章介绍） (3)采用存储系统（本章第二、第三节介绍）采用存储系统（本章第二、第三节介绍）3.1.4 3.1.4 并行访问存储器并行访问存储器方法：方法：把把m字字w位的存储器改变成为位的存储器改变成为m/n字字nw位的位的存储器存储器逻辑实现：逻辑实现：把地址码分成两个部分，一部分作为存储把地址码分成两个部分，一部分作为存储器的地址另一部分负责选择数据器的地址另一部分负责选择数据主要缺点：访问冲突大主要缺点：访问冲突大

20、 (1)(1)取指令冲突取指令冲突 (2)(2)读操作数冲突读操作数冲突 (3)(3)写数据冲突写数据冲突 (4)(4)读写冲突读写冲突选择器 选择器选择器数据寄存器MBR MBR 存储体（m字w位）存储体（m/n字nw位）地址寄存器MARMAR一般存储器 并行访问存储器 并行访问存储器结构框图并行访问存储器结构框图1. 1. 高位交叉访问存储器高位交叉访问存储器主要目的：主要目的：扩大存储器容量扩大存储器容量实现方法：实现方法：用地址码的高位部分区分存储体号用地址码的高位部分区分存储体号参数计算方法参数计算方法: m：每个存储体的容量， n：总共的存储体个数， j：存储体的体内地址，j0，1

21、，2，.，m-1 k：存储体的体号，k0，1，2，.，n-1 存储器的地址：Amkj 存储器的体内地址：AjA mod m。 存储器的体号： AkAm 3.1.5 3.1.5 交叉访问存储器交叉访问存储器 MBR MBR MBR 0000 . . . 00FF 存存储储体体0 0.10.0 . . . 01F.F 存存储储体体1 . FF0.0 . . . FFF.F 存存储储体体n-1 MAR MAR MAR 译译码码器器 （高高位位） 存存储储器器地地址址寄寄存存器器（低低位位） 高位交叉访问存储器结构框高位交叉访问存储器结构框图图2. 2. 低位交叉访问存储器低位交叉访问存储器 主要目的

22、：主要目的：提高存储器访问速度提高存储器访问速度 实现方法：实现方法：用地址码的低位部分区分存储体号用地址码的低位部分区分存储体号 参数计算参数计算: m：每个存储体的容量， n：总共的存储体个数， j：存储体的体内地址，j0，1，2，.，m-1 k：存储体的体号，k0，1，2，.，n-1 存储器地址A的计算公式为：Anjk 存储器的体内地址：Aj 存储器的体号：AkA mod nAn MBR MBR MBR 0.00.0 0.10.0 . . . F.F0.0 存存储储体体0 0.00.1 . . . F.F0.1 存存储储体体1 . 0.0F.F . . . FFF.F 存存储储体体n-1

23、 MAR MAR MAR 译译码码器器 存存储储器器地地址址寄寄存存器器（高高位位） （低低位位） 低位交叉访问存储器结构框图低位交叉访问存储器结构框图 地址是编码方法：地址是编码方法： 由由8 8个存储体构成的低位交叉编址方式个存储体构成的低位交叉编址方式主存储器数据寄存器主存储器数据寄存器0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818191920202121222223232424252526262727282829293030313132323333343435353636373738383939404

24、041414242434344444545464647474848494950505151525253535454555556565757585859596060616162626363体内地址体内地址(3(3 位位) )模块地址模块地址(3(3 位位) )主存储器地址寄存器主存储器地址寄存器（6 6 位）位）体内地址体内地址2体数体数8体号体号 3 n n个存储体分时启动个存储体分时启动 一种采用流水线方式工作的并行存储器 每存储体的启动间隔为：t 其中： Tm为每个存储体的访问周期, n为存储体个数。 0 0 号号存存储储体体 1 1 号号存存储储体体 2 2 号号存存储储体体 n n-

25、-1 1号号存存储储体体 - -存存储储体体周周期期Tm - Tnm访问冲突访问冲突 共有共有n n个存储体，每个存储周期只能取到个存储体，每个存储周期只能取到k k个有效字个有效字, ,其余其余n-kn-k个存储体有冲突。个存储体有冲突。假设p(k)是k的概率密度函数，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值为：N是每个存储周期能够访问到的平均有效字的个数。通常把 N N称为并行存储器的加速比。称为并行存储器的加速比。Nkp kkn()1定义转移概率为g，即读出的是转移指令，且转移成功的概率。这时有： p(1)p(1)g g p(2) p(2)(1-p

26、(1)g(1-p(1)g(1-g)g(1-g)g p(3) p(3)(1-p(1)-p(2)g(1-p(1)-p(2)g(1-g)(1-g)2 2g g p(k) p(k)(1-g)(1-g)k-1k-1g (g (k1,2,n1) p(n) p(n)(1-g)(1-g)n-1n-1 g g(1-g)g(1-g)g(1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)g(1-g)g(1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)(1-g)n-2n-2g g n(

27、1-g)n(1-g)n-1n-1以上共以上共n n行，前行，前n-2n-2行分别为等比级数行分别为等比级数把把n-1n-1行拆分成行拆分成2 2项项则：则：1g1g2(1-g)g2(1-g)g3(1-g)3(1-g)2 2g g (n-1)(1-g)(n-1)(1-g)n-2n-2g gn(1-g)n(1-g)n-1n-1qqaaSnn11等比级数求和公式：1-(1-g)1-(1-g)n-1n-11-(1-g)1-(1-g)n-1n-1 (1-g)-(1-g)(1-g)-(1-g)n-1n-1 (1-g)(1-g)2 2-(1-g)-(1-g)n-1n-1 (1-g)(1-g)n-2n-2-(

28、1-g)-(1-g)n-1n-1 n(1-g)n(1-g)n-1n-1ggNn)1(1化简后得到：(1-g)(1-g)n-2n-2g g1 1(1-g)(1-g)(1-g)(1-g)2 2(1-g)(1-g)n-2n-2(1-g)(1-g)n-1n-1 并行存储体个数与程序转移概率的关系并行存储体个数与程序转移概率的关系 存储体个数存储体个数 g=0.01g=0.01 g=0.1g=0.1 g=0.2g=0.2 g=0.3g=0.3 g=0.4g=0.4 4 4 3.943.94 3.443.44 2.952.95 2.532.53 2.182.18 8 8 7.737.73 5.705.70

29、 4.164.16 3.143.14 2.462.46 1616 14.8514.85 8.158.15 4.864.86 3.323.32 2.502.50 3232 27.5027.50 9.669.66 5.005.00 3.333.33 2.502.50 几台巨型、大型计算机的主存储器结构几台巨型、大型计算机的主存储器结构机器型号机器型号存储体个数存储体个数n n存储体字长存储体字长w w存储周期存储周期 T Tm频带宽度频带宽度 B BmIBM370/165IBM370/1654 432322,000ns2,000ns8MB/s8MB/sCDC6600CDC6600323232321

30、,000ns1,000ns128MB/s128MB/sCDC7600CDC760032323232275ns275ns465MB/s465MB/sCRAY-1CRAY-11616646450ns50ns2,560MB/s2,560MB/sASCASC8 8256256160ns160ns1,600MB/s1,600MB/sSTAR-100STAR-10032325125121,280ns1,280ns1,600MB/s1,600MB/s例例3.7：Star-100巨型机存储系统采用并行和交叉相结合的方式工作，有32个存储体低位交叉，每次并行读写512位，存储周期为1280ns，处理机字长32位

31、，计算它的速度提高多少倍？和频带宽度Bm。解：解：因为：n32，w512，Tm1280ns， Bmn w/tm32512b/1280ns 12.8Gb/s1.6GB/s400MW/s提高提高512512倍倍实际速度的提高要远远小于这个数字实际速度的提高要远远小于这个数字 3.1.6 3.1.6 无冲突访问存储器无冲突访问存储器1. 1. 一维数组一维数组( (向量向量) )的无冲突访问存储器的无冲突访问存储器 按连续地址访问，没有冲突， 位移量为2的变址访问，速度降低一倍， 0 0 号号体体 1 1 号号体体 2 2 号号体体 3 3 号号体体 体体内内地地址址 0 0 a0 a1 a2 a3

32、 1 1 a4 a5 a6 a7 2 2 a8 a9 a10 a11 3 3 具体方法：具体方法： 存储体的个数取质数，且存储体的个数取质数，且nn向量长度。向量长度。 原因：原因：变址位移量必然与存储体个数互质 例如：例如：Burroughs公司巨型科学计算机BSP 存储体个数为17 向量长度16我国研制的银河巨型向量机 存储体的个数为37 向量长度322. 2. 二维数组的无冲突访问存储器二维数组的无冲突访问存储器要求：要求：一个一个nn的二维数组，按行、列、对角线和的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，反对角线访问，并且在不同的变址位移量情况下，都能实

33、现无冲突访问。都能实现无冲突访问。顺序存储：顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突 0 0 号号体体 1 1 号号体体 2 2 号号体体 3 3 号号体体 体体内内地地址址 0 0 a00 a01 a02 a03 1 1 a10 a11 a12 a13 2 2 a20 a21 a22 a23 3 3 a30 a31 a32 a33 错位存储：错位存储： 按行、按列访问无冲突， 但按对角线访问有冲突0 0号号体体1 1号号体体2 2号号体体3 3号号体体体体内内地地址址0 0a00a01a02a031 1a13a10a11a122 2a22a23a20a213 3a31a32a3

34、3a30nn二维数组无冲突访问存储方案二维数组无冲突访问存储方案 ( P Budnik 和和 D J Kuck提出提出 ) ： 并行存储体的个数并行存储体的个数mn，并且取质数，同时还要在，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。行、列方向上错开一定的距离存储数组元素。 设同一列相邻元素在并行存储器中错开设同一列相邻元素在并行存储器中错开d1个存储体个存储体存放，同一行相邻元素在并行存储器中错开存放，同一行相邻元素在并行存储器中错开d2个存个存储体存放。当储体存放。当m22p1（p为任意自然数）时，为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线能够同时实现

35、按行、按列、按对角线和按反对角线无冲突访问的充要条件是：无冲突访问的充要条件是：d12P，d21。例如：例如：44的二维数组，取并行存储体的个数的二维数组，取并行存储体的个数m5，由关系式由关系式m22P1，解得到，解得到p1，计算得到：，计算得到： d1212 d210 0号号体体1 1号号体体2 2号号体体3 3号号体体4 4号号体体体体内内地地址址0 0a00a01a02a031 1a13a10a11a122 2a21a22a23a203 3a30a31a32a3344 nn数组中的任意一个元素数组中的任意一个元素aij在无冲突并行存储器中在无冲突并行存储器中的体号地址和体内地址的计算公

36、式：的体号地址和体内地址的计算公式： 体号地址：体号地址：(2P ijk) MOD m 体内地址：体内地址：i 其中：0in1， 0jn1， k是数组的第一个元素a00所在体号地址， m是并行存储体的个数，要求mn且为质数， p是满足m22P1关系的任意自然数。 主要缺点：主要缺点：浪费存储单元 对于对于nn数组数组, ,有有(m-n) m个存储单元浪费个存储单元浪费 主要优点：主要优点：实现简单 列元素顺序存储，行元素按地址取模顺序存储列元素顺序存储，行元素按地址取模顺序存储3. 3. 二维数组的无冲突访问存储器二维数组的无冲突访问存储器( (之二之二) )规则：规则：对于任意一个对于任意一

37、个nn的的数组，如果能够找到满足数组，如果能够找到满足n22P关系的任意自然数关系的任意自然数p，则这个二维数组就能够，则这个二维数组就能够使用使用n个并行存储体个并行存储体实现按行、列、对角线和反对角实现按行、列、对角线和反对角线的无冲突访问。线的无冲突访问。4 44 4数组用数组用4 4个存储体的无访问冲突存储方案个存储体的无访问冲突存储方案0 0号号体体1 1号号体体2 2号号体体3 3号号体体体体内内地地址址0 0a00a20a30a101 1a21a01a11a312 2a32a12a02a223 3a13a33a23a03实现方法：实现方法： 假设假设aij是是4 44 4数组中的任意一个元素，数组中的任意一个元素，下标下标i和和j都可都可以用两位二进制表示。假设以用两位二进制表示。假设i和和j的高位和低位分别为的高位和低位分别为iH、iL、jH和和jL，则则aij在无冲突并行存储器中的体号地在无冲突并行存储器中的体号地址和体内地址如下：址和体内地址如下： 体号地址：体号地址：2(iL jH)(iH iL jL) 体内地址：体内地址：j 其中：其中：0i3，0j3主要优点：主要优点：没有浪费的存储单元没有浪费的存储单元，主要缺点：主要缺点：在执行并行读和写操作时需要借助比较复杂在执行并行读和写操作时需要借助比较复杂的对准网络的对准网络。