RISCV-Simulator Part1

1 开源声明

该项目是上海科技大学 CS211 Advancing Computer Architecture 课程设计,引用北京大学 hehao 写的 RISCV 平台(https://github.com/hehao98/RISCV-Simulator )。

2 平台安装与测试

其实整个平台的简介,安装和运行原作者已经有了详尽的文档(https://hehao98.github.io/posts/2019/03/riscv-simulator/ )。个人推荐是直接阅读原文。项目本体应该没有显著的 bug(我并不敢打包票,因为我自己就发现了一个并且提了 issue,然而作者表示 3 年前写的,已经忘光了 lmao),个人测试在大部分 linux 发行版上面都可以正常运行。

3 项目框架介绍和 Lab 总览

(其实想吐槽一下整个平台有屎山的味道,但是转念一想,毕竟不是人人都是 pintos 这种历经了数十年打磨的项目,也就心平气和了)
项目结构其实很简单,在 4 个 Lab 中基本只需要关注\src即可,文件名基本说明了其功能,详细情况我将在具体的 Lab 分析中谈及。\test放置测试文件,需要编译为 RISCV 放置在\riscv-elf中运行。
Lab 0 主要是实现原子指令。Lab 1 涉及实现不同 policy 的 Cache。Lab 2 实现基于感知机的分支预测。Lab 3 实现多核 CPU。
在 Part 1 中,我将分析 Lab 0 和其具体实现。

4 Lab 0

Lab 0 相对来说是四个项目中最简单的一个(合理,毕竟谁也不想一上来就写多线程),而且我不幸的发现,这是唯一一个我不需要回去看代码就能开些 blog 的 Lab 了。

4.1 文档分析

首先我们通读 Lab 要求文档(https://github.com/HarukiMoriarty/CS211-AdvancingCA-Shanghaitech/blob/main/Lab/Lab0/CS211-Lab0.pdf )。显然,我们需要实现两个原子指令,Load Reserved(LR)Store Conditional(SC)

我们先简短介绍一下原子指令。原子指令是一种重要的并发工具,保证其执行过程中不会被其他进程或线程中断,从而确保数据的一致性和操作的完整性。

RISCV 的原子指令不止 LR/SC,同样存在一批以“AMO”为前缀的原子指令,Lab 0 中我们仅考虑 LR/SC。在这时我们便遇到了第一个问题,在不同版本 RISCV 文档中,对于 LR/SC 的实现要求是不同的,特指功能要求(因为 structure 是一样的)。我选择了 V1 版本(Volume 1, Unprivileged Specification version 20191213)。有兴趣的大佬可以参考 21 年的新版本(v2),对于 LR/SC 指令的要求更为宽松。

我们首先展示 LR/SC 指令结构(没啥好分析的,直接上图)

LR/SC 都是 32 位指令,opcode 为0X2F;funct5 为0x3;对于 8B 数据,funct3 为0x3,对于 4B 数据,funct3 为0x2;本次 Lab 不考虑数据对齐。

然后我们分析其基本功能,LR 指令从 rs1 处获得数据地址,从 rd 处获得符号位扩展,并且对这个地址进行注册保留。SC 指令从 rs1 处获得数据地址,从 rs2 处获得数据,当且仅当该地址注册保留依旧有效(valid)时成功执行,将数据从 rs2 写入内存,向 rd 中写入 0;如果执行失败,则仅向 rd 中写入非 0 值。根据 V1 版本推测,我倾向于无论成功与否,LR/SC 指令的执行都会清除指向地址的注册保留。

我们考虑更多,如果(指令流上)同时存在多个嵌套 LR-SC 指令对怎么办?这不仅仅包括,单一核(hart)执行了嵌套的 LR-SC 指令,也包括多个核同时对一个地址进行 LR-SC 指令。V1 采取了更为保守的策略,只允许 SC 追踪最近的,同一个核的 LR 指令。

我在这里附上原文,An SC can only pair with the most recent LR in program order. An SC may succeed only if no store from another hart to the reservation set can be observed to have occurred between the LR and the SC, and if there is no other SC between the LR and itself in program order. An SC may succeed only if no write from a device other than a hart to the bytes accessed by the LR instruction can be observed to have occurred between the LR and SC. Note this LR might have had a different effective address and data size, but reserved the SC’s address as part of the reservation set.

很绕,我进行简要概括,即,在当前核 LR 到 SC 的程序流中,不能出现额外的 LR/SC 指令,不能出现其他核访问保留注册地址的操作,不能出现本核对于注册保留地址进行写操作,并且 SC 指令观察到保留注册依然有效,才能成功执行。

这其实极大的简化了 Lab 的难度,在一开始我和马老师的讨论中考虑了更为复杂的情况,也是 21 版 V2 中所考虑的,允许一些只读指令在注册保留的地址上操作,并且允许 LR/SC 指令的嵌套。V1 近乎苛刻的要求反而是让人感觉相当奇怪的(不过,先正确,再效率)。这一点其实可以另外写一篇文章讨论。

4.2 框架分析与设计实现

本 Lab 只需要动/src/Simulator即可。

我们先总览 Simulator,其本质上就是实现了 CPU 的五级流水,将他们实现为具体的五个函数,fetch,decode,excute,memoryAccess,和 writeBack,简明易懂。

我们不妨先将 LR/SC 指令的解码和信息传递完成。

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
......
namespace RISCV
{
......
enum Inst
{
......
LRW = 54, /* add encode lr.w instruction as 54 */
LRD = 55, /* add encode lr.d instruction as 55 */
SCW = 56, /* add encode sc.w instruction as 56 */
SCD = 57, /* add encode sc.d instruction as 57 */
......
};
......
/* add LR SC instruction with opcode 0X2F */
const int OP_CAS = 0x2F;
......
inline bool isReadMem(Inst inst)
{
/* As LR and SC both need memory access and write back to
reg, so we need to handle with harzard in pipline */
if (...... || inst == LRW || inst == LRD
|| inst == SCW || inst == SCD)
{
return true;
}
return false;
}
}

我们首先在头文件 Inst 数据结构中加上四个 LR/SC 指令的代号数字,然后将其列入内存操作指令中。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
......
namespace RISCV
{
......
const char *INSTNAME[]{ /* add instruction name */
......,"lrw","lrd","scw","scd"};
}
......
void Simulator::decode()
{
......
if (this->fReg.len == 4) // 32 bit instruction
{
......
switch (opcode)
{
......
case OP_CAS: /* add OP_CAS handler */
{
/* read data in reg[rs1] which store the address */
op1 = this->reg[rs1];
/* read data in reg[rs2] which is no mean in LR,
store the old_value in SC */
op2 = this->reg[rs2];
reg1 = rs1;
reg2 = rs2;
dest = rd; /* The reg which should be write back */

/* Get the funct5 */
uint32_t temp = (inst >> 27) & 0x1F;
switch (temp)
{
case 0x2: /* LR instruction */
if (funct3 == 3) /* LR.D instruction */
{
instname = "lrd";
insttype = LRD;
}
else if (funct3 == 2) /* LR.W instruction */
{
instname = "lrw";
instyype = LRW;
}
else
{
this->panic("Unknown 32bit funct3 0x%x\n", funct3);
}
break;
case 0x3: /* SC instruction */
if (funct3 == 3) /* SC.D instruction */
{
instname = "scd";
insttype = SCD;
}
else if (funct3 == 2) /* SC.W instruction */
{
instname = "scw";
instyype = SCW;
}
else
{
this->panic("Unknown 32bit funct3 0x%x\n", funct3);
}
break;
default:
this->panic("Unknown 32bit funct5
0x%x\n", temp);
}
}
......
}
}
......
}

void Simulator::excecute()
{
......
bool _cas = false; /* To identify whether it is a LR or SC */

switch (inst)
{
......
case LRW: /* Datapath of LR.W instruction */
readMem = true;
writeReg = true;
memLen = 4;
out = op1;
readSignExt = true;
_cas = true;
break;
case LRD: /* Datapath of LR.D instruction */
readMem = true;
writeReg = true;
memLen = 8;
out = op1;
readSignExt = true;
_cas = true;
break;
case SCW: /* Datapath of SC.W instruction */
writeReg = true;
writeMem = true;
memLen = 4;
out = op1;
_cas = true;
op2 = op2 & 0xFFFFFFFF;
break;
case SCD: /* Datapath of SC.D instruction */
writeReg = true;
writeMem = true;
memLen = 8;
out = op1;
op2 = op2 & 0xFFFFFFFF;
_cas = true;
break;
......
}
......
/* Pass the information to the next stage */
this->eRegNew._cas = _cas;
}

这都是一些非常“顺其自然”的照猫画虎,接下去我们需要考虑一个合适的数据结构,并且将原子性质在 memoryAccess 中实现。我们之前讨论了(2019)V1 版本的 CAS 指令要求,我选择了直接在 Simulator 类中声明私有变量,存储注册保留的地址,注册保留的字节数,以及注册保留的 valid bit。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Simulator
{
public:
......
private:
......
struct EReg
{
......
bool _cas;
} eReg, eRegNew;
......
uint32_t registry_addr; /* Registry hold the first address */
uint32_t registry_num; /* Registry hold the number */
bool registry_whe; /* Registry hold the valid bit */
}

那么如何利用这些数据结构实现 CAS 也变得显而易见。

对于 SC 指令,我们注意到,任何涉及注册保留地址的存储行为都会使注册保留失效,所以我简单粗暴的在原先的 store 行为上加了一层地址判断。然后,针对 SC 指令,进行特殊的逻辑判断,查找对应地址是否注册保留,如果注册保留有效,那么向内存写入地址,返回 0x0;如果注册保留失败,那么直接返回非 0 值。注意,无论是否是 SC 指令,任何存储行为都会使目标地址的注册保留失效。

对于 LR 指令,我们直接更新数据结构即可,设置目标地址的注册保留有效,从内存中读出数据,并且记录其字节数。正常的读内存指令不需要进行其他操作。我们可以注意到,因为 LR 实时维护了数据结构,所以只会保留最近的 LR 指令,满足了我们之前的讨论要求。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
void Simulator::memoryAccess()
{
......
bool _cas = this->eReg._cas;
......
if (writeMem)
{
switch (memLen)
{
case 1:
good = this->memory->setByte(out, op2, &cycles);
if ((out >= this->registry_addr) && (out <= (this->registry_addr + this->registry_num)))
{ /* If there is any byte write to the reservation set */
this->registry_whe = false;
}
break;
case 2:
good = this->memory->setShort(out, op2, &cycles);
for (uint32_t i = 0; i < 2; i++)
{
if (((out + i) >= this->registry_addr) && ((out + i) <= (this->registry_addr + this->registry_num)))
{ /* Any byte write to the reservation set */
this->registry_whe = false;
}
}
break;
case 4:
if (_cas)
{ /* If this is SC instruction */
if (this->registry_whe && (this->registry_addr == out) && (this->registry_num == 4))
{ /* Reservation set is valid the first address same the access length same */
good = this->memory->setInt(out, op2, &cycles);
out = 0;
}
else
{ /* If failed return code 1 */
out = 1;
}
/* SC eliminate all reservation */
this->registry_whe = false;
}
else
{ /* If not, do basic store operation */
for (uint32_t i = 0; i < 4; i++)
{ /* For all bytes */
if (((out + i) >= this->registry_addr) && ((out + i) <= (this->registry_addr + this->registry_num)))
{ /* Any access to the bytes */
this->registry_whe = false;
}
}
good = this->memory->setInt(out, op2, &cycles);
}
break;
case 8:
if (_cas)
{
if (this->registry_whe && (this->registry_addr == out) && (this->registry_num == 8))
{ /* Reservation set is valid the first address same the access length same */
good = this->memory->setLong(out, op2, &cycles);
out = 0;
}
else
{
out = 1;
}
tthis->registry_whe = false;
}
else
{
for (uint32_t i = 0; i < 8; i++)
{
if (((out + i) >= this->registry_addr) && ((out + i) <= (this->registry_addr + this->registry_num)))
{
this->registry_whe = false;
}
}
good = this->memory->setLong(out, op2, &cycles);
}
}
}
......
if (readMem)
{ /* Handle with LR instruction */
switch (memLen)
{
......
case 4:
if(readSignExt)
{
if(_cas)
{ /* LR.W instruction */
this->registry_whe = true; /* Valid */
this->registry_addr = out; /* Store */
this->registry_num = 4; /* Length */
}
out = (int64_t)this->memory->getInt(out, &cycles);
}
......
case 8:
if(readSignExt)
{
if(_cas)
{ /* LR.W instruction */
this->registry_whe = true;
this->registry_addr = out;
this->registry_num = 8;
}
out = (int64_t)this->memory->getInt(out, &cycles);
}
......
}
}
}

好的,到这里我们完成了 LR/SC 这两个指令,接下去我们就是封装一下写一个 CAS 函数即可,在这里我们直接使用 C++的内联汇编

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int CAS(long *dest, long new_value, long old_value)
{
int ret = 0;

// TODO: write your code here
__asm__ __volatile__(
"retry: lr.w %0, %[output2]\n" /* Load value of addr */
" bne %0, %[input1], fail\n" /* Compare and check */
" sc.w %0, %[input2], %[output2]\n" /* Store new value */
" bnez %0, retry\n" /* Whether atom operation succcess */
" li %[output1], 1\n" /* Return code 1 */
" j success\n" /* Go on following */
"fail: li %[output1], 0\n" /* Return code 0 */
"success: \n"
: [output1] "=&r"(ret), [output2] "+A"(*dest)
: [input1] "rJ"(old_value), [input2] "rJ"(new_value)
: "memory");

return ret;
}

代码中的注释已经十分详尽,我不再额外啰嗦。

4.3 测试

那么接下去测试即可,将 C++文件编译为 RISCV 汇编文件,注意这里使用rv64ia,因为 LR/SC 指令是扩展指令。测试结果如下:

测试通过!

4.4 思考(胡言乱语)

严格来说官方提供的测试文件并不详尽,其也只检测了四字节 LR/SC 指令的正确性,此外像多核情况,嵌套问题也被排除在此次 Lab 的考虑范围之外。或许我有空的时候会重新写一下两个指令,将这些问题考虑进去。(人生目标清单喜加一)


RISCV-Simulator Part1
https://harukimoriarty.github.io/2023/07/03/RISCV-Simulator/
Author
Zhenghong Yu
Posted on
July 3, 2023
Licensed under