申威處理器上數據流運行時系統的設計與實現

張鵬飛，陳俊仕，鄭 重，沈沛祺，安 虹，許 樂

（中國科學技術大學 計算機科學與技術學院，合肥 230026）

0 概述

近年來，摩爾定律不斷放緩，通用處理器的性能增長受到了物理規律限制，如功耗、互連和設計復雜度等。隨著半導體工藝的發展接近物理極限，芯片開始朝專用化、多樣化方向發展，使得多核、眾核成為現代高性能計算系統的主流設計。眾核平臺的主要特點是單個芯片上集成了大量異構的計算核心，且具有多層次的片上存儲結構。為了充分利用片上的大量計算核心，提高多級存儲的訪存帶寬，提高應用于高性能計算平臺的編程效率和運行效率，工業界和學術界開發了眾多的并行編程模型。

早期的并行編程模型是基于fork-join 的多線程模式，也稱大同步模型［1］，如OpenMP［2］、OpenACC［3］、Cilk［4］、OmpSs［5］等，其本質上基于分治算法的思想：將應用中的計算任務分解成若干個相互獨立、并行執行的子任務，并分配給多線程異步執行；一段時間后，再對并行計算的所有或部分線程進行同步操作并等待合并各子任務的計算結果。不同線程在執行過程中處理任務的速度可能有較大差距，例如可并行子任務的劃分不均勻時，最慢的子任務（線程）就會成為性能瓶頸。為了解決粗粒度任務劃分帶來的同步等待問題，工業界和學術界又發展了基于異步任務的并行編程模型，如TBB［6］、DPC++［7］等，其可以進一步挖掘程序中的細粒度并行性，但依然采用join 同步方式，存在由同步帶來的性能損失。

基于數據流的并行編程以數據為中心，將并行應用表示成有向無環的數據流圖，其中節點表示具體計算，而邊表示數據流動和任務間的依賴關系，數據在邊上傳遞，由一個節點流向另一個節點。用這種更自然的風格來表示任務間關系，可以更好地挖掘程序中的細粒度并行性，充分消除同步帶來的等待開銷。在數據流抽象的數據流圖中，當某個節點的依賴關系被滿足時，其相應的計算任務即可被執行，提供了較高的并發度。節點所代表的任務采用異步執行和點對點通信方式［8-10］，可以解決計算資源間的負載均衡問題。當用戶使用數據流方式將應用依賴關系描述完成之后，由運行時系統自動處理程序計算順序、任務調度問題，減輕了程序員負擔。

新一代國產申威處理器采用主從核異構眾核架構，具有很高的峰值性能。該平臺主要提供基于傳統fork-join 執行模型的并行編程接口——athread，這需要用戶基于特定硬件結構進行手動的復雜調優，才能實現計算資源的充分利用和任務負載均衡劃分。數據流所具備的特性可以幫助解決新一代神威眾核平臺并行編程難的問題，充分挖掘不規則應用程序中的并行度，解決眾核計算資源間的負載均衡問題，提高硬件資源的利用率。Codelet 模型［11-12］是美國特拉華大學的高光榮教授團隊提出的一種基于數據流的、細粒度的程序執行模型。該模型已在通用多核平臺上有相關實現［13］，本文則關注于將Codelet 程序模型部署到眾核平臺，實現其上的數據流運行時系統及編程接口。在新一代申威眾核架構上實現基于Codelet 模型的并行編程運行時系統面臨如下問題：

1）從核對原子操作的支持不完善。Codelet 程序執行模型的基本調度和執行單元稱為Codelet。Codelet 之間依賴關系的同步需要用到原子操作，然而從核上對原子操作的支持并不完善且開銷較大。

2）與現有從核計算庫存在兼容問題。神威眾核平臺上的應用程序中往往需要調用從核計算庫，而從核計算庫通常會占用整個從核陣列，與運行時系統產生沖突。這要求數據流運行時系統不能夠長時間地占用從核。

