基于人工神經(jīng)網(wǎng)絡(luò)的線程數(shù)據(jù)加速劃分?

盛紅雷 賈 崟

（1.南京南瑞集團(tuán)公司信息通信技術(shù)分公司 南京 210000）（2.國(guó)網(wǎng)冀北電力有限公司 北京 100054）

1 引言

線程級(jí)推測(cè)（Thread-Level Speculation，TLS）是多核上一種加速串行程序的線程級(jí)自動(dòng)并行化技術(shù)［1］。按照摩爾定律，半導(dǎo)體處理器進(jìn)入了多核時(shí)代［2］。線程級(jí)并行（Thread-Level Parallelism，TLP）逐漸成為很好的一個(gè)選擇，尤其適合于片上多處理器（Chip Multiprocessor，CMP）［3］。為了提升程序在CMP上運(yùn)行的效率，已有的串行程序需要并行化從而能夠在多核上執(zhí)行，從而獲得程序加速比性能的提升。推測(cè)多線程（Speculative Multithreading，SpMT）作為串行程序并行化的一種重要技術(shù)［4］，允許串行程序劃分后生成的多個(gè)線程并行地、激進(jìn)地執(zhí)行，從而獲得程序性能的提高。比較經(jīng)典的 SpMT 代表有［5］Multiscalar，Hydra，Mitosis，POSH，DOMORE，DOE，SEED。機(jī)器學(xué)習(xí)方法已經(jīng)被引入到推測(cè)多線程技術(shù)。文獻(xiàn)［6］開發(fā)了自動(dòng)基于編譯器的方法來實(shí)現(xiàn)利用機(jī)器學(xué)習(xí)匹配一個(gè)并行化的程序到多核處理器，該方法利用機(jī)器學(xué)習(xí)實(shí)現(xiàn)了并行程序的最佳線程數(shù)目和調(diào)度策略。文獻(xiàn)［7］給出一個(gè)自適應(yīng)的基于OpenMP的機(jī)制，該機(jī)制利用機(jī)器學(xué)習(xí)方法給給定的循環(huán)產(chǎn)生合理數(shù)目的多線程版本，且選擇一個(gè)運(yùn)行時(shí)在多核結(jié)構(gòu)上最合適的版本來執(zhí)行。文獻(xiàn)［8］利用機(jī)器學(xué)習(xí)方法來分配并行任務(wù)，具體方法是基于相似程序分配策略的先驗(yàn)知識(shí)在決定最佳任務(wù)分配方案之前利用靜態(tài)程序特征來分類程序。機(jī)器學(xué)習(xí)在線程級(jí)推測(cè)中的應(yīng)用主要包含：線程到多核的匹配、線程的調(diào)度、多線程的優(yōu)化、線程劃分的決策等，文獻(xiàn)［9］利用K-Nearest-Neighbour（KNN）算法，根據(jù)相鄰的相似度較高的訓(xùn)練程序的劃分方案綜合決定待劃分程序的劃分方案。

本文提出一種基于人工神經(jīng)網(wǎng)絡(luò)的線程劃分預(yù)測(cè)模型?；谟?xùn)練程序的特征信息和最優(yōu)劃分方案，預(yù)測(cè)模型按照指定的精度進(jìn)行訓(xùn)練。訓(xùn)練好的模型根據(jù)測(cè)試程序的特征信息預(yù)測(cè)出劃分方案。本文中ANN模型和Prophet自動(dòng)劃分編譯器相互配合，使用Olden基準(zhǔn)程序集進(jìn)行離線學(xué)習(xí)和指導(dǎo)劃分。

2 線程數(shù)據(jù)加速劃分模型

2.1 基本思想

對(duì)于TLS自動(dòng)劃分過程，本文使用Prophet編譯器完成。ANN預(yù)測(cè)模型通過寫讀（write and read）預(yù)測(cè)結(jié)果文件和Prophet關(guān)聯(lián)［10］，從樣本集中學(xué)習(xí)線程劃分的知識(shí)，并根據(jù)待測(cè)過程的特征信息，預(yù)測(cè)該過程的劃分方案，并將該方案反饋給Prophet的劃分遍，從而實(shí)現(xiàn)Prophet對(duì)該過程有較優(yōu)的劃分。圖1給出了ANN預(yù)測(cè)模型和Prophet關(guān)系圖。箭頭1代表ANN預(yù)測(cè)模型產(chǎn)生的劃分方案反饋給Prophet過程，箭頭2代表Prophet劃分過程為ANN預(yù)測(cè)模型提供劃分方案生成依據(jù)。

圖1 ANN預(yù)測(cè)模型和Prophet關(guān)系圖

