cs61c-proj2

Project 2: CS61Classify

cs61c - Great Ideas in Computer Architecture (Machine Structures) proj2 笔记

课程主页:https://inst.eecs.berkeley.edu/~cs61c/fa20/#by-week

个人仓库:https://github.com/2333monster/my-cs61c-proj

注:是sp22 的proj2

Part A: Math Functions

完成

  • abs
  • dot product
  • matrix multiplication
  • an element-wise rectifier function (ReLU)
  • an argmax function for vectors.

Task 1: Absolute Value (Walkthrough)

熟悉工作流

Running Tests

在linux 环境下,进行操作即可

1
2
3
bash test.sh
bash test.sh part_a
bash test.sh test_abs

Using VDB to debug tests via Venus

根据the setup section of the spec 设置venus,注意在linux 下即可

在/src/abs.s 中添加ebreak

1
2
3
4
5
6
7
8
9
10
11
12
13
abs:
# Prologue
ebreak
# PASTE HERE

blt a0, zero, done

# Negate a0
sub a0, x0, a0

done:
ret
# Epilogue

在terminal 中,运行

1
2
cd /vmfs/test-src
vdb test_abs_one.s

然后再simulator 中debug就好,发现错误后(大于0但是取了相反数),修改

1
2
3
4
5
6
7
8
9
10
11
12
13
abs:
# Prologue
ebreak
# PASTE HERE

bge a0, zero, done

# Negate a0
sub a0, x0, a0

done:
ret
# Epilogue

Task 2: ReLU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
relu:
# ebreak
# Prologue
li t5,1
blt a1,t5,exit_relu
add t0, x0,x0
addi t2, x0, 4
loop_start:
beq t0, a1, loop_end
mul t1, t0, t2
add t3, a0, t1
lw t4, 0(t3)
bgt t4, x0, loop_continue
sw zero, 0(t3)
loop_continue:
addi t0, t0, 1
j loop_start
loop_end:
# Epilogue
ret
exit_relu:
li a0 36
j exit

Task 3: Argmax

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
argmax:
ebreak
# Prologue
li t5, 1
blt a1, t5, exit_argmax
li t0,0 #max_index
lw t1,0(a0) #max_value
add t2,x0,x0 #i
li t5,4
loop_start:
beq t2,a1,loop_end
mul t4,t2,t5 #4i
add t6,a0,t4 #&a0[i]
lw t3,0(t6) #a0[i]
bge t1,t3,loop_continue
mv t1,t3
mv t0,t2
loop_continue:
addi t2,t2,1
j loop_start
exit_argmax:
li a0,36
j exit
loop_end:
mv a0,t0
ret

Task 4: Dot Product

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
dot:
ebreak
# Prologue
li t5,1
blt a2,t5,exit_36
blt a3,t5,exit_37
blt a4,t5,exit_37
li t0,0 #result
li t1,0 #i
slli a3,a3,2
slli a4,a4,2
loop_start:
beq t1,a2,loop_end
lw t2,0(a0)
lw t3,0(a1)

mul t4,t2,t3
add t0,t0,t4

add a0,a0,a3
add a1,a1,a4
addi t1,t1,1
j loop_start
exit_36:
li a0 36
j exit
exit_37:
li a0 37
j exit
loop_end:
# Epilogue
mv a0 t0
ret

Task5: Matrix Multiplication

做了好久,刚开始写确实很乱,静下心梳理。

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
matmul:
ebreak
# Error checks
li t5, 1
blt a1, t5, exit_38
blt a2, t5, exit_38
blt a4, t5, exit_38
blt a5, t5, exit_38
bne a2, a4, exit_38

# Prologue
addi sp, sp, -16
sw s0, 0(sp)
sw s1, 4(sp)
sw s2, 8(sp)
sw s3, 12(sp)
li s0, 0 # i
li s1, 0 # j

outer_loop_start:
li s1, 0

inner_loop_start:
# save context
addi sp, sp, -32
sw ra, 0(sp)
sw a0, 4(sp)
sw a1, 8(sp)
sw a2, 12(sp)
sw a3, 16(sp)
sw a4, 20(sp)
sw a5, 24(sp)
sw a6, 28(sp)

# set arguments for dot function
addi t4, x0, 4
mul t4, t4, s1
add a1, a3, t4
li a3, 1
mv a4, a5

# call dot function
jal dot

