基于人工神經網絡的線程數據加速劃分?

盛紅雷 賈 崟

（1.南京南瑞集團公司信息通信技術分公司 南京 210000）（2.國網冀北電力有限公司 北京 100054）

1 引言

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

本文提出一種基于人工神經網絡的線程劃分預測模型。基于訓練程序的特征信息和最優劃分方案，預測模型按照指定的精度進行訓練。訓練好的模型根據測試程序的特征信息預測出劃分方案。本文中ANN模型和Prophet自動劃分編譯器相互配合，使用Olden基準程序集進行離線學習和指導劃分。

2 線程數據加速劃分模型

2.1 基本思想

對于TLS自動劃分過程，本文使用Prophet編譯器完成。ANN預測模型通過寫讀（write and read）預測結果文件和Prophet關聯［10］，從樣本集中學習線程劃分的知識，并根據待測過程的特征信息，預測該過程的劃分方案，并將該方案反饋給Prophet的劃分遍，從而實現Prophet對該過程有較優的劃分。圖1給出了ANN預測模型和Prophet關系圖。箭頭1代表ANN預測模型產生的劃分方案反饋給Prophet過程，箭頭2代表Prophet劃分過程為ANN預測模型提供劃分方案生成依據。

圖1 ANN預測模型和Prophet關系圖

2.2 整體框架

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

圖2 線程劃分預測框架

2.3 特征提取

特征提取是由Prophet的剖析器Pro_ler來實現。Pro_ler首先分析基準程序的輸入特征，并依據輸入特征構造輸入訓練集。Pro_ler通過多次預執行程序捕獲程序的剖析信息，工作流程如圖3所示，當執行一個程序指令時，首先對指令類型做出判斷，當指令是循環指令時，記錄循環的迭代次數D，動態指令數M，循環個數C。當指令為非循環指令時，記錄基本塊個數N和動態指令數M，和分支個數P。最終，ANN模型選取程序關鍵路徑上的5個特征：基本塊個數N，動態指令數M ，分支指令個數P，循環個數C，函數調用次數E，并由這5個特征組成特征向量 X=＜N，M，P，C，E＞。

圖3 程序剖析器Profiler

2.4 劃分方案

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

表1 線程劃分最具影響的五個閾值

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

3 實驗準備

3.1 實驗配置

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

表2 Prophet參數配置和取值

表3 ANN預測模型的參數配置和取值

3.2 評價指標

為了對ANN線程劃分預測模型進行有效評價，從兩個方面進行評價，分別是預測精度和性能增長率。其中，預測精度如圖4給出了預測精度的計算圖。

圖4 預測精度計算圖

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

其中，‖‖a，‖‖b和‖‖c分別代表線段a，b，c的長度。假設點1的坐標為 (Dt，TsL，TsU，SdL，SdU)，點 2 的坐標為 (Dt+δ1，TsL+δ2，TsU+δ3，SdL+δ4，SdU+δ5)，其中，δ1，δ2，δ3，δ4，δ5分別表示預測的五維輸出和原有目標輸出之間對應的差值。則

利用式（4），我們對基于ANN線程劃分預測模型的預測精度進行定量評估。為了定量分析，定義性能增長率為

其中，C表示預測結果指導程序劃分后獲得的加速比；O表示原有基于啟發式規則線程劃分［15］取得的加速比；R代表性能增長率。

4 實驗分析

4.1 加載樣本集

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

4.2 建立模型

為了建立ANN預測模型，首先確定網絡的各層結構，并初始化網絡。根據樣本特征向量X的維度確定神經網絡的輸入層含有5個神經元，而劃分方案H的維度確定網絡輸出層含有5個神經元。利用Matlab中的new_（）函數，選擇traingdm（）的訓練方法以及learngdm（）的學習方法，針對輸入的樣本＜X，H＞進行訓練，利用mse（）均方差來評價誤差。利用train（）函數進行訓練，并利用sim（）函數進行結果仿真。

4.3 實驗結果分析

通過采用Matlab神經網絡工具箱中的與BP網絡有關的函數對樣本數據進行訓練，使得預測輸出盡可能接近目標輸出，在訓練的過程中選擇一部分作為訓練樣本，一部分作為測試樣本。其中，目標輸出結果如圖4所示，經過神經網絡預測模型預測出的11個過程的結果如表5所示。

表4 目標輸出結果

通過式（4），計算出基于ANN的線程劃分預測模型對這11個過程的預測精度值，分別是0.8417，0.9411，0.6383，0.8354，0.7402，0.941，0.3414，0.2407，0.9193，0.4345，0.8401。平均的預測精度為（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個過程的預測精度值和平均值。

圖5 11個過程的預測精度值

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

圖6 性能增長率

由圖6可以看出，與傳統的方法相比，基于ANN線程劃分預測模型預測結果指導劃分后使Olden基準測試集的增長率變化范圍由1.00%到11.8%。實驗數據顯示，本文的預測模型能產生出更優的劃分方案，使得指導后的過程劃分獲得更好的加速比提升。

5 結語

本文提出，驗證和應用了一種基于人工神經網絡的線程劃分預測模型。該文主要創新在于：1）利用人工神經網絡非線性學習能力從樣本集中學習線程劃分知識，并預測未知程序的劃分方案；2）用向量表達程序特征和線程劃分方案，利于預測模型的學習；3）本文的預測模型和Prophet線程劃分平臺通過共享文件方式傳遞預測結果，從而在不影響Prophet正常運行的情況下，實現了預測結果指導Prophet線程劃分過程的目的。實驗證明了該文提出的預測模型能夠學習樣本集劃分知識，為測試程序生成劃分方案，實現了對該程序的自動和有效劃分。