БЫСТРЫЙ СПОРТ В MIPS

Question

Я написал алгоритм быстрой сортировки на сборке MIPS в соответствии с кодом C ++. В C ++ он работает очень хорошо, но в MIPS не работает. Я отладил это, и проблема в рекурсии. Это алгоритм:

QuickSort(Data[], l , r)
{
    // If the first index less or equal than the last index
    if l <= r:
    {
        // Create a Key/Pivot Element
        key = Data[r]

        // Create temp Variables to loop through array
        i = l;
        j = r;

        while i <= j:
        {
            while Data[i] < key AND i < r:
                i = i + 1
            while Data[j] > key AND j > 0:
                j = j - 1
            if i <= j:
            {
                swap Data[i], Data[j]
                i = i + 1 
                j = j + 1
            }
        }

        if l < j:
            QuickSort(Data, l, j);
        if r > i:
            QuickSort(Data, i, r);
    }
}

Это код MIPS. В некоторых случаях это работает. Пример: array = {6, 5, 4, 3, 2, 1}. Код MIPS:

#-function QuickSort(arr, left,right)
    #parameter
    #          $a0: array
    #          $a1: left
    #          $a2: right

QuickSort:
    subu $sp, $sp, 16
    sw   $a0, 0($sp)
    sw   $a1, 4($sp)
    sw   $a2, 8($sp)
    sw   $ra, 12($sp)

    la   $s0, 0($a0)
    move $s1, $a1
    move $s2, $a2

    bgt  $s1, $s2, done

    sll  $t3, $s2, 2
    add  $t3, $s0,$t3
    lw   $t2, 0($t3)

    move $t0, $s1
    move $t1, $s2

    WhileOuter:
        While_i:
            sll $t3, $t0, 2
            add $t3, $s0, $t3
            lw  $t4, 0($t3)

            bge $t4, $t2, EndWhile_i
            bge $t0, $s2, EndWhile_i
            addi $t0, $t0, 1    
            j While_i
        EndWhile_i:

        While_j:
            sll $t3, $t1, 2
            add $t3, $s0, $t3
            lw $t4, 0($t3)

            ble $t4, $t2, EndWhile_j
            blez $t1, EndWhile_j
            addi $t1, $t1, -1
            j While_j
        EndWhile_j:

        bgt $t0, $t1, EndWhileOuter

        #swap arr[i], arr[j]
        sll $t4, $t0, 2
        sll $t5, $t1, 2

        add $s3, $s0, $t4
        add $s4, $s0, $t5

        lw $t4, 0($s3)
        lw $t5, 0($s4)

        sw $t4, 0($s4)
        sw $t5, 0($s3)

        addi $t0, $t0, 1
        addi $t1, $t1, -1
        j WhileOuter
    EndWhileOuter:

    bge $s1, $t1, call2
    lw $a1, 4($sp)
    move $a2, $t1
    move $a0, $s0
    jal QuickSort

    call2:
    ble $s2, $t0, done
    move $a1, $t0
    lw $a2, 8($sp)
    move $a0, $s0
    jal QuickSort
    done:
    addu $sp, $sp, 16
    lw $a0, 0($sp)
    lw $a1, 4($sp)
    lw $a2, 8($sp)
    lw $ra, 12($sp) 

    jr $ra

Может ли кто-нибудь найти ошибку (и) в этом коде? Спасибо за любую помощь.

Answer 1

1. Вы используете сохраненные регистры $s0, $s1, $s2, но без соблюдения требования о сохранении значений в этих регистрах для вызывающего.

Таким образом , вызывающим абонентам QuickSort не гарантируется, что их регистры $s будут сохранены.

Вы не показываете остальную часть кода, например main.

Однако мы знаем, что QuickSort вызывает сам себя, и после первого рекурсивного вызова самого себя он полагается на регистры $s0 & $s2, что должно быть в порядке, но мы знаем, что они не сохраняются должным образом QuickSort.

Вам необходимо более внимательно проанализировать использование вашего регистра и требования. Следующий код запускается после первого (рекурсивного) вызова QuickSort. Он справедливо ожидает сохранения $s0 и $s2, но также ожидает сохранения $ t0 - временного регистра, означающего, что он не сохраняется при вызове, поэтому это ошибка.

        jal QuickSort       # this call wipes out $t0
     call2:
        ble $s2, $t0, done  # what's supposed to be in $t0 here?
        move $a1, $t0
        lw $a2, 8($sp)
        move $a0, $s0

Вам не требуется сохранять регистр $s1, и вместо этого вам нужно было выбрать временный регистр для этого использования. Я бы просто использовал переменную в ее исходном регистре $a1.

Вы сохраняете регистр $a0 в памяти, но не используете значение этой ячейки памяти.

Он либо отсутствует, либо вы изменили расположение внешнего, а условие выхода l oop. Его больше нет в верхней части l oop. Теперь он читается так:

  while true:
        {
            while Data[i] < key AND i < r:
                i = i + 1
            while Data[j] > key AND j > 0:
                j = j - 1
            if i > j break;

Код Python выполняет

    if i <= j:
    {
        swap Data[i], Data[j]
        i = i + 1 
        j = j + 1
    }

, тогда как после обмена код сборки делает i ++, но j--.

Вы используете $s3 и $s4, но для простого временного использования - вместо этого используйте регистры $t.