面向處理器微體系結構評估的高通量MicroBenchmark研究

薛 瑞 苗福濤 葉笑春 孫凝暉 徐文星

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190) 2(中國科學院大學 北京 100049) 3(中國農(nóng)業(yè)銀行 北京 100073) 4 (北京石油化工學院 北京 102617) (xuerui@ict.ac.cn)

隨著互聯(lián)網(wǎng)、云計算、社交網(wǎng)絡等技術的飛速發(fā)展，全球產(chǎn)生的信息量急劇增長.全球數(shù)據(jù)庫每天以2.5 MB的數(shù)據(jù)增長，其中90%的數(shù)據(jù)是在過去2年創(chuàng)造的，這些數(shù)據(jù)無處不在[1].例如能源、制造業(yè)、交通運輸業(yè)、服務業(yè)、科教文化、醫(yī)療衛(wèi)生等領域都積累了TB級、PB級乃至EB級的大數(shù)據(jù).著名的全球連鎖超市沃爾瑪每小時需要處理100余萬條的用戶請求，維護著一個超過2.5 PB的數(shù)據(jù)庫；在高能物理實驗中，2008年開始投入使用的大型強子對撞機每年產(chǎn)生超過25 PB的數(shù)據(jù)；社交網(wǎng)絡Facebook現(xiàn)已存儲超過500億張照片.

海量數(shù)據(jù)的快速處理的需求，對面向高通量應用的處理器微體系結構設計提出了更高的要求[2-3].然而，現(xiàn)階段面向高通量應用的Benchmark，如DCBench，LinkBench，CloudSuite，BigDataBench等，大都是在Hadoop等計算機集群平臺針對目標系統(tǒng)進行測試，主要衡量的是網(wǎng)絡、IO等系統(tǒng)能力，難以對處理器微體系結構的設計進行有效的評估.因此，針對高通量處理器微體系結構評估的需求，也急需一套新的、面向高通量應用的處理器微體系結構評估的基準測試程序.

針對上述問題，本文首先從高通量的典型應用出發(fā)，分析高通量應用實例的整體特征;然后選取高通量應用中的典型Workload作為代表，分析面向高通量應用的處理器的微體系結構需求，設計并實現(xiàn)了一套面向高通量應用的處理器微體系結構評估的基準測試集：HTC-MicroBench;最后通過HTC-MicroBench對現(xiàn)有的代表性多核和眾核處理器微體系結構進行性能測試和分析.

1 相關工作

Benchmark的主要作用是對計算機系統(tǒng)或計算機的各組件進行測試評價，從而更好地指導計算機系統(tǒng)的設計或者指導消費者選擇合適的計算產(chǎn)品.而對處理器微體系結構的研究作為計算機系統(tǒng)結構研究中的重點方向，也離不開對相應Benchmark研究的支持.

傳統(tǒng)的高性能計算領域的Benchmark有SPEC基準測試體系[4]，SPEC CPU 2006是業(yè)界常用的一套程序集，包括整型計算和浮點計算，覆蓋到了計算機編程、算法、人工智能、基因、流體力學、分子動力學和量子計算等方面，保證了測試的完整性.PARSEC是多線程應用程序組成的測試程序集[5]，具有多線程、新型負載、非針對高性能和研究性等幾個典型特征，主要應用于計算機視覺、視頻編解碼、金融分析、動畫物理學和圖像處理等.HPCC是測試高性能計算能力的基準測試集[6]，包含HPL,DGEMM,STREAM,PTRANS,FFTE,RandomAccess和帶寬延遲[7]測試7個主要的測試程序，可以對浮點計算能力、持續(xù)內存帶寬大小、處理器協(xié)作能力、隨機內存訪問效率和內部高速互聯(lián)網(wǎng)絡的性能等方面進行測試.以上Benchmark主要針對高性能應用中計算量大的特點進行基準測試程序的設計，而沒有考慮高通量應用的主要特征.

對于大數(shù)據(jù)相關應用領域的Benchmark也已經(jīng)有大量的研究成果[8].HiBench是Intel開放的Hadoop Benchmark集[9]，包含9個典型的Hadoop負載，用于測評運行Hadoop集群的性能;雅虎開發(fā)的YCSB用于對比NoSQL數(shù)據(jù)庫的性能[10]，其目的是評估鍵值和云數(shù)據(jù)庫;DCBench是針對數(shù)據(jù)中心負載的Benchmark集[11-12];第1個發(fā)行版本含有19個代表性的負載，根據(jù)應用特征的不同，可以分為on-line和off-line這2類，根據(jù)編程模型的不同，可以分為MPI，MapReduce等[13];LinkBench是Facebook開發(fā)的一套用于對社交網(wǎng)絡數(shù)據(jù)庫進行性能測評的工具集[14];專門用于測試存儲社交圖譜和網(wǎng)絡服務的數(shù)據(jù)庫;CloudSuite[15]是針對云計算開發(fā)的一套測試程序集，CloudSuite2.0選取了數(shù)據(jù)分析、數(shù)據(jù)緩存、數(shù)據(jù)服務、圖分析、流媒體、軟件測試、網(wǎng)絡搜索和網(wǎng)絡服務等云計算中常用的負載;BigDataBench[16-17]是由中國科學院計算技術研究所開發(fā)的一套互聯(lián)網(wǎng)大數(shù)據(jù)應用相關的Benchmark集，其覆蓋了結構數(shù)據(jù)、半結構數(shù)據(jù)和非結構數(shù)據(jù)，其負載模擬了搜索引擎、社交網(wǎng)絡和電子商務等業(yè)務模型[18].