2.2 整體框架

基于ANN的線程劃分預(yù)測(cè)模型如圖2所示。模型主要分為兩個(gè)部分：訓(xùn)練階段（上面虛框），測(cè)試階段（下面虛框）。樣本集是ANN預(yù)測(cè)模型學(xué)習(xí)劃分知識(shí)的來源，其中的樣本由兩部分組成，即過程特征X和劃分方案H。在訓(xùn)練階段，首先從樣本集中每一個(gè)樣本分離出各自的過程特征x和劃分方案h，并作為ANN模型的輸入和輸出來訓(xùn)練網(wǎng)絡(luò)，直至網(wǎng)絡(luò)達(dá)到指定的精度。在測(cè)試階段，首先提取測(cè)試過程的特征信息，組成特征向量作為ANN模型的輸入，并執(zhí)行訓(xùn)練好的模型得出測(cè)試過程的劃分方案。

圖2 線程劃分預(yù)測(cè)框架

2.3 特征提取

特征提取是由Prophet的剖析器Pro_ler來實(shí)現(xiàn)。Pro_ler首先分析基準(zhǔn)程序的輸入特征，并依據(jù)輸入特征構(gòu)造輸入訓(xùn)練集。Pro_ler通過多次預(yù)執(zhí)行程序捕獲程序的剖析信息，工作流程如圖3所示，當(dāng)執(zhí)行一個(gè)程序指令時(shí)，首先對(duì)指令類型做出判斷，當(dāng)指令是循環(huán)指令時(shí)，記錄循環(huán)的迭代次數(shù)D，動(dòng)態(tài)指令數(shù)M，循環(huán)個(gè)數(shù)C。當(dāng)指令為非循環(huán)指令時(shí)，記錄基本塊個(gè)數(shù)N和動(dòng)態(tài)指令數(shù)M，和分支個(gè)數(shù)P。最終，ANN模型選取程序關(guān)鍵路徑上的5個(gè)特征：基本塊個(gè)數(shù)N，動(dòng)態(tài)指令數(shù)M ，分支指令個(gè)數(shù)P，循環(huán)個(gè)數(shù)C，函數(shù)調(diào)用次數(shù)E，并由這5個(gè)特征組成特征向量 X=＜N，M，P，C，E＞。

圖3 程序剖析器Profiler

2.4 劃分方案

在Prophet線程劃分遍中，對(duì)程序加速比影響比較大有五個(gè)閾值，分別是依賴數(shù)，線程粒度下限，線程粒度上限，激發(fā)距離下限，激發(fā)距離上限，它們的名稱（包括縮寫）和釋義如表1所示。

表1 線程劃分最具影響的五個(gè)閾值

在圖2中，得出上面五個(gè)因素變化能夠影響加速比。五個(gè)因素變化時(shí)，Prophet劃分遍在劃分過程時(shí)產(chǎn)生不同的限制條件，程序的加速比因此產(chǎn)生波動(dòng)。對(duì)程序中每個(gè)過程進(jìn)行線程劃分時(shí)，通過五個(gè)因素值的改變，導(dǎo)致程序中每個(gè)過程的加速比提高，從而整個(gè)程序的加速比也得到提高。我們把影響程序劃分結(jié)果的最重要五個(gè)閾值作為線程劃分方案 H 的組成部分，即 H=＜Dt，TsL，TsU，SdL，SdU＞。

3 實(shí)驗(yàn)準(zhǔn)備

3.1 實(shí)驗(yàn)配置

本文基于MatlabR2015b神經(jīng)網(wǎng)絡(luò)工具箱和SUIF/MACHSUIF［11］開發(fā)的 Prophet編譯器［12］和模擬器，并選用了Olden基準(zhǔn)程序集［13］作為預(yù)測(cè)模型的輸入和驗(yàn)證程序集。Prophet模擬器是基于Tomasulo算法［14］模擬了8核超標(biāo)量四流水的基于MIPS的R3000處理器，是一個(gè)執(zhí)行驅(qū)動(dòng)的模擬器，每個(gè)處理單元有獨(dú)立的程序計(jì)數(shù)器、取指令單元、解碼單元、執(zhí)行單元。各個(gè)PE能夠以順序方式在一個(gè)時(shí)鐘周期發(fā)射4條指令，而且有各自的多版本L1緩存（2時(shí)鐘周期訪問延遲）。多版本L1緩存被用于緩存各個(gè)執(zhí)行單元的推測(cè)結(jié)果，并且進(jìn)行緩存之間的通信。8個(gè)處理單元通過一個(gè)監(jiān)聽總線共享一個(gè)寫回L2緩存。表2給出了Prophet參數(shù)配置列表。Prophet編譯器實(shí)現(xiàn)預(yù)測(cè)方案指導(dǎo)劃分的過程，而模擬器驗(yàn)證指導(dǎo)劃分后獲得的加速比。ANN線程預(yù)測(cè)模型的實(shí)驗(yàn)平臺(tái)如下，軟件平臺(tái)：Windows7+Matlab2015a；硬件平臺(tái)：處理器Intel（R） Core（TM）i5-2400 CPU@3.10GHz，64bit；8.00GB RAM。表3給出了ANN預(yù)測(cè)模型的參數(shù)配置。

