Analysis of Redundancy and Application Balance in the SPEC CPU2006 Benchmark Suite

1. 摘要：
   • 使用spec2006可能出現的問題：研究人員由于仿真時間限制，編譯器困難，lib庫或者系統調用的問題等原因，可能會選擇其中部分測試集，但是一個随機的子集就可能會出現誤導結果的可能。
   • 文章工作：
     • 在幾個系統平台上，利用性能計數器實驗分析了spec 2006的特征
     • 利用主成分分析和聚類等統計技術對測試集的相似性和備援性進行推斷，進而給出了一個有意義的子集
   • 結論：
     • spec2006中沒有繼續包含EDA應用領域的測試集，但是從基本程式特征的角度分析，目前所包含的程式提供了比EDA程式更廣的特征空間
     • 對于整個spec2006套件，使用一個子集包括6個定點程式和8個浮點程式就可以包含大部分的套件資訊
2. 介紹
   • spec2006是第五代spec，包括29個程式，12個定點，17個浮點程式。每一代更新時，容易受到不公平編譯器優化影響的程式被停用，程式運作時間增加，程式的記憶體通路強度增加
   • Is SPEC CPU2006 well-balanced? （spec cpu2006是不是均衡的？）
     • 之前的spec中包含了EDA軟體程式，但是2006中沒有，是以是否會損失這類應用的特征或者其它程式中是否提供了和EDA程式類似的特征？
     • 當包含同一個領域中的多個程式時，是否有足夠的特有的特征，保證這些程式不會互相包含（備援）
   • 論文工作：使用多元統計分析技術，例如PCA和聚類分析
     • 研究spec2006套件是否足夠平衡（全面）
     • 識别spec2006程式之間的相似和不同之處
     • 識别多個輸入集之間的相似之處，并找出具有代表性的輸入集
     • 提出能夠代表整個套件的程式子集
3. spec cpu2006的介紹
   • 整數程式12個，使用C/C++編寫；浮點17個，使用C/C++/Fortran語言
   • 論文通過在Pentium D processor (2.1 GHz, 16KB L1 data and instruction caches, and 2x2MB L2 cache)運作spec2006，得到了一些指令組成分析結果和指令局部性的分析結果
   • 指令的組成分析
     • 29個程式中，有24個程式的動态指令數超過了萬億（trillion），剩餘五個為（429.mcf，471.omnetpp，433.milc， 477.soplex，453.povray）

     • 整數程式，分支指令占比接近20%，但是456.hmmer和464.h246ref隻有7%左右的分支。最高的是483.xalancbmk ，有25%的分支指令（動态指令中）。在浮點程式中隻有三個程式（447.dealll, 450.soplex, 453.povray）的分支大概在15%左右，其餘的基本都在5%一下。10.bwaves, 470.lbm,

       436.cactusADM中甚至分支指令小于1%

     • 通過子程式分析确定指令的局部性。利用PIN工具分析子程式的調用頻率，識别熱點子程式，同時計算子程式中動态/靜态指令的數量。下圖為統計結果，橫軸為子程式的靜态指令數，縱軸為動态指令數。圖中第二點，第三點，第四點和五點分别代表前五，十，十五和二十個子程式。當折線的斜率非常大時，意味着局部性非常好

       

       

     • 指令局部性的結論，與上一代SPEC CPU基準測試套件中的程式類似，SPEC CPU2006基準測試中的大多數都表現出良好的指令局部性，但也有一些明顯的例外
   • 執行過程中的一些其它額外資訊（和運作環境相關 16KB L1 data and instruction caches, and 2x2MB L2 cache）

     

4. Spec 2006套件中的備援性——實驗方法
   • 基本思想：統計每個程式的靜态資訊和動态資訊，通過聚類分析，進行備援性分析。（指令局部性，資料局部性，分支可預測性和指令的分布情況等）

   • 問題1：動态資訊和微體系結構緊密相關，是以需要考慮思考消除這種微架構可能帶來的偏差。

     解決：在基于四種ISA和編譯器的五種機器上分别測試每個程式的特征（IBM Power，Sun UltraSparc， Itanium，x86）

     問題2：某些測量得到的性能計數器特征可能對性能（CPI）的影響非常小

     解決：在實際實驗過程中，根據結果，選擇和性能有較大相關的特征

     

   • 測量資料的重新處理（主成分分析，取出變量/特征之間的相關性）：如果每個機器（n個）測量m個特征，則每個程式将會有n*m個特征變量。但是這些特征變量之間有相關性，如果直接使用這些變量，某些特征将會在結果中占據更大的比例，是以需要消除這種變量之間的相關性
   • PCA：消除特征變量之間的相關性（主要工作：降維）
     • 為了消除每個變量的數量級不同，将所有資料歸一化到正态分布，均值為0，方差為1

     • PCA會使用一組新的變量替代之前的變量。将P個原本的變量X轉換為P個新的變量Z

       Z i = ∑ j = 0 p a i j X j V a r [ Z 1 ] > = V a r [ Z 2 ] . . . . > = V a r [ Z p ] Z_i=\sum_{j=0}^{p}{a_{ij}X_j}\\Var[Z_1]>=Var[Z_2]....>=Var[Z_p] Zi​=j=0∑p​aij​Xj​Var[Z1​]>=Var[Z2​]....>=Var[Zp​]

       Var代表特征值，即最終選擇特征值最大的n個變量作為新的特征向量。特征值越大意味着對結果的影響和作用越大。

     • 選擇标準（kaiser标準）：特征值大于或者等于1則被保留。某些情況下，如果變量之間有相關性，則可以使用少部分變量擷取大部分資訊
   • 利用聚類分析，測量相似性。論文在兩種聚類方法中選擇了一種（K-means和層級聚類），前一種需要事先指令需要聚類的個數，後者則不需要
     • 層級聚類(hierarchical)思想：利用建構樹的方式聚類。開始時，每個程式屬于單獨的一類，然後計算互相之間的距離（利用特征向量計算歐式距離），将兩個距離最短的程式劃分為一類，然後重複這個過程，直到最後變為一類
     • 計算兩個子簇之間的距離的方法：
       1. 取兩個類中最近的樣本計算
       2. 取兩個類中最遠的樣本計算
       3. 将兩個類中兩兩點之間的距離放在一起求平均等多種方法
     • 通過這種算法得到的聚類結果可以繪制成一張樹狀結構圖。如下，橫軸代表兩個類之間的距離，縱軸沒有特殊含義

       