一個Benchmark必須有特定的目標系統(tǒng)和特定的目標應用類型[16].因此，雖然以上Benchmark的目標應用具有高通量應用的特點，但是其目標系統(tǒng)不是處理器的微體系結構，沒有針對處理器的微體系結構進行測試和評估.例如HiBench用于對Hadoop集群性能測試、YCBS用于對NoSQL數(shù)據(jù)庫系統(tǒng)測試、LinkBench用于對社交圖譜數(shù)據(jù)庫測試、BigDataBench關注互聯(lián)網(wǎng)服務系統(tǒng)整體性能等.

在目標系統(tǒng)層面，系統(tǒng)級的評價主要關注系統(tǒng)運行的整體性能，如集群內部協(xié)同工作的效率、板間互連和通信的效率、系統(tǒng)軟件棧的性能等.而對于處理器的微體系結構的測試和評估主要關注如眾核處理器中多個核的并行處理能力、線程在處理器中的調度效率、共享存儲的利用效率、Cache效率、CPU吞吐量等.在目標應用層面，學術界對高通量應用的研究尚不完善，缺少一個整體的對高通量應用的歸納、分類和分析的工作.本文的目標系統(tǒng)是高通量處理器微體系結構，目標應用是高通量應用.

2 高通量應用Workload分類模型

2.1 高通量應用及Workload

高通量處理器是適用于互聯(lián)網(wǎng)新興應用負載特征的在強時間約束下能夠全局可控地處理高吞吐量請求的高性能處理器系統(tǒng).高通量應用和傳統(tǒng)的高性能應用存在本質上的區(qū)別，表1對高通量應用負載特性和高性能負載特性進行了對比.從表1中可以看出，面向網(wǎng)絡服務的新型高通量應用在很多方面和面向科學計算的高性能應用存在著不同之處.傳統(tǒng)高性能計算主要針對科學計算應用，程序往往具有較好的局部性，屬于數(shù)據(jù)密集型和計算密集型應用，其所追求的目標是提高單個應用的執(zhí)行速度，這類應用以LINPACK[19]為典型代表.而高通量應用面向的是新型網(wǎng)絡服務，任務并發(fā)度大且對實時性有較高要求，其數(shù)據(jù)量大且程序局部性較差，屬于數(shù)據(jù)密集型和請求密集型應用[20].這類應用追求的目標是高通量，即提高單位時間內處理的并發(fā)任務數(shù)目[21].

Table 1 The Comparative Analysis of High-Throughput Load and Conventional High-Performance Load 表1 高通量負載與傳統(tǒng)高性能負載對比分析

通過對業(yè)界已有典型的大數(shù)據(jù)Benchmark[22-23]和UC Berkeley提出的patterns中的相關內容，調研分析了當前熱門的高通量研究領域和實用領域，總結出典型的高通量應用包括大數(shù)據(jù)分析、機器學習、網(wǎng)頁搜索、社交網(wǎng)絡、電子商務、無線網(wǎng)絡控制器和流媒體等.

上述的每一類應用又包括各自特有的Workload集合.表2所示是高通量應用及各應用的Workload匯總.

在此基礎上，本文提出了一種基于高通量應用需求特點的高通量Workload的分類模型，對上述高通量Workload進行分類和分析.

Table 2 Summary of High-Throughput Application and Workload表2 高通量應用及Workload匯總

2.2 分類模型介紹及Workload選取

對表2列出的應用進行應用特征分析，可將高通量應用的需求分為：單位時間內能夠處理盡量大的數(shù)據(jù)量、單位時間內能夠處理盡量多的請求數(shù)、能夠同時支持盡量多的用戶在線實時處理數(shù)據(jù).根據(jù)上述3種高通量應用的需求，我們將高通量Workload分為數(shù)據(jù)處理類、數(shù)據(jù)服務類和實時交互類這三大類.圖1所示是基于高通量應用需求的高通量Work-load分類模型.

本文所實現(xiàn)的Benchmark的選取主要基于2點原則：

1) 從3類高通量Workload中選取代表性Work-load.根據(jù)分析可知，每一類高通量Workload在應用特征和性能指標方面有很大的相似性，因此，從每一類高通量Workload中集中選取包含至少一個應用領域的Workload，來代表此類Workload.

2) 選取的Workload是使用量較大的.要保證從每一大類中選取出來的Workload具有代表性，則需要此Workload在測試性能中的使用量大.

