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

1(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所) 北京 100190) 2(中國科學(xué)院大學(xué) 北京 100049) 3(中國農(nóng)業(yè)銀行 北京 100073) 4 (北京石油化工學(xué)院 北京 102617) (xuerui@ict.ac.cn)

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 高通量應(yīng)用Workload分類模型

2.1 高通量應(yīng)用及Workload

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

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

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

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

在此基礎(chǔ)上，本文提出了一種基于高通量應(yīng)用需求特點(diǎn)的高通量Workload的分類模型，對上述高通量Workload進(jìn)行分類和分析.

Table 2 Summary of High-Throughput Application and Workload表2 高通量應(yīng)用及Workload匯總

2.2 分類模型介紹及Workload選取

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

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

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

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

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

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

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ù)服務(wù)類選取了解析字符串、數(shù)據(jù)庫操作計(jì)算詞頻、計(jì)算網(wǎng)頁權(quán)重和建立關(guān)鍵詞匹配組等Work-load來實(shí)現(xiàn)HTC-MicroBench，因?yàn)橐陨蟇orkload的特征要求在單位時(shí)間內(nèi)處理盡量多的請求數(shù)，最符合數(shù)據(jù)服務(wù)類HTC-MicroBench的特點(diǎn).典型應(yīng)用有網(wǎng)頁搜索、社交網(wǎng)絡(luò)、電子商務(wù)和流媒體.

實(shí)時(shí)交互類選取了源數(shù)據(jù)的簡單處理、控制數(shù)據(jù)包的解析轉(zhuǎn)存、用戶的實(shí)例查詢和數(shù)據(jù)包的協(xié)議處理等Workload來實(shí)現(xiàn)HTC-MicroBench，因?yàn)橐陨蟇orkload是根據(jù)協(xié)議的定義，模擬數(shù)據(jù)包處理流程，并且各個(gè)Workload之間是一個(gè)有機(jī)的整體，均需要能夠?qū)Υ罅坑脩暨M(jìn)行實(shí)時(shí)響應(yīng)與處理，與實(shí)時(shí)交互類HTC-MicroBench表現(xiàn)特征一致.典型應(yīng)用有無線網(wǎng)絡(luò)控制器、社交網(wǎng)絡(luò)、流媒體.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體流程包括4個(gè)步驟：

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

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

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

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

4) 將處理結(jié)果返回給用戶，作為對用戶操作的響應(yīng).

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

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

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

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

具體流程有4個(gè)步驟：

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

2) 對Query Tree中每個(gè)葉節(jié)點(diǎn)的Term，進(jìn)行Database Query，得到相應(yīng)的數(shù)據(jù);

3) 計(jì)算Term Weight，并結(jié)合Query Tree中的布爾關(guān)系，計(jì)算Document Weight;

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

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

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

具體包括3個(gè)部分：

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)評估

4.1 基本程序特征評估

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

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

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

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

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

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

對數(shù)據(jù)處理類HTC-MicroBench進(jìn)行實(shí)驗(yàn).本實(shí)驗(yàn)所用平臺是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ù)的關(guān)系,如表5所示.

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

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

Table5TheRelationshipBetweenDataProcessingEfficiencyandTheNumberofThreads

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

表5 數(shù)據(jù)處理效率與線程數(shù)的關(guān)系 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í)間處理請求量與線程數(shù)的關(guān)系

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

Table8TheRelationshipBetweentheNumberofSustainingUsersandtheNumberofThreads

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

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

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

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

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

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

由實(shí)驗(yàn)結(jié)果可以看出，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%，而其他幾個(gè)算法所占比例幾乎是可以忽略的.因此，HTC-MicroBench能夠正確反映出各作業(yè)之間低耦合性的特點(diǎn).

4.1.3 Cache效率的評估

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

本實(shí)驗(yàn)使用Linux的性能評估軟件Perf進(jìn)行實(shí)驗(yàn)測試，分別得到HTC-MicroBench和Splash2的L1 Cache Hit Rate，L2 Cache Hit Rate，LLC Cache Hit Rate這3個(gè)指標(biāo)，其分別如圖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命中率

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

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

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

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

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

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

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í)間處理數(shù)據(jù)量以單線程為標(biāo)準(zhǔn)進(jìn)行歸一化，得到歸一化單位時(shí)間處理數(shù)據(jù)量與線程數(shù)之間的關(guān)系，如圖12所示：

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

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

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

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

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

圖14所示是實(shí)驗(yàn)得到RNC用戶面Benchmark在Xeon和Tilegx這2種處理器上的結(jié)果.

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

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

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

這也從另一個(gè)角度佐證了本文所抽取和實(shí)現(xiàn)的Benchmark對面向高通量應(yīng)用的處理器微體系結(jié)構(gòu)設(shè)計(jì)的評估是合理有效的.

5 結(jié)束語

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

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.