# 2017 q3 Homework3(simulator)
contributed by <`williamchangTW`>
###### tags: `Class_Project`, `Jserv`
---
[TOC]

## 閱讀`現代處理器設計`，心得及疑惑
- [x] 閱讀 [現代處理器設計](http://hackfoldr.org/cpu) 教材和觀看裡頭所有錄影，記錄你的心得和疑惑
##### 分成三個部分所得到的心得和疑惑，分別為`原理關鍵和特徵`， `Cache 原理和多核心議題`，`虛擬機器設計與實作`
---
#### `原理關鍵和特徵` 心得及疑惑：
---
##### 根據影片：[現代處裡器架構及特徵(上)](https://www.youtube.com/watch?v=9hNl8fWnHLI) 所作的整理
>Ascii Text Value : The cake is a lie.
>Binary Value : 01010100 01101000 01100101 00100000 01100011 01100001 01101011 01100101 00100000 01101001 01110011 00100000 01100001 00100000 01101100 01101001 01100101 00101110

- 參考資料：[Micro architecture](https://en.wikipedia.org/wiki/Microarchitecture)
- 也稱為 `Computer organization` 這是較大眾所知的名詞
- Intel core 2 microarchiteture

- 參考資料：[什麼是AES-GCM加密算法](http://blog.csdn.net/t0mato_/article/details/53160772)
- GCM(Galois/Counter Mode) 指的是該對稱加密採用 Counter 模式，並帶有 GMAC 消息認證碼
- 參考資料：[Advanced Encryption Standard(AES)](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard)
- 是一種為了電子資料所做編碼規格，由美國 National Institute of Standards and Technology (NIST) 在 2001 所創立
- NIST 選擇在 Rijndeal family 其中三個成員，每個成員皆擁有 128 bits 的 block size 但擁有不一樣的三個密鑰長度，分別為 128, 192 和 256 bits
- `Performance` :
- AES 選擇 process 的條件標準是是高速但對 RAM 需求少是
- 當在選擇演算法時，AES 可以執行非常好在很多的硬體上，從 8-bit smart cards 到高效能的電腦上都可以

- 在 Pentium Pro, AES 每個 byte 編碼需要 18 clock cycles ，等價於在 200 MHz 的產量在 11 MB/s 若在 1.7 GHz Pentium M 產量在 60 MB/s

- 在 Intel Core i3/i5/i7 和 AMD APU 還有 FX CPUs 支持 AES-NI 指令集的延伸， throughput 可達到 700 MB/s
>Rijndael 是一個密碼家族擁有不一樣的 key 和 block sizes.

- Bitcoin 使用加密方式：
- [SHA family](https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F) 中的 SHA-256，目前還沒有有效的攻擊方式

|演算法和變體|輸出雜湊值長度(bits)|中繼雜湊值長度(bits)|資料區塊長度(bits)|最大輸入訊息長度(bits)|迴圈次數|使用到的運算子|碰撞攻擊(bits)|效能範例|
|:---:|:---:|:---:|:---:|:----:|:----:|:---:|:---:|:---:|
|SHA-2(SHA-256)|256|256(8 x 32)|512|2^64^-1|64|And, Xor, Rot, Add(mod 2^32^), Or, Shr|128|139|
- [Cloud computing](https://en.wikipedia.org/wiki/Cloud_computing) 重視的是 stable 而不是 unstable ，以致於不是用 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 而是 [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)
- Unstable sorting 相關資料可以參考這，簡易而論，就是在 sort 過後，相同值的變數，原本該在前面的跑到後面，後面的跑到前面，比如：1255^*^3 sort-> 1235^*^5
- Stable sorting 與上述相反
- 若超頻效能上升原本的1.13倍，但功耗上升原本的1.73倍，但若降頻功耗降低一半，效能只有降低 13%，所以才有`多核說`
- 再來，有相對大的內核搭配相對小的內核的使用已發生在現在的裝置上
- Cache 是 sequential 的執行，為什麼要這樣做
- 原因：可以先把指令載到 level 較低的 cache 中，有可能後面的指令會在後面做到，也就是降低主記憶體的存取 (Cache prefetching)
- 若能提升對 Cache 的使用率，效能就能有顯著的提升
- `Performance` 的定義，在一個 clock cycle 中可以執行多少指令
- 圖一 :
- 圖二 :
>比較兩個部分，`圖一`一個 `clock cycle` 才做三個指令，而`圖二`一個 `clock cycle` 做七個指令，相較而知後者效率較好，而且 CPU idle time 也較少，在每個 stage 中都可以有事情做(4 - stages)

- 但 pipeline 不是一直很好的，也有不好的地方，如: data hazard , stall ,etc

- instruction pointer(IP) = programing counter(PC)，依據不同的CPU，指令不一定只+1，也有+2

- for example 5 stage :
- Instruction Fetch
- Decode
- Excute
- Prediction
- Branch 有可能對 pipeline 傷害，進而萌生用猜的去猜下一個指令做什麼去減少對 pipeline 的傷害
- pipeline hazard:
- data hazard:
- 讀寫記憶體 atomic，所以可能後面的指令要等待前面指令的結果，可是前面只衖還未算出結果，所以會造成延遲
- control hazard:
- Branch or jump 指令會發生，可能還未算出目的位置在那，而不確定要執行哪項指令，所以造成延遲
- structure hazard:
- 因為硬體上的資源是有限的，可能因為這樣的限制而造成延遲，不會造成錯誤，比如記憶體不同階層上的存取時間差異差很多，需要去等待
- 為何不用 GPU 而繼續用 CPU?
- 本質上的用途不一樣所以無法做取代
- CPU : 是通用的，可以做很多事情，在循序的操作很好
- [GPU](https://zh.wikipedia.org/zh-tw/%E5%9C%96%E5%BD%A2%E8%99%95%E7%90%86%E5%99%A8) : 是用來處裡繪圖，循序的執行是非常差的，是用來分擔 CPU 工作減少對其的依賴，GPU是平行處裡較強，參考資料：[NVIDIA-GPU與CPU效能比較](http://www.nvidia.com.tw/object/what-is-gpu-computing-tw.html)
- Superpipeline (追求深度) :
- 由影片中提及：Core i^*^2/i^*^3 Sandy/Ivy Bridge, Corei^*^4/i^*^5 Haswell/Broadwell 與 Pentium 4E Prescott 的 pipeline depth 分別為 14/19 和 31 但在效能上前者卻比較好，證明 pipeline depth 越深對效能的實質提昇無太大的影響，反而浪費電
- 但深度不夠對效能有時直上的影響，比如：Cortex A9 及 Cortex-A15/A57 ，深度分別為 8 及 15 但後者效能較好

- Superscaler (追求廣度) :
- 整數的運算速度最快，浮點數的運算速度最慢，所以想法是在其中插入一些指令運作，例如 ： Branch
- Dispatch
- Superscaler + Superpipeline = Superpipeline-superscaler :

---
##### 根據影片：[現代處理器及特徵(下)](https://www.youtube.com/watch?v=UHOvgmZNjXI)所作的整理
- [展頻 (Spread Spectrum,SS)](https://zh.wikipedia.org/wiki/%E6%89%A9%E9%A2%91) : 將傳輸訊號的頻譜打散到較其原始頻寬更寬的一種通訊技術，常用於無線通訊
- 傳輸端會用獨特的 Code ，與傳輸資料無關，接收端必須也使用這個 Code 才能獲得資料
- [VLIW(Very Long Instruction Word) 超長指令字元](https://en.wikipedia.org/wiki/Very_long_instruction_word):
- 是一個設計利用 [Instruction-Level parallelism(ILP)](https://en.wikipedia.org/wiki/Instruction-level_parallelism) 的 CPU 結構，會有這樣的設計是因為，按照順序執行指令處理器不能充分的利用處理器的資源，可能導致較低的性能
- 想法是盡量在一個指令中，安插許多 OP code ，以提昇效能，同一個時間內可以執行許多算，如影片中的：`{MUL R1, R2, R3;ADD R3, R4, R5}{SUB R8, R9, R10}`適合用在影像及聲音訊號處理，因為陣列先乘後加
- 不用擔心任何 hazard 問題，因為他在一個指令內就做了許多運算
- 但是若遇到 Cache misses 存取的時間會相對長很多，因為相較之下讀取一個指令時間較長
- 壞處：Compiler 的設計更加複雜，因為不需要再用硬體調度指令，而是把工作交給 Compiler 執行，硬體設計相對簡單
>整理一下，在這裡有提到技術使得硬體設計變得複雜的技術有： Out-of-order execution, Superscaler, Superpipeline
- 指令相依
~~~
先考慮下列算式
`a = b * c`
`d = a + 1`
~~~
很顯然的 a 這個變數造成了相依，而後面的指令需要等待前面的指令，稱之 Instruction latency

- condition excution :
- 條件符合才做才往下做
- 到 Execute stage 才決定要不要跳，但此時已經 Fetch 的指令必定要流失掉
- 現在的指令約有 7% 是 Branch

- [Branch predictor](https://en.wikipedia.org/wiki/Branch_predictor):
- mispredeict penalty
- two-level adaptive predictor
- [Out-of-order execution](https://en.wikipedia.org/wiki/Out-of-order_execution):
- 循序的指令，但在這個技術下可以指令可以不循序的執行指令，有些指令執行較快可能超越前面的指令，不用等那些執行較慢的指令，先來的可能後到
- 好處：可能效率增加，跟 in-order 可能差到 4 倍之多
- 壞處：因為不是循序的執行，所以有可能出現執行錯誤的結果，且電路變得非常的複雜
- [Register renaming](https://en.wikipedia.org/wiki/Register_renaming):

- 硬體執行單元：Thread:SMT,Hyper-thread&Multi-core
- SIMD:視覺影響，電子書
- [Late Binding](https://en.wikipedia.org/wiki/Late_binding) :
- 又稱為 Dynamic Binding，是一種 `Computer programming mechanism`，指 Compiler 不再編譯程式的時候就把功能和物件連在一起，而是把物件的位址創立一個 virtual table(v-table)
- 在物件導向程式設計特性之一 Dynamic Binding ，富有彈性、擴充性及城市延伸

---
#### `Cache 原理與多核心議題` 心得及疑惑：

###### 大部分的資料都由前幾項作業得知，所以這裡只記錄少數幾項重要的資料
- 資料由 [memory hierarchy](https://en.wikipedia.org/wiki/Memory_hierarchy) 中的下層網上層傳輸的資料單位為 block，當資料剛子在上層被找到，稱之為 hit，hit rate + Miss rate = 1 ，現今的處理器都可以達到 hit rate 95% 以上
- 電腦效能取決於：
- Hit time :
- 判斷是否 hit + High-level data transfer to CPU total time
- Miss penalty：
- 把 Low-level 記憶體資料搬到 High-Level 的時間 + High-level data transfer to CPU total time
- cache 需要兩的欄位分別為：
- tag
- 紀錄該資料原本在記憶體內的位置，不需要紀錄完整的記憶體位置，只需紀錄前幾個 bits
- valid bit(1 or 0)
- 用來記錄欄位內的資料是否為有效資料
---
#### `虛擬機器設計與實作`心得及疑惑
- [Bytecode](https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjQv_7y2Z_XAhVMGpQKHR8LDWUQFggmMAA&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBytecode&usg=AOvVaw15C5sg2NTGzD61iXLiP2wB) 又稱為 Portable code or p-code:
- 指已經經過編譯，但與特定機器碼無關，需要等 Interpreter 轉譯後才能成為機器碼，其存在目的是為實現特定軟體運行和軟體環境，與硬體無關連，如影片中的 [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck) 的實作，透過 Compiler or Virtual machine(a p-code machine i.e,interpreter) 去實作
- [Ethereum Smart Contract](https://medium.com/taipei-ethereum-meetup/ethereum-smart-contract-%E5%85%A5%E9%96%80%E9%9B%9C%E8%AB%87-59a6398f03c):
- 最重要的是 [Smart contract](https://www.slideshare.net/NicholasLin15/intro-to-smart-contract-on-blockchain) 一詞的解釋：
- 跟平常已知的合約，差別在主動及被動，智能合約是自動的，只要設定條件達成，即可自動生成一個智能合約，現實上有的例子是，自動販賣機、U-bike 及線上投注都是
- 在 Blockchain 上，最主要是提供一個自動化的合約和**沒有任何信任基礎的對象進行交易**
- 應用在 Blockchain 上的合約，合約的執行結果都會儲存在 Bolckchain 上，比如：發行貨幣，並且提供轉帳以及買賣功能就屬一種合約
- 建立合約流程：
- 1.寫合約(用 Code 寫)
- 2.編譯合約，轉成 Bytecode
- 3.Broardcast 並放入等待區等待被使用
- 4.執行合約
- 能使用的 Code language:
- Serpent(python-like)
- Solidity(Javascript-like)
---
## 研究`full-stack-hello`學習其中的 ISA 和模擬器實作
---
- [ ] 研究給定的 [full-stack-hello](https://github.com/sysprog21/full-stack-hello)，學習其中 ISA 和模擬器實作，並在 GitHub 上 fork [full-stack-hello](https://github.com/sysprog21/full-stack-hello)，對照研讀 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me) 教材和觀看直播錄影，以得知編譯器運作原理
---

## 用`full-stack-hello`實作費氏數列

---
- [ ]需要包含 recursive 和 non-recursive 實作，分別置於檔案 `tests/fib-recursive.s` 和 `tests/fib-iterative.s`
- [ ]修改 `vm.c` (和對應的原始程式碼)，允許執行時期由使用者 (和 `Makefile`) 帶入參數，如 `--input`，這數值應該透過暫存器作為上述 Fibonacci 數列程式的 `Fib(N)`
- [ ]研究現有 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 的自動測試程式，整合上述兩種 Fibonacci 程式實作，並且比較效能 (需要包含 vm 內部的 cycle count)
---

## 考屢下列 `Fabonacci` 數列的實作方式，善用 GNU plot 製圖和解讀`Tail recursion`,`Q-Matrix`,`Fast doubling`

---
- [ ]Tail recursion
- [ ]Q-Matrix
- [ ]Fast doubling
>- 過程中可修改 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 模擬器的程式碼，加入追蹤 / 除錯用途的指令 (instruction)，也應該探討模擬器的運作機制並說明自己修改的方式
>- 注意 Fib(63) 之後的數值會超過 2^32^ 可表達的範圍，需要設計有效的數值表示機制來處理 (如用兩個 32-bit 暫存器保存 2^64^ 數值)
>- 觀察 [Add label support](https://github.com/jserv/full-stack-hello/pull/30) 的實作方式，試著在[full-stack-hello](https://github.com/sysprog21/full-stack-hello) 給定的組譯器中新增 label 的支援
---