針對上述問題，本文設計并實現了一個面向申威眾核架構的數據流運行時系統——swTasklet。用戶可通過其提供的編程接口，將并行程序表示為數據流風格的細粒度并行任務，自動地完成計算任務在從核陣列上高并發的調度執行。本文提出將從核上的Codelet 分離為純計算和同步操作兩個部分，由從核完成純計算部分，主核完成同步操作。由于從核不需要執行同步操作，對共享數據的操作維護在主存上，因此不需要原子操作的支持。相比于通用CPU 平臺上將每個計算核心映射為一個具有獨立的任務調度執行功能的計算單元（Computing Unit，CU），本文提出在眾核平臺上由主核完成從核數據流計算任務的調度執行。由主核將任務隊列中的任務動態分配給從核，不需要從核檢查任務隊列。由于從核不會被長時間地使用，因此不會與已有從核計算庫沖突。為了驗證swTasklet 的有效性，本文以NPB LU 程序和向量-向量為實例，采用swTasklet 編程接口對其重構。

1 研究背景

1.1 申威異構眾核處理器

新一代申威眾核處理器采用異構融合體系結構，采用片上陣列集群和分布式共享存儲融合的異構眾核體系結構，使用64 位自主研發的申威指令系統。申威處理器芯片由6 個核組構成，每個核組包括1 個主核（運算控制核心，MPE）和64 個從核（運算核心，CPE）。圖1 展示了申威異構眾核處理器的體系結構。

圖1 申威異構眾核處理器體系結構Fig.1 Shenwei heterogeneous many-core processor architecture

神威超算平臺采用異構加速編程模型，如圖2所示，其平臺程序由主核代碼和從核代碼兩部分組成，其中：主核代碼運行在運算控制核心上，負責數據和任務的分配和管理（即啟動從核，調用從核代碼，等待從核隊列上的任務執行完成）；從核代碼運行在運算核心上，實現對核心功能模塊（即可并行任務）的加速。

圖2 申威異構加速編程Fig.2 Shenwei heterogeneous acceleration programming

主核程序采用athread 加速線程庫的相關接口對并行任務進行管理。根據接口功能的不同，并行任務可在一個或多個從核上執行，主核可在從核運行期間執行其他任務。athread 加速線程庫屬于fork-join 并行執行模型，使用athread_spawn 接口啟動多個從核線程，在所有從核完成任務之后，再使用athread_join 接口等待所有從核線程完成。

申威處理器98%的計算性能來源于從核陣列，挖掘從核架構以充分利用計算資源十分重要。athread 編程采用fork-join 執行方式會產生以下3 個問題：

1）難以產生足夠多的細粒度計算任務分配給眾多的計算核心。采用athread 編程屬于基于控制流的粗粒度任務分割，劃分的任務計算粒度較大。當面對不規則任務時，任務難以劃分，且任務之間粒度差距較大，使得從核空閑，效率不高。

2）難以平衡異構計算單元間的任務負載。申威處理器上主核和從核陣列之間是異構的，計算能力、體系結構和指令集均不相同。需要使兩種計算單元獲得的任務匹配其運行速度，避免一者空閑一者繁忙的情況。而一個從核陣列需要執行的從核任務往往也并不相同，不同從核執行任務的速度差異會嚴重影響應用的加速。

3）難以表達細粒度并行任務中的復雜數據依賴關系。一些非規則、數據依賴復雜的并行應用程序，使用athread 編程難以表達細粒度任務之間的點對點的數據依賴關系。

1.2 Codelet 程序執行模型

Codelet 程序執行模型是一種細粒度的、任務驅動的并行程序執行模型，支持在控制流機器上使用數據流模型組織計算［14-16］。

Codelet 執行模型中最基本的概念稱為Codelet，即一些機器指令的集合或一段代碼片段，Codelet 是該執行模型中的基本調度單位，是原子不可中斷的。每一個Codelet 包含一個依賴計數，表示該任務在執行前需要完成的依賴任務。

