哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 5章 分布式存储器及其
时延容忍
??1 层次存储器技术
??2 高缓一致性协议
??3 共享存储器的一致性
??4 分布式高速缓 /主存体系
结构
哈尔滨工业大学计算机科学与技术学院
?1 层次存储器技术
?分析典型层次存储器的存储
特性和操作性质。
?一、存储部件的特性
?存储时间
?存储容量
?传输速率和带宽
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?二、存储器层次性质
?1.包含性
?2.数据传输单位
哈尔滨工业大学计算机科学与技术学院
?3.访问局部性
?层次存储器结构是基于访问局部性
这一程序特性为基础而发展起来的。
?这些存取在时间、空间和顺序上往
往集中在一定范围内进行。
?(1)时间局部性
?最近的访问项 (指令或数据 )很有可
能在不久的将来被再次访问。
哈尔滨工业大学计算机科学与技术学院
?(2)空间局部性
? 指进程趋向于访问地址接近的数据，
例如：对表和数据的操作会引起对某
一地址空间的集中访问。
? (3)顺序局部性
? 对程序而言，除了跳转指令会导致执
行顺序的打乱之外，指令串行总是按
照一定的串行顺序进行的。
哈尔滨工业大学计算机科学与技术学院
?4,局部性对存储器设计的影响
?时间局部性导致 LRU替换算法等的
使用；
?空间局部性有利于确定相邻存储器
层次间的数据传输单位，也有利于
确定相邻层次的存储器容量。
?顺序局部性影响最佳调度的颗粒度
大小 (颗粒度组合 )。预取技术也受
这些局部性的影响。
哈尔滨工业大学计算机科学与技术学院
?5.一致性问题
? 是系统结构方面一个重要的问题。
哈尔滨工业大学计算机科学与技术学院
?三、存储器容量的规划
? 存储器层次结构的性能由所有层次的
有效存取时间 Teff(effective access
time)决定,Teff由下述量决定,
?相邻层次的命中率 (hitratios)
?访问频率 (accessfrequencies)
哈尔滨工业大学计算机科学与技术学院
?1,命中率
?hi定义,
?存储器层次结构中人以两个相邻层
当在 Mi找到某一信息项时的概率，
成为命中率。
?对 Mi的访问频率
fi(Accessfrequency)定义为,
fi=(1-h1)(1-h2)(1-hn-1)tn
哈尔滨工业大学计算机科学与技术学院
?2.有效存取时间
?Teff=
h1t1+(1-h1)h2.t2+(1-h1)(1-
h2)h3t3 +．．,+(1-h1)(1-h2)(1-
hn-1)tn
哈尔滨工业大学计算机科学与技术学院
3,层次结构的优化
?已知：每一层 Mi的单位价格 ci、容
量 si;
?存储器层次结构的总成本可作如
下估计,
哈尔滨工业大学计算机科学与技术学院
?优化的方法,
?由于 c1>c2>c3>… >cn,
?必须选择 s1<s2<s3… <sn 。
?优化的层次存储器设计应当使
Teff尽量接近于 t1，而总成本接
近于 cn。
哈尔滨工业大学计算机科学与技术学院
?优化过程可以表达为一个由总成
本上限为 C0(取上整值 )线性规划
问题。也就是在如下限制，使 Teff
最小化,
哈尔滨工业大学计算机科学与技术学院
?例题,存储器层次结构的设计
?利用下列存储器特性来设计一个 3层
的层次结构存储器。
?设计目标是使 Teff =10.04μ s，而高
速缓存命中率 h1=0.98，主存命中率
h2=0.9。同时，存储器总成本上限
是 $15,000。总成本是按,
?C=c1s1+c2s2+c3s3<15,000来计算的。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 由上参数可得在不超过预算的前提下，
磁盘的最大容量为 s3=39.8GB。
? 求主存的存取时间 t2。已知有效存取
时间计算如下,
?Teff=h1t1+(1-h1)h2t2+(1-h1)（ 1-
h2)h3t3
代入已知量，有,
? 10.04x10-6=0.98x25x10-9+ 0.02x0.9xt2+
0.02x0.1 x 1 x4x10-3
? 主存存取时间为 t2=903ns。
?
哈尔滨工业大学计算机科学与技术学院
?总结,
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 5章 分布式存储器及其
时延容忍
??1 层次存储器技术
??2 高缓一致性协议
??3 共享存储器的一致性
??4 分布式高速缓 /主存体系
结构
哈尔滨工业大学计算机科学与技术学院
?1 层次存储器技术
?分析典型层次存储器的存储
特性和操作性质。
?一、存储部件的特性
?存储时间
?存储容量
?传输速率和带宽
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?二、存储器层次性质
?1.包含性
?2.数据传输单位
哈尔滨工业大学计算机科学与技术学院
?3.访问局部性
?层次存储器结构是基于访问局部性
这一程序特性为基础而发展起来的。
?这些存取在时间、空间和顺序上往
往集中在一定范围内进行。
?(1)时间局部性
?最近的访问项 (指令或数据 )很有可
能在不久的将来被再次访问。
哈尔滨工业大学计算机科学与技术学院
?(2)空间局部性
? 指进程趋向于访问地址接近的数据，
例如：对表和数据的操作会引起对某
一地址空间的集中访问。
? (3)顺序局部性
? 对程序而言，除了跳转指令会导致执
行顺序的打乱之外，指令串行总是按
照一定的串行顺序进行的。
哈尔滨工业大学计算机科学与技术学院
?4,局部性对存储器设计的影响
?时间局部性导致 LRU替换算法等的
使用；
?空间局部性有利于确定相邻存储器
层次间的数据传输单位，也有利于
确定相邻层次的存储器容量。
?顺序局部性影响最佳调度的颗粒度
大小 (颗粒度组合 )。预取技术也受
这些局部性的影响。
哈尔滨工业大学计算机科学与技术学院
?5.一致性问题
? 是系统结构方面一个重要的问题。
哈尔滨工业大学计算机科学与技术学院
?三、存储器容量的规划
? 存储器层次结构的性能由所有层次的
有效存取时间 Teff(effective access
time)决定,Teff由下述量决定,
?相邻层次的命中率 (hitratios)
?访问频率 (accessfrequencies)
哈尔滨工业大学计算机科学与技术学院
?1,命中率
?hi定义,
?存储器层次结构中人以两个相邻层
当在 Mi找到某一信息项时的概率，
成为命中率。
?对 Mi的访问频率
fi(Accessfrequency)定义为,
fi=(1-h1)(1-h2)(1-hn-1)tn
哈尔滨工业大学计算机科学与技术学院
?2.有效存取时间
?Teff=
h1t1+(1-h1)h2.t2+(1-h1)(1-
h2)h3t3 +．．,+(1-h1)(1-h2)(1-
hn-1)tn
哈尔滨工业大学计算机科学与技术学院
3,层次结构的优化
?已知：每一层 Mi的单位价格 ci、容
量 si;
?存储器层次结构的总成本可作如
下估计,
哈尔滨工业大学计算机科学与技术学院
?优化的方法,
?由于 c1>c2>c3>… >cn,
?必须选择 s1<s2<s3… <sn 。
?优化的层次存储器设计应当使
Teff尽量接近于 t1，而总成本接
近于 cn。
哈尔滨工业大学计算机科学与技术学院
?优化过程可以表达为一个由总成
本上限为 C0(取上整值 )线性规划
问题。也就是在如下限制，使 Teff
最小化,
哈尔滨工业大学计算机科学与技术学院
?例题,存储器层次结构的设计
?利用下列存储器特性来设计一个 3层
的层次结构存储器。
?设计目标是使 Teff =10.04μ s，而高
速缓存命中率 h1=0.98，主存命中率
h2=0.9。同时，存储器总成本上限
是 $15,000。总成本是按,
?C=c1s1+c2s2+c3s3<15,000来计算的。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 由上参数可得在不超过预算的前提下，
磁盘的最大容量为 s3=39.8GB。
? 求主存的存取时间 t2。已知有效存取
时间计算如下,
?Teff=h1t1+(1-h1)h2t2+(1-h1)（ 1-
h2)h3t3
代入已知量，有,
? 10.04x10-6=0.98x25x10-9+ 0.02x0.9xt2+
0.02x0.1 x 1 x4x10-3
? 主存存取时间为 t2=903ns。
?
哈尔滨工业大学计算机科学与技术学院
?总结,
