计算机系统结构实验一流水线指令调度

1、& 4轴技女孕计算机专业类课程实验报告课程名称：计算机系统结构 学院：计算机科学与工程专业：计算机科学与技术学生姓名：林怡学 号：2012060020023 指导教师：叶娅兰日 期：2015年5月5日电子科技大学实验报告实验一一、实验名称：流水线指令调度二、实验学时：4三、实验内容和目的：实验目的：通过本实验，理解指令调度的方法。掌握使用VC开发平台模拟处理机内部指令流调度的编程策略。实验内容：（一）给定要执行的任务和执行该任务的流水线结构流水线的调度方式能够提高任务的并行度，但是针对不同的任务，由于相关的存在，其 并行度的提高是不一致的。在开始程序设计前，我们首先要给定所要完成的任务：这里我

2、们使用最简单的累加操作Ai。n的数值可以变化，通过变换n的值用同一程 i=1序进行多次模拟。X 勺 - 一 J一 -:.给定流水线：X凡二流水线分四个步骤，每个步骤的执行时间均为一个单位时间。（二）对任务进行分解任务分解的目的是为了减少相关。例如n = 4时，任务分解为A1+A2、A3+A4、 A1+A2+A3+A4三个加法操作。如果n的大小是未知的，任务该怎样分解呢？换而言之，在程序模拟中，有没有 一种通行的分解处理方式，可以实现对任意数目的源数据的累加的分解？（三）任务分解程序模拟的思路首先，Ai是对称的，Ai和Aj都是一个源操作，任意更换其相对位置，计算的累 加和的结果是不变的。每次的加

3、法操作能执行的必要条件是存在两个源数据，因此我们可以把所有的源数据放入一个队列中，只要该队列中有两个源，那么就执行加法， 加法计算的结果是下一次计算的源数据，我们把它再放回源数据队列，直到对列中只 剩一个数据、同时加法流水线中没有执行加法操作时，整个累加过程完成。（四）加法流水线的设计加法流水线分为四个步骤，每个步骤时间花费是一个单位时间。模拟程序的目的 是为了计算总的执行时间，因此对于每个步骤执行的功能并不需要关心。为此设计一个总步数为4步的加法器，接收两个输入数据，经过4个时间片，输 出加法的结果。时间片可以用定时器来模拟。（五）程序设计程序应包括一个队列，一个加法类，一个定时器，一个输出

4、对话框。队列用于存放源数据，一开始将n个源数据A1An放入。启动定时器，每一个时间片从队列中取出两个源数据，送入加法器（可以通过调 用加法器中接口函数，把源数据作为参数传入）。构造加法器类，可以考虑用一个长度对4的执行队列来模拟4个步骤，每个时间 片将队列的数据依次下压一格，队列尾的数据进行加法计算并将结果压入源数据队列。用一个记数值表示时间开销，每个时间片对该记数值加1。当源队列只剩一个数据且加法器的执行队列为空时，整个程序结束，记数器的值 就是任务执行的总体时间花费。（五）多次模拟可以通过循环的方式对n从4 20进行循环，将每次模拟运行的时间开销值在对 话框中显示出来。如果可能将结果打印。

5、四、实验原理：程序设计及数据结构：实验程序共有6个类，分别是：PipeAdditionTest公共类，测试程序，每一个n的循环，将计时器清零并初始化长度 为n的源操作数队列，当源操作数队列有多余一个操作数或者加法器的执行队列不为空的时 候持续调用加法器类执行加法操作，在程序结束时输出n以及计时器timercounter的值；OperaQueue操作数队列类，包括一个操作数队列数据结构、队列初始化函数OperaQueue（int queueLength）、从队列中取一个源操作数函数getOperationNum（）和将加法器 计算的结果压入队尾的函数pushOperationNum（int op

6、）；Addition加法器类，包含一个加法执行队列additionQueue, 一个用于暂存操作数的队列addOperandQueue。构造函数Addition(int len)用于初始化加法器执行队列，函 数fetchOpNum在每一个时间片从源操作数队列中取出操作数，函数 getAdditionResult()将两个源操作数相加并返回它们的和，以及一个空操作 executeNop()用于模拟加法器四级流水线。Timer成员变量timerCounter为时间片计数器。DialogFrame 对话框相关。DialogFrameComponent对话框相关。五、实验器材(设备、元器件)Win7操

7、作系统、Eclipse集成开发环境、JDK1.8、Java程序语言六、实验步骤：程序流程图：开始退出七、实验数据及结果分析:当n=4时，时空图如下：此时时间片开销为t=9当n=5时，时空图如下：此时时间片开销为t=12s41234s31234s21234si1234tl t2 t3 t4 t5 t6 t7 t8 t9 tlO til tl2当n=6时，时空图如下：此时时间片开销为t=13s412345s312345s212345si12345tl t2 t3 t4 t5 t6 t7 t8 凶 tlO til tl2 tl3实验程序结果如图:n = 4 timer = 9 sum=10n = 5

