跳到主要内容

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

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

計算機の命令実行と、次の仮想計算機を考える。この仮想計算機はレジスタ reg、プログラムカウンタ program_counter、スタックポインタ stack_pointer、5 要素のスタックを持つ。整数型はすべて 32 bit の符号なし整数であり、配列の添字は 0 から始まる。初期値はいずれも 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 を、それぞれ 50 文字以内で説明せよ。
  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 个元素的栈；整数型均为 32 位无符号整数，数组从下标 0 开始。这些量的初值均为 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. 分别用不超过 5050 个日文字符说明指令执行周期中的 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。说明相应的指令编码格式以及解释器需要怎样修改。

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)​

32 bit の命令語にオペコードを置き、IMM の場合だけ直後の 32 bit 語を即値 II とする。例えば IMM[17] を配列中の二語 {IMM, 17} で表す。この形式なら元の符号なし整数型で表せる値をすべて格納できる。

Fetch 後のインタプリタに次を追加する。

} else if (instruction == IMM) {
    reg = program[program_counter];
    program_counter = program_counter + 1;
}

IMM の処理時点では program_counter は即値の語を指している。これを読み込み、さらに 1 増やすことで次の命令へ進む。

本页目录