在用Codelet 模型表示的應用程序中，一個Codelet 即表示一個計算任務，任務之間的依賴關系通過Codelet 之間的邊來表示，則Codelet 及其上下游的依賴關系可以構成一張數據流圖，稱為CDG（Codelet Graph）。為了實現更好的并發性，根據數據局部性和Codelet 所實現的功能等，將CDG 分成多個子CDG，每個子CDG 被分配給一個Threaded Procedure（TP），它充當CDG 及其Codelets 所需數據的容器，還包括輸入、輸出和Codelet 共享的數據，TP為Codelet 模型提供了二級并行性，如圖3 所示［13］。

圖3 Codelet 程序執行模型Fig.3 Codelet program execution model

Codelet 程序執行模型的執行和調度依賴于抽象機器模型，如圖4 所示。該抽象機器模型描述了Codelet 模型如何在硬件層進行分配、存儲、調度和執行，由許多節點通過互連網絡連接在一起，一個節點中包括多個芯片，每個芯片以高速開關或總線互連。在一個芯片中存在一組有共享內存和本地內存的核心（core），稱為集群（cluster）。核心分為兩種：CU 和SU。CU 是結構簡單的計算核，每個cluster 上有若干個CU。CU 負責執行Codelet 以完成計算任務。SU 是結構較為復雜的調度核，每個cluster 上只有一個SU，SU 主要有3 個任務：1）管理cluster 內的所有硬件資源；2）負責在cluster 間調度TP；3）將處于就緒狀態的Codelet 根據一定的調度策略調度給合適的CU 來執行。

圖4 Codelet 抽象機器模型Fig.4 Codelet abstract machine model

1.3 相關研究

數據流因具有天然的并行性，可以更細粒度地表達程序，消除同步開銷。越來越多的科學計算以及大數據處理開始使用數據流模型［17］，同時也出現了很多基于數據流的并行編程模型。

SWARM［18］是基于Codelet 模型的 一個商業實現。與Codelet 不同的是它沒有TP 的概念。DARTS［13］是由特 拉華大 學CAPSL 開發的 完全基 于Codelet 模型的數據流運行時系統，可以在現有的共享存儲模型的機器上運行。盡管使用硬件與軟件結合可以達到更高的性能，但是為了節約開發時間和成本，DARTS 僅在現有的硬件上進行軟件模擬，實現了動態的任務調度。通過面向對象的編程方式，用戶可以方便地使用DARTS 的編程接口，定義自己的 Codelet Graph，然后將 Codelet Graph 交 給DARTS，自動地完成調度和執行，但只運行在多核上。

美國田納西大學的Jacket Dongarra 開發了數據流編程模型Parsec［19］，目的是通過可移植的編程模型有效地利用異構眾核系統。PaRSEC 由一個運行時和一組工具組成，用于構建、分析和預編譯任務DAG 的中間表示。PaRSEC 可以接受多種形式的任務圖表示，但其內部只有一種稱為JDF 的任務圖表示。它用與問題大小無關的方式表達應用程序的任務及其數據依賴關系。

Taskflow［20-21］是面向GPU 設計的一個輕量級并行和異構任務圖計算系統，其引入了圖內控制流，設計了一個新的條件任務模型。用戶可以在任務圖中加入控制流決策，是一個表達力良好的編程模型。它使用C++閉包設計任務圖編程模型，采用異構工作竊取（work-stealing）方法。

AceMesh［22］是一個 針對網 格應用、數據驅動的并行任務編程框架，其底層有AceMesh 任務調度系統保證任務依賴圖的執行過程。它基于athread 庫設計了支持神威眾核平臺的版本，根據申威體系結構加入層次任務隊列，支持主從任務協同調度，并對并行性和緩存重用進行相關優化。AceMesh 使用制導語句來表示程序中循環的并行區域。