5. 選擇spec 2006的子集
   • 測量資料為之前表格中的資料，然後利用PCA分析和層級聚類得到樹狀圖。對于定點程式，選擇特征值大于1的7個主成分，能夠保留94%的方差。對于浮點程式，選擇5個主成分，能夠保留85%的方差
   • 通過在類似于Figure2中的圖中選擇何時的連接配接距離來選擇出一個具有代表性的子集
   • 當有兩個以上程式的類被選擇時，如何選擇其中一個程式：選擇最靠近類中心的程式作為類的代表（需要重新計算每個點到類中心的距離）
   • 不應該将挑選的子集中程式類型的混合誤認為實際工作負載中程式類型的混合

     

6. 評估挑選的子集的代表性：在八個不同的商業系統上測試子集的有效性

   • AMD Tyan Thunder K8E, Apple iMac 2.0GHz Intel Core Duo,

     Fujitsu SC CELSIUS M440, Intel DG965WH motherboard,

     Intel DG965WH motherboard, Bull SAS NovaScale B260 (Intel Xeon E5320,1.86GHz),

     Dell Precision 690 (Intel Xeon 5160, 3.00 GHz),

     HP Integrity BL860c (1.6GHz Dual-Core Intel Itanium 2)

   • 根據官網上提供的spec cpu2006在不同計算機的執行時間和在參考機器上的執行時間，将程式子集的權重平均（幾何平均）加速比和整個套件的平均加速比進行比較。
   • 當計算子集的平均加速比時，每個子集中的程式會被賦予一個權重，該權重為該程式所屬的子類中程式的個數，然後整體求平均值
   • 結果：

     

7. 選擇每個程式具有代表性的輸入集
   • 上述的分析過程重新做一遍，但是将所有程式和其所有的輸入集都需要參與。對于CINT，根據kaiser标準選擇七個主成分可以覆寫89%的方差；對于CFP，選擇6個主成分覆寫88%的方差。

     

8. 根據分支和存儲行為特征選擇子集
   • 根據資料通路性能特征和分支預測特征分析程式之間的相似性，進而選擇适合研究資料緩存和分支預測的研究子集
   • 針對于分支特征在三個不同的系統中測量資料，選擇兩個主成分基本能夠覆寫92%的方差。
     • 大部分的CFP程式聚集在一起，CINT程式則展示出多樣性。
     • 一些分支占比較少的CINT程式和CFP出現了重疊（464.h264ref, 456.hmmer)
     • 對于PC1的值較大的程式，分支較容易預測
   • 對于資料通路特征同樣在三個系統中測量資料，最後選擇4個主成分，能夠覆寫84%的方差
     • 對于PC1為負值的程式，資料通路行為較差，容易導緻更高的資料緩存缺失率(mcf, omnettp)
     • 對于PC2較高的CFP程式，具有較高的記憶體通路占比
9. Spec cpu2006套件是否足夠平衡（balance）
   • 某些領域的應用并沒有在套件中涉及（例如EDA，spec2000中有），同時某些領域卻有多個代表性的程式（例如AI，sjeng，gobmk，astar）
   • 針對于spec2006沒有包含EDA領域的測試程式，論文将spec2000中的整數程式和spec2006中的整數程式都進行主成分分析，選擇四個主成分。然後将PC1和PC2繪制散點圖，PC3和PC4繪制散點圖。
     • 結論：spec2000中的EDA程式非常類似于spec2006中的astar和bzip2程式，同時EDA程式完全在cpu2006所覆寫的工作負載空間的範圍内，是以沒有EDA不會帶來很大的影響
   • 同一個領域中的程式所具有的差異
     • 通過之前對程式之間的相似分析，可以看出同一個領域的不同程式之間的相似性
     • 結果：表格中加重的程式意味着更加相似

       

10. CPU2006和CPU2000之間的比較
    • 通過将兩者的程式的主成分分析結果繪制成散點圖，可以看出，cpu2006的工作負載的範圍更廣泛
    • cpu2006中的483.xalancbmk和456.hmmer使得PC1和PC2覆寫的範圍更加廣泛
    • PC3和PC4的散點圖中，可以看出445.gobmk, 483.xalancbmk， 462.libquantum和458.sjeng提供了更加廣泛的多樣性
    • 兩者共有的一些程式，行為基本上也很相似。雖然動态指令數和資料通路足迹不太一樣，但是控制流基本沒有變化
    • 在浮點方面，spec cpu2006展現出更加多樣的特征
11. 程式對性能特征的敏感性
    • 實驗方法：在五台機器上運作所有程式，記錄分支預測行為和資料緩存的行為，然後在每台機器的結果中按照記錄的行為特征進行排序，最後計算一個程式在不同機器上的差異程度。通過該結果代表程式對一個給定特征的敏感程度
    • 結果：462.libquantum, 456.hmmer, 464.h264ref 在不同機器上的資料緩存的缺失率變化最明顯，456.hmmer在分支變化上更明顯。gcc的變化非常小，意味着gcc消除了平台的敏感性