Bagian 2 ini

Tujuannya adalah untuk membuat program MIPS yang menggunakan algoritma tersebut. Aku melakukannya. Berhasil, hanya membutuhkan waktu sekitar 30 menit untuk menyelesaikan delta = 1E-2. Program C (dikompilasi dengan gcc) membutuhkan waktu sekitar 1 setengah menit dengan delta itu. Saya sudah mencoba dengan delta = 1E-3 pada program C tetapi harus membatalkannya setelah lebih dari 2 jam.

Saya hanya ingin tahu: apakah ini seharusnya terjadi? Hasilnya terlihat cukup akurat bagi saya (3.13909200 dengan delta = 1E-2). Apakah saya melakukan sesuatu yang salah?

Saya tahu algoritma ini mungkin bukan yang paling efisien, begitu pula MIPS, atau MARS (yang saya gunakan untuk MIPS).

Kode 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

Saya hanya ingin tahu bagaimana profesor saya akan memperbaiki program yang membutuhkan waktu 30 menit untuk dieksekusi.

2
Hypercube 11 April 2020, 08:26

1 menjawab

Jawaban Terbaik

Saya berasumsi bahwa ini menggunakan algoritma yang sama dengan versi C. Itu mendekati nilai untuk Pi dengan menguji kisi titik 3D dalam kubus untuk melihat apakah mereka berada di dalam bola. Itu adalah perhitungan O(N^3) di mana N adalah jumlah unit (delta) di setiap dimensi grid.

Jadi ... ya ... kode MIPS Anda diperkirakan membutuhkan waktu lama untuk menghitung perkiraan Pi yang akurat.

  • Jika l_cubo adalah 4, dan delta adalah 1/100, maka Anda harus melakukan 400 x 400 x 400 = 64.000.000 iterasi. 30 menit tampaknya berlebihan untuk itu.

  • Jika l_cubo adalah 4, dan delta adalah 1/1000, maka Anda harus melakukan 4000 x 4000 x 4000 = 64.000.000.000 iterasi.

Tetapi jika Anda ingin memeriksanya, kode MIP Anda harus secepat, jika tidak lebih cepat dari, implementasi C ketika dijalankan pada perangkat keras yang sama dengan parameter yang sama. (Catatan: jika Anda menjalankan kode MIPS pada emulator MIPS, Anda tidak akan dapat melakukannya.)

4
Stephen C 11 April 2020, 05:47