E07: bits

tags: sysprog2018

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

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

預期目標

• 深度學習 CS:APP 第 2 章和對應的補充教材
• 跨越理論與實務的鴻溝

在 Ubuntu Linux x86 64-bit 安裝 32-bit 開發套件

$ sudo apt update
$ sudo apt install libc6-dev:i386 gcc:i386

詳細閱讀 CMU CS:APP Data Lab 要求

• Data Lab: Manipulating Bits
  • 忽略 2 Logistics, datalab-handout.tar, dlc, driver.pl, 和 8 The "Beat the Prof" Contest 相關內容
  • 專注於修改 bits.c 即可
• 取得成功大學修改過的版本 datalab
  ​​​​$ git clone https://github.com/sysprog21/datalab
  ​​​​$ cd datalab
  ​​​​$ make check
  

• 參考輸出: (一開始什麼事都沒做，當然零分)
  ​​​​ERROR: Test twosComp2SignMag(-2147483647[0x80000001]) failed...
  ​​​​...Gives 42[0x2a]. Should be -1[0xffffffff]
  ​​​​ERROR: Test upperBits(0[0x0]) failed...
  ​​​​...Gives 42[0x2a]. Should be 0[0x0]
  ​​​​Total points: 0/228
  

作業要求

• 自 GitHub 上 fork datalab，依據 Data Lab: Manipulating Bits，補完欠缺的程式碼，並且通過自動測試
  • 確保儘可能少的指令，可用 $ gcc -S bits.c 輸出組合語言並觀察 bits.s 的程式碼裡頭的 x86 (IA32) 指令
  • 避免用分支 (branch)，設計時間複雜度為
    $O(1)$ 的實作
• 選出其中 7 個位元操作的函式，詳細解釋其原理，需要比照 clz 應用 和 bit-reverse 的分析方式，舉出真實世界中的應用案例 (最好在 GitHub 找出程式碼)，解說應搭配有效的測試程式碼
• 探討讓 datalab 得以 64-bit friendly 的提案，並舉出實際程式碼修改

繳交方式

• 編輯 Homework 5 作業區共筆，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

截止日期

• Oct 31, 2018 (含) 之前進行，不該截止日前一天才動手
• 越早在 GitHub 上有動態、越早接受 code review，評分越高

參考資訊

• 深入理解計算機系統（CS:APP) - Data Lab 詳解
• CSAPP：datalab