基于以上2點原則，表3所示是本文選取的HTC-MicroBench中的Workload.

數(shù)據(jù)處理類選取了字符統(tǒng)計、Tera數(shù)據(jù)排序、聚類和搜索匹配等Workload來實現(xiàn)HTC-MicroBench[24]，因為以上Workload均是大數(shù)據(jù)處理中的基礎算法，使用量廣泛.并且Workload之間相對獨立，各個Workload所反映出的應用特點、程序特性和對硬件系統(tǒng)的需求也很相似.典型應用有大數(shù)據(jù)分析及機器學習.

Fig. 1 High-throughput workload classification model圖1 高通量Workload分類模型

ClassificationWorkloadBasic OperationDomainDataProcessingClassWordcountCharacter statisticsBig data analysisTerasortTera data sortBig data analysisK-meansClusteringBig data analysis; Machine LearningGrepSearch matchBig data analysisDataServiceClassQuery ParserParse the stringWeb Search; Social Network; E-commerce; Stream MediaDatabase QueryDatabase operationWeb Search; E-commerce; Stream MediaTerm WeightCalculate word frequencyWeb Search; Social Network; E-commerceDocument WeightCalculate web page weightsWeb SearchMSetCreate keyword matching groupWeb Search; Social Network; E-commerce; Stream MediaReal-timeInteractiveClassSDU ReceiveSimple processing of source dataRNC; Social Network; Stream MediaMACD ScheduleControl the analysis and dumping of data packetsRNC; Social Network; Stream MediaEntity QueryUser instance queryRNC; Social Network; Stream MediaSegmentPacket protocol processingRNC; Social Network; Stream Media

數(shù)據(jù)服務類選取了解析字符串、數(shù)據(jù)庫操作計算詞頻、計算網(wǎng)頁權重和建立關鍵詞匹配組等Work-load來實現(xiàn)HTC-MicroBench，因為以上Workload的特征要求在單位時間內處理盡量多的請求數(shù)，最符合數(shù)據(jù)服務類HTC-MicroBench的特點.典型應用有網(wǎng)頁搜索、社交網(wǎng)絡、電子商務和流媒體.

實時交互類選取了源數(shù)據(jù)的簡單處理、控制數(shù)據(jù)包的解析轉存、用戶的實例查詢和數(shù)據(jù)包的協(xié)議處理等Workload來實現(xiàn)HTC-MicroBench，因為以上Workload是根據(jù)協(xié)議的定義，模擬數(shù)據(jù)包處理流程，并且各個Workload之間是一個有機的整體，均需要能夠對大量用戶進行實時響應與處理，與實時交互類HTC-MicroBench表現(xiàn)特征一致.典型應用有無線網(wǎng)絡控制器、社交網(wǎng)絡、流媒體.

3 HTC-MicroBench的實現(xiàn)

由第2節(jié)分析可知，高通量應用的典型特點是含有大量小規(guī)模作業(yè)，作業(yè)之間耦合性低.因此，要提高處理器對高通量應用的吞吐效率，必須支持多處理節(jié)點并行處理.如Hadoop等系統(tǒng)級的軟件棧[25-26]，提高應用程序吞吐效率的重要手段就是采用分布式系統(tǒng)，并行化多節(jié)點處理作業(yè).在處理器級別能夠并行工作的載體是線程，因此，要實現(xiàn)HTC-MicroBench，需要將不同的作業(yè)處理節(jié)點用線程實現(xiàn)，以達到在處理器級別多節(jié)點并行的效果.

本文提出了一種適用于面向高通量處理器微體系結構評估的HTC-MicroBench的并行模型思想：基于線程的作業(yè)處理多節(jié)點并行模型.

3.1 數(shù)據(jù)處理類HTC-MicroBench多節(jié)點并行化模型

數(shù)據(jù)處理類HTC-MicroBench通常使用MapReduce框架，將算法的處理分為Map階段和Reduce階段[27].本文參考以共享內存方式實現(xiàn)的MapReduce框架的Phoenix系統(tǒng)對數(shù)據(jù)處理類HTC-MicroBench進行了實現(xiàn)[28].在基于線程來實現(xiàn)MapReduce框架時，我們在每個階段，將算法中需要處理的大量數(shù)據(jù)分塊，每塊數(shù)據(jù)作為一個作業(yè)，交給不同的處理節(jié)點處理，一個處理節(jié)點為一個線程.圖2所示是數(shù)據(jù)處理類HTC-MicroBench實現(xiàn)模型:

Fig. 2 Implementation model of data processing圖2 數(shù)據(jù)處理類實現(xiàn)模型

