C07: simulator

tags: sysprog2017

主講人: jserv / 課程討論區: 2017 年系統軟體課程

返回「進階電腦系統理論與實作」課程進度表

預期目標

• 搭配 現代處理器設計，實際練習系統軟體開發
• 思考函式呼叫和掌握遞迴程式開發技巧
• 擴充給定的指令集 (ISA) 模擬器

full-stack-hello

• full-stack-hello 是成功大學發展的小型指令集模擬器，附帶組譯器和編譯器等系統工具
• 編譯和測試

$ git clone https://github.com/sysprog21/full-stack-hello.git
$ cd full-stack-hello
$ make
$ make check

預期得到以下輸出:

42
tests/halt.s pass

Hello World
tests/hello.s pass

42
50
150
tests/test.s pass

$ make test
python tests/run_tests.py
..
---------------------------------------------------------
Ran 4 tests in 0.002s

OK

• 組譯器使用

$ ./as_exec -h
Usage: as_exec [-w] [-x] [-o <out_file>] <in_file>
       -w Assemble <in_file> and write to an ELF file, see -o below
       -o if -w is specifed, <out_file> is used to store the object code
       -x Load <in_file> and execute it

       <in_file> the file name to be used by commands above

• 用給定的 tests/hello.s 檔案做示範
  1. 組譯和執行
  ​​​​$ ./as_exec tests/hello.s
  

  2. 組譯並輸出 ELF 格式目的檔 tests/hello.o
  ​​​​$ ./as_exec -w tests/hello.s
  

  3. 組譯並輸出 ELF 到給定的路徑
  ​​​​$ ./as_exec -o tests/temp.o -w tests/hello.s
  

  4. 載入之前組譯得到的 ELF 檔案並執行
  ​​​​$ ./as_exec -x tests/hello.o
  

• 輸出的 ELF 檔案可用 objdump 工具分析和觀察:

$ objdump -x tests/hello.o

• 注意 vm.c 用到 GCC computed goto 的機制

#define OP(name) OP_##name

#define BEGIN_OPCODES                          \
    const static void *labels[] = {OP_LABELS}; \
    goto *labels[OPCODE.opcode]

#define DISPATCH                     \
    do {                             \
        ++env->r.pc;                 \
        goto *labels[OPCODE.opcode]; \
    } while (0)

#define GOTO(n)                      \
    do {                             \
        env->r.from = env->r.pc;     \
        env->r.to = n;               \
        env->r.pc = n;               \
        goto *labels[OPCODE.opcode]; \
    } while (0)

#define END_OPCODES

clang-format

• LLVM 專案旗下的 clang-format
• 安裝方式:

$ sudo apt-get install clang-format

• 延伸閱讀: 使用Clang-format來幫助你美化你的程式碼

作業要求

• 閱讀 現代處理器設計 教材和觀看裡頭所有錄影，記錄你的心得和疑惑
• 研究給定的 full-stack-hello，學習其中 ISA 和模擬器實作，並在 GitHub 上 fork full-stack-hello
  • 對照研讀 你所不知道的 C 語言：編譯器和最佳化原理篇 教材和觀看直播錄影，以得知編譯器運作原理
• 閱讀 你所不知道的C語言：遞迴呼叫篇 和觀看對應講座錄影，用 full-stack-hello 的指令實作 Fibonacci 數列
  • 需要包含 recursive 和 non-recursive 實作，分別置於檔案 tests/fib-recursive.s 和 tests/fib-iterative.s
  • 修改 vm.c (和對應的原始程式碼)，允許執行時期由使用者 (和 Makefile) 帶入參數，如 --input，這數值應該透過暫存器作為上述 Fibonacci 數列程式的 Fib(N)
  • 研究現有 full-stack-hello 的自動測試程式，整合上述兩種 Fibonacci 程式實作，並且比較效能 (需要包含 vm 內部的 cycle count)
• 除了 recursive 和 iterative 版本，應該一併考慮以下 Fibonacci 數列的實作方式，並善用 GNU plot 製圖和解讀
  • Tail recursion
  • Q-Matrix
  • Fast doubling
• 過程中可修改 full-stack-hello 模擬器的程式碼，加入追蹤 / 除錯用途的指令 (instruction)，也應該探討模擬器的運作機制並說明自己修改的方式
• 注意 Fib(46) 之後的數值會超過 2³² 可表達的範圍，需要設計有效的數值表示機制來處理 (如用兩個 32-bit 暫存器保存 2⁶⁴ 數值)
• 觀察 Add label support 的實作方式，試著在full-stack-hello 給定的組譯器中新增 label 的支援
• 相關的背景知識錄影共有 18 小時 (當然不可能看了就懂，請預留思考和提問討論的時間)，務必及早開始
• 將你的觀察、上述要求的解說，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「作業區」

截止日期

• Nov 9, 2017 (含) 之前
• 越早在 GitHub 上有動態、越早接受 code review，評分越高