4无访问冲突存储器 访问数据比取指令的冲突更为严重 介绍数组的无冲突访问存储器 一维数组(向量)的无冲突访问存储器 维数组的存储方案 0号体1号体2号体3号体 体内地址0 a3 a10 按连续地址访问,没有冲突 按位移量为2的变址方式访问,频带宽度降低一半 方法:存储体的个数取质数,且n≥向量长度。 原因:变址位移量必然与存储体个数互质 例如: Burroughs公司巨型机BSP,存储体个数为17 我国研制的银河巨型计算机,存储体的个数为37 二维数组的无冲突访问存储器之一) 要求:一个n×n的二维数组,按行、列、对角线和反对角线访问,并且在 不同的变址位移量情况下,都能实现无冲突访问 顺序存储:按行、对角线访问没有冲突,但按列访问每次冲突 0号体1号体2号体3号体 体内地址0 a00 a02 a a10 a12 a13 20 a a22 a30 a31 a32 133 错位存储:按行、按列访问无冲突,按对角线访问有冲突 0号体1号体2号体3号体 体内地址0「am 10 1 a23 221 a31 a32 a a30 P· Budnik和D·J·Kuck提出了一种能够实现n×n的二维数组无冲突访问
3—1 4 无访问冲突存储器 访问数据比取指令的冲突更为严重 介绍数组的无冲突访问存储器 • 一维数组（向量）的无冲突访问存储器 一维数组的存储方案 0 号体 1 号体 2 号体 3 号体 体内地址 0 a0 a1 a2 a3 1 a4 a5 a6 a7 2 a8 a9 a10 a11 3 … … … … 按连续地址访问，没有冲突 按位移量为 2 的变址方式访问，频带宽度降低一半，…… 方法：存储体的个数取质数，且 n≥向量长度。 原因：变址位移量必然与存储体个数互质 例如：Burroughs 公司巨型机 BSP，存储体个数为 17 我国研制的银河巨型计算机，存储体的个数为 37 • 二维数组的无冲突访问存储器(之一) 要求：一个 n×n 的二维数组，按行、列、对角线和反对角线访问，并且在 不同的变址位移量情况下，都能实现无冲突访问。 顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突 0 号体 1 号体 2 号体 3 号体 体内地址 0 a00 a01 a02 a03 1 a10 a11 a12 a13 2 a20 a21 a22 a23 3 a30 a31 a32 a33 错位存储：按行、按列访问无冲突，按对角线访问有冲突 0 号体 1 号体 2 号体 3 号体 体内地址 0 a00 a01 a02 a03 1 a13 a10 a11 a12 2 a22 a23 a20 a21 3 a31 a32 a33 a30 P·Budnik 和 D·J·Kuck 提出了一种能够实现 n×n 的二维数组无冲突访问
的存储方案 并行存储体的个数m≥m,并且取质数,同时还要在行、列方向上错开一定 的距离存储数组元素。设同一列相邻元素在并行存储器中错开d个存储体存放 同一行相邻元素在并行存储器中错开d个存储体存放。当m=22+1(p为任 意自然数)时,能够同时实现按行、按列、按对角线和按反对角线无冲突访问 的充要条件是:d1=2,d=1 例如:4×4的二维数组,取并行存储体的个数m=5, 由关系式m=22+1,解得到p=1,计算得到d=21=2,d=1。 4×4二维数组按行、列、对角线和反对角线访问都不冲突的存储方案 0号体1号体2号体3号体4号体 体内地址02a0 a a13 a10 2 22 a32 a33 n×n二维数组中的任意一个元素a在无冲突并行存储器中的体号地址和体 内地址的计算公式 体号地址:(2Pi+j+k)MODm 体内地址 其中,0≤,j≤n-1,k是数组的第一个元素a0所在体号地址,m是并行存储 体的个数,要求m≥n且为质数;p是满足m=2P+1关系的任意自然数 主要缺点:浪费存储单元 在n×n二维数组的存储方案中,有(m-n)/m个存储单元浪费, 主要优点:实现简单 列元素按地址顺序存储,行元素按地址取模顺序存储 二维数组的无冲突访问存储器之二) 规则:对于任意一个n×n的二维数组,如果能够找到满足n=2关系的任意自 然数p,则这个二维数组就能够使用n个并行存储体实现按行、列、对角线和反 对角线的无冲突访问。 4×4数组用4个存储体的无访问冲突存储方案 0号体 1号体 2号体3号体 体内地址0 a00 20 a30 a10 221 a11 a31 232 a12 a02 a22 a 13 33 a23 a03 实现方法: 假设a是4×4二维数组中的任意一个元素,其中的下标i和j都可以用两 位二进制数表示,假设i和j的高位和低位分别为i、i、j和j,则a在无冲
3—2 的存储方案： 并行存储体的个数 m≥n，并且取质数，同时还要在行、列方向上错开一定 的距离存储数组元素。设同一列相邻元素在并行存储器中错开 d1个存储体存放， 同一行相邻元素在并行存储器中错开 d2个存储体存放。当 m＝2 2p＋1（p 为任 意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问 的充要条件是：d1＝2 P，d2＝1。 例如：4×4 的二维数组，取并行存储体的个数 m＝5， 由关系式 m＝2 2P＋1，解得到 p＝1，计算得到 d1＝2 1＝2，d2＝1。 4×4 二维数组按行、列、对角线和反对角线访问都不冲突的存储方案 0 号体 1 号体 2 号体 3 号体 4 号体 体内地址 0 a00 a01 a02 a03 1 a13 a10 a11 a12 2 a21 a22 a23 a20 3 a30 a31 a32 a33 n×n 二维数组中的任意一个元素 aij 在无冲突并行存储器中的体号地址和体 内地址的计算公式： 体号地址：（2 P i＋j＋k） MOD m 体内地址：i 其中，0≤i，j≤n－1，k 是数组的第一个元素 a00 所在体号地址，m 是并行存储 体的个数，要求 m≥n 且为质数；p 是满足 m＝2 2P＋1 关系的任意自然数。 主要缺点：浪费存储单元 在 n×n 二维数组的存储方案中，有（m－n）／m 个存储单元浪费， 主要优点：实现简单 列元素按地址顺序存储，行元素按地址取模顺序存储。 • 二维数组的无冲突访问存储器(之二) 规则：对于任意一个 n×n 的二维数组，如果能够找到满足 n＝2 2P关系的任意自 然数 p，则这个二维数组就能够使用 n 个并行存储体实现按行、列、对角线和反 对角线的无冲突访问。 4×4 数组用 4 个存储体的无访问冲突存储方案 0 号体 1 号体 2 号体 3 号体 体内地址 0 a00 a20 a30 a10 1 a21 a01 a11 a31 2 a32 a12 a02 a22 3 a13 a33 a23 a03 实现方法： 假设 aij 是 4×4 二维数组中的任意一个元素，其中的下标 i 和 j 都可以用两 位二进制数表示，假设 i 和 j 的高位和低位分别为 iH、iL、jH 和 jL，则 aij 在无冲
突并行存储器中的体号地址和体内地址可以通过如下公式计算: 体号地址:2(i⊕j)+(ii⊕j) 体内地址:j 其中,0≤i≤3,0≤j≤3,i、i、j、j均为0或1。 当数组的维数n大于4时,可以把数组划分成多个4×4的子阵。 主要优点:没有浪费的存储单元, 主要缺点:在执行并行读和写操作时需要借助比较复杂的对准网络。 3.2虚拟存储器 1961年英国曼彻斯特大学的 Kilborn等人提出的。 到了70年代被广泛地应用于大中型计算机系统中。 目前,许多微型机也开始使用虚拟存储器。 主要内容: 3.2.1虚拟存储器工作原理 3.22地址的映象和变换方 33.3加快内部地址变换速度的方法 3.3.4页面替换算法及其实现方法 3.3.5提高主存命中率的方法 3.2.1虚拟存储器工作原理 把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块一一页,每页 的大小相同。主存储器的页称为实页,虚拟存储器中的页称为虚页。 个主存地址A由两部分组成,实页号p和页内偏移d 个虚地址Av由三部分组成,用户号U、虚页号P和页内偏移D, 内部地址变换: 多用户虚拟地址A变换成主存实页号p 多用户虚拟地址中的页内偏移D直接作为主存实地址中的页内偏移d, 主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A。 用户号U 实页号P 页内偏移D 多用户虚拟地址Av的组成 实页号p 页内偏移d 主存地址A的组成 进行外部地址变换: 首先查外页表得到磁盘存储器的实地址
3—3 突并行存储器中的体号地址和体内地址可以通过如下公式计算： 体号地址：2（iL jH）＋（iH iL jL） 体内地址：j 其中，0≤i≤3，0≤j≤3，iH、iL、jH、jL 均为 0 或 1。 当数组的维数 n 大于 4 时，可以把数组划分成多个 4×4 的子阵。 主要优点：没有浪费的存储单元， 主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。 3.2 虚拟存储器 1961 年英国曼彻斯特大学的 Kilbrn 等人提出的。 到了 70 年代被广泛地应用于大中型计算机系统中。 目前，许多微型机也开始使用虚拟存储器。 主要内容： 3.2.1 虚拟存储器工作原理 3.2.2 地址的映象和变换方 3.3.3 加快内部地址变换速度的方法 3.3.4 页面替换算法及其实现方法 3.3.5 提高主存命中率的方法 3.2.1 虚拟存储器工作原理 把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块——页，每页 的大小相同。主存储器的页称为实页，虚拟存储器中的页称为虚页。 一个主存地址 A 由两部分组成，实页号 p 和页内偏移 d， 一个虚地址 Av 由三部分组成，用户号 U、虚页号 P 和页内偏移 D， 内部地址变换： 多用户虚拟地址 Av 变换成主存实页号 p 多用户虚拟地址中的页内偏移 D 直接作为主存实地址中的页内偏移 d， 主存实页号 p 与它的页内偏移 d 直接拼接起来就得到主存实地址 A。 用户号 U 实页号 P 页内偏移 D 多用户虚拟地址 Av 的组成 实页号 p 页内偏移 d 主存地址 A 的组成 进行外部地址变换： 首先查外页表得到磁盘存储器的实地址
然后再查内页表,看主存储器中是否有空页 把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机, 把要访问数据所在的一整页都从磁盘存储器调入到主存储器 页面替换:把主存中暂时不用的一页写回到磁盘存储器中原来的位置上 (书第148页)图3.17图页式虚拟存储器工作原理 3.2.2地址的映象与变换 三种地址空间:虚拟地址空间,主存储器地址空间,辅存地址空间 三种地址:虚拟地址、主存地址、磁盘地址 地址映象:把虚拟地址空间映象到主存地址空间 地址映象:在程序运行过程中,把虚拟地址变换成主存实地址 因地址映象和变换方法不同,有三种虚拟存储器: 页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器 1、段式虚拟存储器 地址映象方法:每个程序段都从0地址开始编址,长度可长可短,可以在程 序执行过程中动态改变程序段的长度 (书第149页)图3.18段式虚拟存储器的地址映象 段表主要包括:段的长度和起始地址。段号可以省掉。 地址变换方法 由用户号找到基址寄存器 从基址寄存器中读出段表的起始地址 把起始地址与多用户虚地址中段号相加得到段表地址 把段表中给出的起始地址与段内偏移D相加就能得到主存实地址。 (书第150页)图3.19段式虚拟存储器的地址变换 段式虚拟存储器的主要优点: (1)程序的模块化性能好 (2)便于程序和数据的共享 (3)程序的动态链接和调度比较容易 (4)便于实现信息保护
3—4 然后再查内页表，看主存储器中是否有空页。 把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机， 把要访问数据所在的一整页都从磁盘存储器调入到主存储器。 页面替换：把主存中暂时不用的一页写回到磁盘存储器中原来的位置上 （书第 148 页）图 3.17 图页式虚拟存储器工作原理 3.2.2 地址的映象与变换 三种地址空间：虚拟地址空间，主存储器地址空间，辅存地址空间 三种地址：虚拟地址、主存地址、磁盘地址 地址映象：把虚拟地址空间映象到主存地址空间 地址映象：在程序运行过程中，把虚拟地址变换成主存实地址 因地址映象和变换方法不同，有三种虚拟存储器： 页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器 1、段式虚拟存储器 地址映象方法：每个程序段都从 0 地址开始编址，长度可长可短，可以在程 序执行过程中动态改变程序段的长度。 （书第 149 页）图 3.18 段式虚拟存储器的地址映象 段表主要包括：段的长度和起始地址。段号可以省掉。 地址变换方法： 由用户号找到基址寄存器 从基址寄存器中读出段表的起始地址 把起始地址与多用户虚地址中段号相加得到段表地址 把段表中给出的起始地址与段内偏移 D 相加就能得到主存实地址。 （书第 150 页）图 3.19 段式虚拟存储器的地址变换 段式虚拟存储器的主要优点： (1) 程序的模块化性能好。 (2) 便于程序和数据的共享。 (3) 程序的动态链接和调度比较容易。 (4) 便于实现信息保护
段式虚拟存储器的主要缺点 (1)地址变换所花费的时间比较长,做两次加法运算 (2)主存储器的利用率往往比较低。 (3)对辅存(磁盘存储器)的管理比较困难。 2、页式虚拟存储器 由用户号U直接找到相对应的基址寄存器 从基址寄存器中读出页表起始地址 把页表起始地址与多用户虚地址中虚页号相加得到页表地址 从页表中读出主存页号p与虚地址中的页内偏移D拼接得到主存实地址 (书第152页)图3.20页式虚拟存储器的地址映象 (书第152页〕图3.21页式虚拟存储器的地址变换 页式虚拟存储器的主要优点: (1)主存储器的利用率比较高 (2)页表相对比较简单,节省了页表的存储容量 (3)地址映象和变换的速度比较快。 (4)对辅存(磁盘存储器)的管理比较容易。 页式虚拟存储器的主要缺点: (1)程序的模块化性能不好 (2)页表很长,需要占用很大的存储空间。 例如:虚拟存储空间4GB,页大小1KB,则页表的容量为4M字,16MB。 3、段页式虚拟存储器 用户按照程序段来编写程序,每个程序段分成几个固定大小的页。 地址映象方法: 每个程序段在段表中占一行 在段表中给出该程序段的页表长度和页表的起始地址, 页表中给出这个程序段的每一页在主存储器中的实页号 (书第154页)图3.22段页式虚拟存储器的地址映象 地址变换方法 先查段表,得到该程序段的页表起始地址和页表长度, 再查页表找到要访问的主存实页号, 最后把实页号p与页内偏移d拼接得到主存的实地址
3—5 段式虚拟存储器的主要缺点： (1) 地址变换所花费的时间比较长，做两次加法运算。 (2) 主存储器的利用率往往比较低。 (3) 对辅存（磁盘存储器）的管理比较困难。 2、页式虚拟存储器 由用户号 U 直接找到相对应的基址寄存器 从基址寄存器中读出页表起始地址 把页表起始地址与多用户虚地址中虚页号相加得到页表地址， 从页表中读出主存页号 p 与虚地址中的页内偏移 D 拼接得到主存实地址 （书第 152 页）图 3.20 页式虚拟存储器的地址映象 （书第 152 页）图 3.21 页式虚拟存储器的地址变换 页式虚拟存储器的主要优点： (1) 主存储器的利用率比较高。 (2) 页表相对比较简单，节省了页表的存储容量。 (3) 地址映象和变换的速度比较快。 (4) 对辅存（磁盘存储器）的管理比较容易。 页式虚拟存储器的主要缺点： (1) 程序的模块化性能不好。 (2) 页表很长，需要占用很大的存储空间。 例如：虚拟存储空间 4GB，页大小 1KB，则页表的容量为 4M 字，16MB。 3、段页式虚拟存储器 用户按照程序段来编写程序，每个程序段分成几个固定大小的页。 地址映象方法： 每个程序段在段表中占一行。 在段表中给出该程序段的页表长度和页表的起始地址， 页表中给出这个程序段的每一页在主存储器中的实页号。 （书第 154 页）图 3.22 段页式虚拟存储器的地址映象 地址变换方法： 先查段表，得到该程序段的页表起始地址和页表长度， 再查页表找到要访问的主存实页号， 最后把实页号 p 与页内偏移 d 拼接得到主存的实地址
(书第154页)图3.23段页式虚拟存储器的地址变换 4、外部地址变换 在操作系统中,把页面失效当作一种异常故障来处理。 每个用户程序都有一张外页表,虚拟地址空间中的每一页或每个程序段,在 外页表中都有对应的一个存储字 每一个存储字除了磁盘存储器的地址之外,至少还包括一个装入位。 匚磁盘号拄面号磁头号块号 磁盘存储器的地址格式 (书第156页)图3.25外部地址变换 32.3加快内部地址变换的方法 造成虚拟存储器速度降低的主要原因: (1)要访问主存储器必须先查段表或页表 (2)可能需要多级页表。 页表级数的计算公式:g=W2MD-lg2M 其中:Nv为虚拟存储空间大小, Np为页面的大小 Nd为一个页表存储字的大小, 例如:虚拟存储空间大小Nv=4GB,页的大小Np=1KB,每个页表存储字占 用4个字节。计算得到页表的级数: 8=/og24G-lg2IK]「32-10=3 log 21K-log 24 页表共有256×256×64=4M字,每个字存放一页(4K)的信息。 通常把1级页表驻留在主存储器中,2、3级页表只驻留一小部分在主存。 1、目录表 基本思想:用一个小容量高速存储器存放页表, 方法:页表的中包括多用户虚页号、主存实页号、修改位等, 采用相联方式访问。 地址变换过程:要把多用户虚地址中U与P拼接起来,相联访问目录表。 读出主存实页号p,把p与多用户虚地址中的D拼接得到主存实地址
3—6 （书第 154 页）图 3.23 段页式虚拟存储器的地址变换 4、外部地址变换 在操作系统中，把页面失效当作一种异常故障来处理。 每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在 外页表中都有对应的一个存储字。 每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。 磁盘号 拄面号 磁头号 块号 磁盘存储器的地址格式 （书第 156 页）图 3.25 外部地址变换 3.2.3 加快内部地址变换的方法 造成虚拟存储器速度降低的主要原因： (1) 要访问主存储器必须先查段表或页表， (2) 可能需要多级页表。 页表级数的计算公式： g Nv Np Np Nd = − − log log log log 2 2 2 2 其中： Nv 为虚拟存储空间大小， Np 为页面的大小， Nd 为一个页表存储字的大小， 例如：虚拟存储空间大小 Nv＝4GB，页的大小 Np＝1KB，每个页表存储字占 用 4 个字节。计算得到页表的级数： g G K K = − − = − − = log log log log 2 2 2 2 4 1 1 4 32 10 10 2 3 页表共有 256 256 64＝4M 字，每个字存放一页（4K）的信息。 通常把 1 级页表驻留在主存储器中，2、3 级页表只驻留一小部分在主存。 1、目录表 基本思想：用一个小容量高速存储器存放页表， 方法：页表的中包括多用户虚页号、主存实页号、修改位等， 采用相联方式访问。 地址变换过程：要把多用户虚地址中 U 与 P 拼接起来，相联访问目录表。 读出主存实页号 p，把 p 与多用户虚地址中的 D 拼接得到主存实地址
如果相联访问失败,发出页面失效请求。 主要优点:与页表放在主存中相比,查表速度快。 主要缺点:可扩展性比较差 主存储器容量增加时,目录表的造价高,速度降低 (书第158页)图3.26目录表法的地址变换过程 2、快慢表 快表TLB( Translation lookaside buffer) 小容量(几~几十个字),高速硬件实现,采用相联方式访问 慢表:当快表中查不到时,从存放在主存储器中的慢表中查找 按地址访问,用软件实现 快表与慢表也构成了一个两级存储系统。 (书第159页)图3.27采用快慢表的地址变换过程 3、散列函数 目的:把相联访问变成按地址访问,从而加大快表容量 散列( Hashing)函数:Ah=H(Pv),20位左右→6~8位 (书第160页)图3.28一种用硬件实现的散列函数 采用散列变换实现快表按地址访问 进免散列冲突:采用相等比较器 地址变换过程:相等比较与访问存储器同时进行 (书第161页)图3.29采用散列变换实现快表按地址访问
3—7 如果相联访问失败，发出页面失效请求。 主要优点：与页表放在主存中相比，查表速度快。 主要缺点：可扩展性比较差。 主存储器容量增加时，目录表的造价高，速度降低。 （书第 158 页）图 3.26 目录表法的地址变换过程 2、快慢表 快表 TLB(Translation Lookaside Buffer)： 小容量(几～几十个字)，高速硬件实现，采用相联方式访问 慢表：当快表中查不到时，从存放在主存储器中的慢表中查找 按地址访问，用软件实现 快表与慢表也构成了一个两级存储系统。 （书第 159 页）图 3.27 采用快慢表的地址变换过程 3、散列函数 目的：把相联访问变成按地址访问，从而加大快表容量 散列（Hashing）函数：Ah＝H（Pv），20 位左右6～8 位 （书第 160 页）图 3.28 一种用硬件实现的散列函数 • 采用散列变换实现快表按地址访问 避免散列冲突：采用相等比较器 地址变换过程：相等比较与访问存储器同时进行 （书第 161 页）图 3.29 采用散列变换实现快表按地址访问