トップ：http://galaxy.u-aizu.ac.jp/note/wiki/CAEX2022

乗算アルゴリズムの実装

第5版教科書上巻p.177の「3.3 乗算」をよく読んで、乗算をおこなうプログラムを作ってください。 乗数A、被乗数B、積Cは32ビットです。求める乗算結果は64ビットではなく、下位の32ビットだけで十分です。 つまり、乗数と被乗数は最大16ビットまでを仮定してください。 今後演習で設計するMIPSプロセッサは、シフト命令をサポートしていませんので、以下のような工夫が必要になります。

左シフト

1ビット左シフトは2倍することと同等なので加算命令によって実現できます。

シフト命令を使う場合：

sll $8,$9,1

加算命令の場合：

add $8,$9,$9

右シフト

1ビット右シフトを他の命令で単純に実現することは困難です。 そこで今回は乗算アルゴリズムとハードウエアの直列バージョン(教科書上巻p.178 - 179 図3.4)に あるアルゴリズムを、左シフトのみを使うように修正して乗算を実現します。

乗算で使われる右シフトは、ビットを下位から順に調べることだけが目的なので、 左シフトを使って同等の機能を実現することができます。

下のように、右シフトの結果と定数1とのandをとる代わりに、 初期値として1をレジスタに入れておき、これを左シフトしたものとand をとるようにします。

シフト命令を使う場合：

  srl $8,$8,1
  andi $9,$8,1

加算命令の場合：

  addi $10,$0,1     # $10に1を代入（前処理）
    :
  addu $10,$10,$10  # 左シフト。通常でslr命令だった部分に相当
  and $9,$8,$10     # 通常でandi命令だった部分に相当

この様にして各ビットが1か0かを調べられます。

シフト命令を使う方法（上）だと結果は 0…01（32ビット） か 00…0（32ビット）の2通りだけですが、 加算命令を使用した方法（下）だと、そのビットが0のときは 00…0 ですが、そのビットが1だった場合、 その結果もそれが何桁目かによって、結果を左にシフトしています。 ですから、結果が0であるか否かで条件分岐をすることになります。

初期化部分

        .data 
A:      .word 13 
B:      .word 37 
C:      .word 0

       ... 必要な変数の領域を追加する ....
        .text 
main:       ... プログラムを書く .... 


exit:   j exit

作成ファイル名は「ex02_p4.s」としてください。一時的に使う変数のレジスタは$8 - $15($t0 - $t7)としてください。

Ex02のレポート

乗算プログラムについて、プログラムの説明を書き、アセンブラソースファイルを添付してレポートを提出してください。 プログラムの細かな説明は、ソースファイルにコメントの形で埋め込んでも構いません。 xspimに表示される実行後のメモリの値をウィンドウ画像ダンプ等で取得し、乗算結果の部分を丸で囲むなどして強調した上でレポートに含めてください。