Try   HackMD

2017 q3 Homework3(simulator)

contributed by <williamchangTW>

tags: Class_Project, Jserv

閱讀現代處理器設計，心得及疑惑

分成三個部分所得到的心得和疑惑，分別為原理關鍵和特徵， Cache 原理和多核心議題，虛擬機器設計與實作

原理關鍵和特徵 心得及疑惑：

根據影片：現代處裡器架構及特徵(上) 所作的整理

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

    • 也稱為 Computer organization 這是較大眾所知的名詞

  • Intel core 2 microarchiteture

    image alt

  • 參考資料：什麼是AES-GCM加密算法

    • GCM(Galois/Counter Mode) 指的是該對稱加密採用 Counter 模式，並帶有 GMAC 消息認證碼

  • 參考資料：Advanced Encryption Standard(AES)

    • 是一種為了電子資料所做編碼規格，由美國 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 中的 SHA-256，目前還沒有有效的攻擊方式
演算法和變體 輸出雜湊值長度(bits) 中繼雜湊值長度(bits) 資料區塊長度(bits) 最大輸入訊息長度(bits) 迴圈次數 使用到的運算子 碰撞攻擊(bits) 效能範例
SHA-2(SHA-256) 256 256(8 x 32) 512 264-1 64 And, Xor, Rot, Add(mod 232), Or, Shr 128 139
  • Cloud computing 重視的是 stable 而不是 unstable ，以致於不是用 Quick sort 而是 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 : 是用來處裡繪圖，循序的執行是非常差的，是用來分擔 CPU 工作減少對其的依賴，GPU是平行處裡較強，參考資料：NVIDIA-GPU與CPU效能比較

  • 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 :

根據影片：現代處理器及特徵(下)所作的整理
  • 展頻 (Spread Spectrum,SS) : 將傳輸訊號的頻譜打散到較其原始頻寬更寬的一種通訊技術，常用於無線通訊
    • 傳輸端會用獨特的 Code ，與傳輸資料無關，接收端必須也使用這個 Code 才能獲得資料
  • VLIW(Very Long Instruction Word) 超長指令字元:
    • 是一個設計利用 Instruction-Level parallelism(ILP) 的 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:

    • mispredeict penalty
    • two-level adaptive predictor

  • Out-of-order execution:

    • 循序的指令，但在這個技術下可以指令可以不循序的執行指令，有些指令執行較快可能超越前面的指令，不用等那些執行較慢的指令，先來的可能後到
      • 好處：可能效率增加，跟 in-order 可能差到 4 倍之多
      • 壞處：因為不是循序的執行，所以有可能出現執行錯誤的結果，且電路變得非常的複雜

  • Register renaming:

  • 硬體執行單元：Thread:SMT,Hyper-thread&Multi-core

  • SIMD:視覺影響，電子書

  • Late Binding :

    • 又稱為 Dynamic Binding，是一種 Computer programming mechanism，指 Compiler 不再編譯程式的時候就把功能和物件連在一起，而是把物件的位址創立一個 virtual table(v-table)
    • 在物件導向程式設計特性之一 Dynamic Binding ，富有彈性、擴充性及城市延伸

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

大部分的資料都由前幾項作業得知，所以這裡只記錄少數幾項重要的資料
  • 資料由 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 又稱為 Portable code or p-code:
    • 指已經經過編譯，但與特定機器碼無關，需要等 Interpreter 轉譯後才能成為機器碼，其存在目的是為實現特定軟體運行和軟體環境，與硬體無關連，如影片中的 Brainfuck 的實作，透過 Compiler or Virtual machine(a p-code machine i.e,interpreter) 去實作
  • Ethereum Smart Contract:
    • 最重要的是 Smart contract 一詞的解釋：
      • 跟平常已知的合約，差別在主動及被動，智能合約是自動的，只要設定條件達成，即可自動生成一個智能合約，現實上有的例子是，自動販賣機、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實作費氏數列

  • [ ]需要包含 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)

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

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