流水线指令设计及页面置换算法在WinDLX软件中的应用,计算机组成原理论文

1、流水线指令设计及页面置换算法在windlx软件屮的应用，计算机组成原理论文流水线指令设计及页血置换算法在windlx软件中的应用实验一 windlx概述1一实验目的1二 windlx 概述1三实验实验结果截图 7实验二 流水线中的结构相关 8 一五实验目的:8实验流水线中的数据相关换算法模拟10 一 实验目10二实验lru页面置12 实验目12二 预备知识12三实验内容与步骤 15四实验过程分析 15五 实验程序15六实验结果截图 18七 心得体会18附录：windlx教程19实验一 windlx概述一实验目的1. 熟练掌握windlx模拟器的操作和使用，熟悉dlx指令集结构及其特点；2. 加

2、深对计算机流水线基本概念的理解；3. 了解dlx基本流水线各段的功能以及基本操作；二 windlx 概述1. windlxwindlx模拟器是一个图形化、交互式的dlx流水线模拟器，能够演示dlx流水线是如 何工作的。该模拟器可以装载dlx汇编语言程序（后缀为“.s"的文件），然后单步、设断点 或是连续执行该程序。cpu的寄存器、流水线、i/o和存储器都可以用图形表示出来，以形 象生动的方式描述dlx流水线的工作过程。模拟器还提供了对流水线操作的统计功能，便 于对流水线进行性能分析。有关windlx的详细介绍，见附录（windlx教程）。2. 熟悉windlx指令集和windlx源代

3、码的编写三 实验 r2, rl, r0）、gcm.loop （seg r3,rl,r2）和 result+oxc（trap 0x0）设置断点，采用单步 和连续混合执行的方法完成程序，注意中间过程和寄存器的变化情况，然后单击主菜单execute/display dlx-i/o,观察结果。32 1四实验程序实验源程序如下：gcm.s2#.卜 卜 .卜；* windlx ex.l: greatest common measure *1991 gather raidl士 士 士 卜 士 士<t%<t%<t%;* modified 1992 maziar khosravipour;pr

4、ogram begins at symbol main;requires module input;read two positive integer numbers from stdin, calcukite the gem ; and write the result to stdout严* prompts for inputprompt 1: .asciiz &quot;first number:&quot;prompt2: .asciiz &quot;second number: &quot;；* data for printf-trap .align

5、2printfformat 4 printffoitnat:asciiz &quot;gcm=%dnn&quot; printfpar:loop:rl greater:result: ;* write the result (rl)4j ;* subtract r2 from rl rl,rl,r2 loop sub;* compare rl and r2 r3,rl,r2 ;r1=r2 ? r3,result r3,rl,r2 rl &gt; r2 ? r3,rlgreater seq bnez sgt bnez ;* subtract rl from r2 r2,r

6、2,rl loop sub j.text .global main ;* read two positive integernumbers into rl and r2 addi jal add addi jal rl,ro,prompt i inputunsigned ;read uns.-integer into rl r2,rl,r0 ;r2 &lt; rl rljo,prompt? inputunsigned ;read uns.-integer into rl word .data printfvalue:space main: r2greater:sw addi trap

7、;* end trap printfvaluerl r!4jo,printfpar 5 0input.s.*windlx ex. 1: read a positive integer number * ；*(c) 1991 g 騰 ther raidl;subprogramcall by symbol&q uot;inputunsigne d&q uot;expect the address of a zero-terminated prompt string in rl;returns the read value in rl;changes the contents of

8、registers r1,r13,r14；* data for read-trap8009readbuffer,80 readbuffer: .space readpar: .wordsaver2:saver3:saver4:saver5:.global saver2,r2 saver3,r35inputunsigned inputunsigned: sw swtext .space space .space .spacedata for printf-trap .space4 printfpar:.data4444*上 2 *1*上!* 上 2 上上彳.彳.彳.彳.彳.彳.rtw rtw r

9、tw rtw rtw rtw rtw ez* rtw »yw rtw »yw rtw »yw rtw rtwmodified 1992 maziar khosravipour* save register contentssw sw saver4,r4 saver5,r5 ;* prompt sw addi trap printfpar,rl rl4,ro,printfpar 5 ;* call trap-3 to read line addi trap rl 4,ro,readpar 3 ;* determine value addi addi addir2,r

