MIPS 어셈블리의 이진 검색이 작동하지 않습니다.

Question

데이터 세그먼트에서 숫자를 검색하여 저장 위치를 ​​인쇄하고 싶습니다.

### Binary search ############################################################ 
.text 
binsearch: 
############################################################################## 
# $a0 - Number n 
# $a1 - Lower bound lo 
# $a2 - Upper bound hi 
# $v0 - Position where n is found, -1 if not found 
############################################################################## 

addi $sp, $sp, -4 
sw $ra, 0($sp) 
bge $a1, $a2, binsearch_not_found 

sub $t0, $a2, $a1 
srl $t0, $t0, 2 
add $t1, $a1, $t0 
sll $t2, $t1, 2 
lw $t3, list($t2) 
beq $t3, $a0, binsearch_found 
blt $t3, $a0, binsearch_upper_half 

binsearch_lower_half: 
##################### 
subi $a2, $t1, 1 
jal binsearch 
j binsearch_return 

binsearch_upper_half: 
##################### 
addi $a1, $t1, 1 
jal binsearch 
j binsearch_return 

binsearch_found: 
################ 
move $v0, $t2 
j binsearch_return 

binsearch_not_found: 
#################### 
li $v0, -1 

binsearch_return: 
################# 
lw $ra, 0($sp) 
addi $sp, $sp, 4 
jr $ra 

### Main ##################################################################### 
.globl main 
main: 
############################################################################## 

li $v0, 4 
la $a0, input 
syscall 

li $v0, 5 
syscall 
move $a0, $v0 

move $a1, $zero 
lw $a2, length 
subi $a2, $a2, 1 
jal binsearch 

li $t0, -1 
beq $v0, $t0, not_found 

found: 
###### 
mul $t0, $v0, 4 
lw $a0, list($t0) 
li $v0, 1 
syscall 

li $v0, 4 
la $a0, success 
syscall 
j repeat 

not_found: 
########## 
li $v0, 4 
la $a0, failure 
syscall 

repeat: 
####### 
li $v0, 4 
la $a0, continue 
syscall 

# Read characters 
li $v0, 12 
syscall 
move $t0, $v0 

li $v0, 4 
la $a0, newline 
syscall 

# End when 'y' 
bne $t0, 'y', main 

li $v0, 10 
syscall 

### Data ##################################################################### 
.data 
############################################################################## 

input: .asciiz "Which number? " 
continue: .asciiz "Abort? (y/n) " 
failure: .asciiz "Not found\n" 
success: .asciiz " found\n" 
newline: .asciiz "\n" 

length: .word 100 
list:  .word 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 
      .word 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 
      .word 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 
      .word 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 
      .word 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 
      .word 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 
      .word 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 
      .word 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 
      .word 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 
      .word 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000 

Answer 1

오류가

을 발견 : 여기

코드입니다 ... 그것은 1과 10000을 제외한 모든 번호를 작동하지만, 또한 잘못 "위치"를 출력한다 왜 몰라

1. 행 13 : 때 $a1 == $a2, 수 $a0가 발견 되었기 때문에 bge $a1, $a2, binsearch_not_found
   가 bgt을이 있어야합니다. $a2을 엄격한 상한으로 해석하려면 보다 binsearch 전에 main을 호출하는 것이 이상합니다.

2. 행 16 : srl $t0, $t0, 2
1 대신 2이 있어야합니다. 당신은하지 4.

3. 라인 (37)에 의해, 2 $t0를 나눌 : move $v0, $t2는
   $t1 대신 $t2이 있어야합니다. binsearch은 바이트로 오프셋되지 않고 배열에 인덱스를 반환해야합니다. 오프셋을 반환하려면 줄 123 (mul $t0, $v0, 4)의 main에서 binsearch의 반환 값을 4로 곱하면 안됩니다.

다른 관찰과 생각

• 현재 조사 구간의 중간의 인덱스를 계산하는 또 다른 방법이있다. mid = (hi - lo)/2 + lo 대신 mid = (hi + lo)/2을 사용할 수 있습니다. 이렇게하면 명령이 저장되고 오버 플로우가 문제가되지 않습니다.

• binsearch보다 많은 레지스터를 사용합니다. 인덱스의 경우 $t0 만 사용하고 list의 오프셋의 경우 $t1을 사용한 다음 해당 오프셋의 값을 사용했습니다. 성능에 어떤 영향을 미치는지는 모르겠다. (이 점을 바꾸는 것은 오류가 발생하기 쉽기 때문에 레지스터의 값을 어디에 사용하는지 생각해보십시오. 동시에 모든 참조를 변경해야합니다.)

• 발견 한 번호 만 인쇄합니다. 색인을 인쇄하는 것도 도움이 될 수 있습니다.

MARS

나는 MIPS의 MARS 시뮬레이터를 사용하여 코드를 디버깅하는 방법 (미주리 주립 대학, 게리 슈트의 사이트에 nice description, 미네소타 덜 루스의 대학에서). binsearch 레이블 앞에 j main을 추가해야합니다. 그렇지 않으면 main 대신 binsearch이 실행되어 곧바로 충돌이 발생했습니다.

MARS에서 delayed branching이 꺼져 있습니다. 그렇지 않으면 점프 및 분기 후에 nop 명령어를 추가해야 실행되지 않아야하는 항목이 실행되지 않습니다.나는 MIPS가 지연 슬롯을 가지고 있다고 가르쳤지 만, 당신은 그것을 고려하지 않는 것 같다. 왜냐하면 아키텍처가 지연 슬롯을 가지고 있거나 가지지 않는다면 아마 더 잘 알고 있기 때문입니다. 또한 어셈블러 프로그래밍이 아니며 지연 슬롯을 사용하여 프로그래밍의 복잡성을 알지 못합니다.