算法開始運行時，首先會創(chuàng)建MapReduce類，在MapReduce類中創(chuàng)建線程，當線程創(chuàng)建時，會運行一個線程體，當線程體沒有執(zhí)行任何算法時，線程體會被一個信號量阻塞，進入Wait狀態(tài)，不執(zhí)行具體操作，同時將作業(yè)壓入Task Queue中.然后，當算法開始執(zhí)行后，執(zhí)行到函數(shù)run_map時，DPUMRLIB內部會調用函數(shù)start_workers，打開信號量，此時線程體開始執(zhí)行通過函數(shù)指針傳入的函數(shù)，同時從Task Queue中取作業(yè).運行完一個作業(yè)后，線程會再從Task Queue中取下一個作業(yè)來執(zhí)行.最后，直到Task Queue中的作業(yè)被執(zhí)行完畢，線程再次進入Wait狀態(tài)，等待下一階段(Reduce或Merge)的函數(shù)start_workers.

此設計的優(yōu)點在于，即使Workload的Task都不相同，但每個物理線程執(zhí)行的工作量是相同的，有利于均衡.另外，將線程處理的數(shù)據(jù)記錄在Task中，并將線程執(zhí)行的函數(shù)用函數(shù)指針表示增加了靈活性，線程可以在創(chuàng)建之后完成多種任務直到線程被停止.

基于此模型，本文對大數(shù)據(jù)分析中的Wordcount，Terasort，K-means，Grep算法進行了實現(xiàn)，作為數(shù)據(jù)處理類HTC-MicroBench.

Wordcount算法是經(jīng)常用于大數(shù)據(jù)文本處理的1個算法，用來統(tǒng)計文本中各單詞出現(xiàn)的次數(shù).構建Wordcount測試用例需要完成split，map，reduce這3個功能函數(shù).

函數(shù)split用于切分輸入數(shù)據(jù)，將大量數(shù)據(jù)切分成小塊數(shù)據(jù)，分發(fā)給多個函數(shù)map創(chuàng)建的不同線程.函數(shù)map是MapReduce中多線程并行處理部分，多個函數(shù)map由不同的線程來并行執(zhí)行，函數(shù)map對各自對應的數(shù)據(jù)塊進行詞頻統(tǒng)計.函數(shù)reduce用于合并各個線程得到的詞頻統(tǒng)計的結果.Wordcount算法執(zhí)行過程如圖3所示:

Fig. 3 Execution flow of Wordcount圖3 Wordcount算法執(zhí)行過程

Terasort算法是一個大規(guī)模鍵值對數(shù)據(jù)排序的算法，是計算機領域作為系統(tǒng)計算性能測評的標準算法.Terasort測試用例的構建主要包括3個步驟：

1) 數(shù)據(jù)采樣.從需要排序的所有鍵值對數(shù)據(jù)中選取部分數(shù)據(jù)，采用傳統(tǒng)的排序方式進行排序，然后根據(jù)需要的分割點個數(shù)，從排序后的數(shù)據(jù)中等步長的距離選擇數(shù)據(jù)點作為分割點，組織到1棵Trie樹中.在Map階段，此Trie樹中的數(shù)據(jù)作為將每個數(shù)據(jù)分到不同任務中的依據(jù).

2) Map階段.Map階段的輸入數(shù)據(jù)是對源數(shù)據(jù)進行簡單切分后的一塊數(shù)據(jù)，對其中的每一個數(shù)據(jù)，根據(jù)Trie樹中的分割點信息，將數(shù)據(jù)分配到Reduce的各線程中.

3) Reduce階段.每個Reduce的線程將從Map階段得到的數(shù)據(jù)進行內部排序，然后按照Reduce的線程編號，順序輸出每個線程內部排序后的結果，即可得到最終排序結果.

K-means算法是用于聚類分析的經(jīng)典算法，用于將多維空間中的大量數(shù)據(jù)點按照距離分到不同的集合.本文所實現(xiàn)的K-means測試用例流程如下：

1) 隨機生成D維的數(shù)據(jù)點P個和D維的聚類中心點C個.對于每個聚類，定義一個D維的Sum，用于記錄一次循環(huán)中，屬于此聚類的各個數(shù)據(jù)點各個維度之和，定義一個Count用于計數(shù)屬于此聚類的點的個數(shù).Sum和Count用于在每次循環(huán)后，計算新的聚類中心點.

2) 每個數(shù)據(jù)點作為一個Map作業(yè)，每個Map作業(yè)計算此數(shù)據(jù)點到所有聚類中心點的距離，然后取距離最小的，作為此數(shù)據(jù)點此次循環(huán)所屬的聚類.將此數(shù)據(jù)點的各維度的值與所屬聚類的Sum各維度的值求和，得到新的Sum，Count值加1.

3) 所有數(shù)據(jù)點計算完成后，執(zhí)行Reduce階段，Reduce階段對每個聚類計算新的中心點，計算公式為SumCount.

4) 循環(huán)執(zhí)行過程2)3)，直到所有數(shù)據(jù)點新計算出的所屬聚類與上次循環(huán)計算出的所屬聚類相同，結束循環(huán).得到所有聚類中心點和所有數(shù) 據(jù)點所屬的聚類.

Grep算法是大數(shù)據(jù)分析中最基本的算法.用于在大文本中匹配模式字符串.MapReduce框架實現(xiàn)Grep算法主要流程有3個步驟：

