高等计算机系统结构

存储器层次 第0层 第1层 第2层 第3层 第4层 特性 CPU寄存器 高速缓存 主存储器 磁盘存储器 磁带存储器 设备工艺 存取时间 容量(字节) ECL 10ns 512B SRAM 25-40ns 128KB 72 DRAM 60-100ns 512MB 5.6 磁盘机 10-20ms 磁带机 2-20min
第五章 并行存储器系统
5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术
5.4.1 5.4.2 5.4.3 5.4.4 虚拟存储器原理 共享存储和分布存储 DSM与SVM 虚拟存储器的主要技术
5.5 交叉访问的存储器
5.4 虚拟存储器技术
容 量 和 存 取 时 间 增 加
层0：M0
层1：M1 层2：M2 层3：M3 层4：M4 CPU内的寄存器 高速缓存 主存储器 磁盘存储器 磁带机
每 位 成 本 增 加
五个参数：
存取时间ti：从CPU到第i层存储器的往返时间 存储器容量Si：第i层的字节或字的数量 每字节成本Ci：第i层存储器的成本为CiSi 传输带宽bi：相邻层之间传送信息的速率 传输单位Xi：i和i+1层之间数据传送的粒度 对存储器系统中各层次存储器的特性， 1993年的统计数据如下表：
2. 相邻层之间的数据传送单位 CPU高速缓存：字 高速缓存主存储器：块（每块32个字节 （8个字）） 主存磁盘：页面（比如每页4K字节，包 含128块） 磁盘磁带：段 包含性可以用下面的图来说明：
M1:高速缓存
CPU寄存器 字单位 …… a ……
b
a,b为高速缓存 块，32个字节
块单位
5.3.2 有效存取时间
每当发生缺失时，就要付出代价去访问较 高层次的存储器。这种缺失在Cache中称为块 缺失。在主存储器中称为缺页错（page fault），因为块和页面是这些层次之间传送 信息的单位。 缺页错付出的时间代价要比块缺失付出的 更大：
Teff