表2 Prophet參數(shù)配置和取值

表3 ANN預(yù)測(cè)模型的參數(shù)配置和取值

3.2 評(píng)價(jià)指標(biāo)

為了對(duì)ANN線程劃分預(yù)測(cè)模型進(jìn)行有效評(píng)價(jià)，從兩個(gè)方面進(jìn)行評(píng)價(jià)，分別是預(yù)測(cè)精度和性能增長(zhǎng)率。其中，預(yù)測(cè)精度如圖4給出了預(yù)測(cè)精度的計(jì)算圖。

圖4 預(yù)測(cè)精度計(jì)算圖

預(yù)測(cè)模型的一個(gè)輸出值對(duì)應(yīng)于五維空間中的一個(gè)點(diǎn)，提取三個(gè)點(diǎn)：預(yù)測(cè)輸出點(diǎn)，實(shí)際點(diǎn)和坐標(biāo)軸原點(diǎn)，組成一個(gè)平面，橫豎坐標(biāo)軸分別為x軸和y軸。黑色五角星2代表ANN模型預(yù)測(cè)的結(jié)果，黑色圓圈1代表原有結(jié)果，線b代表預(yù)測(cè)結(jié)果到原點(diǎn)線段，線c代表原有結(jié)果到原點(diǎn)線段，虛線a代表預(yù)測(cè)輸出和原有結(jié)果之間線段，我們用線b和線c之間夾角α(0～π)的余弦值cosα(0～1)來代表預(yù)測(cè)精度。當(dāng)五角星和圓圈越近（即預(yù)測(cè)值和實(shí)際值越接近），夾角越小，余弦值越大，精度越高；反之，五角星和圓圈越遠(yuǎn)（即預(yù)測(cè)值和實(shí)際值越遠(yuǎn)），夾角越大，余弦值越小，精度越小。根據(jù)余弦定理：

其中，‖‖a，‖‖b和‖‖c分別代表線段a，b，c的長(zhǎng)度。假設(shè)點(diǎn)1的坐標(biāo)為 (Dt，TsL，TsU，SdL，SdU)，點(diǎn) 2 的坐標(biāo)為 (Dt+δ1，TsL+δ2，TsU+δ3，SdL+δ4，SdU+δ5)，其中，δ1，δ2，δ3，δ4，δ5分別表示預(yù)測(cè)的五維輸出和原有目標(biāo)輸出之間對(duì)應(yīng)的差值。則

利用式（4），我們對(duì)基于ANN線程劃分預(yù)測(cè)模型的預(yù)測(cè)精度進(jìn)行定量評(píng)估。為了定量分析，定義性能增長(zhǎng)率為

其中，C表示預(yù)測(cè)結(jié)果指導(dǎo)程序劃分后獲得的加速比；O表示原有基于啟發(fā)式規(guī)則線程劃分［15］取得的加速比；R代表性能增長(zhǎng)率。

4 實(shí)驗(yàn)分析

4.1 加載樣本集

根據(jù)特征提取和劃分方案，提取的特征向量為X=＜N，M，P，C，E＞ ，線 程 劃 分 方 案 為H=＜Dt，TsL，TsU，SdL，SdU＞ 。我們用 (X，H)來表示樣本，從而得出樣本是一個(gè)10維向量，即＜N，M，P，C，E，Dt，TsL，TsU，SdL，SdU＞ 。 提 供樣本集的是database.text文件，共存儲(chǔ)10321個(gè)樣本。利用Matlab的導(dǎo)入功能將database.txt中的過程名去掉（方便預(yù)測(cè)模型訓(xùn)練），只導(dǎo)入特征向量X和對(duì)應(yīng)的劃分方案H，形成database.m文件。

4.2 建立模型