1) Split階段對較大的源數(shù)據(jù)文件進行切分，每一數(shù)據(jù)塊對應一個Map作業(yè).

2) Map階段在對應的數(shù)據(jù)塊中查找模式字符串.

3) Reduce階段對Map階段匹配的結果做匯總.

3.2 數(shù)據(jù)服務類HTC-MicroBench多節(jié)點并行化模型

Fig. 4 Programming model of data service 圖4 數(shù)據(jù)服務類實現(xiàn)模型

具體流程包括4個步驟：

隨著身體的急速生長，個體的新陳代謝旺盛，血液循環(huán)和呼吸系統(tǒng)的功能也顯著增強；心臟容積增大，收縮力增強。這給初中學生的活動范圍提供了物質基礎，使他們有了獨立活動的體力和精力。一般來說，除了參加學校的體育活動之外，他們還有余力。如果剩余的精力用在不當之處，則會惹是生非。這就要求我們體育教師要善于引導他們，經(jīng)常組織他們參加有益的集體體育活動，以利于他們的身心康健和培養(yǎng)他們良好的道德品質。

1) 創(chuàng)建一個Listen Thread，用于監(jiān)聽請求，將收到的請求發(fā)送到不同線程對應的Job Queue中.

2) 每個線程對應一個Job Queue，用于緩存Listen Thread接收到的用戶請求.

3) 創(chuàng)建線程池，大量線程作為作業(yè)處理節(jié)點，循環(huán)從對應的Job Queue中獲取作業(yè)，然后做相應處理.

4) 將處理結果返回給用戶，作為對用戶操作的響應.

基于此模型，本文對網(wǎng)頁搜索應用響應用戶請求中的Query Parse，Database Query，Term Weight，Document Weight，MSet算法進行了測試程序的實現(xiàn)，作為數(shù)據(jù)服務類HTC-MicroBench.

網(wǎng)頁搜索應用中響應用戶請求部分的執(zhí)行過程如圖5所示.

Fig. 6 Programming model of real-time interaction圖6 實時交互類實現(xiàn)模型

Fig. 5 Execution flow of response to the use request圖5 響應用戶請求部分執(zhí)行過程

具體流程有4個步驟：

1) 由Query Parser對用戶輸入的Key Words進行解析得到Query，此過程主要是去掉Key Words中的Stop Words，提取單詞詞干得到Term，組織各個Term之間的布爾關系等，最后形成一個Query Tree;

2) 對Query Tree中每個葉節(jié)點的Term，進行Database Query，得到相應的數(shù)據(jù);

3) 計算Term Weight，并結合Query Tree中的布爾關系，計算Document Weight;

4) 執(zhí)行MSet過程，從查詢結果中選取最符合要求的結果，返回給用戶.

3.3 實時交互類HTC-MicroBench多節(jié)點并行化模型

實時交互類HTC-MicroBench中，每個作業(yè)按照協(xié)議處理用戶數(shù)據(jù).實時交互類HTC-MicroBench的編程模型，如圖6所示.

具體包括3個部分：

1) 每個用戶注冊之后都會有與具體協(xié)議相關的實例表，處理數(shù)據(jù)時需要查詢;

2) 線程池，大量線程作為作業(yè)處理節(jié)點;

3) 每個作業(yè)處理節(jié)點對應多個用戶，輪詢處理每個用戶的數(shù)據(jù)包Buffer，處理時查詢相應的實例表.

無線網(wǎng)絡控制器應用是移動通信陸地無線接入網(wǎng)中數(shù)據(jù)處理的核心部分，包含用戶面和控制面.控制面主要控制初始化、資源的分配以及數(shù)據(jù)處理結束后的資源釋放，用戶面負責對接入用戶的數(shù)據(jù)包接收、存儲、數(shù)據(jù)的協(xié)議處理和轉發(fā)，整個用戶面按照協(xié)議來處理用戶數(shù)據(jù).

基于此模型，本文對無線網(wǎng)絡控制器應用中的SDU Receive，MACD Schedule，Entity Query，Segment算法進行Benchmark的抽取實現(xiàn)，作為實時交互類HTC-MicroBench.

無線網(wǎng)絡控制器應用中響應用戶請求部分的執(zhí)行過程有4個步驟：

1) 利用SDU Receive算法，從核心網(wǎng)獲取數(shù)據(jù)，得到含有用戶業(yè)務信息的源數(shù)據(jù)，對源數(shù)據(jù)進行幾個操作相對簡單的協(xié)議層協(xié)議處理，得到RLC層的服務數(shù)據(jù)單元(SDU)，并將RLC SDU緩存于SDU緩存區(qū).

2) 為了保證服務質量，MACD Schedule算法控制每10 ms中完成一個用戶SDU數(shù)據(jù)包的解析和轉存.設計一個作業(yè)調度線程，配合一個定時器來進行用戶SDU數(shù)據(jù)包調度和分發(fā).當計時完成，作業(yè)調度線程從SDU數(shù)據(jù)包緩存區(qū)中讀取每個用戶的數(shù)據(jù)包，發(fā)送到不同作業(yè)處理節(jié)點等待處理.

