基于WindLX的计算机系统结构实验，随机输入n个数，求数i的概率

源码：
https://github.com/Justlovesmile/WindLX-Experiment
https://gitee.com/justlovesmile/WindLX-Experiment

《计算机系统结构》课程实验

一、实验名称：

随机输入n个数，求数i的概率

二、实验原理：

  1. WinDLX平台与流水线
    WinDLX是一个基于Windows的、图形化、交互式的模拟器，能够演示DLX流水线是如何工作的，它采取伪汇编形式编码，模拟流水线的工作方式。流水线的指令执行分为5个阶段：取指、译码、执行、访存、写回。
    WinDLX模拟器还提供了对流水线操作的统计功能，便于对流水线进行性能分析。
  2. 流水线中的相关及解决办法
    （1）结构相关：当某一条机器指令需要访问物理器件时，该器件可能正在被占用，例如连续的两条加法指令都需要用到浮点加法器，就产生结构相关，可以通过增加加法器的方式解决结构相关；
    （2）数据相关：当某一条指令需要访问某个寄存器时，此时这个寄存器正被另一条指令所使用，从而产生数据相关，可以通过重定向技术解决数据相关；
    （3）控制相关：当程序执行到某个循环语句时，顺序执行的下一条语句将被跳继续执行循环体的内容，从而产生控制相关，可以通过循环展开解决控制相关。

三、实验目的：

1、加深对流水线理论知识的理解；
2、掌握对流水线性能分析的方法，了解影响流水线效率的因素；
3、熟悉在WinDLX体系结构下的汇编代码编写和优化；
4、了解相关的类型及各类相关的解决办法；
5、培养运用所学知识解决实际问题的能力。

四、实验内容：

1、根据WinDLX模拟器伪汇编指令规则编写：随机输入n个数后，求数i的概率的程序gailv.s以及input.s
2、分别按照不同顺序将gailv.s和input.s装入主存，分析输入顺序不同对运行结果产生的影响；
3、观察程序中出现的数据、控制、结构相关，指出程序中出现上述现象的指令组合，并提出解决相关的办法；
4、分别考察各类解决的相关办法，分析解决相关后性能的变化。
注意：
除解决结构相关，其他情况下加、乘、除运算器都只有一个。
本问题中所有浮点延迟部件设置为：加法：2个延迟周期；乘法：5个延迟周期；除法：19个延迟周期。

五、实验器材（设备、元器件）：

设备：笔记本电脑一台
软件：VMware Workstation
虚拟机：Windows7 32位操作系统
WinDLX模拟器

六、实验步骤及操作：

1、初始化WinDLX模拟器
（1）为WinDLX创建目录，C:\WinDLX。将WinDLX和gailv.s、gailv2.s、input.s放在这个目录中。
（2）初始化WinDLX模拟器：点击File 菜单中的 Reset all 菜单项，弹出一个“Reset DLX”对话框，点击窗口中的“确认”按钮即可。如图1所示。

图1 初始化模拟器界面

2、将程序装入WinDLX平台
点击File 菜单中的 Load Code or Data 菜单项，依次双击gailv.s和input.s。点击load，将两个程序装入。如图2所示。

图2 程序装入界面

3、运行程序并观察

进行单步调试，在WinDLX模拟器的6个子窗口观察程序的执行情况。观察程序运行的总时钟周期，产生的相关种类以及每种相关的数量。

4、解决数据相关

勾选Enable Forwading，采用重定向技术添加专用数据通路减少数据相关，观察数据相关的数量变化。

5、解决结构相关

将Addition Units的数目由1到2，观察结构相关的数量变化。

6、解决控制相关

将gaillv.s的循环体展开形成新文件gailv2.s，采用循环展开的方法减少控制相关，观察控制相关的数量变化。

七、实验数据及结果分析：

1、程序装入顺序对运行结果的影响
先装入gailv.s再装入input.s时，程序能够正确执行；当先装入input.s再装入gailv.s时，因为input.s的地址高，而程序顺序执行到input.s时无法正确地输出，因此不会出现结果。

