理解MIPS算法

Question

我对编码非常陌生，我们从MIPS开始。我们被“扔进冷水中”，必须实现一种算法来检查数组中的元素是否按升序排序。如果对其进行排序，则1将存储在$v0中，否则将存储为0。给我们的解决办法是：

.data
A: .word 1, 2, 3, 4, 5
l: .word 5

.text
main:
la $s0, A #address of A
lw $s1, l
add $t0, $0, $0 #counter for loop
addi $v0, $0, 1
sub $s1, $s1, $v0
for:
beq $t0, $s1, done
sll $t1, $t0, 2 #byte offset
add $t1, $t1, $s0
lw $t1, 0($t1) #$t1 = A[j]
addi $t2, $t0, 1
sll $t2, $t2, 2
add $t2, $t2, $s0
lw $t2, 0($t2) #$t2 = A[j + 1]
sub $t3, $t2, $t1 #$s3 = A[j+1] - A[j]?
slt $t4, $t3, $0
addi $t3, $0, 1
beq $t3, $t4 unsort #A isn’t sorted if A[j+1] - A[j] has a negative value
addi $t0, $t0, 1 #$t0 = $t0 + 1
j for

unsort:
add $v0, $0, $0 #set $v0 if array isn’t sorted

done:

我很难理解这个代码/算法。首先，什么是数组，为什么我们特别需要其中的5个？但对我来说更重要的是理解这个代码/算法。所以我需要一个很好的人，一步一步地向我解释，简单地说:D，这个代码是如何工作的。

会很有帮助的，提前感谢。

Answer 1

简短回答

基本上，这个程序在循环计数器的循环中迭代数组A，比如i。索引i被初始化为0，并在每次循环迭代中递增1，直到到达l-1为止，其中l是数组A的大小/长度。在每次迭代中，该算法检查A[i] < A[i + 1] (即A中的i-th和(i+1)-th元素是否按升序排列)。如果是这样，则继续执行，$v0保持1，否则它将$v0设置为0并终止。

长答案

数组和内存

数组基本上是一个有序的数据列表--在这种情况下，它是一个有序的单词列表( MIPS中的单词表示:32位值，它由4个字节组成，每个字节有8位信息)。所以在这种情况下，每个字代表一个32位整数。

如果我们有一个长度为A的数组l，则将这些元素从0索引到l-1。数组A (符号：A[0])中的第一个元素保存在内存中的某个地址，我们称之为addr。然后将A (A[i])中的第一个元素保存在内存地址addr + 4*i中.这是因为MIPS中的内存是字节可寻址的，也就是说，每个字节都有自己的地址，因为一个单词由4个字节组成，单词地址被4个字节所抵消(见下文)。

​

​

.data剖面

A: .word 1, 2, 3, 4, 5
l: .word 5

这样，您就会意识到，您没有5个数组，只有一个数组(称为A)，它包含值1、2、3、4和5。因此，长度为5，它在单词l中指定。您可以向数组中添加更多的值，但是必须调整长度，否则会发生奇怪的事情(或者至少结果是随机的)。您的数据在本.data部分中指定，因此存储在程序的内存空间中。

MIPS组件

为了理解.text部分中的代码，您必须了解MIPS程序集。如果我写一个寄存器，就把它当作32位值的占位符。例如，$0是零寄存器，它总是存储32位0.其他寄存器用于临时存储程序中使用的值。您使用的说明如下：

• la路，标签(“加载地址”) (rd =标签的地址；将由“标签”指定的单词的地址存储在目的地寄存器rd中)
• lw路，标签("load word") 或 lw路，偏移(Rs) (将标签指定的数据或地址rs+offset上的数据加载到目标寄存器rd)
• 添加 rd，rs，rt (rd = rs + rt；添加源寄存器rs和rt，并存储结果为目的地寄存器rd)
• addi rd，rs，imm (“立即添加”) (rd = rs + imm；添加源寄存器rs和立即(16位常量)值，并存储结果为目标寄存器rd)
• 潜艇路，rs，rt (“减法”) (rd = rs - rt；从源寄存器rs和存储中减去源寄存器rt，导致目标寄存器rd)
• beq rs，rt，label (“分支如果相等”) (如果rs中的值等于rt中的值，请跳到label)
• sll rd，rs，shamt (“移位逻辑左”) (rd = rs << 2；以rs为单位，左移两位，并将其存储在rd中)
• slt rd，rs，rt (“设置小于”) (rd = (rs < rt)？1: 0；如果rs中的值小于rt中的值，则将rd设置为32位1，否则设置为32位0)
• j标签(“跳转”) (跳到标签)

.text剖面

main:
la $s0, A
lw $s1, l
add $t0, $0, $0
addi $v0, $0, 1
sub $s1, $s1, $v0

for:
beq $t0, $s1, done
sll $t1, $t0, 2 #byte offset
add $t1, $t1, $s0
lw $t1, 0($t1) #$t1 = A[j]
addi $t2, $t0, 1
sll $t2, $t2, 2
add $t2, $t2, $s0
lw $t2, 0($t2) #$t2 = A[j + 1]
sub $t3, $t2, $t1 #$s3 = A[j+1] - A[j]?
slt $t4, $t3, $0
addi $t3, $0, 1
beq $t3, $t4 unsort #A isn’t sorted if A[j+1] - A[j] has a negative value
addi $t0, $t0, 1 #$t0 = $t0 + 1
j for

unsort:
add $v0, $0, $0 #set $v0 if array isn’t sorted

done:

此程序集代码等效于伪代码(如果您不习惯伪代码或并发循环，请在internet中查找)：

s0 <- address of first element in A
s1 <- l
t0 <- 0
v0 <- 1
s1 <- s1-1

while (t0 != s1) do
    t1 <- 4 * t0
    t1 <- t1 + s0
    t1 <- word at address t1
    t2 <- t0 + 1
    t2 <- 4 * t2
    t2 <- t2 + s0
    t2 <- word at address t2
    t3 <- t2 - t1
    if (t3 < 0) then t4 <- 1
    else t4 <- 0
    t3 <- 1
    if (t3 == t4) then
        v0 <- 0
        return
    else t0 <- t0 + 1

希望这个有帮助。我认为，如果您以前没有编写过代码，那么从程序集代码开始是相当雄心勃勃的。祝好运!