3) 利用Entity Query算法進行實例查詢.每個用戶在接入系統(tǒng)時，注冊一個用戶實例，此實例中包含業(yè)務處理的相關信息.在對每個用戶的SDU數(shù)據(jù)包解析之前，需要根據(jù)用戶ID、查詢實例表，得到用戶SDU數(shù)據(jù)包處理的相關信息，以進行SDU數(shù)據(jù)包的處理.

4) 利用Segment函數(shù)對數(shù)據(jù)包進行協(xié)議處理.從當前作業(yè)節(jié)點對應的作業(yè)隊列中，讀取一個SDU數(shù)據(jù)包，解析SDU，獲取頭部信息，從頭部信息中讀取用戶ID，根據(jù)用戶ID查詢實例表，根據(jù)實例表中的信息進行數(shù)據(jù)包的處理，然后將得到RLC PDU緩存.

經(jīng)過4個步驟，一個SDU數(shù)據(jù)包即可被成功地分段重組成PDU并放入緩存區(qū).

4 實驗評估

4.1 基本程序特征評估

根據(jù)高通量應用的特征分析，HTC-MicroBench主要從3個方面進行驗證：

1) 能夠多節(jié)點并發(fā)處理作業(yè).面向高通量應用的處理器的一個重要目的是在線程級別，支持高通量應用的大規(guī)模并發(fā)作業(yè)，因此，處理器的吞吐效率與用于處理作業(yè)的節(jié)點數(shù)量的關系，可以體現(xiàn)出設計的Benchmark是否具有良好的并發(fā)性，從而可以驗證HTC-MicroBench設計的正確性和有效性.

2) 作業(yè)之間耦合性較低.由于本文所實現(xiàn)的Benchmark是基于共享內存并行編程模型的[29]，每個作業(yè)是由一個線程來處理，所有線程均在多核或眾核處理器上運行.因此，核間共享數(shù)據(jù)量的大小，可以反映出作業(yè)之間耦合性的大小.

3) 數(shù)據(jù)處理類HTC-MicroBench由于處理的數(shù)據(jù)量大、處理的數(shù)據(jù)存儲規(guī)則，因此Cache命中率高.數(shù)據(jù)服務類和實時交互類HTC-MicroBench由于處理的是不同用戶的數(shù)據(jù)，數(shù)據(jù)離散性強，地址空間訪問不規(guī)則數(shù)據(jù)空間局部性差，因此Cache命中率較低.

基于上述分析，本部分實驗主要從作業(yè)并發(fā)性、作業(yè)之間耦合性和Cache使用效率3方面對HTC-MicroBench設計的合理性和有效性進行驗證.

4.1.1 作業(yè)的并發(fā)性評估

對數(shù)據(jù)處理類HTC-MicroBench進行實驗.本實驗所用平臺是Intel Xeon處理器，處理器配置如表4所示:

Table 4 Intel Xeon Configuration表4 Intel Xeon處理器配置

各測試程序所用數(shù)據(jù)集分別為Wordcount(500 MB)，Terasort(200 MB)，K-means(12 MB)，Grep(500 MB)，數(shù)據(jù)處理效率與線程數(shù)的關系,如表5所示.

本部分主要關注各測試程序吞吐效率的并行加速比，因而對所有測試程序得到的數(shù)據(jù)，以1線程的情況為標準進行歸一化，歸一化數(shù)據(jù)吞吐率與線程數(shù)之間的關系,如表6所示.

數(shù)據(jù)服務類HTC-MicroBench關注的需求指標是單位時間內處理的請求數(shù).對數(shù)據(jù)服務類HTC-MicroBench，即網(wǎng)頁搜索應用中的響應用戶請求部分進行實驗.單位時間處理請求量與線程數(shù)的關系,如表7所示.

Table5TheRelationshipBetweenDataProcessingEfficiencyandTheNumberofThreads

表5 數(shù)據(jù)處理效率與線程數(shù)的關系 MBs

表5 數(shù)據(jù)處理效率與線程數(shù)的關系 MBs

Number of ThreadsWordcountTerasortK-meansGrep111.551.440.0867.61221.662.750.16138.03439.284.660.26265.91865.816.310.56504.88

Table 6 The Relationship Between Normalized Data

Table7TheRelationshipBetweentheThroughputandNumberofThreads

表7 單位時間處理請求量與線程數(shù)的關系

實時交互類HTC-MicroBench關注的高通量應用需求指標是在保證對每個用戶的服務質量的前提下，能夠同時支持在線用戶數(shù).實時交互類HTC-MicroBench，即無線網(wǎng)絡控制器應用進行實驗.支持用戶數(shù)與線程數(shù)之間的關系,如表8所示：

Table8TheRelationshipBetweentheNumberofSustainingUsersandtheNumberofThreads

表8 支持用戶數(shù)與線程數(shù)之間的關系

對以上各個測試程序的歸一化測試結果做圖表,HTC-MicroBench中各測試程序的并行加速能力，如圖7所示:

