owned this note
owned this note
Published
Linked with GitHub
# 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
![image alt](https://upload.wikimedia.org/wikipedia/commons/6/60/Intel_Core2_arch.svg)
- 參考資料:[什麼是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 中可以執行多少指令
- 圖一 :
![](https://i.imgur.com/DtkwMdL.png)
- 圖二 :
![](https://i.imgur.com/XKnjaMW.png)
>比較兩個部分,`圖一`一個 `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 的支援
---