Changes between Initial Version and Version 1 of Ex03課題2016

Timestamp:

May 9, 2016 2:45:24 PM (10 years ago)

Author:

nakasato

Comment:

--

Ex03課題2016

@@ +1 @@
+トップ：http://galaxy.u-aizu.ac.jp/note/wiki/CAEX2016
+
+= swap手続き =
+第4版教科書上巻p.137の「2.13 Cプログラムの包括的な例題解説」にあるswap手続き(関数)を
+本演習で利用可能な命令で実装したプログラムを示します。
+教科書の該当分をよく読んで、C言語とMIPS命令との対応を理解すること。
+
+== C言語 ==
+{{{
+void swap(int v[], int k)
+{
+  int temp;
+  temp = v[k];
+  v[k] = v[k+1];
+  v[k+1] = temp;
+}
+}}}
+
+== アセンブリプログラム ==
+{{{
+swap:    addi $t1, $a1, 0 
+         add $t1, $t1, $t1 
+         add $t1, $t1, $t1 
+         add $t1, $a0, $t1 
+         lw $t0, 0($t1) 
+         lw $t2, 4($t1) 
+         sw $t2, 0($t1) 
+         sw $t0, 4($t1) 
+         jr $ra
+}}}
+
+引数の受け渡しは$a0と$a1のレジスタを使います。
+ここでは、$a0でswapされる整列させる配列の先頭アドレスを、$a1でswapする箇所の配列の添え字(k)を受け渡します。
+
+シフト命令は利用できないので、add命令の組み合わせで「k*4」を実現しています。
+
+== 練習課題１ ==
+以下のテンプレートと組み合わせて、swap関数の動作を確認すること。
+
+{{{
+       .data 
+k:     .word 3 
+A:     .word 32 
+       .word 422 
+       .word 83 
+       .word 2 
+       .word 92 
+       .word 32 
+       .word 97 
+       .word 22 
+       .word 4 
+       .word 86 
+
+       .text 
+main:  la $a0, A 
+       lw $a1, k 
+       jal swap 
+exit:  j exit 
+}}}
+
+= ソート手続き =
+教科書に従い、swap関数を使って単純なソートプログラムの動作を確認します。
+
+{{{
+       .data 
+N:     .word 3 
+A:     .word 32 
+       .word 422 
+       .word 83 
+       .word 2 
+       .word 92 
+       .word 32 
+       .word 97 
+       .word 22 
+       .word 4 
+       .word 86 
+
+       .text 
+main:  la $a0, A 
+       lw $a1, N 
+       jal sort 
+exit:  j exit 
+
+sort:  addi $sp, $sp, -20 
+       sw $ra, 16($sp) 
+       sw $s3, 12($sp) 
+       sw $s2, 8($sp) 
+       sw $s1, 4($sp) 
+       sw $s0, 0($sp) 
+
+       or $s2, $0, $a0     #move $s2, $a0 
+       or $s3, $0, $a1     #move $s3, $a1 
+
+       or $s0,$0,$0        # $s0(= i) = 0 
+
+for1tst: slt $t0,$s0,$s3     # $t0 = (i < N) 1:0 
+         beq $t0,$0,exit1    # if $t0 == 0 then exit1 
+         addi $s1, $s0, -1   # j = i - 1 
+
+for2tst: slti $t0, $s1, 0    # $t0 = (j < 0) 1:0 
+         beq $t0, $0, cont   #bne $t0, $0, exit2 変更点2 
+         j exit2 
+
+cont:    or $t1, $s1, $0     # $t1 = j * 4 
+         add $t1, $t1, $t1   #変更点3 
+         add $t1, $t1, $t1 
+
+         add $t2, $s2, $t1   # $t2 = &(A[j]) 
+         lw $t3, 0($t2)      # $t3 = A[j] 
+         lw $t4, 4($t2)      # $t4 = A[j+1] 
+
+         slt $t0, $t4, $t3   # $t0 = (A[j]< A[j+1]) 1:0 
+         beq $t0, $0, exit2  # if $t0 == 0 then exit2 
+         or $a0, $s2, $0     # $a0 = $s2(&A) 
+         or $a1, $s1, $0     # $a1 = $s1(j) 
+         jal swap 
+
+         addi $s1, $s1, -1   # j = j - 1 
+         j for2tst 
+
+exit2:   addi $s0, $s0, 1    # i = i + 1 
+         j for1tst 
+
+exit1:   lw $s0, 0($sp) 
+         lw $s1, 4($sp) 
+         lw $s2, 8($sp) 
+         lw $s3, 12($sp) 
+         lw $ra, 16($sp) 
+         addi $sp, $sp, 20 
+         jr $ra 
+}}}
+
+sort関数の、引数の受け渡しは$a0と$a1のレジスタを使います。
+ここでは、$a0に整列させる配列の先頭アドレスを、$a1にNをそれぞれセットしています。
+
+教科書のプログラムとの変更点は以下のところです。
+ * move命令をor命令に置換
+ * bne命令をbeqとj命令の組み合わせに置換
+ * sll命令をadd命令の組み合わせに置換
+
+$spは明示的に初期化されていませんが、xspimによって自動的に設定されます。
+
+== 練習課題２ ==
+swap関数と組み合わせて、N = 3の時に正しく動作することを確認すること。
+また、変数Nが10の場合に正しい結果が得られることを確認すること。
+
+= 課題6：手続きを用いた行列の積アルゴリズム = 
+第2回演習で作成した、行列の積を求めるプログラムのうち、2つの整数の積を求める部分を手続き呼び出しに置き換えなさい。
+ 1. 手続きのラベルは「MUL」にする。
+ 1. 引数は$a0と$a1を介して引き渡す。
+ 1. この手続きでは結果は$v0に保持する。
+ 1. メインプログラムでは、計算結果$v0を使って行列積を計算する。
+
+ファイル名は「ex03_p6.s」としてください。
+
+= 再帰手続き呼び出し = 
+第4版教科書上巻p.105にある階乗を計算する再帰的手続きをもとに、スタックレジスタ($sp)の使いかたを理解します。
+メインプログラムは、ラベルmainからはじまり、$a0にNをセットして手続きfactを呼び出します。
+Nは要素数を指定し、結果はFNに格納します。
+
+この手続きは自分自身を呼び出すので、$a0と$raレジスタをスタックに保持する必要があります。
+
+{{{
+        .data 
+N:      .word 5 
+FN:     .word 0 
+
+.text 
+main:   lw $a0, N         # $a0(= N) = 10 
+        jal fact          # $v0 = fact($a0) 
+        sw $v0 FN         # FN = $v0 
+        exit: j exit 
+
+fact:   addi $sp, $sp, -8 
+        sw $ra, 4($sp) 
+        sw $a0, 0($sp) 
+
+        slti $t0, $a0,1   # $t1 = ($a0 < 1) 1:0 
+        beq $t0, $0, L1   # if $t1 = 0 then L1 
+
+        addi $v0,$0,1     # $v0 = 1 
+        addi $sp,$sp,8    # $sp = $sp + 8 
+        jr $ra            # return FN = 1 
+
+L1:     addi $a0,$a0,-1 
+        jal fact          # fact($a0 - 1) 
+        lw $a0, 0($sp) 
+        lw $ra, 4($sp) 
+        addi $sp,$sp,8 
+        mul $v0,$a0,$v0 
+        jr $ra
+}}}
+
+== 練習課題３ ==
+N = 5、8の時に、正しく階乗が計算できていることの動作を確認しなさい。特に、スタックポインタ($sp)について理解すること。
+
+= 課題7：手続きを用いたプログラムの作成 = 
+下記の機能を実現する手続きを作成し、実行を確認してください。
+作成するプログラムでは、main関数から、作成した関数(手続き)を呼び出し、動作を確認する部分も含めること。
+
+== 16bit整数a, b, cを引数とし d = a*b + cを計算する関数: int mac(int a, int b, int c) ==
+以下のパターンについて動作確認をすること。
+{{{
+(a, b, c) = (11, 21, 0)
+(a, b, c) = (11, 21, 6)
+(a, b, c) = (3333, 4444, 5555)
+}}}
+
+ファイル名は「ex03_p7a.s」としてください。
+
+== 16bit整数aをn bit左シフトする関数:  int left_shift(int a, int n) ==
+動作確認は”0x1”を1, 4, 7, 15 bitシフトした結果を確認すること。シフト命令を使ってはいけない。
+
+ファイル名は「ex03_p7b.s」としてください。