Fig. 7 The ability of parallel acceleration for HTC-MicroBench圖7 HTC-MicroBench各測試程序并行加速能力

由圖7實驗結果可以看出，HTC-MicroBench中的測試程序均有較好的并行加速特性，即各測試程序的作業(yè)之間具有良好的并發(fā)性，能夠反映出高通量應用并發(fā)性的特點.當線程數(shù)為8時，加速比較線程數(shù)為1時有了4～8倍的提高.

4.1.2 作業(yè)之間耦合性

本實驗使用Intel的硬件性能測試軟件VTune進行實驗，通過統(tǒng)計核間共享數(shù)據(jù)量占訪存總量的比例來反映作業(yè)之間的耦合性，實驗結果如圖8所示.

由實驗結果可以看出，HTC-MicroBench核間共享數(shù)據(jù)量占訪存指令總數(shù)的比例是極小的，Wordcount只有不到0.02%，Terasort不到0.19%，K-means不到0.06%，Grep，Search，RNC均都不到0.02%.其中Terasort核間共享數(shù)據(jù)量所占比例最大，由于Terasort算法中，大部分需要多線程之間共享數(shù)據(jù)，但是，核間共享數(shù)據(jù)量也只有不到0.19%，而其他幾個算法所占比例幾乎是可以忽略的.因此，HTC-MicroBench能夠正確反映出各作業(yè)之間低耦合性的特點.

4.1.3 Cache效率的評估

Splash2[30]是傳統(tǒng)并行應用領域中典型的Benchmark，是斯坦福大學推出的共享存儲并行應用Benchmark，其中選取的算法和應用都是傳統(tǒng)高性能并行應用，本實驗以Splash2為對比，選取其中的Raytrace，Cholesky，Radix，Ocean，Radiosity，Barnes這6個測試程序進行指標測試，驗證HTC-MicroBench與傳統(tǒng)的并行應用在Cache使用效率方面的差別，同時說明本文所實現(xiàn)的HTC-MicroBench的有效性.

本實驗使用Linux的性能評估軟件Perf進行實驗測試，分別得到HTC-MicroBench和Splash2的L1 Cache Hit Rate，L2 Cache Hit Rate，LLC Cache Hit Rate這3個指標，其分別如圖9～11所示.

Fig. 8 The ratio of sharing data between cores for HTC-MicroBench圖8 HTC-MicroBench各測試程序核間共享數(shù)據(jù)情況

Fig. 9 The L1 cache hit rate of HTC-MicroBench and Splash2圖9 HTC-MicroBench和Splash2各測試程序L1 cache命中率

Fig. 10 The L2 cache hit rate of HTC-MicroBench and Splash2圖10 HTC-MicroBench和Splash2各測試程序L2 cache命中率

Fig. 11 The LLC cache hit rate of HTC-MicroBench and Splash2圖11 HTC-MicroBench和Splash2各測試程序LLC cache命中率

由實驗結果看出，HTC-MicroBench和Splash2的L1 Cache Hit Rate值都在90%以上，沒有明顯的差別.因為兩者數(shù)據(jù)都具有較好的局部性特征，因此L1 Cache命中率高.而對于L2 Cache和LLC Cache，HTC-MicroBench的平均命中率比Splash2程序的明顯要低.對于L2 Cache，HTC-MicroBench的平均命中率為65%，而Splash2程序為90%；對于LLC Cache，HTC-MicroBench的平均命中率為50%，而Splash2程序為80%.

這是由于L1 Cache具有較高的命中率，基本消耗了HTC-MicroBench應用的空間局部性特征，而且HTC-MicroBench應用具有流式特征，時間局部性并不強，且數(shù)據(jù)量巨大，時間局部性超出了低級Cache的相聯(lián)度，導致L2 Cache和LLC Cache命中率較小.Splash2相對于HTC-MicroBench應用來說，時間局部性較強，數(shù)據(jù)量相對較低，因而L2 Cache和LLC Cache仍具有相對較高的命中率.

4.2 TILE-Gx和Intel Xeon處理器評估

TILE-Gx處理器是Tilera公司推出的一款眾核處理器[31]，使用了一種新的iMesh網(wǎng)絡，iMesh是一種5層網(wǎng)絡結構，使得各個處理器核之間能夠高效通信.TILE-Gx處理器達到了處理效率更高，并發(fā)處理能力更強，能耗更小和擴展性更強等方面的效果.而處理器中的每一個核的處理能力有限，尤其對浮點計算的支持能力很弱.由于TILE-Gx處理器具有眾核，并發(fā)處理能力強的特點，因此本實驗采用的TILE-Gx系列中的TILE-Gx 8036處理器.

TILE-Gx 8036處理器有36個核，L1和L2這2級Cache是獨立的，L3是共享的.表9所示是使用的TILE-Gx和Xeon這2種處理器的基本參數(shù).