SunwayFlow［23-24］是在神威·太湖之光上設計并實現的一種基于數據流的編程模型，其基于Codelet程序執行模型。該模型去除了TP 結構，設計和實現了數據流編程模型的運行時系統。但它將從核映射為完整功能的CU，導致從核硬件線程會被長期占用。從核代碼不可避免地需要調用高性能從核計算庫，需要顯式地將從核運行時停止，然后在調用完庫后再啟動從核陣列來完成運行時的后續工作。

2 面向異構眾核架構的數據流運行時系統

本節主要介紹swTasklet 數據流編程和運行時系統的設計，為用戶提供面向基于Codelet 數據流模型的編程接口，將并行程序表示為數據流風格的細粒度并行任務，運行時系統自動地完成數據流計算任務在申威從核陣列上動態、高并發的調度執行。

2.1 Codelet 模型到申威眾核的映射

為了在新一代申威眾核平臺上實現基于Codelet 模型的數據流運行時系統，首先需要將Codelet 模型映射到眾核處理器上。

一個核組包含1 個結構復雜的主核（控制核心）和64 個結構簡單的從核（運算核心）；核組可映射為Codelet 抽象機器模型中的集群，包含兩種負責不同功能的計算核，其中：主核映射為調度單元，主要負責任務的分配和調度，也包括管理從核隊列資源；從核負責任務計算，并映射為不完全的CU。使用主核分配、調度和管理從核中的計算任務可以有效實現單核組內的主從動態并行。

主核對應一個SU，負責Tasklet 任務隊列的調度，管理核組內的計算和存儲資源。從核相對主核結構簡單，存儲層次結構不適合維護復雜共享數據結構的一致性。如果從核被映射為SU，則需要頻繁地訪問主存，影響任務的執行速度，且SU 之前需要同步來進行任務調度，涉及共享數據結構，而維護共享數據結構需要使用互斥鎖，會嚴重影響并行效率。因此，每個從核對應一個CU，負責完成Tasklet 任務計算，如圖5 所示。CU 不維護任務隊列，只提供固定容量的Tasklet 任務緩沖。CU 的任務緩沖存儲在主存中，而不是存放在訪存延遲更短的LDM 上。

圖5 抽象機器模型映射Fig.5 Abstract machine model mapping

因為從核的一些結構特點，在swTasklet 中從核并不映射成具有完整功能的CU，一部分功能需要主核來完成。將從核映射成一個完整的CU，即擁有完整獨立的Tasklet 任務調度功能，會產生以下兩個問題：

1）與現有從核高性能計算庫的兼容問題。應用程序中不可避免地要調用BLAS 或者FFT 等高度優化的計算庫。采用SunwayFlow 的CU 映射方式，即任務緩沖放在LDM 中，會導致從核硬件線程被長期占用，從核硬件線程一直不停地檢查任務緩沖是否為空，如果有就一直執行。如果調用高性能計算庫，需要先手動將從核上的運行時暫停。調用完后，如果Tasklet 隊列中仍有任務，要再一次啟動從核陣列進行計算，這反而降低了用戶應用開發的效率。

2）從核不完善的原子操作。將從核映射為CU，從核完成Tasklet 的計算任務之后，需要進行同步操作，即通知其他的Tasklet 按照數據依賴關系對依賴計數進行減1 操作。而依賴計數屬于共享數據結構，因為存在多個從核完成計算任務之后對同一個Tasklet 的依賴計數進行減1 操作的情況，此時需要從核提供原子操作來保證數據一致性。然而從核上對原子操作的支持不完善且開銷較大。

2.2 swTasklet 運行時系統設計和實現

swTasklet 運行時系統主要負責任務的分配調度和任務之間的同步。整個系統分為兩層：第一層為用戶層，為數據流編程框架提供描述，創建可執行任務的接口，用戶通過接口對應用程序進行數據流風格的抽象，并將細粒度任務交給第二層——運行時執行層；第二層負責將已滿足數據依賴關系的計算任務分配給空閑的硬件資源，將滿足依賴關系的任務放入任務隊列，并隨之啟動從核完成計算任務。

