毕业论文网
该文是关于计算机系统论文范文，为你的论文写作提供相关论文资料参考。
《计算机系统结构》课程中程序局部性原理的应用
郑丽萍,赵玉娟
（河南工业大学信息科学与工程学院,河南郑州450001）
摘 要：程序局部性原理是计算机系统设计的四个定量原理之一,贯穿计算机系统设计各部分.通过有效地利用局部性原理,增加较少的硬件资源,有效提高计算机系统在存储系统和流水线技术功能性.
关键词：程序局部性原理；存储系统；LRU替换算法；流水线技术
中图分类号：G434文献标识码：A文章编号：16727800（2018）06004202
收稿日期：20180303
基金项目：河南省研究生教育教学改革研究与实践项目（2017SJGLX046Y）；河南工业大学教改项目（27610011）
作者简介：郑丽萍（1976）,女,硕士,河南工业大学信息科学与工程学院计算机工程系讲师,研究方向计算机系统结构与软件开发；赵玉娟（1979）,女,硕士,河南工业大学信息科学与工程学院计算机工程系副教授,研究方向计算机系统结构与网络安全.
0引言
程序的局部性原理（Principle of Locality）是计算机系统设计的四个定量原理之一,程序执行时所访问的存储器分布存在一个规律：程序执行时间的90%是在执行程序中的10%的代码［1］.程序的局部性包括时间局部性和空间局部性［2］.时间局部性是指即将访问信息很可能就是目前正在使用的信息；程序的空间局部性是即将访问信息和现在正在使用的信息在空间上相邻或者临近.因此,利用程序的局部性原理,可以根据程序最近的访问情况预测将来可能要访问的指令和数据.
1程序局部性原理在存储系统中的应用
1.1存储系统原理
存储器是计算机的核心部件之一,其性能直接关系到整个计算机系统的高低.而单个存储器没有办法满足用户对其的要求：高速度、低单位和大容量的需求.存储系统［3］有效地利用程序的局部性原理将两个或以上的存储器通过硬件或软硬件的方式结合起来,从整体上达到用户对存储器的需求,如图1所示,其中,离CPU近的存储器：容量小,速度快,单位高.虚拟存储系统和Cache存储系统是现代计算机最常见的两种存储系统,也是程序的局部性原理的有效利用.
虚拟存储系统的设置使计算机可以运行比其主存容量大得多的程序.利用有限的主存空间和程序运行的局部性原理,虚拟存储系统弥补了主存容量的不足.当CPU在主存中访问指令或数据发生页面失效时,虚拟存储系统将虚拟存储器中包含此信息的相应页面调入主存,根据时间局部性原理,即将用到的信息很大可能是CPU刚才访问的信息,再次访问时,将在主存中命中.例如在循环程序中,反复多次执行相同的一段程序和访问相同的数据；根据空间局部性原理,即将访问的指令或数据可能包含在刚刚调入主存的页面中,与刚刚访问的指令或数据相邻或临近,例如在程序执行过程中,除跳转指令成功、调用子程序和返回主程序之外,指令的执行都是顺序执行的,也就是时间上前后访问的指令或数据,在存储上也是相邻或临近的,已经被刚刚指令执行时,调入了主存.因此,CPU执行程序时,主存命中率非常高,虚拟存储系统的容量相当于虚拟存储器的容量.
图1多级存储系统
根据程序局部性原理,由高速缓冲存储器和主存构成Cache存储系统,实现主存速度的提高.CPU访问Cache存储系统时,当发生块失效时,将信息所在的数据块从主存中调入Cache,根据程序局部性原理,在接下来程序访问的数据很大可能就是刚才所访问的数据（时间局部性）或者是与刚才访问信息相邻近的数据（空间局部性）,刚刚访问的数据和其临近的数据很可能在同一块中,已经调入Cache中.因此,CPU执行程序时,在Cache存储系统中,Cache的命中率非常高,Cache存储系统的速度接近于Cache的访问速度.
除此之外,在虚拟存储器中的快慢表的设置,Cache存储系统的两级Cache设置都是通过有效地利用程序局部性原理提高系统的性能的.而多体交叉存储器的主存在某种程度上也利用了程序的局部性原理的性质.
1.2Cache存储系统查询方式中的主候选位置
Cache存储系统的查询方式是指当所要访问的块在Cache存储器中时,如何找到该块.在Cache存储系统中,地址映像方式有三种：全相联、直接相联和组相联.在不同的映像方式下,主存中的块调入Cache中的位置不同.直接相联映射在主存某一块；组相联和全相联映射在主存多个块中,这些块称为候选位置或候选项.假设Cache的候选位置有4块,分别是：A、B、C、D,当CPU访问Cache时,Cache中有所要访问的块,如何确定其位置？采用顺序查找的方式可以有四种情况,如图2所示.
图2顺序查找四种情况
从哪个候选项开始查找最有可能是包含要找的数据呢？根据程序性局部性原理,上次访问过的数据块在最有可能包含所需要的信息,从上次访问块开始访问,最有可能开始查找就找到所要访问的块,此块称为主候选位置（Most Recently used）.因此,计算机系统结构设计中,在Cache存储系统中查找所需要的数据时,从主候选位置开始顺序查找.
1.3存储系统中LRU替换算法
在存储系统中,当发生失效时,低一级的存储器相应的内容需要调入到高一级的存储器中,而高一级的存储器又被占满,这时需要考虑替换问题.例如在Cache存储系统中,当新调入一块,而Cache已被占满时,需要考虑替换哪一块？在直接相联中,替换块只有一块,不必选择；在全相联和组相联中,则有多个选择.
主要的替换算法有：随机法RAND、先进先出FIFO和最近最少使用法LRU.随机法和先进先出没有利用历史记录,在进行块替换时,失效率较高.LRU替换算法指选择近期最少被访问的块作为替换块,在实际实现时在LRU的基础上变通,选择最久没有被访问过的块作为替换块.也就是说,在近期被访问的块很可能在接下来的时间被重新访问,或者说在接下来的时间访问的数据和刚刚访问的数据在同一块中；反之,最久没有被访问的块,在最近时间内可能也不会被访问.表1给出了两种Cache容量的不同相联度的LRU和随机替换法的失效率比较.从表中可以看出,对于容量和相联度都相同的Cache,采用LRU替换算法的失效比采用随机替换算法的失效率小；同时也能看出,采用Cache存储系统时,Cache的命中率都在94%以上,达到了设置Cache存储系统的目标.
表1LRU和随机替换算法的失效率比较
Cache
容量（KB）相 联 度2路LRU
（%）随机替换
（%）4路LRU
（%）随机替换
（%）8路LRU
（%）随机替换
（%）
165.85.694.675.294.394.96
641.882.011.541.661.391.53
2程序局部性原理在流水线技术中的应用
流水线方式是把一个重复的过程分解为若干个子过程,每个子过程由专门的功能部件来实现,每个子过程可以与其他子过程同时进行.通过流水线技术,可以提高指令的并行度,最终提高处理机程序的执行速度.
流水线处理机的关键技术是缓冲技术和预处理技术.在流水线处理机结构中通常设置多个缓冲栈,按照程序指令的编写顺序,将指令和操作数预取或预处理到相应的缓冲栈.也就是说,接下来要执行的指令,很大可能是当前正在执行的指令的相邻指令,根据缓冲栈的容量,预取指令和其所需要的操作数.在此基础上,各个功能部件独立运行,大幅度地提高了指令的执行速度.
3结语
程序局部性原理是计算机系统设计中四个定量原理之一,根据程序的空间局部性和时间局部性设计计算机系统结构,可以有效地提高计算机系统的性能.存储器系统通过有效地利用程序局部性原理,设计了满足用户需求的高速度、大容量和低单位的存储系统.流水线技术根据程序局部性原理,采用预取技术,保证了流水线各个功能的独立运行,提高了流水线处理机的程序执行速度.目前,计算机系统设计人员仍在研究,如何最大程度挖掘程序局部性原理,提高计算机系统结构的性能.
参考文献：
［1］杜文晟.MIMD并行计算机系统结构与定量分析［J］.湖北师范学院学报,2015,35(3):16.
［2］张广艳,郑纬民.高等计算机系统结构课程研究型教学探讨［J］.计算机教育,2016(5):57.
［3］常瑞,何红旗,黄浩炜,等.面向系统能力的计算机系统结构课程教学内容设计［J］.计算机教育,2014(5):5861.
（编辑：李飒）
计算机系统论文范文结:
大学硕士与本科计算机系统毕业论文开题报告范文和相关优秀学术职称论文参考文献资料下载，关于免费教你怎么写计算机系统方面论文范文。
1、论文计算机
4、论文查询系统
6、计算机硕士论文