10、oreadbuffer rl,r0,0 r4,r0j0 ;decimal system loop:;* reads digits to end of line r3,0(r2) r5,r3,10 ;lf &gt; exit r5,finish r3,r3,48 ;? rl,rl,r4 ;shift decimal rl,rl,r3 r2,r2,l ;increment pointer loop lbu seqi bnez subi multu add addi j lw lw lw lw finish: ;* restore old register contents r2,saver

11、2 r3,saver3 r4,saver4 r5,saver5 r31; return jr6五.实验结果截图实验二流水线111的结构相关一实验目的：1. 近一步熟悉dlx指令集结构及其特点；2. 通过本实验，加深对结构相关的理解，了解结构相关对cpu性能的影响。二实验 f0,0(r2)addd f2, fo, f2 ; &lt; a stall is found (an example of how to answer your questions)存在 结构冲突2. addi r2, r2, #8addi r3, r3, #83. addi r3, r3, #8sub r5, r4

12、, r24. sub r5, r4, r2bnez r5,3. 记录由结构相关引起的暂停时钟周期数9 ,计算暂停时钟周期数占总执行周期数的百 分比。9/139=6.475%4. 论述结构相关对cpu性能的影响，讨论解决结构相关的方法。三实验过程分析四实验程序实验源程序如下：structure_d.slh1r2, (a&gt;&gt;l 6)&amp;oxffffadduir2, r2, a&amp;oxfffflhir3, (b&gt;&gt; 16)&amp;oxffffadduir3, r3, b&amp;oxffffaddu

13、r4, ro, r3loop:ld fo, 0(r2)8ld f4,0(r3)adddfo, fo, f4adddf2, fo, f2 ;&lt;- a stall is found (an example of how to answer your questions) 取扌旨令 时和上一条冲突addi r2, r2, #8&lt; a stall is foundaddi r3, r3, #8 &lt; a stall is foundsub r5, r4, r2 &lt;- a stall is foundbnez r5, looptrap #0; exi

14、t &lt; this is a comment!a:.double 1, 2, 3, 4, 5, 6, 7, & 9, 10b:.double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10五实验结果截图实验报告中应包含：实验目的、实验内容、实验步骤（要有程序清单并以注释的形式対定 义的变量和使用的寄存器进行说明）、实验结果等内容。9实验三流水线中的数据相关一实验目的1. 加深对数据相关的理解，了解数据相关对cpu性能的影响；2. 了解解决数据相关的方法，掌握如何使用定向技术來减少数据相关带來的暂停。二实验3023.44%并计算采用定向技术后性能提高的倍数220/

15、128=1.72三实验过程分析四实验程序实验源程序见文件data_d.slhiadduilhiadduiadduloop:r2, (a&gt;&gt; 16)&amp;0xffffr2, r2, a&amp;0xffffr3, (b&gt;&gt; 16)&amp;0xffffr3, r3, b&amp;0xffffr4, ro, r3ldldadddadddaddiaddisub10f0, 0(r2)f4, 0(r3)f0, f0, f4f2, f0, f2r2, r2, #8r3, r3, #8r5, r4, r2bneztr

16、apr5? loop#0a:.double 1, 2, 3, 4, 5,6, 7, 8, 9, 10b:.double 1, 2, 3, 4, 5, 6, 7, & 9, 10五实验结杲截图实验四lru页面置换算法模拟一、实验目的1、了解系统拥有足够的对换区空间，这时可以全部从对换区调入所需页而，以提高调 页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。12(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入； 而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区 调入。(3) unix方式。由于与进程有

17、关的文件都放在文件区，故凡是未运行过的页面，都从 文件区调入。而対于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应 从对换区调入。由于unix系统允许页面共享，因此，某进程所请求的页面有对能己被其它 进程调入常见置换算法最佳置换算法(optimal)：它是由belady于1966年提出的一种理论上的算法。英所选择的被淘汰页面，将是以后永 不使用的或许是在最长(未來)时间先进先出(fifo)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入 lru置换算法：这是本次设计的 重点。 clock置换算法：a,简单clock置换算法；b,改进型clock算法。lru算法 是较