2.2.1 前端接口設計

該運行時系統主要用C++語言實現。用戶定義細粒度計算任務主要使用3 個基本的數據結構：Task，Tasklet，CpeTasklet，其關系如圖6 所示。

圖6 swTasklet 主要類及其編程接口Fig.6 Main classes and their programming interfaces in swTasklet

Task 類是程序中所有任務的抽象基類，主要包含一個或多個細粒度Tasklet 計算任務及其所需要的上下文數據。它結合了Codelet 程序執行模型中的TP 和Codelet，當TP 創建時立即執行一段Tasklet 任務。這種結合的設計能夠減少程序運行過程中創建的Tasklet 數目，降低一定的時間開銷。

Tasklet 類對應Codelet 程序執行模型中的Codelet，是運行時系統中的基本執行和調度單元，一旦分配計算資源執行即不可中斷。Tasklet 由依賴計數、執行函數和同步函數三部分組成。依賴計數記錄該Tasklet 的任務依賴個數，執行函數為其需要完成的計算任務，同步函數是指當執行函數完成后Tasklet 通知其下游的Tasklet 依賴計數減1。

CpeTasklet 類是Tasklet 的子類，用于定義既可以運行在主核也可以運行在從核上的Tasklet 計算任務。CpeTaskelet 的功能分為兩個部分：execute（）和synchornize（）。execute（）接口就是用來定義可以在主核或者從核上執行的計算任務。用戶需要定義execute（）函數在主核和從核上兩個版本的代碼，且不包含同步操作，并針對各自的結構特征進行相應的優化。當CpeTasklet 被調度執行的時候，如果沒有空閑的從核可用，則運行時系統會調用主核版本的execute（）代碼執行。當有空閑從核時，則運行時系統會調用從核版本的execute（）代碼執行。在從核完成計算任務后，由主核調用相應CpeTasklet 的同步操作，即synchornize（），釋放相應Tasklet 的依賴計數。

2.2.2 運行時系統設計

運行時系統負責任務的分配調度和執行并啟動、管理從核。運行時系統只運行在主核上，不在從核上。從核只負責Tasklet 子類中的計算函數execute（）的執行，不在LDM 中維護任何共享數據結構或任務狀態。主核負責任務的分配和調度，以及維護從核的狀態。

1）主核運行模式

主核主要負責任務的分配和調度。運行時系統在主存中維護兩個任務隊列，分別對應Task 和Tasklet。當計算單元完成Tasklet 的計算任務后，主核完成Tasklet 的同步操作并將下游滿足依賴關系的任務添加到對應任務隊列中，并釋放剛完成的Tasklet 計算任務所占用的硬件資源。運行時循環檢查Task 任務隊列，將隊首任務取出并執行，然后循環檢查Tasklet 任務隊列，將Tasklet 任務分配到計算資源上。

運行時通過檢測Tasklet 狀態轉換來完成任務的調度執行。首先，Tasklet 接受必要的參數后，進入預備狀態，即實例化；然后，當該Tasklet 的數據依賴滿足，就會進入就緒狀態，并被壓入任務隊列。接著，分配給主核，主核完成Tasklet 的計算任務。最后，進行同步操作，通知與其有數據依賴的Tasklet，表示數據已就緒，被通知的Tasklet 變為預備狀態，其運行模式如圖7 所示。

圖7 swTasklet 主核運行模式Fig.7 Master core run mode in swTasklet

Tasklet 的計算任務可由主核完成，該情況適合計算任務數較多、計算量較少的情況，有效減少了任務上下文在主從核的切換。雖然從核陣列較多，但單個從核的計算能力比主核弱，當任務數量較少時，放在主核上，可以降低計算任務的執行時間，還可以有效節省不必要的調度開銷，包括將Tasklet 分配給空閑從核和釋放硬件資源等。當并行應用的并行度較低時，使用主核執行Tasklet 任務可有效覆蓋運行時的調度開銷，從而提升效能。

