MIPS-Simulator项目总结

[TOC]

项目简介

本项目为上海交通大学2017年ACM班PPCA个人大作业。

项目应为一个可以正确模拟MIPS功能的解释器，在完整的项目中应包含与CPU类似的pipeline结构。

除了上述内容外，还可实现(括号中为本项目中实现的)：

静态/动态分支预测
并发的五级流水（多线程）
Tomasulo算法以及对应的多级流水
不同的架构（如龙芯九级流水）

项目于6月26日开始，与7月10日正式完成，与7月11日完成code review宣告结束。

在此对学到的相关知识以及整个经过做一总结。

关于MIPS汇编与五级流水

MIPS汇编

首先推荐一个制作非常精良的入门教程【十分钟教你汇编】MIPS编程入门

简单的说，高级语言在执行之前“翻译”成汇编这种较为基础的语言，然后再变成机器码供CPU等设备运行，不同的CPU使用不同的指令集，如MIPS处理器处理MIPS指令集（对应不同的硬件设计）。

数据主要存在于寄存器，内存当中，而处理器负责解析数据的流动、操作方式。

一些值得注意的事情：

PC寄存器标识当前行，用于读取下一条命令
[0,32)号寄存器各有各的用途，除此之外还有lo，hi两个寄存器用于特殊计算，如long long乘法等
处理器逐条的执行PC寄存器的命令，每执行一次默认让pc寄存器+1
特殊的有B/J开头的两类指令会修改PC寄存器
程序运行开始前会提前分配.data区的内存大小
内存分为堆空间为栈空间，堆空间靠syscall分配，而栈空间由程序自行管理

严格意义上，.text区的内容也应编码后放入内存，但考虑到编程复杂度问题故还是用类来存储，使用类似Harvard结构的方式来进行项目。

五级流水

实际早起CPU中，有的采用分为五级的流水线的结构，即同时让至多五条指令同时运行而分处不同阶段，以达到以下效果：

   	1. **理想情况下**效率提升五倍（因为相当于同时有五个指令在运作，每个占时原本的约五分之一）
 	2. 使功能专化，易于各部件的设计（我yy的）

这五级流水分别是：

IF：pc寄存器取下一条指令
ID：解码得到具体指令，把输入的寄存器换算成对应值
EX：进行数据运算与地址运算
MEM：访问I/O设备，访问内存进行读写
WB：将数据改动写回寄存器（在传统架构下包括pc寄存器）

但这样会造成一些问题，即冒险（Hazard）。冒险分为结构冒险、数据冒险以及控制冒险等

结构冒险：由于设备原因造成两阶段不能同时访问资源的问题
数据冒险：邻近的几条指令存在数据依赖而在上一条未写回前无法进行下一条操作的
控制冒险：由于B或J指令导致pc寄存器产生改变而影响之后IF读取内容的

为了解决冒险问题，最简单粗暴的方式是暂停流水线，即阻塞法（也称气泡法），直到冒险消失方继续

但上述解决方法十分暴力，会导致浪费许多时钟周期，故有了各种各样的优化策略。

具体编程中的问题

在编写这个项目的过程中进行了一次重构，故尝试了两种风格的写法

总结得到如下tips：

非流水线做法很好写而且很快，只需声明好变量后将命令挨个处理即可
五级流水做法通常采用一个类内多个成员函数（本项目中采用的）或多个类表示各个步骤的方法
尝试对指令进行分类抽象从某种意义上会使代码复杂化

分级传递的实现 vs “Tik Tok” 实现

不同的流水实现方式

流水的实现方式主要分为两类

五个阶段能执行则执行，分级把指令向下传递
主过程控制时钟周期，每周期五个阶段各进行一次

本项目对以上两种方式分别做了尝试。两种方法的主要区别在多线程时体现出来，以下是一些对比：

实现方式	分级传递	Tik Tok
实现难度	较大	较小
涉及拷贝	多	少
分支预测	难兼容	易兼容
多线程	支持	支持
多线程编码复杂度	高	低
多线程效率	较高	较低
模拟CPU程度	不接近	较接近

分级传递

分级传递的主要思路是每一级应该把上一层的数据拿来进行处理，再送到下一层去，期间使用流水线寄存器来缓存中间结果。每一次运行会分为读阶段和写阶段，在读阶段取上层数据，写阶段下传。该种实现方式完全依赖于上下级之间良好的沟通而不存在一个总的调配，故在编码上存在一定难度，多线程时的加锁也比较复杂。但由于本任务的特殊性，若正确实现，其多线程效率会高于tik tok模式。由于分支预测要求EX阶段在得知预测错误时要及时通知上两级但该机制在没有总调配的情况下较难实现，故实现分支预测十分困难。

Tik Tok

顾名思义，模拟了时钟周期的概念，让每个周期每个步骤都会执行一次。相比传递，在模拟中可采用指针的技巧做到数据不产生移动节省部分时间，每个阶段的实现与传递区别不大。但在每个周期后可进行一个总的调配，在多线程中即主线程在等候其他线程执行完成后进行统一调配，使得分支预测等操作变得容易起来。分线程与主线程之间的往复在一定程度上降低了效率。

性能分析、程序效率的提高与多线程

性能分析

神奇的优化开关