18、好的一种算法,而由于lru在硬件上要求较多，在实际应用屮多采用lru的近似算法。 clock算法就是用得较多的一种lru近似算法。13最少使用(lfu:least frequently used)g换算法：在采用该算法吋，应为在 页面缓冲算法(pba： page buffering algorithm)、最近最久未使用置换算法lru(least recently used)置换算法的描述fifo置换算法性能之所以较差，是因为它所依据的条件是各个页面调入1) 寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存屮的页面配置一个移位寄存 器，可表示为r=rn-lrn-2rn-3r2r1r

19、0当进程访问某物理块时，要将相应寄存器的rnl位置成1。 此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的 数看作是一个整数,那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。 如图1示出了某进程在内存屮具有8个页面，为每个内存页面配置一个8位寄存器时的lru 访问情况。这里，把8个内存页面的序号分别定为1飞。由图可以看出，第7个内存页面的 r值最小，当发生可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将 页血的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页血的编号民，而 栈底则是最近最久未使用的页

20、面的页面号。14三实验/*页血逻辑结构，结构为方便算法实现设计引page bm; /*/*调入队列计数变量*/*初始化内存单元、缓冲区勺void init(page *b,int cmn)int ij;for(i=0;i&lt;n;i+)bi.num=-l;bi.time=n-i-l;for(i=0;i&lt;m;i+)for(j=0;j&lt;n;j+)ciu=-l；15/*取得在 int getmax(page *b) int i;int m“x二 1;int tag=o;for(i=0;i&lt;m;i+)if(bi.time&gt;max)max

21、=bi.time;tag=i;return tag;/*判断页面是否己在内存屮*/int equation(int fold,page *b)int i;for(i=0;i&lt;m;i+)if (fbld=bi.num)return i;return -1;/*lru核心部分*/void lru(int fold,page *b)int i;int val;val=equation(fold,b);if (val&gt;=o)bval.time=o;for(i=0;i&lt;m;i+)if(i!=val)bi.time+;else16queue+kj=fold;/*

22、记录调入页面 */val=getmax(b);bfval.num=fold;bfval.tiitie=o;for(i=0;i&lt;m;i+)if (i!=val)bi.time+;/*主程序勺void main()int an戶1,0丄0,2,4,1,0,0,8,7,5,4,3,2,3,4;int i,j;start:k=-l;lnit(b, c);for(i=0;i&lt;n;i+)lru(ai,b);clojli=ai;/* 记录当前的 for(j=0;j&lt;m;j+) cji=bfjl.num;/*结果输出*/printf(&quot;内存状态为:n

23、&quot;); myprintf;for(j=0;j&lt;n;j+) printf(&quot;|%2d &quot;,aj); printf(&qu ot;|n&q uot;);myprintf;for(i=0;i&lt;m;i+) for(j=0;j&lt;n;j+)if(ciu=-l)printf(&quot;|%2c &quot;,32);elseprintf(&quot;|%2d &quot;,cfijl);printf(&qu ot;|n&q uot;);myprin

24、tf;17 printf(&quot;n 调 入 队 歹 为:&quot;);for(i=0;i&lt;k+1 ;i+)printf(&quot;%3d&quol;,queued);printf(&quol;n 缺页次数为： %6dn 缺页率：% 16.6f&quot;,k+1 ,(float)(k+1 )/n); printf(&quot;nare you continuing!ty?&quot;); if(getche()=ty,) goto start;六实验结果截图实验报告中应包含：实验目的、实验内容、实验步骤(要

25、有程序清单并以注释的形式对定 义的变量和使用的寄存器进行说明并画出程序流程图)、实验结果等内容。七心得体会18附录：windlx教程dlx 处理器（发音为 &quot;deluxe&quot;）是 hennessy 和 patterson 合著一书computer architecture - a quantitative approach中流水线处理器的例子。windlx 是一 个基于windows的模拟器。本教程通过一个实例介绍windlx的使用方法。windlx模拟 器能够演示dlx流水线是如何工作的。本教程使用的例子非常简单，它并没有囊括windlx的各个方面，仅仅作为