2）主從核協作模式

由于體系結構限制，在從核上無法實現完整功能的CU，需要主核一起參與協作完成。在編程接口上，swTasklet 將Tasklet 中計算操作和同步操作分離，從核只負責計算操作的執行，而同步操作由主核完成。主核通過一個從核陣列監測器（CpeMonitor）來實現對從核工作狀態和CpeTasklet 執行狀態的管理。

CpeMonitor 為從核陣列中的每個從核設置4 種狀態：初始化，空閑，繁忙，完成。運行時系統采取按需啟動策略，當用戶向運行時系統提交第一個Task任務時才開始進行初始化操作。在運行時系統初始化過程中，每個從核狀態被設置為初始化狀態。當運行時系統初始化完成后，每個從核的狀態轉換為空閑狀態。當從任務隊列頂端取出就緒CpeTasklet任務時，調度器循環檢查從核狀態。當從核狀態為空閑時，則將其狀態改變為繁忙［圖8 中步驟（1）］，并將該任務分配給從核異步執行［圖8 中步驟（2）］，即CpeTasklet 類從核版本的execute（）函數［圖8 中步驟（3）］。計算完成后，由從核將運行時系統中該從核的狀態變量置為完成態［圖8 中步驟（4）］。完成態指該從核上執行的CpeTasklet 完成了計算操作，但是同步操作尚未執行。當調度器檢測到處于完成態的從核時，說明該從核上一個CpeTasklet 同步操作尚未完成。此時主核會執行該CpeTasklet 的synchnorize（）函數［圖8 中步驟（5）］，進行同步操作。同步操作可能產生依賴滿足的Tasklet，并將其添加到任務隊列中。執行完同步操作后，調度器將任務隊列頂端的CpeTasklet 分配給該完成態的從核，并將其狀態改為繁忙。另外，當任務循環結束時，調度器會檢測是否存在仍處于完成態的從核，如果存在，則執行對應CpeTasklet 的同步操作，并將從核狀態由完成轉換為空閑。

圖8 swTasklet 主從協同運行模式Fig.8 Master-slave coordination run mode in swTasklet

主核和從核陣列以異步的方式運行，通過狀態變量進行通信。主核主動地查詢從核的狀態變量，進行任務分配或資源釋放；從核被動地等待任務，接受任務之后進行計算，計算完成后改變自己的狀態變量并繼續等待；對于主核和從核共享的一些數據結構，只由主核進行修改操作，避免使用互斥鎖等。從核被動地接受計算任務，不需要檢查任務隊列，從核不會被長時間地占用，從而不會與已有從核計算庫沖突。主核輪詢地檢查從核狀態變量，而不是每次從0 號從核開始檢查，這樣可避免一些從核一直在做任務，而一些從核不能獲得Tasklet 的情況，避免冗余檢查狀態變量。

從核每次最多處理一個CpeTasklet 的計算任務，并不維護緩沖隊列，原因主要有兩個：如果在主存上維護該隊列，從核的訪問代價會過大；也不能存放在LDM 中，因為LDM 容量過小。且該隊列是主核和從核共享的數據資源，需要使用并發隊列或者互斥鎖來解決一致性問題，對性能影響較大。所以從核一段時間內最多處理一個計算任務，該計算任務由主核分配，采用生產者-消費者模式。這樣調度開銷較小，當任務較多時，每一個從核都能及時得到任務。

3 實驗結果與分析

實驗在新一代申威眾核處理器單核組上進行。主核工作頻率為2.1 GHz，從核工作頻率為2.25 GHz。主存大小為16 GB，單個從核的LDM 大小為256 KB。在本節中，選取向量-向量加和NPB LU 程序用于驗證swTasklet 數據流運行時系統的有效性。編譯器使用系統提供的眾核基礎編譯器swg++，編譯選項都使用-O3，生成更高級優化的可執行代碼。

