Changes between Initial Version and Version 1 of Ex01_CA_2022

Timestamp:

Apr 5, 2022 4:05:28 PM (4 years ago)

Author:

nakasato

Comment:

--

Ex01_CA_2022

@@ +1 @@
+トップ：http://galaxy.u-aizu.ac.jp/note/wiki/CAEX2021
+
+= 演習の目的 =
+ * 命令レベルシミュレータに慣れること
+ * MIPSのアセンブリ命令の使い方を理解すること
+ * 今後の課題で使用するプログラムを作成すること
+ 
+今回の演習ではMIPSプロセッサのシミュレータをを用いてプログラミングを行います。
+ここで作成したプログラムはあとで設計するMIPSプロセッサで実行させるテストプログラムになります。
+
+= SPIMのドキュメント =
+http://galaxy.u-aizu.ac.jp/comparch2021/spim.pdf
+
+= 演習を始める前に = 
+以下のページの留意点をよく読んでから演習を始めてください：[wiki:"Ex01 演習の留意点2021"]
+
+= 単純な代入文 = 
+定数の代入文はor immediate命令とstore word命令の組み合わせで実現できます。
+
+例えばC言語のコード
+{{{
+A = 15;
+}}}
+
+は、擬似的なプログラム
+{{{
+$8 = 15
+A = $8
+}}}
+に置き換えることができます。
+
+各行をMIPSの命令に置き換えると：
+{{{
+ori $8, $0, 15
+sw $8, A
+}}}
+となります。
+
+== 考察 == 
+ * この2つの命令で、なぜ「A=15」が正しく実現できているか考えなさい。
+ * なぜ$0が使われるのか？
+ * この方法で扱える代入文の右辺の定数の範囲を考えなさい。
+ * 符号付き32bitの範囲の定数の代入文を実装する方法を考えなさい。
+
+= メモリの初期化 =
+代入文「A = 15」は、Aへの代入としてプログラム開始から最初に実行され、一度しか実行されない場合
+{{{
+    .data
+A:  .word 15 
+}}}
+とすることで、アセンブリ言語の疑似命令による、メモリ領域の初期化によっても実現できます。
+
+「A:」の部分はラベルと呼び、この場合にはこのメモリ領域のアドレスを表す定数としてプログラムの中で利用できます。
+
+しかし、この初期化を含んだプログラムをサブルーチンに用いる場合、
+1回目の実行でAの値が変更されてしまうと、2回目以降の呼び出しにおいてAは15以外の値を持つ可能性があります。
+この様な場合、上記のようにori命令とsw命令の組み合わせで代入文を実現します。
+
+= 例題１：変数の代入 = 
+変数A, B, Cがある時に「C = A + B」の演算を実現するプログラムについて考えます。
+
+変数A, B, Cは、メモリ上に以下のように配置されているとします。
+それぞれは32ビットワードの変数であり、1変数につき4バイトのアドレス空間を占めます。 
+ 
+|| 変数 || アドレス(16進数) ||  初期値(10進数) || 演算結果(10進数) ||
+||     A|| 0x0|| 19|| 19||
+||     B|| 0x4|| 75|| 75||
+||     C|| 0x8||  0|| 94||
+
+MIPSプロセッサでの演算はレジスタ間でのみ行うことができます。
+したがって、メモリの中のデータを演算するためには一度レジスタの中にデータをロードし、
+演算を行った後に演算結果をメモリにストアしなければなりません。
+そのようなプログラムを下に示します。 
+
+{{{
+         .data 
+A:       .word 19 
+B:       .word 75 
+C:       .word 0 
+         .text 
+main:    lw   $8, A 
+         lw   $9, B 
+         add  $10, $8, $9 
+         sw   $10, C 
+exit: j  exit
+}}}
+
+このプログラムを「sum1.s」としてファイルに保存し、xspimでシミュレーションを行ってください。
+
+アセンブリプログラムで「.data」から始まる部分を、データセグメントと呼びます。
+各行は「32ビット数値で内容は「19」の変数を定義しそのアドレスを「A」で参照できるようにする」という意味です。
+
+「.text」で定義される部分をテキストセグメントと呼び、これがプログラムの本体になります。
+各命令の概要を以下のテーブルで説明します。
+
+このプログラムでは、レジスタ$8, $9, $10を利用しています。
+各行が実行される毎にその内容は変化する場合があります。
+
+|| 命令         || 動作 || $8の内容 || $9の内容 || $10の内容 ||
+||lw  $8, A     ||アドレスAのデータをレジスタ$8にロード|| 19 || 不定 || 不定 ||
+||lw  $9, B     ||アドレスBのデータをレジスタ$9にロード|| 19 || 75 || 不定 ||
+||add  $10, $8, $9  ||レジスタ$8と$9を加算して、結果を$10に格納|| 19 || 75 || 94 ||
+||sw   $10, C   ||レジスタ$10の内容をアドレスCにストア|| 19 || 75 || 94 ||
+||j  exit       ||ラベルexitにジャンプ || 19 || 75 || 94 ||
+ 
+補足：「lw $8, A」 は 「lw $8, A($0)」 の省略形であり、レジスタ$8には「A + $0」の値がロードされます。
+
+xspimを立ち上げると、以下のような画面となります。
+
+[[Image(http://galaxy.u-aizu.ac.jp/note/raw-attachment/wiki/Ex01%20MIPS%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E5%9F%BA%E7%A4%8E2017/xpsim.png)]]
+
+画面の上段には各レジスタの内容が示されています。
+
+中段には各ボタンがあり、ソースファイルの読み込みにはloadボタン、プログラムの実行にはstepボタンをクリックします。
+
+下段にはテキストセグメント(Text Segments)と、データセグメント(Data Segments)が示され、
+一番下の部分には実行時のメッセージが表示されます。
+
+プログラムの実行には二つの方法があり、stepボタンによる実行では、テキストセグメントの命令が一命令ずつ実行されます。
+一方runボタンを使うと、プログラムを一度に実行できます。
+
+「sum1.s」をstep実行し、一命令ずつレジスタやデータセグメントの値が変化するのを確かめること。
+
+= 複雑な式の評価 =
+代入文の右辺が複雑な場合は式を変換して考えます。
+{{{
+A= B * C - 5
+}}}
+
+という演算をする場合、右辺は一時的な変数Tempを用いて、
+
+{{{
+Temp = B * C
+A = Temp - 5
+}}}
+と変換できます。
+
+より複雑な式も、このように一時的な変数を導入して分解して、右辺の演算が実装する命令で実行できるようにします。
+if文の条件判定の式が複雑な場合も同様に分解します。
+
+アセンブリプログラムでは、一時的な変数の役割はレジスタが担います。
+しかし、すべての一時的なレジスタを使いきるような場合、一時変数を保持するのにメモリを利用する必要があります。
+メモリを利用する場合、swおよびlw命令が必要となり、
+実行命令数が増えるので、可能な限りレジスタを効率的に使用するようにします。
+
+= 課題１ =
+3つの変数と定数を含んだ式「S = (A ＋ B ー C) | 3」の計算を行うプログラムを作成し、xspimでシミュレーションを行ってください。
+"|" はビットごとの論理和演算です。
+
+各変数の初期値は以下のように設定してください。
+
+||アドレス    ||データ(10進数) ||
+||A ||  19 ||
+||B ||  75 ||
+||C ||  10 ||
+||S ||  結果の格納 ||
+
+作成ファイル名は「ex01_p1.s」としてください。
+
+= 例題２ レジスタによるメモリの参照 =
+この例題ではメモリを間接的に参照するためにレジスタ相対アドレスを用いる方法を示します。
+以下のような配列変数の和を計算することを考えます。
+
+{{{
+S=A[0]+A[1]+A[2]+A[3]
+}}}
+
+配列のように連続するデータのアドレスが規則的に並んでいる場合、
+レジスタを使ってアドレスを加算しながらメモリにアクセスするとプログラムが簡単に記述できます。
+たとえば次のようにデータが並んでいるとします。　 
+ 
+||アドレス    ||データ(10進数) ||
+||A      || 19 ||
+||A+4 || 75 ||
+||A+8 || 10 ||
+||A+12 || 15 ||
+||S ||  結果の格納場所 ||
+
+このような場合、最初のアドレスAがわかれば、次のアドレスはAに４を足すことによって求めることができます。
+したがって、4つの要素の和を求める場合、次のようなプログラムを記述すればよいことになります。 
+  
+{{{
+        .data 
+A:      .word 19 
+        .word 75 
+        .word 10 
+        .word 15 
+S:      .word 0
+        .text 
+main:   or   $8, $0, $0   # 和($8レジスタ)を 0 に初期化 
+        la   $9, A        # la命令によりAのアドレスを $9 に入れる。実際は ori 命令に置き換わる。
+
+        lw   $10, 0($9) 
+        add  $8, $8, $10 
+
+        lw   $10, 4($9) 
+        add  $8, $8, $10
+
+        lw   $10, 8($9) 
+        add  $8, $8, $10
+
+        lw   $10, 12($9) 
+        add  $8, $8, $10
+
+        sw   $8, S 
+exit:   j exit
+}}} 
+
+また、上のプログラムは下のように書き直すこともできます。
+この形は各データに対する処理が全く同じ命令列になるため、後で述べるループを用いて和を求める場合に適しています。 
+
+{{{
+        .data 
+A:      .word 19 
+        .word 75 
+        .word 10 
+        .word 15 
+S:      .word 0
+        .text 
+main:   or   $8, $0, $0 
+        la   $9, A     
+
+        lw   $10, 0($9) 
+        add  $8, $8, $10  
+        addi $9, $9, 4    # アドレスを次へすすめる
+
+        lw   $10, 0($9) 
+        add  $8, $8, $10 
+        addi $9, $9, 4
+
+        lw   $10, 0($9) 
+        add  $8, $8, $10 
+        addi $9, $9, 4
+
+        lw   $10, 0($9) 
+        add  $8, $8, $10
+
+        sw   $8, S 
+exit:   j exit
+}}} 
+
+上の2番目のプログラムをエディタにコピー＆ペーストして、xspimで動作を確認してください。
+レジスタを使って配列アドレスををインクリメントしながらメモリにアクセスする方法を理解してください。 
+
+= 条件分岐 =
+本演習で利用可能な命令の中で、条件分岐に利用できるのはbranch on equal命令(比較結果が等しい場合に指定したアドレスにジャンプする)だけです。
+例えば、C言語での以下の条件分岐は
+
+{{{
+if(i == j) goto label
+
+...
+
+label:
+}}}
+
+以下のbeq命令と同等です。
+
+{{{
+beq $i,$j,label
+}}}
+
+beqなどのjump系の命令では、「ラベル名:」で指定したラベルを使って、jump先を指定できます。
+
+== 大小比較 ==
+大小比較をするには、set on less than命令、あるいはset less than imm命令と、beq命令を組み合わせて実現します。
+
+=== C言語 ===
+{{{
+if(a > b) {サブプログラム1｝else {サブプログラム2}
+}}}
+
+=== MIPSアセンブリ ===
+{{{
+lw $8, a
+lw $9, b
+slt $8,$9,$8
+beq $8,$0,label1
+
+サブプログラム１に対応する部分
+
+goto label2
+label1:
+
+サブプログラム２に対応する部分
+
+label2:
+}}}
+
+「<=」による条件分岐をどのように実現するか、また、
+「if (条件１ ｜｜ 条件２)」や「if (条件１ ＆＆ 条件２)」をどのように実現するかは各自検討してください。
+
+== while文 ==
+=== C言語 ===
+{{{
+while（条件）{ サブプログラム }
+}}}
+
+=== 疑似的なアセンブリプログラム ===
+{{{
+label1:
+$a ← if (条件) 1 else 0
+beq $a,$0,label2
+
+サブプログラムに対応する部分
+
+goto label1
+label2:
+}}}
+
+なお、条件が等式の場合は$aを用いず、直接beq命令で等式判定をします。
+
+== for文 ==
+{{{
+for( i = init_value; i < terminate_value ;更新式){サブプログラム}
+}}}
+
+のようなfor文は、while文を使って
+
+{{{
+i = init_value;
+while(i < terminate_value){
+サブプログラム;
+更新式;
+}
+}}}
+
+と置き換えることができるので、while文のアセンブリプログラムを応用することで変換可能です。
+
+このとき、iの値をレジスタに保持しておくと、iへのswやlw命令を省略でき、
+高速化が行えますが、繰り返しの中で自由に使えるレジスタが減ってしまいます。
+多重ループの場合は、内部の繰り返しに優先してfor文の制御変数(今の場合i)をレジスタに割り付けるといいでしょう。
+この場合繰り返しの最後に、レジスタの値をメモリに書き戻さないと、正しい最適化とはなりません.
+
+= 例題３ ループによる演算 =
+この例題では、1からnまでを単純に加算するプログラムを扱います。
+
+== Ｃ言語 ==
+{{{
+main() 
+{ 
+  int i = 0; 
+  int n = 15; 
+  int s = 0;
+  while( i != n ) { 
+     i++; 
+     s += i; 
+  } 
+}
+}}}
+
+総和演算のような処理は処理はwhile文を用いることによって記述できます。
+
+=== MIPSアセンブリプログラム ===
+アセンブリプログラムでは、分岐命令と比較命令を用いてループを実現します。
+メモリの初期状態を以下のように仮定します。 
+ 
+|| アドレス || データ ||
+|| n || 15 ||
+|| s ||         結果の格納 ||
+
+このコードをアセンブリプログラムに変換します。
+
+ループ変数 i を$8、n の値が入っているレジスタを$9とすると、ループの部分は次のように書けます。 
+{{{
+      or  $8, $0, $0    　      # i = 0 
+loop: beq  $8, $9, loopend      # i == n なら loopend へ飛ぶ 
+      addi $8, $8, 1            # i++ 
+　 
+   　    ・・・・ループの中身・・・・・ 
+　 
+      j loop 
+loopend:
+}}}
+
+例題のソースファイル全体は次のようになります。 
+{{{ 
+         .data 
+n:       .word 15 
+s:       .word 0
+         .text 
+main:    or   $8, $0, $0       # i = 0 
+         lw   $9, n            # nの値をロード 
+         or   $10, $0, $0      # s = 0
+
+loop:    beq  $8, $9, loopend  # i == n なら loopend へ 
+         addi $8, $8, 1        # i++ 
+         add  $10, $10, $8     # s += i 
+         j    loop
+
+loopend: sw   $10, s           # sの値をストア
+
+exit:    j    exit
+}}}
+
+= 課題２ 配列の総和計算 =
+メモリ上に並んだN要素からなる配列の総和を求めるプログラムを作成し、SPIMシミュレータで動作確認を行ってください。
+プログラムの先頭部分(配列データ)には下のコードを使用してください。 
+ {{{
+       .data 
+N:     .word 10    # The length of Array 
+A:     .word 8     # A[0] = 8 
+       .word 4     # A[1] = 4 
+       .word 7 
+       .word 12 
+       .word 13 
+       .word 19 
+       .word 23 
+       .word 43 
+       .word 56    # A[8] = 56 
+       .word 32    # A[9] = 32 
+S:     .word 0
+       .text 
+main: 
+}}}
+
+作成ファイル名は「ex01_p2.s」としてください。
+
+= 課題３ 配列のコピー =
+メモリ上に並んだＮ要素からなる配列Aの内容を別の配列Bにコピーするプログラムを作成し、シミュレータで動作確認を行ってください。
+プログラムの先頭部分には、下のコードを使用して下さい。 
+{{{ 
+      .data 
+N:    .word 10    # The length of Array 
+A:    .word 8     # A[0] = 8 
+      .word 4     # A[1] = 4 
+      .word 7 
+      .word 12 
+      .word 13 
+      .word 19 
+      .word 23 
+      .word 43 
+      .word 56    # A[8] = 56 
+      .word 32    # A[9] = 32 
+B:    .space 40   # 配列B の格納先を確保する。大きさは40バイト(10ワード分)
+      .text 
+main: 
+}}}
+
+作成ファイル名は「ex01_p3.s」としてください。
+
+= 課題４ バブルソート =
+バブルソートのアルゴリズムを使って、配列Aに格納されたN個の整数を昇順にソートするプログラムをアセンブラで作成し、シミュレータで動作確認を行ってください。 Nの値および配列Aの初期値は、課題１ー３と同じものを使って下さい。 参考までに、C言語プログラムの一部を下に示します。
+
+{{{
+    for( i = 0; i < N-1; i++ ) {
+        for( j = N-2; j >= i; j-- ) {
+            if( A[j] > A[j+1] ) {
+               tmp = A[j];
+               A[j] = A[j+1];
+               A[j+1] = tmp;
+            }
+        }
+    }
+}}}
+
+= Ex01のレポート = 
+課題１〜４について、プログラムの説明を書き、アセンブラソースファイルを添付してレポートを提出してください。例題についてはレポートでは特に触れなくて結構です。
+
+ * プログラムの細かな説明は、ソースファイルにコメントの形で埋め込んでも構いません。
+ * 課題１、２については、プログラムの実行結果（計算結果）をレポートに書いてください。
+ * 課題３、４では、xspimに表示される実行後のメモリの値をウィンドウ画像キャプチャで取得し、レポートに含めてください。
+
+