26、使用windlx 的入门级介绍。当你阅读完本教程后，请参考帮助文件。通过按f1键，你可以在任何时候 获得相关的帮助信息。虽然我们将详细讨论例子中的各个阶段，但你应具备基本的使用windows的知识。现假 定你知道如何启动windows,使用滚动条滚动，双击执行以及激活窗口。一、安装windlx包含windlx.exe和windlx.hlp文件。同时，还需要一些扩展名为.s的汇编代码文 件。在本手册中将使用fact.s和input.s这两个汇编代码文件。如果你熟悉windows应用程序的安装，那么将fact.s和input.s拷贝到windlx文件夹 后，你可以直接阅读下一部分。请按以下步骤在w

27、indows下安装windlx：1. 为windlx创建目录,例如d:windlx2. 解压windlx软件包或拷贝所有的windlx文件（至少包含windlx.exe, windlx.hlp, fact.s 和 input.s ）到这个 windlx 目录。二、一个完整的例子我们使用windlx汇编器中的汇编文件fact.s ,这个程序计算数（通过键盘输入）的阶 乘。这需要用到文件inputs,它用于接收从键盘输入的数。1.开始和配置windlx19彖启动任何windows应用程序一样，通过双击windlx图标启动windlx,将出现一个带有六个图标的主窗i丨，双击这些图标将弹出子窗口。后

28、面将解释和介绍如何使用每一个窗口。为了初始化模拟器，点击file菜单中的reset all菜单项，弹出一个"reset dlx"对话框。 然后点击窗口中的“确认"按钮即可。windlx可以在多种配置下工作。你可以改变流水线的结构和时间要求、存储器大小和其 他儿个控制模拟的参数。点击configuration / floating point stages （点击configuration打开菜单，然后点击floating point stages菜单项），选择如下标准配置:coudelaaddition units:multiplicationunits:divi

29、sion units:如果需要，可以通过点击相应区域来改变设置。然后，点击ok返回主窗口。点击configuration / memory size ,可以设置模拟处理器的存储器大小。应设置为0x8000, 然后，点击ok返回主窗口。在configuration菜单中的其他三个配置也可以设置，它们是：symbolic addresses, absolute cycle count和enable forwardingo点击相应菜单项后，在它的旁边将显示一个小钩。2. 装载测试程序20在开始模拟之前，至少应装入一个程序到主存。为此，选择file/load code or data,窗口 中会列出目

30、录中所有汇编程序。我们在前面已经提到，fact.s计算一个整型值的阶乘；inputs中包含一个子程序，它读标 准输入(键盘)并将值存入dlx处理器的通用寄存器r1中。按如下步骤操作，可将这两 个文件装入主存。点击fact.s点击select按钮点击 input.s点击select按钮点击load按钮选择文件的顺序很关键，它决定了文件在存储器屮出现的顺序。对话框屮会显示信息“file(s) loaded successfully. reset dlx?,点击"是(y)"按钮确认。这样，文件就已被装入到存 储器中了。现在可以开始模拟工作了。3. 模拟在主窗口中，你可以看见六个图

31、标，它们分别为“register",“codc”，“pipeline”，“clockcycle diagram", "statistics"和"breakpoints"。点击其中任何一个将弹出一个新窗口(子窗口)。 在模拟过程中将介绍每一个窗口的特性和用法。(1) pipeline 窗口我们首先來看一下dlx处理器的内部结构。为此，双击图标pipeline,出现一个子窗口， 窗口中用图表形示显示了 dlx的五段流水线。你应尽可能地扩大此窗口，以便处于不同流 水段的指令都能够在图表中显示。此图显示dlx处理器的五个流水段和浮点操作(加/

32、减，乘和除)的单元。(2) code 窗口21我们來看一下code窗口。双击图标，你将看到代表存储器内容的三栏信息，从左到右依 次为：地址(符号或数字)、命令的十六进制机器代码和汇编命令。现在，点击主窗口屮的execution开始模拟。在出现的下拉式菜单屮，点击single cycle 或按f7键。这时，窗口中带有地址“$text”的第一行变成黄色。按下f7键，模拟就向前执行一步， 笫一行的颜色变成橘黄色，下一行变成黄色。这些不同颜色指明命令处于流水线的哪一段。 如果pipeline窗口己经关闭，请双击相应图标重新打开它。如果窗口足够大，你能够看到 命令“jal inputunsigned&q