# get answer
mv t1, a0

# restore context
lw ra, 0(sp)
lw a0, 4(sp)
lw a1, 8(sp)
lw a2, 12(sp)
lw a3, 16(sp)
lw a4, 20(sp)
lw a5, 24(sp)
lw a6, 28(sp)
addi sp, sp, 32

# store result in the result matrix d
mul t2, s0, a5
add t2, t2, s1
addi t4, x0, 4
mul t2, t2, t4
add t2, a6, t2
sw t1, 0(t2)

inner_loop_end:
addi s1, s1, 1
beq s1, a5, outer_loop_end
j inner_loop_start

outer_loop_end:
addi s0, s0, 1
addi t4, x0, 4
mul t0, t4, a2
add a0, a0, t0
beq s0, a1, end
j outer_loop_start


end:
# Epilogue
lw s0, 0(sp)
lw s1, 4(sp)
lw s2, 8(sp)
lw s3, 12(sp)
addi sp, sp, 16
ret

exit_38:
li a0, 38
j exit

代码思路

  1. 首先,代码进行维度检查,确保输入矩阵的维度是有效的,如果任何一个维度小于1,则跳转到 exit_38 标签,终止程序。
  2. 然后,代码初始化一些寄存器和变量,为循环做准备。s0 用于追踪当前行,s1 用于追踪当前列。
  3. 进入外层循环 outer_loop_start,其中 s0 追踪矩阵 m0 的当前行。然后,进入内层循环 inner_loop_start,其中 s1 追踪矩阵 m1 的当前列。
  4. 在内层循环内,首先保存寄存器上下文,然设置dot函数的参数。a0不变,计算 a1 的地址(a1 是矩阵 m1 当前列的起始地址),a2不变,设置 a3 为 1,将 a4 设置为矩阵 m1 的列数。
  5. 调用 dot 函数,将矩阵 m0 的当前行和矩阵 m1 的当前列进行点积运算,结果保存在 t1 中。
  6. 恢复寄存器上下文,然后将 t1 的值存储在结果矩阵 d 中的对应位置。
  7. 内层循环结束后,增加 s1 的值,如果 s1 小于矩阵 m1 的列数,则继续内层循环。
  8. 外层循环结束后,增加 s0 的值,然后将 a0 更新为下一行的起始地址。如果 s0 小于矩阵 m0 的行数,则继续外层循环。
  9. 循环结束后,恢复寄存器上下文并返回。
  10. 如果发现维度无效,则跳转到 exit_38,程序终止。

计算a1地址

1
2
3
addi t4, x0, 4
mul t4, t4, s1
add a1, a3, t4

计算结果存储在结果矩阵d 的相对位置

1
2
3
4
5
6
mul t2, s0, a5
add t2, t2, s1
addi t4, x0, 4
mul t2, t2, t4
add t2, a6, t2
sw t1, 0(t2)
  1. mul t2, s0, a5: 这行代码计算了要存储的元素在结果矩阵 d 中的行号。s0 包含了当前正在计算的行号,而 a5 包含了矩阵 m1 的列数(也是结果矩阵 d 的列数)。将这两个值相乘,得到的结果存储在寄存器 t2 中。
  2. add t2, t2, s1: 这行代码将刚刚计算的行号 t2 与当前正在计算的列号 s1 相加。这是为了计算出在结果矩阵 d 中的具体位置。
  3. addi t4, x0, 4: 这行代码将立即数 4 存储在寄存器 t4 中。这是因为每个元素占用 4 个字节(假设是 32 位整数)。
  4. mul t2, t2, t4: 这行代码将刚刚计算的位置 t2 与每个元素的大小相乘,以得到字节偏移量。
  5. add t2, a6, t2: 这行代码将字节偏移量 t2 与结果矩阵 d 的起始地址相加,从而得到最终要存储的地址。
  6. sw t1, 0(t2): 这行代码使用 sw 指令,将点积运算的结果 t1 存储在刚刚计算出的地址上,从而将计算结果存储在结果矩阵 d 中的对应位置。

更新矩阵a0 的行指针,以便在下一次循环中处理下一行