本實驗主要關注TILE-Gx 8036與Xeon X7550在并行加速方面的性能對比.由于HTC-MicroBench主要是處理大量的規(guī)模較小、耦合性較低的作業(yè)，因此處理器的并行加速能力對作業(yè)處理能力具有決定性的影響[32].由于Xeon處理器只有16個硬件線程，因此以下實驗均在16個線程及以下進行并行加速能力的對比.

Table 9 The Basic Parameters of TILE-Gx and Xeon表9 TILE-Gx和Xeon的基本參數(shù)

Fig. 12 The comparison between normalized throughput rate and the number of threads in Xeon and TILE-Gx圖12 數(shù)據(jù)處理類測試程序在2種處理器平臺并行加速比

對數(shù)據(jù)處理類HTC-MicroBench，在Xeon和TILE-Gx處理器分別對不同線程數(shù)的Workload單位時間處理數(shù)據(jù)量以單線程為標準進行歸一化，得到歸一化單位時間處理數(shù)據(jù)量與線程數(shù)之間的關系，如圖12所示：

由實驗結果看出，對于數(shù)據(jù)處理類HTC-MicroBench中的4種Workload，在TILE-Gx 8036處理器單位時間處理的數(shù)據(jù)量均大于在Xeon處理器單位時間處理的數(shù)據(jù)量.如矩形實折線部分Grep算法在TILE-Gx 8036處理器運行線程數(shù)達到16時，加速比比線程為1時提高了14倍，而矩形虛折線部分Grep算法在Xeon處理器運行線程數(shù)達到16時，加速比僅提高了11倍.因此TILE-Gx 8036處理器對數(shù)據(jù)處理類HTC-MicroBench有更好的并行加速比.

對數(shù)據(jù)服務類HTC-MicroBench，本實驗測試單位時間內在Xeon和TILE-Gx處理器分別所能處理的請求數(shù)量，以單線程為基準做歸一化，如圖13所示:

Fig. 13 The test result of speedup in Xeon and TILE-Gx processor (data service applications)圖13 數(shù)據(jù)服務類測試程序在2種處理器平臺并行加速比

由實驗結果看出，TILE-Gx 8036處理器在線程數(shù)達到16時，加速比有16倍的提高，而Xeon處理器對數(shù)據(jù)處理類HTC-MicroBench的加速比僅提高了9倍.TILE-Gx 8036處理器對數(shù)據(jù)服務類HTC-MicroBench也具有更高的并行加速能力.

對實時交互類HTC-MicroBench，主要關注在保證對每個用戶的服務質量的前提下，能夠同時支持在線用戶數(shù).對于RNC用戶面Benchmark，保證服務質量是指用戶數(shù)據(jù)包由于系統(tǒng)繁忙而導致的丟包率在一定的范圍之內，本文取丟包率小于5%為可接受的.

圖14所示是實驗得到RNC用戶面Benchmark在Xeon和Tilegx這2種處理器上的結果.

Fig. 14 The test result of speedup in Xeon and TILE-Gx processor (real-time interaction applications)圖14 實時交互類測試程序在2種處理器平臺并行加速比

由實驗結果看出，TILE-Gx 8036處理器在線程數(shù)提高到16時，能支持的用戶數(shù)是線程數(shù)為1時的11倍；而Xeon處理器對數(shù)據(jù)處理類HTC-MicroBench的加速比僅提高了3倍.對于實時交互類HTC-MicroBench，TILE-Gx處理器同樣具有更高的并行加速能力.

綜上實驗結果可以看出，本文實現(xiàn)的面向高通量應用的HTC-MicroBench對Tile-Gx眾核處理器和Xeon多核處理器均具有良好的并行加速比和并行處理能力，并且對于Tile-Gx眾核處理器微體系結構具有相對更好的評估能力.

這也從另一個角度佐證了本文所抽取和實現(xiàn)的Benchmark對面向高通量應用的處理器微體系結構設計的評估是合理有效的.

5 結束語

本文實現(xiàn)了一個面向高通量應用的處理器微體系結構設計評估的Benchmark——HTC-MicroBench.首先，本文總結了高通量應用以及各應用相應的Workload，提出了面向高通量應用的處理器微體系結構設計評估的基準測試程序——HTC-MicroBench，并提出了一種基于需求特點的高通量應用Workload的分類方法.其次，提出并實現(xiàn)了一種基于線程的作業(yè)處理節(jié)點并行化模型，完成了HTC-MicroBench的設計和實現(xiàn).最后，通過2組實驗評估：1)對HTC-MicroBench中的Workload的并發(fā)性、耦合性和Cache使用效率進行了評估；2)使用HTC-MicroBench對比測試了8核Xeon處理器和眾核TILE-Gx這2種處理器平臺的并行加速能力，實驗結果驗證了本文所實現(xiàn)的HTC-MicroBench在面向高通量應用的處理器微體系結構評估方面的具有有效性和合理性.

XueRui, born in 1993. PhD candidate. Student member of CCF. Her main research interests include high throughput computing architecture and software simulation.

MiaoFutao, born in 1989. Master, engineer. His main research interests include the utilization of big data and machine learning in financial software system.