基於匹配矩陣的異構重構計算的性能分析方法
2023-04-23 14:50:46 1
專利名稱：基於匹配矩陣的異構重構計算的性能分析方法
技術領域：
本發明涉及一種異構重構計算的性能分析方法，尤其是涉及一種基於匹配矩陣的異構重構計算的性能分析方法。
背景技術：
傳統的以同構計算(Homogeneous Computing)為主要計算模式的高性能計算已經開始向異構計算(Heterogeneous Computing, HC)的方向轉變,例如「Roadrunner」和我國國防科技大學研製的「天河一號」。另一方面，可重構計算(Reconfigurable Computing,RC)也已經被引入到高性能計算中。可重構部件以其可配置特性提高了計算的靈活性和處理部件的利用率，以其空間並行執行的特點增強了計算的高效性，同時又降低了功耗。由此可見，包含有各種異構加速部件和可重構部件的異構重構計算(Heterogeneous & Reconfigurable Computing, HRC)是高性能計算發展的新趨勢。HRC具有HC和RC的所有優點如高效性、靈活性、高性價比、低功耗、穩定性、高容錯性和短開發周期等。但是HRC系統是否真的能夠實現應用的高效執行則需要進行性能評價。傳統上，高性能計算的性能分析方法有理論分析，模擬仿真，測試測量等[6-8]。理論分析方法是指對並行系統進行形式化建模，這些方法可以分為兩類，確定性和概率性形式。在確定性模型中，所有的量都是固定的。在概率性模型中，存在著不確定性和隨機變量。模擬是性能分析領域的一個被廣泛使用的技術。它提供了一個有效的方法來預測還沒有被生產出來的計算機系統的性能。也可以被用來驗證理論分析方法的正確性。模擬技術包括仿真技術，Monte Carlo模擬，追蹤驅動模擬，執行驅動模擬和離散時間模擬。性能測量技術包含兩種技術第一個技術是profiling，在程序運行時跟蹤基本的性能信息。程序的性能信息通常是在程序執行結束後就立即展示給用戶，可以顯示程序的執行時間在不同程序代碼之間的分布。第二個技術是跟蹤(tracing)。跟蹤技術維護了一個記錄程序所有活動細節的日誌文件。跟蹤通常會產生大量的跟蹤數據，特別是運行時間較長的程序。但是，跟蹤技術可以用來重建應用程式在運行時的行為。也可被用來評價由Profiling技術提供的性能信息。因此，跟蹤被認為是一個更通用的性能測量技術。這些現有的並行計算性能分析方法不再適用於HRC，主要存在以下問題當給定一個應用時，選擇怎樣體系結構的並行計算機？應用在某種體系結構下運行的性能如何？什麼樣的性能指標來衡量性能？怎樣得到性能數據？這些問題都是性能分析的目標和研究內容。對於具有計算形式靈活、應用與資源的高效匹配、可編程性、可移植性、穩定性、可擴展性和低功耗等多重分析標準的高效能計算，性能分析所涉及的內容也得到了擴展，同時也產生一系列問題。對HRC計算系統性能分析存在的問題(I)由於目前異構重構計算剛剛起步，還沒有一個現成的異構重構計算系統及其計算模型。
(2)沒有現成的性能分析技術可以對異構重構計算系統的性能進行分析和預測。現有的分析工具還不足以對異構重構計算系統進行分析。(3)選擇怎麼樣的性能指標來說明分析系統的性能。
發明內容
本發明的目的就是為了克服上述現有技術存在的缺陷而提供一種基於匹配矩陣的異構重構計算的性能分析方法。本發明的目的可以通過以下技術方案來實現一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，包括以下步驟 I)建立異構重構計算系統模型HRCS ；2)建立異構重構任務圖模型HR-DAG ；3)生成異構匹配矩陣Ma;4)生成重構耦合矩陣C。；5)通過調度算法來計算應用任務的執行完成時間，從來進行性能分析。所述的異構重構計算系統模型HRCS為HRCS = (Vp, Ep);其中，點集Vp = {Pl，p2,…，pM}表示系統中處理部件的集合；邊集Ep = Ie1, e2,…，eL}表示處理部件間鏈路的集合。所述的異構重構任務圖模型HR-DAG為HR-DAG= (VT, ET, w, D, H, R);其中，點集 Vt= It1J2,…，tN}表示子任務的集合；邊集Et= {e1；e2,,ej是子任務間的偏序關係集合;W表示子任務的計算量集合；D表示子任務間的通信量集合；H表示子任務執行的異構特徵集合；R表示子任務間通信的重構特徵集合。所述的異構匹配矩陣Ma = (Vij)nxm,其中Vij代表應用任務\在處理部件Pj上的執行速度，I彡i彡N，I彡j彡M。所述的重構耦合矩陣C。= (cu)K>a，其中cu表示任務間重構特徵&與拓撲結構tj之間的耦合度，且O彡Cij彡1，I彡i彡K，I彡j彡L，K為異構重構任務圖中邊的個數，L為拓撲結構類型的個數。所述的通過調度算法來計算應用任務的執行完成時間具體為利用異構匹配矩陣Ma將應用任務優化映射匹配到處理部件上，根據公式I :Tcomp(t,) = WiAij求出應用任務的執行時間，其中Wi為任務ti的計算量；利用重構耦合矩陣C。來指導系統拓撲結構的動態重構，並根據公式2 =Tcofflffl(ta, tb) = dab/(B*CiJ.)求出任務間的通信時間，其中dab為任務&和tb之間的通信量，B為系統的通信帶寬；循環直至所有的任務執行完畢，最後可計算出整個應用任務的完成時間。與現有技術相比，本發明具有以下優點(I)給出了異構計算，重構計算、異構重構計算的定義，以及異構、重構、高性能計算三者之間的相互關係；(2)建立了異構重構計算體系結構模型和異構重構應用任務HR-DAG圖模型，後者是對傳統DAG的擴展，通過增加應用任務異構特徵和通信重構特徵的描述，更加豐富和準確地表達了應用任務對計算和通信的需求；(4)定義了異構匹配矩陣Ma，描述不同類型應用任務在各種處理部件上執行效果的匹配程度；(5)定義了重構耦合矩陣C。，刻畫了處理部件間的通信鏈路滿足子任務對通信模式或拓撲結構需求的程度。
圖1為本發明的流程圖。
具體實施例方式下面結合附圖和具體實施例對本發明進行詳細說明。實施例異構重構計算系統HRCS是可能包含通用處理器CPU、專用加速部件(如GPU)和可重構部件(如FPGA)的新型高性能計算機系統，系統中的所有處理部件通過一個可編程的互連網絡進行連接，使得互連網絡的拓撲結構能夠適合應用任務的通信需求。為了開展對HRCS的性能分析，需要建立HRCS的系統模型，基於該模型可以進行任務執行時間、加速比、可擴展性、性能價格比等其它性能指標的分析。具體實施方案如下(1)把應用程式生成異構重構任務圖，並根據經驗數據得到任務圖中每個子任務的計算量和子任務之間的通信量，計算每個計算任務適合的計算部件和每條通信任務適合的互連網絡類型。任務圖中的節點表示為三元組(Whi),其中ti表示第i個任務，Wi表示任務&的計算量,Iii表示任務\的異構特徵；邊同樣表示為三元組(ej/dj/r」)，其中e」表示第j條通信邊，dj表示通信邊ej上的通信量，表示通信邊ej連接的兩個任務之間的通信特徵。(2)根據異構匹配矩陣生成任務圖中每個計算任務在不同處理部件上的計算時間，為每個計算任務選擇適合的處理部件。(3)根據重構耦合矩陣生成任務圖中的每個通信任務在不同互連網絡上的通信時間，為每個通信任務選擇適合的網際網路類型。(4)根據提出的基於度量矩陣的任務執行時間分析算法把任務圖中的計算任務和通信任務進行調度，安排每個任務所適合的處理部件，並根據通信任務的時機對可重構的互連網絡進行重構，以適合通信任務的通信，最後可得出整個異構重構任務圖的執行時間。
權利要求
1.一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，包括以下步驟 1)建立異構重構計算系統模型HR CS； 2)建立異構重構任務圖模型HR-DAG; 3)生成異構匹配矩陣Ma; 4)生成重構耦合矩陣C。； 5)通過調度算法來計算應用任務的執行完成時間，從來進行性能分析。
2.根據權利要求I所述的一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，所述的異構重構計算系統模型HRCS為 HRCS= (Vp, Ep);其中，點集Vp= {ρι，ρ2，…，pM}表示系統中處理部件的集合；邊集Ep=Ie1, e2,…，ej表示處理部件間鏈路的集合。
3.根據權利要求2所述的一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，所述的異構重構任務圖模型HR-DAG為 HR-DAG = (VT, Et, ff, D，H，R);其中，點集Vt = It1, t2，…，tN}表示子任務的集合；邊集ET= {e1；e2, ---,ej是子任務間的偏序關係集合;W表示子任務的計算量集合；D表示子任務間的通信量集合；Η表示子任務執行的異構特徵集合#表示子任務間通信的重構特徵隹A 口 O
4.根據權利要求3所述的一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，所述的異構匹配矩陣Ma = (Vu)NXM，其中代表應用任務ti在處理部件&上的執行速度，I ^ i ^ N, I ^ j ^ M0
5.根據權利要求4所述的一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，所述的重構耦合矩陣C。= (cu)K>a，其中Cu表示任務間重構特徵&與拓撲結構tj之間的耦合度，且O彡Cij彡1，I彡i彡K，I彡j彡L，K為異構重構任務圖中邊的個數，L為拓撲結構類型的個數。
6.根據權利要求5所述的一種基於匹配矩陣的異構重構計算的性能分析方法，其特徵在於，所述的通過調度算法來計算應用任務的執行完成時間具體為 利用異構匹配矩陣Ma將應用任務優化映射匹配到處理部件上，根據公式I :!；_(&)=WiAij求出應用任務的執行時間，其中Wi為任務ti的計算量；利用重構耦合矩陣C。來指導系統拓撲結構的動態重構，並根據公式2 =Tcofflffl(ta, tb) = dab/(B*Cij)求出任務間的通信時間，其中dab為任務ta和tb之間的通信量，B為系統的通信帶寬；循環直至所有的任務執行完畢，最後可計算出整個應用任務的完成時間。
全文摘要
本發明涉及一種基於匹配矩陣的異構重構計算的性能分析方法，包括以下步驟1)建立異構重構計算系統模型HRCS；2)建立異構重構任務圖模型HR-DAG；3)生成異構匹配矩陣Ma；4)生成重構耦合矩陣Co；5)通過調度算法來計算應用任務的執行完成時間，從來進行性能分析。與現有技術相比，本發明具有通過增加應用任務異構特徵和通信重構特徵的描述，更加豐富和準確地表達了應用任務對計算和通信的需求等優點。
文檔編號G06F9/50GK102890642SQ20111044043
公開日2013年1月23日 申請日期2011年12月23日 優先權日2011年12月23日
發明者曾國蓀, 王偉, 譚一鳴 申請人:同濟大學, 上海紅神信息技術有限公司