第一个版本单线程刚调出来的时候，由于不清楚windows下make的使用，直接将debug模式的.exe文件扔进bin文件夹跑测试，结果30个点使用了总共900秒的时间。而在第二天使用release模式的.exe文件测试时这个时间变为了150秒，在虚拟机上-o2用make编译后运行只是用了90秒，同一段程序。

GProf

一开始看到性能分析的原理之后手写了一个naive的丑陋性能分析，即开一个新线程在主线程之外对主线程正在进行的过程进行采样……

后来被介绍了这个linux下的神奇命令，Ubuntu好像自带这个，考虑到Visual Studio 2015的Community版本性能分析并不完整，故学习了一下这个。具体用法为：

首先，在makefile中加入-pg命令再make
执行需要进行性能分析的测试
使用命令行读取gmon.out文件即可得到call graph等运行信息
```
gprof [binary file] gmon.out
```

本项目中的经验

前一个版本经过gprof分析有80%的时间在rb_tree中，即浪费在set与map，将字符串匹配到数字中的过程里了。这也让我注意到，本次犯的一个最大的失误是错误的估计了这个项目对性能的需求。

如某个测试点（tak）中实际执行的行数达三百余万，若每行执行常数很大的话超过1秒是很自然的事情。

故在推倒重来之前，有了以下几点想法：

减少数据，尤其是string的移动
能提前解码，翻译的东西要在正式执行之前做（这条最为重要）
使用编号后（其实应该使用enum，这是一个失误）的switch...case...代替if...else if... else if...结构（据说编译器在switch语句case很多的时候会自动优化为二叉搜索的结构，在本程序中，有数十个case的情况下若该优化成立则会节省很大常数的时间）
多线程时减少锁、原子量的个数

实际第二版也确实将单线程的运行时间提升到了4秒以内（30个点）

多线程

本次项目也让我学习了一些多线程的技巧，尤其是c++11的原生库的一些使用技巧，有：

thread的使用方法

#include<thread>
thread t = thread(&function,arg0,arg1,...)
thread t = thread(&A::function,this,arg0,...) 
//use 'this' when this line is in a member function of the same class.
thread t = thread(&function,ref(arg0),...) 
//if arguments are references, it should be explicitly claimed.

mutex互斥量的使用方法

#include<mutex>
mutex mtx;
void f1() {mtx.lock(); [do what you cannot do while f2 is running]; mtx.unlock(); }
void f2() {mtx.lock(); [do what you cannot do while f1 is running]; mtx.unlock(); }
//use like this to avoid strange problems

atomic原子量的使用方法

#include<atomic>
atomic_int a;
atomic<B> b; //B is a class name
//mutex is used in atomic variables

future/promise机制（promise提供要返回的接口，对应future）

async异步完成

#include<future>
T f1(arg0,...) { return something; }
future<T> f = async(launch::async, &f1, arg0,...);
//or use launch::deferred to delay the running of new thread
T ans = f.get();
//it will wait until f1 finished
//async(launch::async, &A::f, this, arg0,...) is similar to thread usages.

while + this_thread::yield()显式告知让出资源

while (some condition) this_thread::yield();
//but sometimes it will stuck here if condition's variables are not changed

需要注意若不写yield直接while(true)，在CPU线程较少情况下可能导致死机QAQ

同时需要注意的是，使用多线程时-o2有一定几率会导致奇怪错误。编译不过的时候可以尝试加-pthread。

减少浪费周期与分支预测

IF包办pc寄存器，转发

为减少时钟周期的浪费，第一版本中pc寄存器由IF独占（标准实现中为WB写入，IF读取），则对于：

JR/JALR

IF读到该指令时锁定，ID读取到相应寄存器后将数据转发（forwarding）给IF，IF来修改pc寄存器到对应位置后解锁
B***

IF读到该指令时锁定，EX阶段得到比较结果后将数据转发IF，IF修改pc寄存器到对应位置后解锁

分支预测

分支预测推荐阅读相关wiki（好像要ss），其中有许多高大上的名字可以忽略……

本项目采用的是局部分支预测，记录四位历史，分别存饱和计数器。最终测试中平均正确率达95%。

在tik tok实现中使用，若预测错误则由主线程清空前两个过程占用的数据位置（Pack），并回滚操作（如先于锁上的寄存器进行判断，若回滚则不加锁）

项目内各文件说明

code（代码存放）

Versions是一些版本的文件备份
mips_sim是Visual Studio 2015的工作目录
- mips_sim.cpp: 主程序，初始化各种表格
- CPU.hpp: 核心程序，读入程序，具体处理各种指令
- oracle.hpp: 分支预测程序
- Pack.hpp: 指令操纵数据的存储结构
- program.hpp: 完成parser的工作，计算预留内存大小
- op.hpp(old version): 完成EX阶段的运算
- Brick.hpp(old version): 负责对于寄存器、内存地址以及立即数的抽象
testCpp是一些测试语言特性的小程序
threadTest是测试多线程的vs工作目录

documents（资料，测试数据）

MipsTest中有最朴素的makefile以及用于测试的test.py以及测试数据

“编译前的源码”是测试数据变成汇编之前的样子，可帮助理解与调试

structure（命令编号表，思维导图）

instructions记录了指令的一些相关信息以及第二版本中各个数字的具体意义

各种pdf是第一版本时未考虑性能情况下的一些结构图，使用ProcessOn绘制