i 1
n
f i ti h1t1 (1 h1 ) h2t 2
空间局部性（spatial locality）：一个 进程访问的各项的地址彼此很近，例如，表操 作或数组操作含对地址空间中某一区域的集中 访问。 顺序局部性（sequential locality）：在 典型程序中，除转移指令产生不按次序的转移 外，指令都是顺序执行的。
局部性原理指导我们去设计高速缓存、主存储 器以及虚拟存储器组织。
第五章 并行存储器系统
5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性
5.2.1 包含性 5.2.2 一致性 5.2.3 局部性
5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器
5.2 包含性、一致性和局部性
5.2.1 包含性（inclusion）
1. 包含性的定义 初始时，所有信息项都存放在最外层Mn， 在处理过程中，它的子集被复制到Mn-1，同 样， Mn-1的子集被复制到Mn-2，…… 如果在Mi中找到一个信息字，那么同一个 字的Copy在所有的高层Mi+1，Mi+2，……， Mn中都一定可以找到，即存在如下规律： M0 M1 M2…… Mn
• 1961年英国曼彻斯特大学Kilbrn等人提出 了70年代被广泛地应用于大中型计算机系 统中、目前许多微型机也广泛使用的虚拟 存储器。 • 虚拟存储器提供了几乎没有限制的存储器 工作空间。 • 虚拟地址在编译时产生。 • 虚拟地址到物理地址的转换在运行时进行， 需要使用转换表和映象系统。 • 替换策略。
• Hennessy和Patterson（1990年）提出了一条 90-10规则：
–典型程序在10%的代码上可能要耗费其执行时间的 90% –例如嵌套循环操作的最内层循环
• 时间局部性（temporal locality）：最近的 访问项（指令或数据）很可能在不久的将来再 次被访问。即对最近使用区域的集中访问。
M2:主存储器 a 页面A b 页面B
页单位
M3:磁盘存储器 a 页面A b 页面B 段G
段F 段单位
M4:磁带机 后援存储器 a 页面A 段F b 页面B 段G
5.2.2 一致性（coherence）
1.一致性定义
同一个信息项与后继存储器层次的副本是 一致的。 如果在高速缓存中的一个字被修改过，那 么在所有更高层上该字的副本也必须立即或最 后加以修改 。
• 内部地址变换：
– 多用户虚拟地址Av变换成主存实地址A – 多用户虚拟地址中的页内偏移D直接作为 主存实地址中的页内偏移d – 主存实页号p与它的页内偏移d直接拼接 起来就得到主存实地址A
• 外部地址变换：
– 首先查外页表得到磁盘存储器实地址 – 把磁盘存储器实地址和主存储器实页号送 入输入/输出处理机 – 把要访问数据所在的一整页都从磁盘存储 器调入到主存储器
访问主存
主存页面表
主存未满 主存满
0页 1页 … … 2P-1
X 用 户
p
d
A
页面 替换算法
0页 1页 … … 2 -1 主存储器
p
主存页号
0页 1页 … … 磁盘存储器
Y 用 户
I/O 处理机 调入页 被替换页 （I/O 通道） 替换页
调入页
页式虚拟存储器工作原理
• 地址变换：在程序运行时，把虚地址变 换成主存实地址 • 因地址映象和变换方法不同，有三种虚 拟存储器：页式虚拟存储器、段式虚拟 存储器、段页式虚拟存储器
c3=0.0002美元
要求：有效存取时间Teff=10.04s,
高速缓存命中率为h1=0.98， 主存储器命中率h2=0.9， 总成本上限为15000美元。
解：
C C1S1 C2 S 2 C3 S3 15000 代入有：S3 39.8GByte Teff h1t1 (1 h1 )h2t 2 (1 h1 )(1 h2 )h3t3 10.04 代入可得t 2 903ns
如果在同样的预算限制条件下，要把主存储 器容量提高64M字节，那么只好以减少磁盘容 量为代价，但是这一变化并不影响高速缓存的 命中率。如果使用合适的页面替换算法，可能 会增加主存储器的命中率，但Teff有所降低。
练习：
P168 习题4.11
层次化存储器系统必须解决的问题：
（1）数据块在较高层存储器中存放在哪个 位置？即块和页的定位问题。如果一个块存放 在某一上层存储器中，怎样确定并找到该块， 即块的寻址问题。 （2）不命中的将从下层存储器中访问，并 将该块调入上层存储器中，但是如果上层存储 器中已无空闲空间，则势必将上层存储器中的 某一块调出，但应调出那一块，即替换问题。 （3）在写访问时，写入上层存储器中的数 据必须在适当的时候写入下层存储器，何时写？
2.维护一致性的两种策略
（1）写直达（write-through,WT），即如果 在Mi（i=1，2，…，n-1）中修改了一个字，则 在Mi+1中需要立即修改。
（2）写回（write-back,WB），即在Mi+1 中 的修改延迟到Mi中正在修改的字被替换时才进 行。
5.2.3 局部性（locality）
地址的映象与变换
• 三种地址空间：虚拟地址空间，主存储 器地址空间，辅存地址空间 • 地址映象： 把虚拟地址空间映象到主存地址空间
磁盘存储器地址
访磁盘存储器
命中 未命中 访磁带等
外部地址变换 虚页号磁盘实地址 U+P P U+P
选页
外部地址变换
U
主存页面失效
未命中
D
Av 多用户虚地址
内部地址变换 命中 虚页号主存实页号
第五章 并行存储器系统
5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划
5.3.1 命中率 5.3.2 有效存取时间
5.4 虚拟存储器技术 5.5 交叉访问的存储器
5.3 存储器容量的规划
存储器层次结构的性能是由层次结构的有 效存取时间Teff决定的，它依赖于相继层 次的命中率和访问频率。
计算机科学技术学院研究生课程
高等计算机系统结构
黑龙江大学计算机科学技术学院
李金宝
2006年2月-2010年4月
高等计算机系统结构
第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 第十章 并行计算机模型 程序划分与调度 系统互连与通信 可扩展性能原理 并行存储器系统 高速缓存与共享存储器 指令级并行处理 标量处理机与向量处理机 并行模型、语言与编译器 并行程序设计与开发
60-228GB 512G-2TB 0.23 0.01
成本(美分/KB) 18000
带宽(MB/S) 400-800
传送单位 字:4-8B
250-400
80-133
3-5
0.18-0.23
块:32B 页:0.5-1KB
文件:5- 后援存储器 512KB
分配管理 编译器分配 硬件控制 操作系统 操作系统/ 操作系统/ 用户 用户
5.4.1 虚拟存储器工作原理
• 把主存储器、磁盘存储器和虚拟存储器 都划分成固定大小的页，主存储器的页 称为实页，虚拟存储器中的页称为虚页。 • 一个主存地址A由两部分组成，实页号p 和页内偏移d • 一个虚地址Av由三部分组成，用户号U、 虚页号P和页内偏移D。
用户号U
虚页号P 页内偏移D 多用户虚拟地址Av的组成 实页号p 页内偏移d 主存地址A的组成
f i (1 h1 )(1 h2 ) (1 hi 1 )hi
即在较低层次有i-1次缺失而在Mi有一次命中 时访问Mi成功的概率。
f
i 1
n
i
1, f1 h1
通常情况下，有：
f1 f 2 f n
对存储器内层的访问比对外层的访问要多。
访问内存比访问外存要多。
(1 h1 )(1 h2 ) (1 hn 1 ) hn t n
5.3.3 层次结构的优化
• 优化目标
– 使Teff接近于M1的t1， – 总成本接近于Mn的Cn。
• 优化过程可以表达为：对一个线性规划求最小 值问题:
Si 0, ti 0, 对于i 1,2,, n Ctotal Ci Si C0 (总价格的上限）时，
1、段式虚拟存储器 • 地址映象方法：每个程序段都从0地址 开始编址，长度可长可短，可以在程序 执行过程中动态改变程序段的长度。
主程序
0 1k 0 500 0 200 0 200
0段
1段 2段
段号 段长 起址 0 1k 8k 1 500 16k 2 200 9k 3 200 30k
0
8k 9k
16k 30k
3段
程序 空间
Leabharlann Baidu
主存储器
• 地址变换方法：
–由用户号找到基址寄存器 –从基址寄存器中读出段表的起始地址 –把起始地址与多用户虚地址中段号相加得 到段表地址 –把段表中给出的起始地址与段内偏移D相 加就能得到主存实地址
多用户 用户号U 段号S 虚地址 0 6 n-1 As As 0 1 2 3 4
5.3.1 命中率
• 在Mi中找到一个信息项时，称之为命中，反 之称为缺失。 • 假定在层次结构中的存储器层次为Mi和Mi-1， 其中i=1，2，…，n。则在Mi层的命中率hi是 信息项可在Mi中找到的概率。 • 它是表示两个相邻层Mi-1和Mi特性的函数。 • 在Mi中的缺失率定义为1-hi。
• 相继层的命中率是存储器容量、管理策略和程 序行为的函数，它是独立的随机变量，其值在 0到1之间。 • 假设h0=0和hn=1，即CPU总是先访问M1，并且访 问到最外层Mn时总是命中。则对Mi的访问频率 为：
i 1 n
要将有效存取时间Teff f i ti 减到最小值。
i 1
n
例1：存储器层次结构设计
存储器层次 高速缓存 主存储器 磁盘阵列 存取时间 t1 = 25ns t2 = 未知 t3 = 4ms 容量 价格/K字节
s1=512K字节 c1=1.25美元 s2=32M字节 c2=0.2美元 s3 = 未知
第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器
5.1 存储器系统的层次结构
现代计算机系统都以存储器为 中心，在计算机运行过程中， 存储器是各种信息存储和交 换的中心。
存储器系统的层次结构图