2、主要代码及说明
(1)gailv.s主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
.data
Prompt:         .asciiz     "input An integer which is array's size value >=0 : "
PromptLast:    .asciiz     "input an integer :"
PromptNum:     .asciiz     "input an integer>=0 which you need:"
PrintfFormat:   .asciiz     "Probability: %g "
PromptError:   .asciiz     "Error!Need int>=0!Input:(Go:1,other to End)"
.align   2
PrintfPar:      .word        PrintfFormat
Printf:        .space       8
PrintfValue:    .space       1024
.text
.global main
main:
                ;*** 输入数组大小和相关初始化
                addi            r1,r0,Prompt     ;将Prompt字符串首地址放入r1寄存器中
                jal         InputUnsigned    ;跳转子函数，输入数组大小n
                bnez           r10,Error        ;输入异常处理
                beqz           r1,InputNum      ;如果r1为0，跳转InputNum
                add            r2,r0,r1         ;将数组大小n存于r2
                add            r6,r0,r1         ;将数组大小n存于r6
                addi           r3,r0,0          ;初始化r3
                addi           r7,r0,1          ;r7等于1
                movi2fp        f1,r7            ;f1等于1
                addf           f2,f2,f0         ;初始化f2,f3,f4
                addf           f3,f3,f0
                addf           f4,f4,f0
                movi2fp        f5,r1            ;将数组大小n存于f5

InputArray:
                ;*** 输入数组
                beqz           r2, ProcessPart      ;如果r2等于0则跳转ProcessPart 
                addi           r1,r0,PromptLast     ;输入数字
                jal            InputUnsigned
                bnez           r10,Error
                sw             PrintfValue(r3),r1   ;将r1寄存器中的数放入r3寄存区中所存数地址的存储器中
                addi           r3,r3,4              ;r3后移
                subi           r2,r2,1              ;r2减1
                j              InputArray           ;循环输入

ProcessPart:
                addi           r3,r0,0              ;初始化r3

InputNum:
                ;*** 输入求概率的数字 
                addi           r1,r0,PromptNum
                jal            InputUnsigned
                 bnez           r10,Error
                add            r2,r0,r1             ;保存i到r2
                movi2fp        f2,r2                ;保存i到f2

Loop:
                ;*** 循环与计数       
                beqz           r6,Output          ;如果r6等于0则结束Loop跳转Output
                subi           r6,r6,1            ;r6减1
                lf             f3,PrintfValue(r3) ;取出r3地址中的数到f3
                addi           r3,r3,4            ;r3后移
                movfp2i        r7,f2                
                movfp2i        r8,f3
                seq            r12,r7,r8          ;如果r7等于r8,r12为1，否则为0 
                bnez           r12,Sum            ;r12为不等于0,则跳转到Sum计数，否则继续循环
                j              Loop               ;循环

Sum:
                addf           f4,f4,f1           ;计数
                j              Loop

Output:
                cvti2d         f0,f4              ;单精度转换为双精度
                cvti2d         f6,f5
                movfp2i        r5,f5
                beqz           r5,OutputInner     ;分母为0
                divd           f6,f0,f6           ;f6=f0/f6

OutputInner:
                sd              Printf,f6
                addi            r14,r0,PrintfPar     
                trap            5                    ;标准输出
                trap            0                    ;程序结束

Error:
                addi            r1,r0,PromptError
                jal             InputUnsigned
                bnez            r1,main
                    trap                0

（2）input.s主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
Loop:       ;*** reads digits to end of line
        lbu         r3,0(r2)
        seqi        r5,r3,10    ;LF -> Exit
        bnez        r5,Finish
        slti        r11,r3,58;***判断是否为非法字符
        beqz        r11,Error
        slti        r10,r3,48   
        bnez        r10,Error
        subi        r3,r3,48    ;转换ASCAII码
        multu       r1,r1,r4    ;转换十进制
        add         r1,r1,r3
        addi        r2,r2,1     ;指针后移
        j           Loop

3、程序分析及运行结果

（1）根据提示输入一个正整数n代表接下来输入的数的总个数。
测试用例：n=5。

（2）再根据提示输入n个数字。
测试用例：1，2，3，3，4

（3）输入想要求概率的数i。
测试用例：3

图3 运行结果截图

由图3可知运行结果为0.4，计算结果正确。

（4）异常处理：输入任何不是自然数的字符，如：负数，小数，以及其他非法字符均会提示错误。异常处理结果如图4所示。

图4 异常处理结果截图