8、 timer = 12 sum=15n = 6 timer = 13 sum=21n = 7 timer = 14 sum=28n = 8 timer = 15 sum=36n = 9 timer = 16 sum=45n = 10 timer = 17 sum=551n = 11 timer = 18 sum=661n = 12 timer = 19 sum=78n = 13 timer = 20 sum=91n = 14 timer = 21 sum=105In = 15 timer = 22 sum=120n = 16 timer = 23 sum=136n = 17 timer = 2

9、4 sum=1531n = 18 timer = 25 sum=171n = 19 timer = 26 sum=190n = 20 timer = 27 sum=210J由截图可知，实验结果与时空图的结果是一致的，说明实验程序的正确性。八、实验结论、心得体会和改进建议：1、通过本次实验，我自己动手实现了一个简单的加法流水线，增加了我对于流水线的工作流程的理解，也明白了通过指令的分解可以加快指令的运行速度并减少相 关。2、通过对流水线的模拟，不仅熟悉了流水线指令调度的过程，也训练了我多种数据结构的使用，以及将问题抽象的能力。在模拟程序的实现中，我采用了队列、类等 等基本的结构，这次实验，让我理

10、解了流水线的调度策略，同时实际的程序开发 也提高了我的编程能力。实验代码如下：/*PipeAdditionTest.java*/package Pipeline;import java.awt.Dimension;import java.awt.EventQueue;import java.awt.Font;import java.awt.Graphics;import java.util.LinkedList;import java.util.Queue;import javax.swing.JComponent;import javax.swing.JFrame;public class

11、PipelineAdditionTestpublic static String printStr =;public static void main(String args) int n = 0;String tempStr =;for (n=4;n 1)| !addition.additionQueue.toString().equals(0, 0, 0, 0)/*若指令到达流水线最后一级，则求和并将结果压入源操作数队列*/if (addition.additionQueue.peek() = 1)sum =addition.getAddtionResult(addition.addOpe

12、randQueue.poll(),addition.addOperandQueue.poll();operaQueue.pushOperationNum(sum); 加法操作得到的结果压 入操作数队列System.out.println(peek后 operaQueue.size()=+operaQueue.opQueue.size();/*若源操作数队列中有多于两个操作数*/if (operaQueue.opQueue.size() 1)(System.out.println(before operaQueue,size()=+operaQueue,opQueue,size();op1 =

13、operaQueue.getOperationNum();op2 = operaQueue.getOperationNum();/从操作数队列中取两个源操作数addition.addOperandQueue.offer(opl);addition.addOperandQueue.offer(op2); 暂存入加法器的操作 数队列，以便后续进行加法操作System. out.println(取数后 operaQueue,size()=+operaQueue,opQueue,size();addition.fetchOpNum();/指令进入加法流水线，压入加法器执行队列else addition

14、.executeNop(); /若源操作数队列中的元素个数少于2 个，执行空操作System. out.println(执行后addQueue=+addition.additionQueue.toString();if (operaQueue.opQueue.size() = 1 & addition.additionQueue.toString().equals(0, 0, 0, 0) sum = operaQueue.opQueue.poll();break;Timer.timerCounter+;System.out.println( t+Timer.timerCounter+n);te

15、mpStr = n = +n+ timer = +Timer.timerCounter+ sum=+sum+n;printStr = printStr + tempStr;/*调用对话框*/EventQueue.invokeLater(new Runnable() public void run() JFrame frame = new DialogFrame();frame.setTitle(流水线加法指令调度”)； frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE );frame.setVisible(true);)；/*操作数队列，长

16、度初始化为n */class OperaQueue(Queue opQueue;public OperaQueue(int queueLength)(opQueue = new LinkedList(); 初始化队列for (int i=1;iqueueLength+1;i+)opQueue.offer(i);/操作数 1n 依次入队 int getOperationNum()return opQueue.poll(); void pushOperationNum(int op)opQueue.offer(op);将相加后的操作数入队 /*加法器类，分为四个步骤*/class Addition

17、Queue additionQueue = new LinkedList();Queue addOperandQueue = new LinkedList();Addition(int len)/*初始化加法器执行队列*/while (len-!=0)additionQueue.offer(0);void fetchOpNum()/*执行队列下压一格，模拟4个步骤*/*第一级取数操作*/additionQueue.poll();additionQueue.offer(1);void executeNop()/*执行队列下压一格，模拟4个步骤*/*空操作*/additionQueue.poll(

18、);additionQueue.offer(0);int getAddtionResult(int opa,int opb)/*将两个源操作数相加，返回它们的和*/ return opa+opb;/* 计时器timerCounter*/class Timerpublic static int timerCounter; /计时器timercounter /*对话框*/class DialogFrame extends JFramepublic DialogFrame()add(new DialogFrameComponent();pack();DialogFrameComponent extends JComponentclasspublic static int MESSAGE_X = 40;public static int MESSAGE_Y = -200;private static final int DEFAULT_WIDTH = 400;private static final int DEFAULT_HEIGHT = 350;public void pai