Эта программа MIPS должна занять так много времени? (программа, которая приближается к пи) - PullRequest
Новая
       75

Эта программа MIPS должна занять так много времени? (программа, которая приближается к пи)

2 голосов
/ 11 апреля 2020

Часть 2 этого

Целью этого было написать программу MIPS, которая использовала этот алгоритм. Я сделал. Это работает, только требуется около 30 минут, чтобы завершить с дельта = 1E-2. Программа C (скомпилированная с g cc) занимает около полутора минут с этой дельтой. Я пытался с delta = 1E-3 в программе C, но мне пришлось прервать его через 2 часа.

Я просто хочу знать: это должно произойти? Результат выглядит достаточно точным для меня (3.13909200 с дельтой = 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 минут.

1 Ответ

4 голосов
/ 11 апреля 2020

Я предполагаю, что для этого используется тот же алгоритм, что и для версии C. Это приближает значение для Pi, проверяя трехмерную сетку точек в кубе, чтобы увидеть, находятся ли они внутри сферы. Это вычисление O(N^3), где N - это количество единиц (дельт) в каждом измерении сетки.

Итак ... да ... ожидается, что ваш код MIPS примет долгое время для вычисления точного приближения Pi.

  • Если l_cubo равно 4, а дельта 1/100, то вы должны выполнить 400 x 400 x 400 = 64 000 000 итераций. 30 минут кажутся излишними.

  • Если l_cubo равно 4, а дельта 1/1000, то вы должны выполнить 4000 x 4000 x 4000 = 64 000 000 000 итераций.

Но если вы хотите проверить его работоспособность, ваш код MIP должен быть таким же быстрым, если не быстрее, чем реализация C при запуске на том же самом аппаратное обеспечение с такими же параметрами. (Примечание: если вы запускаете код MIPS на эмуляторе MIPS, вы не сможете этого сделать.)

...