33、uot;在 if 段，“addi rl, ro, 0x1000 ”在第二段 id。其他方框屮带有一个“x” 标志，表明没有处理有效信息。再次按下f7键，代码窗口屮的颜色会再改变，红色表明命令处入第三段“intexs 再按 下f7，图形显示将变为：在代码窗口中，黄色出现在更下面的位置，并且可能是唯一彩色行。查 看一下pipeline窗口，你会发现if, intex和mem段正在使用而id段没有。为什么？(3) clock cycle diagram 窗 口使所有子窗口图标化，然后打开clock cycle diagram窗口。它显示流水线的时空图。在窗口中，你将看到模拟正在第四时钟周期，第一条命

34、令正在mem段，第二条命令在intex段，第四条命令在if段。而第三条命令指示为&quot;aborted&quot;« 其原因是：第二条命令(jal)是无条件分支指令，但只有在第三个时钟周期，jal指令被 译码后才知道，这时，下一条命令movi2fp已经取出，但需执行的下一条命令在另一个地址 处，因而，movi2fp的执行应被取消，在流水线中留下气泡。22jal的分支地址命名为&quot;lnputunsigned&quot；o为找到此符号地址的实际值，点击主窗 口中的memory和symbols, i'll现的子窗口中显示相应的符号和对应的

35、实际值。在 &quot;sort： &quol;区域选定&quot;name&quot;,使它们按名称排序，而不是按数值排序。 数字丿匸的&quot;g&quot;代表全局符号，&quot;l&quot;代表局部符号。&quot;input&quot; 屮的&quot;inputunsigned&quot;是一个全局符号,它的实际值为0x144 ,用作地址。点击ok 按纽关闭窗口。再一次点击f7 ,第一条命令（addi）到达流水线的最后一段。如果想了解某条命令执行 后处理器内部会发生什么？你只要对准

36、clock cycle diagram窗口中相应命令所在行，然后双 击它，弹出一个新窗口。窗口中会详细显示每一个流水段处理器内部的执行动作。这个窗口 &quot;information about .&quot;作为将来的 information 窗口。观察完后，点击 ok 按钮关 闭窗口。双击第三行（movizrp）,你会看到它只执行了第一段（if）,这是因为出现跳转而 被取消。（双击code窗口中的某一行或者pipeline窗口中的某一段，同样可以information窗口。）（4）breakpoint 窗口当通过code窗口观察代码时（如果未打开，双击图标code）,你会

37、看到接下来的儿条指 令几近一样，它们都是sw-操作：将寄存器中的数写入存储器中。重复按f7将很枯燥，因 此，我们使用断点加快此过程。现在，请指向code窗口中包含命令trap 0x5的0x0000015c行，此命令是写屏幕的系统调 用。单击命令行，然后点击主窗口菜单code,单击set breakpoint （确保命令行仍被标记！）, 将弹出一，个新的&quot;set breakpoint&quot;窗口。通过此窗口，你可以选择命令运行到流 水线的哪一阶段时，程序停止执行。缺省为id段。点击0k关闭窗口。在code窗口中,trap 0x5 if上出现了&quot;bi

38、d&quot;,它表示当本指令在译码段时, 程序中止执行。如果想查看已定义的断点，你只要单击图标reakpoints,将弹出一个小窗口，其中显示了 所有断点。重新使窗口图标化。现在你只要点击execution / run或按f5,模拟就继续运行。会11!现一个对话框提示你 &quot;ld-stage: reached at breakpoint #1&quot;,按“确认”按钮关闭。23点击clock cycle diagram窗i丨屮的trap 0x5行，你将看到模拟正处于时钟周期14。trap 0x5 行如下所示：原因是：无论何时遇到一条irap指令时，dlx处理

39、器中的流水线将被清空。在information 窗口（双击trap行弹出）中，在if段显示消息&quot;3 stall（s） because of trap-pipeline-clearing!&quot;o （不要忘了按 ok 关闭窗口）。指令trap 0x5己经写到屏幕上，你可以通过点击主窗口菜单条上的execute / displaydlx-i/o来查看。(5) register 窗 口为进一步模拟，点击code窗口，用箭头键或鼠标向下滚动到地址为0x00000194的那一 行(指令是 lw r2, saver2(i*0),点击此行，然后按 ins 键，或点击 code/set breakpoint / ok,