跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 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. 整数 II を引数に持ち、reg に II を格納する命令 IMM[I] を追加する。命令形式とインタプリタの変更を説明せよ。

题目描述​

考虑计算机的指令执行过程以及如下虚拟机。它具有寄存器 reg、程序计数器 program_counter、栈指针 stack_pointer 和一个含 55 个元素的栈；这些量的初值均为 00。虚拟机按下列伪代码取指并执行：

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. 分别用不超过 3030 个词说明指令执行周期中的 Fetch、Decode、Execute。

  2. 执行程序

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

    后，求 reg、program_counter、stack_pointer 以及 stack 的值。

  3. 给出一个指令数不超过 1313、执行结束时使 reg 等于 1717 的程序。

  4. 现增加带整数参数 II 的指令 IMM[I]，其作用是把 II 存入 reg。说明相应的指令编码格式以及解释器需要怎样修改。

考点​

  • 指令周期：准确区分取指、译码和执行三个阶段各自完成的工作。
  • 栈式虚拟机跟踪与编程：逐条更新寄存器、程序计数器、栈指针和栈内容，并在指令数限制内组合常量与加法得到 1717。
  • 指令编码扩展：为立即数设计操作码与操作数字段，并修改取指、程序计数和执行逻辑以读取参数。

Kai​

(1)​

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

(2)​

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

reg=6,program_counter=8,stack_pointer=0,stack={3,1,0,0,0}\boxed{\begin{aligned} \mathtt{reg}&=6,\\ \mathtt{program\_counter}&=8,\\ \mathtt{stack\_pointer}&=0,\\ \mathtt{stack}&=\{3,1,0,0,0\} \end{aligned}}

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

(3)​

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

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

最初の 1 をスタックの底に保存した後、1→2→4→8→161\to2\to4\to8\to16 と倍化し、最後に保存した 1 を加えるため、reg は 17 となる。

(4)​

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

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

reg = sign_extend(immediate_operand)

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

本页目录