（5）点击Statistics窗口，查看程序执行的时钟周期以及数据相关、结构相关、控制相关的发生次数。
程序执行共用621个时钟周期，数据相关发生172次，结构相关发生2次，控制相关发生42次，如图5所示。

图5 时钟周期和相关数据截图

4、数据相关及解决

（1）数据相关产生的原因

1
2
3
movfp2i              r8,f3
seq                  r12,r7,r8       ;如果r7等于r8,r12为1，否则为0 
bnez                 r12,Sum         ;r12为不等于0,则跳转到Sum计数，否则继续循环

seq指令要使用r8寄存器的数据，但是上一条指令movfp2i刚刚执行完数据还没有更新，产生数据相关，并且之后的bnez指令也需要上一条seq指令的中还没更新的寄存器r12，产生数据相关，如图6所示。

图6 数据相关截图

（2）数据相关的解决

采用重定向技术，勾选Configuration的Enable Forwading选项。在第一条指令结束后直接将寄存器r8的内容更新，在第二条指令结束后直接将寄存器r12数据更新，以此来消除数据相关，如图7所示。

图7 解决数据相关截图

查看运行结果，数据相关数量降低了64，处理后的数据相关个数为108，如图8所示。

图8 解决数据相关的数据截图

5、控制相关及解决

（1）控制相关的产生原因

1
2
3
4
5
6
7
8
9
10
Loop:       ;*** 循环与计数       
            beqz          r6,Output          ;如果r6等于0则结束Loop跳转Output
            subi          r6,r6,1            ;r6减1
            lf            f3,PrintfValue(r3) ;取出r3地址中的数到f3
            addi          r3,r3,4          ;r3后移
                movfp2i       r7,f2                
            movfp2i       r8,f3
            seq           r12,r7,r8        ;如果r7等于r8,r12为1，否则为0 
            bnez          r12,Sum   ;r12为不等于0,则跳转到Sum计数，否则继续循环
            j             Loop      ;循环

在这段程序中，循环体的出现造成了控制相关。

（2）控制相关的解决

采用循环展开的方式将循环体的内容复制一次。可以降低控制相关的个数。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Loop:       ;*** 循环与计数      
            beqz          r6,Output          ;如果r6等于0则结束Loop跳转Output
            subi          r6,r6,1            ;r6减1
            lf            f3,PrintfValue(r3) ;取出r3地址中的数到f3
            addi          r3,r3,4            ;r3后移
                movfp2i       r7,f2                
            movfp2i       r8,f3
            seq           r12,r7,r8    ;如果r7等于r8,r12为1，否则为0 
            bnez          r12,Sum      ;r12为不等于0,则跳转到Sum计数，否则继续循环
            beqz          r6,Output          ;如果r6等于0则结束Loop跳转Output
            subi          r6,r6,1            ;r6减1
            lf            f3,PrintfValue(r3) ;取出r3地址中的数到f3
            addi          r3,r3,4            ;r3后移
                movfp2i       r7,f2                
            movfp2i       r8,f3
            seq           r12,r7,r8    ;如果r7等于r8,r12为1，否则为0 
            bnez          r12,Sum      ;r12为不等于0,则跳转到Sum计数，否则继续循环
            j             Loop         ;循环

重新运行后控制相关数量减少为40，如图9所示。

图9 解决控制相关的数据截图

6、结构相关及解决

（1）结构相关产生的原因

1
2
3
addf          f2,f2,f0         ;初始化f2,f3,f4
addf          f3,f3,f0
addf          f4,f4,f0

在这段语句运行时需要连续进行加操作，由于加法器只有一个，产生结构相关。

（2）结构相关的解决

添加加法器Addition Units的个数，如图10所示。

图10 增加加法器Addition Units界面的截图

再次运行程序可以发现结构相关数量降低，降低到0个，如图11所示。

图11 解决结构相关的数据截图

7、程序流程图

如图12所示。

图12 程序流程图

八、实验结论：

  1. 通过采用重定向技术减少了数据相关；
  2. 通过循环展开的方式将循环体的内容展开来减少控制相关；
  3. 通过增加硬件的数目来减少结构相关；
  4. 执行程序的顺序会影响程序执行是否正确，必须先执行源程序gailv.s，再执行input.s；修改后的程序必须清空之前所有的操作（reset all）之后再重新运行。