章節.1 量化設計與分析的基礎

1. 電腦的分類

  1. 個人行動裝置(Personal Mobile Device): 強調能量效率跟即時性 不像嵌入式電腦，PMD可以執行第三方開發的程式

  1. 桌面計算(Desktop Computing): 強調性價比

  2. 伺服器(Servers): 強調availability, scalability, throughput

  3. 電腦叢集(Clusters)/庫房規模計算機(Warehouse Scale Computers): 將大量的電腦連接起來做為一台大電腦 強調 Emphasis on availability 和性價比 子級:超級電腦(Supercomputers) 強調浮點數運算效能，且其內部以快速的網路連接

  4. 嵌入式電腦(Embedded Computers): 強調價格

2. 平行的分類與平行架構:

  1. 應用程式主要可以分成兩種平行:

    1. 數據層級平行(Data-Level Parallelism,DLP): 同時操作許多的數據

    2. 任務層級平行(Task-Level Parallelism,TLP): 程式可以平行執行任務

  2. 硬體可以有下列四種方式來開發這兩種類型的平行程式:

    1. 指令層級的平行(Instruction-Level Parallelism,ILP): 透過流水線的概念與動態執行技術(speculative execution)來開發DLP

    2. 向量架構和圖像運算單元(Vector architectures/Graphic Processor Units (GPUs)): 透過單條指令來處理收集的資料的概念來開發DLP

    3. 多線程層級平行(Thread-Level Parallelism): 透過一些硬體的支援，使不同的Thread可以做些資訊的交換，此方法可以用來開發DLP或TLP

    4. 請求層級平行(Request-Level Parallelism): 此分類是針對Warehouse Scale Computers，將請求平行發送

  3. Michael Flynn提出費林分類法(Flynn's Taxonomy)，依照指令與資料可分成四大類，此分類法現今能持續被使用

    1. Single instruction stream, single data stream(SISD): 即為傳統的單核處理器

    2. Single instruction stream, multiple data streams(SIMD): 使用者使用單一指令，可以使多個處理器處理各自記憶體中的資料 ex.
      • Vector architectures
      • Multimedia extensions
      • Graphics processor units

    3. Multiple instruction streams, single data stream(MISD): 沒有商業價值

    4. Multiple instruction streams, multiple data streams(MIMD): 各個電腦依據各自的指令來處理徹自記憶體中的資料
      • Tightly-coupled MIMD: SMP, NUMA, etc
      • Loosely-coupled MIMD: Cluster, Network of Workstations, etc

3. 技術趨勢:

技術不斷的進步，促使電腦領域不斷的發展，以下稍微列出個部份最近的發展（近10年的數字）：

  • Integrated circuit technology
    • Transistor density: 35%/year
    • Die size: 10-20%/year
    • Integration overall: 40-55%/year

  • DRAM capacity: 25-40%/year (slowing)

  • Flash capacity: 50-60%/year
    • 15-20X cheaper/bit than DRAM
  • Magnetic disk technology: 40%/year
    • 15-25X cheaper/bit then Flash
    • 300-500X cheaper/bit than DRAM

  1. 效能趨勢： 在效能中，我們關心的通常是頻寬(bandwidth) 而非延遲（latency），其差異如下： 頻寬：指給定特定時間其可以完成多少個任務，即為吞吐量（throughput）。 延遲：任務開始到結束所花的時間，即為反應時間（response time）。

  2. 尺寸微縮對電晶體與導線的影響： 單位面積上電晶體的數量依摩爾定律預測，每隔18-24個月會倍增，故每一次前進到下一代的技術，通常都是將電晶體某個方向的尺寸縮為原本的70％（因為$0.7\times0.7=0.49$），因為尺寸的微縮，會對電晶體的效能帶來增長，整體來說，電晶體的效能為線性的增長，但是導線並不會因為尺寸的微縮而使其延遲減少，相反的，因為導線變細，電阻增大，整體導線的延遲反而是增加的，同時也會因為電阻變大放出更多的熱，故這邊可以觀察到導線的延遲和功率(power)問題變得越來越重要，而其中，功率問題重於導線延遲問題。

4. 積體電路功率與能量的趨勢:

功耗在積體電路是非常重要的課題，主要有兩點值得研究：

  • 如何將功率適當的分配到需要功率的元件上面
  • 如何將多餘的廢熱從電路上移除
  1. 設計者問題: 設計者在設計系統時，在功率、能量、效能上，必須考量下述幾個問題:

    1. 最大功率為何? 使用者必須使電源供應器能夠負荷這樣的功率，否則可能會指系統的功能出錯。

    2. 持續功率為何? 持續功率也被稱為熱設計功率(thermal design power,TDP)，設計者通常依據TDP來設計電源供應器與散熱系統。

      • 通常峰值功率是TDP的1.5倍，而通常平均功率則比持續功率低

    3. 能量與能量效能為何? 為什麼是考慮所耗的能量而不是看所其功率呢，因為我們在比較的時候是採用同樣的工作負載，如果是功率大的機器，通常會比較快執行完畢，故我們所要觀察的應該是同樣的能量能做多少工作。

  2. 微處理器能量與功率的公式:

    $I:電流$, $C:電容$, $V:電壓$, $f:切換頻率$

    $Energy_{dynamic}\propto{\frac{1}{2}}\times{C}\times{V^2}$

    $Power_{dynamic}\propto{\frac{1}{2}}\times{C}\times{V^2}\times{f}$

    $Power_{static}\propto{I_{static}}\times{V}$

    ${f_{max}}\propto\frac{(V_{dd}-V_t)^2}{V_{dd}}$

    ${I_{static}}\propto\exp(\frac{-V_t}{35mV})$

    1. 在製程進步時，通常切換頻率增加功率的速度大於電容和電壓減少功率的速度，事實上現今的時脈速度已經很難再做提升(因為風扇散熱的能力有限)。

    2. 對效能越好的電腦，通常它的靜態功率所占的比率會更大，因為效能好的電腦通常會有比較大的SRAM 快取

    3. 現今分散功率、移除廢熱與避免產生過熱區域變成越來越困難的問題，針對不同的系統，設計者常用的技巧有:

      1. 關掉那些沒運作區塊的時脈(clock gating)，極端情形就是只留下一個小區塊維持運作，其他區塊則維持休眠，只有當該做事時，才透過活動區塊將其他休眠區塊喚醒。
      2. 動態電壓頻率調整(Dynamic Voltage-Frequency Scaling, DVFS)
      3. 超頻(Overclocking)
      4. 針對使用上的一般情形來設計軟硬體配備

5. 積體電路成本的趨勢:

  1. 影響因素
    1. 時間: 在積體電路中，良率是影響成本的重要因素，一個製程隨著時間的發展，技術會越趨成熟，良率會隨著時間演進而持續提高，這個良率變化的曲線，我們稱之為學習曲線(learning curve)。
    2. 數量: 當生產數量增加時，能使每單位的成本大幅下降
    3. 規格化: 當規格化後，許多廠商進入這個市場，會使成本大量下降(技術提升)，但是同時單位獲利也會大幅下降
  2. 積體電路的成本計算:

    1. 積體電路的成本公式:

      $Cost_{IC}=\ \frac{Cost_{die}\ +\ Cost_{test}\ +\ Cost_{packaging\ and\ final\ test}}{Yield_{final\ test}}$

      $Cost_{die}=\ \frac{Cost_{wafer}}{Die\ per\ wafer\times{Yield_{Die}}}$

      $Die\ per\ wafer=\frac{\pi\times{radius_{wafer}^2}}{Area_{Die}}\ - \frac{\pi\times{Diameter}}{\sqrt{2\times{Area_{Die}}}}$

      其中，前項是晶圓面積與晶片面積的比值，而後項則是用來去除圓周上無效的晶片(圓周長/晶片對角線)，然而前面幾個公式都沒有考慮到良率的問題，事實上，良率會導致某些晶片是無法使用的。

      以下為良率的經驗公式:

      $Yield_{Die}\ =\ Yield_{wafer}\times{\frac{1}{(1+Defect\ per\ unit\ area\times{Area_{die}})^N}}$

      其中，N取決於製程技術

    2. 討論

      1. DRAM或SRAM產業由於承受著巨大的價格壓力，通常設計人員都會在上面加入一些冗餘(redundancy)，這些冗餘的儲存單位可以在容許產品一定數量的缺陷。

      2. 由上述幾個公式可以知道，晶片的良率跟晶片面積的關係相當密切，良率的增長大約是跟晶片面積的平方成正比，故設計人員在設計晶片時，必須對面積斤斤計較，排除不必要的功能，減少不必要的I/O訊號。

      3. 少量生產情況下，光罩的成本是相當可觀的，故設計者有時會透過可程式邏輯或使用邏輯閘陣列來避開光罩的高成本。

      4. 一般公司，RD的成本是公司所得4~12%

6. 可信任度(dependability):

如何判斷一個系統運作是否正常，是個難題，隨著互聯網的普及，問題變得更為明確 。基礎建設的供應商會提供服務等級協定(service level agreements,SLAs)或是服務等級目標(service level objectives,SLOs)，依據其上的規範，我們可以知道系統是否運作正常。

  1. 指標 可信任度主要的指標有:

    • 模組可靠度(module reliability) : 通常其度量值為初始狀態到發生錯誤的時間，平均無故障時間(mean time to failure,MTTF) 為一種常見的度量值，其倒數為故障率(Failures in time,FIT)，其值通常為每10億個小時有幾個故障。

    • 模組可使用度(module availability) : 指的是當模組從運作正常到運作失常再到運作正常，可使用的時間比例，其中MTTR為平均修复时间(Mean Time To Repair)

      $module\ availability\ =\ \frac{MTTF}{(MTTF+MTTR)}$

      主要應對故障的方法是冗餘(redundancy)，包含:

      • 資源冗餘(resource redundancy) : 重複多組元件(通常是不同的製造商或是不同的製造方法)
      • 時間冗餘(time redundancy) : 重複操作

7. 效能評估:

在比較計算機效能時，比較準確的方法就是看單位時間完成的工作量，或是單位工作所消耗的時間，但並非每次都是採用這個度量標準，故我們只用其他方式來大約評比其效能。

執行時間(excution time)也稱為掛鐘時間(wall-clock time)、響應時間(response time)、已用時間(elapsed time)，這個時包含了許多的相關時間，像是I/O等待的時間，故又有一個術語被提出來:CPU時間，這個時間只計算CPU在做計算時所耗的時間。

  1. 基準測試(Benchmarks test)

    用一些程式運行在系統上來比較時間，過去會用遠比實際應用小且簡單的程式來做分析，包含:

    • 程式內核(kernels):應用程式的核心部分
    • 玩具程式(Toy programs):小程序
    • 合成基準測試程式(Synthetic):為了某些特性所編寫的假程式

    Benchmarks的評估結果並不一定可信，因為開發者有時會透過一些特別的手段使系統在執行Benchmarks時特別的快速。

    故現在流行的方法是透過基準程式集(benchmark suites) 來評比程式的效能，它透過一大群程式來解決剛剛所說的問題，最成功的例子為SPEC(Standard Performance Evaluation Corporation)，其提供了完整的benchmark suites來評比系統的效能

    1. 分類
      • Desktop benchmarks
        • processor-intensive benchmarks
        • graphics-intensive benchmarks
      • Server benchmarks
        • processor throughput-oriented benchmarks
        • file server benchmarks
        • web server benchmarks
        • Transaction-processing benchmarks 有些工程師針對Transaction-processing benchmarks成立 TPC(Transaction Processing Council)提供公平可靠的benchmarks
        • etc

  2. 性能測試結果

    • 性能測試結果必須要有重現性(reproducibility)
    • 性能評分有幾種算法:
      • 將多個測試結果利用加權平均得到代表性能的數值(各家公司的權重不同)
      • 算出benchmarks在基準電腦的執行時間與待評價電腦的執行時間得比值，SPEC採用這個方法，並稱這個比值為SPECRatio

        $SPECRatio\ =\ \frac{Execution\ time_{reference}}{Execution\ time_{wanted}}$

        再針對SPECRatio做算術平均，得到針對許多benchmark suites的效能值。(因為SPECRatio是比值，故算數平均並沒有意義，我們在使用時是利用幾何平均。)

8. 量化原理(Quantitative Principles):

  1. 瓶頸部分或是常見情形優化: 在設計時，如果發現某個部分是整個系統的效能的瓶頸所在，或是某些情形是非常常見的，我們可以對其特別進行優化，使整體系統效能提升。

    • Amdahl’s law 其定義了:針對電腦系統裡面某一個特定的元件予以最佳化，對於整體系統有多少的效能改變 $\begin{split}Speedup&=\frac{Performance\ for\ entire\ task\ using\ the\ enhancement\ when\ possible}{Performance\ for\ entire\ task\ without\ using\ the\ enhancement}
      &=\frac{Execution\ time\ for\ entire\ task\ without\ using\ the\ enhancement}{Execution\ time\ for\ entire\ task\ using\ the\ enhancement\ when\ possible} \end{split}$

      $Execution\ time_{new}=Execution time_{old}\times((1-區塊所佔的比例)+\frac{區塊所佔的比例}{區塊加速比})$

      speed_up

      <font color=blue>Amdahl’s law最主要的缺點是在衡量區塊所占比例這件事並不容易。</font>

  2. 處理器性能公式:

    1. 公式 $\begin{split}CPU\ time&=\frac{CPU\ clock\ cycles\ for\ a\ program}{Clock\ rate}
      &={CPU\ clock\ cycles\ for\ a\ program}\times{Clock\ cycle\ time}
      &=\frac{Instructions}{Program}\times\frac{Clock cycles}{Instructions}\times\frac{Second}{Clock cycles}
      &=(\sum_{k=1}^{N}IC_i\times{CPI_i})\times{Clock\ cycle\ time} \end{split}$

      $\begin{split}CPU\ clock\ cycles=\sum_{k=1}^{N}IC_i\times{CPI_i}\end{split}$

    2. 討論

      1. 相關性

        相關 Clock cycle time CPI Instruction count
        compiler X X O
        ISA X O O
        organization O O X
        Hardware O X X

      2. 比較： 相較起來，處理器性能公式比Amdahl’s law更好來估計效能增減，因為Amdahl’s law中，求加速部份佔全部的比例這件事是不容易的，但相反的，要測得各指令的CPI和IC就比較容易。

9.常見的迷思與陷阱(Fallacies and Pitfalls)

  1. 在做系統優化前記得要利用Amdahl’s law來試算優化的程度。
  2. 一個容錯系統要實現，其內每一部分都必須要有冗餘(redundancy)
  3. 硬體上的故障並不一定會影響結果
  4. benchmarks不一定準確，特別是當這個benchmarks成為公定的標準時。

參考資料： John L. Hennessy, David A. Patterson. “Computer Architecture: A Quantitative Approach, 5/e”, Chapter 1