1
2
3
addi t4, x0, 4
mul t0, t4, a2
add a0, a0, t0
  1. addi t4, x0, 4: 这行代码将立即数 4 存储在寄存器 t4 中。这是因为每个元素占用 4 个字节(假设是 32 位整数)。
  2. mul t0, t4, a2: 这行代码将刚刚存储在寄存器 t4 中的值(即每个元素的大小)与矩阵 m0 的列数 a2 相乘,得到的结果存储在寄存器 t0 中。这是为了计算当前行中下一个元素的偏移量。
  3. add a0, a0, t0: 这行代码将刚刚计算出的偏移量 t0 加到矩阵 m0 的起始地址 a0 上,以更新行指针。这将使指针指向下一行的开头,以便在下一次循环中处理下一行

Part B: File Operations and Classification [09/14]

Task 7: Read Matrix

Matrices are stored in files as a consecutive sequence of 4-byte integers. The first and second integers in the file indicate the number of rows and columns in the matrix, respectively. The rest of the integers store the elements in the matrix in row-major order.

Fill in the read_matrix function in src/read_matrix.s. This function should do the following:

  1. 以读取权限打开文件。 文件路径作为参数 (a0) 提供。
  2. 从文件中读取行数和列数(记住:它们是文件中的前两个整数)。 将这些整数存储在内存中提供的指针处(a1 表示行,a2 表示列)。
  3. 在堆上分配空间来存储矩阵。 (提示:使用上一步中的行数和列数来确定要分配多少空间。)
  4. 将矩阵从文件中读取到上一步分配的内存中。
  5. 关闭文件。
  6. 返回指向内存中矩阵的指针。

参数要求:https://inst.eecs.berkeley.edu/~cs61c/sp22/projects/proj2/part-b/#your-task

c program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int* read_matrix(char* filename, int* row, int* col){
File* file = fopen(filename, "rb");
if(file == null){
fopen_error();
}

fread(row, size_4, 1, file);
fread(col, size_4, 1, file);

int* matrix = (int *)malloc((*row) * (*col) * size_4);
if(matrix == 0){
matrix_error;
}
int byte_read = fread(matrix, size_4, (*row) * (*col), file);
if(byte_read != (*row) * (*col)){
free(matrix);
fclose(file);
fread_error;
}
if(fclose(file) == -1){
fclose_error;
}
return matrix;
}

risc-v code

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
read_matrix:

# Prologue
addi sp, sp, -32
sw ra, 4(sp)
sw s0, 8(sp)
sw s1, 12(sp)
sw s2, 16(sp)
sw s3, 20(sp)
sw s4, 24(sp)
sw s5, 28(sp)

mv s1, a1
mv s2, a2
li a1, 0
jal ra, fopen

li t0, -1
beq a0, t0, fopen_error
sw a0, 0(sp)

mv a1, s1
li s3, 4
mv a2, s3
jal ra, fread
bne a0, s3, fread_error

lw a0, 0(sp)
mv a1, s2
li s3, 4
mv a2, s3
jal ra, fread
bne, a0, s3, fread_error

lw t0, 0(s1)
lw t1, 0(s2)
mul s4, t0, t1
slli, s4, s4, 2
mv a0, s4
jal ra, malloc
beqz a0, malloc_error

mv s5, a0
lw a0, 0(sp)
mv a1, s5
mv a2, s4
jal ra, fread
bne a0, s4, fread_error

lw a0, 0(sp)
jal ra, fclose
bnez a0, fclose_error

mv a0, s5

# Epilogue
lw ra, 4(sp)
lw s0, 8(sp)
lw s1, 12(sp)
lw s2, 16(sp)
lw s3, 20(sp)
lw s4, 24(sp)
lw s5, 28(sp)
addi sp, sp, 32
ret


malloc_error:
li a0, 26
j exit
fopen_error:
li a0, 27
j exit
fclose_error:
li a0, 28
j exit
fread_error:
li a0, 29
j exit

Task 8: Write Matrix

Fill in the write_matrix function in src/write_matrix.s. This function should do the following:

  1. 以写权限打开文件。 文件路径作为参数提供。
  2. 将行数和列数写入文件。 (提示:fwrite 函数需要一个指向内存中数据的指针,因此您应该首先将数据存储到内存,然后将指向数据的指针传递给 fwrite。)
  3. 将数据写入文件。
  4. 关闭文件。

参数要求:https://inst.eecs.berkeley.edu/~cs61c/sp22/projects/proj2/part-b/#task-8-write-matrix

