跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2017年8月実施 午前 問9

标签：

Author​

GPT-5

Description​

計算機の命令実行と、次の仮想計算機を考える。この仮想計算機はレジスタ reg、プログラムカウンタ program_counter、スタックポインタ stack_pointer、5 要素のスタックを持つ。初期値はいずれも 0 であり、命令は次のように実行される。

while not stop:
    instruction = program[program_counter]
    program_counter = program_counter + 1

    POP:   stack_pointer = stack_pointer - 1
           reg = stack[stack_pointer]
    PUSH:  stack[stack_pointer] = reg
           stack_pointer = stack_pointer + 1
    IMM0:  reg = 0
    IMM1:  reg = 1
    ADD:   stack_pointer = stack_pointer - 1
           reg = reg + stack[stack_pointer]
    STOP:  stop = true
  1. 命令実行サイクルにおける Fetch、Decode、Execute を、それぞれ 30 語以内で説明せよ。
  2. プログラム {IMM1, PUSH, PUSH, ADD, ADD, PUSH, ADD, STOP} の実行終了時における reg、program_counter、stack_pointer、stack の値を求めよ。
  3. 実行終了時に reg の値を 17 とする、命令数 13 以下のプログラムを示せ。
  4. 整数 を引数に持ち、reg に を格納する命令 IMM[I] を追加する。命令形式とインタプリタの変更を説明せよ。

Kai​

(1)​

  • Fetch: プログラムカウンタが指すメモリから次の命令を読み出し、プログラムカウンタを次の位置へ進める。
  • Decode: 命令のオペコードとオペランドを解釈し、実行する操作と必要なデータを決定する。
  • Execute: デコード結果に従って演算、メモリアクセス、分岐などを行い、計算機の状態を更新する。

(2)​

命令を順に追跡すると、実行終了時の状態は

となる。PUSH で書き込まれた値は、ADD でスタックポインタが減っても消去されないことに注意する。

(3)​

例えば、次の 12 命令で実現できる。

{IMM1, PUSH, PUSH, ADD, PUSH, ADD,
 PUSH, ADD, PUSH, ADD, ADD, STOP}

最初の 1 をスタックの底に保存した後、 と倍化し、最後に保存した 1 を加えるため、reg は 17 となる。

(4)​

例えば、1 命令語を固定長 32 bit とし、上位部分をオペコード、残りを符号付き即値オペランド とする。Fetch では従来どおり命令語を読み出し、Decode ではビットマスクとシフトによってオペコードと即値を分離し、必要なら即値を符号拡張する。

インタプリタには IMM の場合分けを追加し、デコードされたオペランドを使って

reg = sign_extend(immediate_operand)

を実行させる。必要な整数範囲が 1 命令語のオペランド欄に収まらない場合は、後続語を即値として使う複数語形式にしてもよい。その場合、Fetch 時に後続語の分だけ program_counter をさらに進める。

目录