这个 MIPS 程序应该花这么长时间吗? (近似 pi 的程序)
Is this MIPS program supposed to take this long? (program that approximates pi)
其中的 objective 是编写一个使用该算法的 MIPS 程序。
我做到了。它有效,只需大约 30 分钟即可完成 delta = 1E-2。
C 程序(用 gcc 编译)使用该增量大约需要 1 分半钟。
我试过在 C 程序上使用 delta = 1E-3 但在 2 个多小时后不得不中止它。
我只想知道:这应该发生吗?结果对我来说看起来足够准确(3.13909200,delta = 1E-2)。我做错了什么吗?
我知道这个算法可能不是最有效的,MIPS 或 MARS(我用于 MIPS)也不是。
MIPS 代码:
.data
l_cubo: .double 1.0
delta: .double 1E-2
zero: .double 0.0
dois: .double 2.0
six: .double 6.0
.text
.globl main
main:
la $a0,l_cubo
l.d $f20,0($a0) #l_cubo
la $a0,dois
l.d $f4,0($a0)
div.d $f22,$f20,$f4 #r_esfera
la $a0,delta
l.d $f24,0($a0) #delta
la $a0,zero
l.d $f26,0($a0) #v_cubo ou v_total
l.d $f28,0($a0) #v_esfera
l.d $f4,0($a0) #x
l.d $f6,0($a0) #y
l.d $f8,0($a0) #z
loop_x:
c.lt.d $f4,$f20
bc1f end_loop_x
l.d $f6,0($a0)
loop_y:
c.lt.d $f6,$f20
bc1f end_loop_y
l.d $f8,0($a0)
loop_z:
c.lt.d $f8,$f20
bc1f end_loop_z
add.d $f26,$f26,$f24
mov.d $f12,$f4
mov.d $f14,$f6
mov.d $f30,$f8
jal in_esfera
l.d $f10,0($a0)
beqz $v0,continue
add.d $f28,$f28,$f24
continue:
add.d $f8,$f8,$f24
j loop_z
end_loop_z:
add.d $f6,$f6,$f24
j loop_y
end_loop_y:
add.d $f4,$f4,$f24
j loop_x
end_loop_x:
mul.d $f24,$f24,$f24
mul.d $f28,$f28,$f24
mul.d $f26,$f26,$f24
div.d $f28,$f28,$f26
la $a0,six
l.d $f10,0($a0)
mul.d $f28,$f28,$f10
li $v0,3 #
mov.d $f12,$f28 #
syscall # print pi
li $v0,10 #
syscall #exit
####################################
.text
.globl in_esfera
in_esfera:
sub.d $f12,$f12,$f22
mul.d $f12,$f12,$f12
sub.d $f14,$f14,$f22
mul.d $f14,$f14,$f14
sub.d $f30,$f30,$f22
mul.d $f30,$f30,$f30
add.d $f30,$f12,$f30
add.d $f30,$f14,$f30
mul.d $f16,$f22,$f22
li $v0,0
c.le.d $f30,$f16
bc1f continue2
li $v0,1
continue2:
jr $ra
我只是想知道我的教授将如何纠正一个需要 30 分钟才能执行的程序。
我假设这使用与 C
版本相同的算法。这通过测试立方体中的点的 3D 网格以查看它们是否在球体内来近似 Pi 的值。这是一个 O(N^3)
计算,其中 N
是网格每个维度中的单位数(增量)。
所以...是的...您的 MIPS 代码预计需要很长时间才能计算出 Pi 的准确近似值。
如果 l_cubo 为 4,delta 为 1/100,那么您应该执行 400 x 400 x 400 = 64,000,000 次迭代。 30 分钟似乎太过分了。
如果 l_cubo 是 4,delta 是 1/1000,那么你应该执行 4000 x 4000 x 4000 = 64,000,000,000 次迭代。
但是如果您想对其进行健全性检查,您的 MIP 代码 应该 与 运行 在同一硬件上的 C 实现一样快,甚至更快具有相同的参数。 (注意:如果您 运行 在 MIPS 仿真器上运行 MIPS 代码,您将无法做到这一点。)
其中的 objective 是编写一个使用该算法的 MIPS 程序。 我做到了。它有效,只需大约 30 分钟即可完成 delta = 1E-2。 C 程序(用 gcc 编译)使用该增量大约需要 1 分半钟。 我试过在 C 程序上使用 delta = 1E-3 但在 2 个多小时后不得不中止它。
我只想知道:这应该发生吗?结果对我来说看起来足够准确(3.13909200,delta = 1E-2)。我做错了什么吗?
我知道这个算法可能不是最有效的,MIPS 或 MARS(我用于 MIPS)也不是。
MIPS 代码:
.data
l_cubo: .double 1.0
delta: .double 1E-2
zero: .double 0.0
dois: .double 2.0
six: .double 6.0
.text
.globl main
main:
la $a0,l_cubo
l.d $f20,0($a0) #l_cubo
la $a0,dois
l.d $f4,0($a0)
div.d $f22,$f20,$f4 #r_esfera
la $a0,delta
l.d $f24,0($a0) #delta
la $a0,zero
l.d $f26,0($a0) #v_cubo ou v_total
l.d $f28,0($a0) #v_esfera
l.d $f4,0($a0) #x
l.d $f6,0($a0) #y
l.d $f8,0($a0) #z
loop_x:
c.lt.d $f4,$f20
bc1f end_loop_x
l.d $f6,0($a0)
loop_y:
c.lt.d $f6,$f20
bc1f end_loop_y
l.d $f8,0($a0)
loop_z:
c.lt.d $f8,$f20
bc1f end_loop_z
add.d $f26,$f26,$f24
mov.d $f12,$f4
mov.d $f14,$f6
mov.d $f30,$f8
jal in_esfera
l.d $f10,0($a0)
beqz $v0,continue
add.d $f28,$f28,$f24
continue:
add.d $f8,$f8,$f24
j loop_z
end_loop_z:
add.d $f6,$f6,$f24
j loop_y
end_loop_y:
add.d $f4,$f4,$f24
j loop_x
end_loop_x:
mul.d $f24,$f24,$f24
mul.d $f28,$f28,$f24
mul.d $f26,$f26,$f24
div.d $f28,$f28,$f26
la $a0,six
l.d $f10,0($a0)
mul.d $f28,$f28,$f10
li $v0,3 #
mov.d $f12,$f28 #
syscall # print pi
li $v0,10 #
syscall #exit
####################################
.text
.globl in_esfera
in_esfera:
sub.d $f12,$f12,$f22
mul.d $f12,$f12,$f12
sub.d $f14,$f14,$f22
mul.d $f14,$f14,$f14
sub.d $f30,$f30,$f22
mul.d $f30,$f30,$f30
add.d $f30,$f12,$f30
add.d $f30,$f14,$f30
mul.d $f16,$f22,$f22
li $v0,0
c.le.d $f30,$f16
bc1f continue2
li $v0,1
continue2:
jr $ra
我只是想知道我的教授将如何纠正一个需要 30 分钟才能执行的程序。
我假设这使用与 C
版本相同的算法。这通过测试立方体中的点的 3D 网格以查看它们是否在球体内来近似 Pi 的值。这是一个 O(N^3)
计算,其中 N
是网格每个维度中的单位数(增量)。
所以...是的...您的 MIPS 代码预计需要很长时间才能计算出 Pi 的准确近似值。
如果 l_cubo 为 4,delta 为 1/100,那么您应该执行 400 x 400 x 400 = 64,000,000 次迭代。 30 分钟似乎太过分了。
如果 l_cubo 是 4,delta 是 1/1000,那么你应该执行 4000 x 4000 x 4000 = 64,000,000,000 次迭代。
但是如果您想对其进行健全性检查,您的 MIP 代码 应该 与 运行 在同一硬件上的 C 实现一样快,甚至更快具有相同的参数。 (注意:如果您 运行 在 MIPS 仿真器上运行 MIPS 代码,您将无法做到这一点。)