c program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void write_matrix(char* filename, int*matrix, int rows, int cols){
File* file = fopen(filename,"wb");
if(file == null){
fopen_error;
}
fwrite(&rows,size_4,1,file);
fwrite(&cols,size_4,1,file);

fwrite(matrix,size_4,rows*cols,file);

if(fclose(file) == -1){
fclose_error;
}

}

risc-v code

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
write_matrix:

# Prologue
addi sp, sp, -32
sw ra, 4(sp)
sw s0, 8(sp)
sw s1, 12(sp)
sw s2, 16(sp)
sw s3, 20(sp)
sw s4, 24(sp)
sw s5, 28(sp)

mv s0, a0
mv s1, a1
mv s2, a2
mv s3, a3

li a1, 1
jal ra, fopen
li t0, -1
beq a0, t0, fopen_error
mv s5, a0

sw s2, 0(sp) # rows
mv a0, s5
mv a1, sp
li s4, 1
mv a2, s4
li a3, 4
jal ra, fwrite
bne a0, s4, fwrite_error

sw s3, 0(sp) # cols
mv a0, s5
mv a1, sp
li s4, 1
mv a2, s4
li a3, 4
jal ra, fwrite
bne a0, s4, fwrite_error

mul s4, s2, s3 # data
mv a0, s5
mv a1, s1
mv a2, s4
li a3, 4
jal ra, fwrite
bne a0, s4, fwrite_error

mv a0, s5
jal ra, fclose
li t0, -1
beq a0, t0, fclose_error

# Epilogue
lw ra, 4(sp)
lw s0, 8(sp)
lw s1, 12(sp)
lw s2, 16(sp)
lw s3, 20(sp)
lw s4, 24(sp)
lw s5, 28(sp)
addi sp, sp, 32
ret

fopen_error:
li a0, 27
j exit
fwrite_error:
li a0, 30
j exit
fclose_error:
li a0, 28
j exit

Task 9: Classify

最后一部分,写了两个晚上,将近8个小时左右

Fill in the classify function in src/classify.s. This function should do the following:

  1. 从文件中读取三个矩阵 m0、m1 和输入。 它们的文件路径作为参数提供。 您需要为 read_matrix 的指针参数分配空间,因为该函数需要一个指向已分配内存的指针。
  2. 计算 h = matmul(m0, 输入)。 您可能需要 malloc 空间以适合 h。
  3. 计算 h = relu(h)。 请记住,relu 是就地执行的。
  4. 计算 o = matmul(m1, h) 并将结果矩阵写入输出文件。 输出文件路径作为参数提供。
  5. 计算并返回argmax(o)。 如果 print 参数设置为 0,则还打印出 argmax(o) 和换行符。
  6. 释放使用 malloc 分配的所有数据。 这包括通过调用 read_matrix 分配的任何堆块。
  7. 请记住在返回之前将返回值 argmax(o) 放入适当的寄存器中。

参数要求:https://inst.eecs.berkeley.edu/~cs61c/sp22/projects/proj2/part-b/#task-9-classify

c program,大体的一些,为了满足汇编函数的参数有些写得有些模糊

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
int classify(int argc, char** argv,int a2){
int num_rows_m0,num_cols_m0;
int num_rows_m1,num_cols_m1;
int num_rows_input,num_cols_input;
int* m0, m1, input;

m0 = read_matrix(argv[1],&num_rows_m0,&num_rows_m0);
m1 = read_matrix(argv[2],&num_rows_m1,&num_rows_m1);
input = read_matrix(argv[3],&num_rows_input,&num_rows_input);

int* h;
matmul(m0,input,h)
relu(h,h_size(num_rows_m0*num_cols_input));

int* o;
matmul(m1,h,o);
write_matrix(argv[4],o,num_rows_m1,num_cols_input);

int classification = argmax(o,o_size);
if(a2 == 0){
print_int(classification);
print_char('\n');
}
free(o);
free(h);
free(m0);
free(m1);
free(input);
free(num_rows_m0);
...
free(num_cols_input);

return classification;
}

risc-v code

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
classify:
# prologue
addi sp, sp, -64
sw s0, 12(sp) # a1
sw s1, 16(sp) # a2
sw s2, 20(sp) # m0_pointer
sw s3, 24(sp) # m1_pointer
sw s4, 28(sp) # input_pointer
sw s5, 32(sp)
sw s6, 36(sp) # num_rows_input
sw s7, 40(sp) # num_cols_input
sw s8, 44(sp) # num_rows_m1
sw s9, 48(sp) # num_cols_m1
sw s10, 52(sp) # num_rows_m0
sw s11, 56(sp) # num_cols_m0
sw ra, 60(sp)