為了建立ANN預(yù)測(cè)模型，首先確定網(wǎng)絡(luò)的各層結(jié)構(gòu)，并初始化網(wǎng)絡(luò)。根據(jù)樣本特征向量X的維度確定神經(jīng)網(wǎng)絡(luò)的輸入層含有5個(gè)神經(jīng)元，而劃分方案H的維度確定網(wǎng)絡(luò)輸出層含有5個(gè)神經(jīng)元。利用Matlab中的new_（）函數(shù)，選擇traingdm（）的訓(xùn)練方法以及l(fā)earngdm（）的學(xué)習(xí)方法，針對(duì)輸入的樣本＜X，H＞進(jìn)行訓(xùn)練，利用mse（）均方差來評(píng)價(jià)誤差。利用train（）函數(shù)進(jìn)行訓(xùn)練，并利用sim（）函數(shù)進(jìn)行結(jié)果仿真。

4.3 實(shí)驗(yàn)結(jié)果分析

通過采用Matlab神經(jīng)網(wǎng)絡(luò)工具箱中的與BP網(wǎng)絡(luò)有關(guān)的函數(shù)對(duì)樣本數(shù)據(jù)進(jìn)行訓(xùn)練，使得預(yù)測(cè)輸出盡可能接近目標(biāo)輸出，在訓(xùn)練的過程中選擇一部分作為訓(xùn)練樣本，一部分作為測(cè)試樣本。其中，目標(biāo)輸出結(jié)果如圖4所示，經(jīng)過神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型預(yù)測(cè)出的11個(gè)過程的結(jié)果如表5所示。

表4 目標(biāo)輸出結(jié)果

通過式（4），計(jì)算出基于ANN的線程劃分預(yù)測(cè)模型對(duì)這11個(gè)過程的預(yù)測(cè)精度值，分別是0.8417，0.9411，0.6383，0.8354，0.7402，0.941，0.3414，0.2407，0.9193，0.4345，0.8401。平均的預(yù)測(cè)精度為（0.8417+0.9411+0.6383+0.8354+0.7402+0.941+0.3414+0.2407+0.9193+0.4345+0.8401）/11=0.701245。圖5顯示出了11個(gè)過程的預(yù)測(cè)精度值和平均值。

圖5 11個(gè)過程的預(yù)測(cè)精度值

基于ANN的線程劃分預(yù)測(cè)模型為測(cè)試過程產(chǎn)生劃分方案以后，應(yīng)用劃分方案指導(dǎo)Prophet對(duì)該過程進(jìn)行線程劃分成為要解決的問題。表4可以看出，預(yù)測(cè)輸出是一個(gè)五維向量H=＜Dt，TsL，TsU，SdL，SdU＞ 的值。利用向量中的5個(gè)值替換劃分中的具體閾值，從而達(dá)到指導(dǎo)劃分的目的。為了反映性能提升的程度，用式（5）計(jì)算各個(gè)基準(zhǔn)程序的性能增長(zhǎng)率，如圖6所示。

圖6 性能增長(zhǎng)率

由圖6可以看出，與傳統(tǒng)的方法相比，基于ANN線程劃分預(yù)測(cè)模型預(yù)測(cè)結(jié)果指導(dǎo)劃分后使Olden基準(zhǔn)測(cè)試集的增長(zhǎng)率變化范圍由1.00%到11.8%。實(shí)驗(yàn)數(shù)據(jù)顯示，本文的預(yù)測(cè)模型能產(chǎn)生出更優(yōu)的劃分方案，使得指導(dǎo)后的過程劃分獲得更好的加速比提升。

5 結(jié)語(yǔ)

本文提出，驗(yàn)證和應(yīng)用了一種基于人工神經(jīng)網(wǎng)絡(luò)的線程劃分預(yù)測(cè)模型。該文主要?jiǎng)?chuàng)新在于：1）利用人工神經(jīng)網(wǎng)絡(luò)非線性學(xué)習(xí)能力從樣本集中學(xué)習(xí)線程劃分知識(shí)，并預(yù)測(cè)未知程序的劃分方案；2）用向量表達(dá)程序特征和線程劃分方案，利于預(yù)測(cè)模型的學(xué)習(xí)；3）本文的預(yù)測(cè)模型和Prophet線程劃分平臺(tái)通過共享文件方式傳遞預(yù)測(cè)結(jié)果，從而在不影響Prophet正常運(yùn)行的情況下，實(shí)現(xiàn)了預(yù)測(cè)結(jié)果指導(dǎo)Prophet線程劃分過程的目的。實(shí)驗(yàn)證明了該文提出的預(yù)測(cè)模型能夠?qū)W習(xí)樣本集劃分知識(shí)，為測(cè)試程序生成劃分方案，實(shí)現(xiàn)了對(duì)該程序的自動(dòng)和有效劃分。