Changes between Version 4 and Version 5 of Ex03課題2015


Ignore:
Timestamp:
Apr 23, 2015 10:49:21 AM (11 years ago)
Author:
nakasato
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • Ex03課題2015

    v4 v5  
    11トップ：http://galaxy.u-aizu.ac.jp/note/wiki/CAEX2015 
    22 
    3 = 手続き呼び出し：ソート = 
    4 mainプログラムから手続きを呼び出すプログラムの例を示します。 
    5 これは、第4版教科書上巻p.137の「2.13 Cプログラムの包括的な例題解説」にある整列アルゴリズムをもとに、 
    6 本演習で利用可能な命令で構成したソートをするプログラムです。 
    7 変数Nは要素数を表し、配列Aの先頭から整列される要素が格納されます。 
     3= swap手続き = 
     4第4版教科書上巻p.137の「2.13 Cプログラムの包括的な例題解説」にあるswap手続き(関数)を 
     5本演習で利用可能な命令で実装したプログラムを示します。 
     6教科書の該当分をよく読んで、C言語とMIPS命令との対応を理解すること。 
     7 
     8== C言語 == 
     9{{{ 
     10void swap(int v[], int k) 
     11{ 
     12  int temp; 
     13  temp = v[k]; 
     14  v[k] = v[k+1]; 
     15  v[k+1] = temp; 
     16} 
     17}}} 
     18 
     19== アセンブリプログラム == 
     20{{{ 
     21swap:    addi $t1, $a1, 0  
     22         add $t1, $t1, $t1  
     23         add $t1, $t1, $t1  
     24         add $t1, $a0, $t1  
     25         lw $t0, 0($t1)  
     26         lw $t2, 4($t1)  
     27         sw $t2, 0($t1)  
     28         sw $t0, 4($t1)  
     29         jr $ra 
     30}}} 
    831 
    932引数の受け渡しは$a0と$a1のレジスタを使います。 
    10 ここでは、$a0に整列させる配列の先頭アドレスを、$a1にNをそれぞれセットしてから、ラベルsortから始まる整列アルゴリズムを手続きとして呼び出します。 
    11  
    12 {{{ 
    13         .data  
     33ここでは、$a0でswapされる整列させる配列の先頭アドレスを、$a1でswapする箇所の配列の添え字(k)を受け渡します。 
     34 
     35シフト命令は利用できないので、add命令の組み合わせで「k*4」を実現しています。 
     36 
     37== 練習課題 == 
     38以下のテンプレートと組み合わせて、swap関数の動作を確認すること。 
     39 
     40{{{ 
     41       .data  
     42k:     .word 3  
     43A:     .word 32  
     44       .word 422  
     45       .word 83  
     46       .word 2  
     47       .word 92  
     48       .word 32  
     49       .word 97  
     50       .word 22  
     51       .word 4  
     52       .word 86  
     53 
     54       .text  
     55main:  la $a0, A  
     56       lw $a1, k  
     57       jal swap  
     58exit:  j exit  
     59}}} 
     60 
     61= ソート手続き = 
     62教科書に従い、swap関数を使って単純なソートプログラムの動作を確認します。 
     63 
     64{{{ 
     65       .data  
    1466N:     .word 3  
    1567A:     .word 32  
    16         .word 422  
    17         .word 83  
    18         .word 2  
    19         .word 92  
    20         .word 32  
    21         .word 97  
    22         .word 22  
    23         .word 4  
    24         .word 86  
    25  
    26         .text  
    27 main:  la $a0, A           # $a0 = &A  
    28           lw $a1, N           # $a1 = N  
    29           jal sort  
    30 exit:    j exit  
     68       .word 422  
     69       .word 83  
     70       .word 2  
     71       .word 92  
     72       .word 32  
     73       .word 97  
     74       .word 22  
     75       .word 4  
     76       .word 86  
     77 
     78       .text  
     79main:  la $a0, A  
     80       lw $a1, N  
     81       jal sort  
     82exit:  j exit  
    3183 
    3284sort:  addi $sp, $sp, -20  
    33          sw $ra, 16($sp)  
    34          sw $s3, 12($sp)  
    35          sw $s2, 8($sp)  
    36          sw $s1, 4($sp)  
    37          sw $s0, 0($sp)  
    38  
    39          or $s2, $0, $a0     #move $s2, $a0  
    40          or $s3, $0, $a1     #move $s3, $a1  
    41  
    42          or $s0,$0,$0         # $s0(= i) = 0  
    43  
    44 for1tst: slt $t0,$s0,$s3   # $t0 = (i < N) 1:0  
     85       sw $ra, 16($sp)  
     86       sw $s3, 12($sp)  
     87       sw $s2, 8($sp)  
     88       sw $s1, 4($sp)  
     89       sw $s0, 0($sp)  
     90 
     91       or $s2, $0, $a0     #move $s2, $a0  
     92       or $s3, $0, $a1     #move $s3, $a1  
     93 
     94       or $s0,$0,$0        # $s0(= i) = 0  
     95 
     96for1tst: slt $t0,$s0,$s3     # $t0 = (i < N) 1:0  
    4597         beq $t0,$0,exit1    # if $t0 == 0 then exit1  
    4698         addi $s1, $s0, -1   # j = i - 1  
    … …  
    50102         j exit2  
    51103 
    52 cont:    or $t1, $s1, $0   # $t1 = j * 4  
     104cont:    or $t1, $s1, $0     # $t1 = j * 4  
    53105         add $t1, $t1, $t1   #変更点3  
    54106         add $t1, $t1, $t1  
    55107 
    56108         add $t2, $s2, $t1   # $t2 = &(A[j])  
    57          lw $t3, 0($t2)         # $t3 = A[j]  
    58          lw $t4, 4($t2)         # $t4 = A[j+1]  
    59  
    60          slt $t0, $t4, $t3      # $t0 = (A[j]< A[j+1]) 1:0  
     109         lw $t3, 0($t2)      # $t3 = A[j]  
     110         lw $t4, 4($t2)      # $t4 = A[j+1]  
     111 
     112         slt $t0, $t4, $t3   # $t0 = (A[j]< A[j+1]) 1:0  
    61113         beq $t0, $0, exit2  # if $t0 == 0 then exit2  
    62114         or $a0, $s2, $0     # $a0 = $s2(&A)  
    … …  
    64116         jal swap  
    65117 
    66          addi $s1, $s1, -1 # j = j - 1  
     118         addi $s1, $s1, -1   # j = j - 1  
    67119         j for2tst  
    68120 
    69 exit2:   addi $s0, $s0, 1 # i = i + 1  
     121exit2:   addi $s0, $s0, 1    # i = i + 1  
    70122         j for1tst  
    71123 
    … …  
    77129         addi $sp, $sp, 20  
    78130         jr $ra  
    79  
    80 swap:    addi $t1, $a1, 0  
    81          add $t1, $t1, $t1    #変更点3  
    82          add $t1, $t1, $t1  
    83          add $t1, $a0, $t1  
    84          lw $t0, 0($t1)  
    85          lw $t2, 4($t1)  
    86          sw $t2, 0($t1)  
    87          sw $t0, 4($t1)  
    88          jr $31 
    89 }}} 
     131}}} 
     132 
     133sort関数の、引数の受け渡しは$a0と$a1のレジスタを使います。 
     134ここでは、$a0に整列させる配列の先頭アドレスを、$a1にNをそれぞれセットしています。 
    90135 
    91136教科書のプログラムとの変更点は以下のところです。 
    92137 * move命令をor命令に置換 
    93138 * bne命令をbeqとj命令の組み合わせに置換 
    94  * sll命令をadd命令に置換 
    95139 
    96140$spは明示的に初期化されていませんが、xspimによって自動的に設定されます。 
    97141 
    98 == 練習課題1 == 
    99 シミュレータで実行し、手続き(関数)呼び出しの実行経過を確認する。 
    100 JAL命令でPCが適切に変更されること、$31に戻り番地が格納されることも確認すること。 
    101  
    102142== 練習課題2 == 
    103 変数Nが10の場合に正しい結果が得られることを確認すること。 
     143swap関数と組み合わせて、N = 3の時に正しく動作することを確認すること。 
     144また、変数Nが10の場合に正しい結果が得られることを確認すること。 
    104145 
    105146= 課題6：手続きを用いた行列の積アルゴリズム =