li t0, 5
bne a0, t0, argnum_error
mv s0, a1 # store argument pointer
mv s1, a2 # store switcher

# Read pretrained m0
li a0, 4
jal ra, malloc
beqz a0, malloc_error
mv s10, a0
li a0, 4
jal ra, malloc
beqz a0, malloc_error
mv s11, a0
# read matrix
lw a0, 4(s0)
mv a1, s10
mv a2, s11
jal ra, read_matrix
mv s2, a0

# Read pretrained m1
li a0, 4
jal ra, malloc
beqz a0, malloc_error
mv s8, a0
li a0, 4
jal ra, malloc
beqz a0, malloc_error
mv s9, a0
# read matrix
lw a0, 8(s0)
mv a1, s8
mv a2, s9
jal ra, read_matrix
mv s3, a0

# Read input matrix
ebreak
li a0, 4
jal ra, malloc
beqz a0, malloc_error
mv s6, a0
li a0, 4
jal ra, malloc
beqz a0, malloc_error
mv s7, a0
lw a0, 12(s0)
mv a1, s6
mv a2, s7
jal ra, read_matrix
mv s4, a0

# Compute h = matmul(m0, input)
lw t0, 0(s10)
lw t1, 0(s7)
# malloc
mul t0, t0, t1
sw t0, 8(sp) # h_size
slli a0, t0, 2 # 4-byte per element
jal ra, malloc
beqz a0, malloc_error
sw a0, 0(sp) # h_pointer

# matmul
mv a0, s2
lw a1, 0(s10)
lw a2, 0(s11)
mv a3, s4
lw a4, 0(s6)
lw a5, 0(s7)
lw a6, 0(sp)
jal ra, matmul

# Compute h = relu(h)
lw a0, 0(sp)
lw a1, 8(sp)
jal ra, relu

# Compute o = matmul(m1, h)
lw t0, 0(s8)
lw t1, 0(s7)
# malloc
mul t0, t0, t1
sw t0, 8(sp) # o_size
slli a0, t0, 2 # 4-byte per element
jal ra, malloc
sw a0, 4(sp) # o_pointer

# matmul
mv a0, s3
lw a1, 0(s8)
lw a2, 0(s9)
lw a3, 0(sp)
lw a4, 0(s10)
lw a5, 0(s7)
lw a6, 4(sp)
jal ra, matmul

# Write output matrix o
lw a0, 16(s0)
lw a1, 4(sp)
lw a2, 0(s8)
lw a3, 0(s7)
jal ra, write_matrix

# Compute and return argmax(o)
lw a0, 4(sp)
lw a1, 8(sp)
jal ra, argmax
sw a0, 8(sp) # argmax(o)

# If enabled, print argmax(o) and newline
bnez s1, done
lw a0, 8(sp)
jal ra, print_int
li a0, '\n'
jal ra, print_char
done:
# free m0
mv a0, s2
jal ra, free
# free m1
mv a0, s3
jal ra, free
# free input
mv a0, s4
jal ra, free

# free h
lw a0, 0(sp)
jal ra, free
# free o
lw a0, 4(sp)
jal ra, free

# free num&col
mv a0, s6
jal ra, free
mv a0, s7
jal ra, free
mv a0, s8
jal ra, free
mv a0, s9
jal ra, free
mv a0, s10
jal ra, free
mv a0, s11
jal ra, free

# return
lw a0, 8(sp)


# epilogue
lw s0, 12(sp)
lw s1, 16(sp)
lw s2, 20(sp)
lw s3, 24(sp)
lw s4, 28(sp)
lw s5, 32(sp)
lw s6, 36(sp)
lw s7, 40(sp)
lw s8, 44(sp)
lw s9, 48(sp)
lw s10, 52(sp)
lw s11, 56(sp)
lw ra, 60(sp)
addi sp, sp, 64

ret
argnum_error:
li a0, 31
j exit
malloc_error:
li a0, 26
j exit

cs61c-proj2
https://2333monster.github.io/2023/08/12/cs61c-proj2/
作者
John Titor
发布于
2023年8月12日
许可协议