3.1 向量-向量加

向量-向量加操作是完全可并行的，計算任務之間無數據依賴，分別使用athread 庫和swTasklet 實現該算例。在該算例中，兩種并行方式的性能均不受同步操作的影響，因此可以體現出swTasklet 運行時調度的開銷。本實驗將數據規模為N的計算分成M個子任務，每個任務的計算量相同。athread 版本和swTasklet 版本均通過DMA 將任務所需數據讀取到從核LDM 中。

圖9 是兩種并行編程模型在任務數量為64 時不同規模下向量-向量加實現的加速比。橫坐標為向量的元素個數，縱坐標為兩種并行版本相較于主核實現的加速比。當數據量較小時，數據流框架實現的加速效果一般，此時主要開銷在運行時系統的任務調度上。當數據規模增大時，運行時系統的調度開銷所占比例逐漸降低，加速效果越來越顯著，最高可超過athread 版本一倍。

圖9 任務數量為64 時不同規模下向量-向量加實現加速比Fig.9 The speedup of vector-vector add achieved with different scales and fixed task number 64

圖10 是兩種并行編程模型在任務數量不同時所實現的加速比。實驗結果表明，大部分情況下，swTasklet 實現的加速比與athread 手動優化相當。

圖10 任務數量不同時向量-向量加實現加速比Fig.10 The speedup of vector-vector add achieves with different task numbers

3.2 NPB LU 程序

本節以NPB（NAS Parallel Benchmarks）中的LU程序為例來驗證并行編程框架的有效性，它被廣泛應用于CFD 模擬。LU 程序基于對稱超松弛（SSOR）迭代法來求解一個三維系統。該系統由三維形式的Navier-Stokes 方程有限差分離散化產生，并將該三維系統分解為一個下三角系統和一個上三角系統，最終得到的結果是5 個非線性偏微分方程的數值解［25］。

分別使用athread 和swTasklet 對LU 程序中的核心代碼進行并行化。LU 程序的數據依賴關系相對比較復雜，數據流模型較fork-join 模型能夠更好地刻畫任務間的點對點依賴關系。使用athread 編程表達LU 程序的數據依賴關系，需要用到復雜的同步操作和設置共享數據結構，在國產眾核架構上實現復雜，且代碼可移植性較差。

在LU 程序求解過程中，首先形成下三角形和對角線系統（JACLD 函數）并求解（BLTS 函數），然后是上三角系統（JACU 函數和BUTS 函數），最后再對結果更新（ADD）。在求解方程組時，（i，j，k）處的解依賴于（i+e，j，k）處的解（i，j+e，k）和（i，j，k+e）。對于三維系統中的每一個網格點，所完成的計算任務就是一次LU 分解再加上一次迭代更新工作，其依賴關系如圖11 所示。

圖11 上下三角系統中的數據依賴關系Fig.11 Data dependencies in the upper and lower triangular systems

可以將整個三維系統看成一個問題規模為N×N×N的三維空間。N是每一維方向上網格點的數目，而每一個網格點都表現為一個5×5 的矩陣。對于所有的三維格點來說，上下三角系統的構造是可以同時進行的，但是每一網格點的求解存在前驅后繼的關系，且需要用到其臨近的3 個點的解。以下三角系統求解為例，圖12 是三維網格的側視圖，也可以看成是整個三維系統的計算依賴圖，其中每個任務包含了垂直方向上的N個網格點。共有三層循環，循環方向為k-i-j；在此任務劃分下，任務粒度為中間的i層循環，每個任務當依賴關系滿足時，即被分配到空閑從核上進行k層循環的計算任務。當左下角的任務計算完成后，它會通知相鄰的任務，并激活該任務。可以看出，在任務的調度、分配和執行過程中，滿足依賴關系且可并行的任務數量先逐漸增大然后減小。在運行時系統工作的開始和結束階段，任務數量較少。上三角系統的計算和下三角系統類似，只不過依賴順序相反。

圖12 fork-join 模型下LU 任務依賴關系Fig.12 LU task dependencies in fork-join model

在使用fork-join 模型表達LU 程序時，如圖12 所示，將整個三維系統（三層循環）表示成一個二維超平面，平面中每一個點依賴其下方和左方的任務；在表達時，整個程序從左下方的任務向右上方任務推進，使用大同步來維護依賴關系，即每個迭代步完成斜線上的任務。而下一個迭代步的任務只能等待上一個迭代步的任務全部完成才能被分配執行。

使用數據流模型表達LU 程序時，也使將三維系統表示成一個二維平面，如圖13 所示。但用點對點同步代替了大同步，每一個點都表示一個任務。當某個任務完成時，就通知其上方和右方任務，被通知任務將依賴計數減1，當依賴計數為0 時，即等待分配執行，不需要等斜線上所有任務完成才被分配執行。

圖13 數據流模型下LU 任務依賴關系Fig.13 LU task dependencies in dataflow model

在本實驗中，NPB 提供了5 種問題規模大小，分別 是S（12×12×12）、W（33×33×33）、A（64×64×64）、B（102×102×102）和C（162×162×162），每個數字是三維系統每一維方向上網格點的數目。在LU 分解中，主要的計算開銷在計算上三角系統和下三角系統中，即將JACLD、BLTS、JACU 和BUTS 4 個函數任務抽象成上述數據流圖形式，通過少量接口，將任務交給運行時系統。同時，通過athread 接口對4 個函數進行并行加速，區別于數據流編程模型，任務的分配調度需要手動完成，但算法并不改變。兩種實現方法的從核實現采用相同的優化方法，如DMA 等，本文比較他們相較于主核單線程版本所達到的加速比。

由圖14 可知，當算例規模較小時，athread 版本達到的加速比高于swTasklet 實現，這是因為當計算量和任務量較小時，任務在數據流實現中會被逐個調度到從核上，而在athread 實現中，可并行的任務會被一起預取到從核陣列上，節省了調度開銷；而當規模增大時，任務較多，數據流運行時調度可以將大量任務更有效地分配給硬件資源運行，并有效平衡任務負載。當某個從核空閑，且任務隊列有待執行任務時，即可立即分配執行，而athread 實現版本需要整個從核隊列在某一點進行同步，然后才能進行下一次并行任務的預取和運行。實驗結果表明，使用規模為B 和C 的數據集時，手動實現版本均加速13.28 倍，swTasklet 版本分別加速14.2 和15.4 倍。在C 規模下，swTasklet 版本比athread 版本快16%。由于athread 版本屬于高度調優的手動優化版本，充分利用了從核陣列的計算資源，而swTasklet 與其計算性能相近，證明了swTasklet 的高效性。

圖14 LU 在不同算例規模下的實現加速比Fig.14 The realize speedup of LU achieves at different problem sizes

4 結束語

本文設計并實現了新一代申威眾核處理器上基于Codelet 數據流模型的運行時系統——swTasklet。用戶可通過該系統提供的編程接口，將應用程序重構成基于數據流圖執行方式的細粒度并行任務，交給運行時系統自動地完成任務的高并發執行和調度。本文將Codelet 機器模型中的CU 在功能上進一步細化，使主從核協作完成數據流計算任務的調度執行，解決了運行時與從核庫的兼容問題，避免了從核執行開銷較大的原子操作。實驗證明了數據流運行時系統的有效性，采用swTasklet 提供的編程接口能夠實現比athread 更高的執行效率。在未來工作中，將進一步完善該運行時系統，提高其性能和可用性，并將swTasklet 數據流運行時系統擴展到多核組上，設計性能開銷更小的任務調度策略，支持使用多從核執行的計算任務。