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

（中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230026）

0 概述

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

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

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

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

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

2）與現(xiàn)有從核計(jì)算庫存在兼容問題。神威眾核平臺上的應(yīng)用程序中往往需要調(diào)用從核計(jì)算庫，而從核計(jì)算庫通常會占用整個(gè)從核陣列，與運(yùn)行時(shí)系統(tǒng)產(chǎn)生沖突。這要求數(shù)據(jù)流運(yùn)行時(shí)系統(tǒng)不能夠長時(shí)間地占用從核。

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

1 研究背景

1.1 申威異構(gòu)眾核處理器

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

圖1 申威異構(gòu)眾核處理器體系結(jié)構(gòu)Fig.1 Shenwei heterogeneous many-core processor architecture

神威超算平臺采用異構(gòu)加速編程模型，如圖2所示，其平臺程序由主核代碼和從核代碼兩部分組成，其中：主核代碼運(yùn)行在運(yùn)算控制核心上，負(fù)責(zé)數(shù)據(jù)和任務(wù)的分配和管理（即啟動從核，調(diào)用從核代碼，等待從核隊(duì)列上的任務(wù)執(zhí)行完成）；從核代碼運(yùn)行在運(yùn)算核心上，實(shí)現(xiàn)對核心功能模塊（即可并行任務(wù)）的加速。

圖2 申威異構(gòu)加速編程Fig.2 Shenwei heterogeneous acceleration programming

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

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

1）難以產(chǎn)生足夠多的細(xì)粒度計(jì)算任務(wù)分配給眾多的計(jì)算核心。采用athread 編程屬于基于控制流的粗粒度任務(wù)分割，劃分的任務(wù)計(jì)算粒度較大。當(dāng)面對不規(guī)則任務(wù)時(shí)，任務(wù)難以劃分，且任務(wù)之間粒度差距較大，使得從核空閑，效率不高。

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

3）難以表達(dá)細(xì)粒度并行任務(wù)中的復(fù)雜數(shù)據(jù)依賴關(guān)系。一些非規(guī)則、數(shù)據(jù)依賴復(fù)雜的并行應(yīng)用程序，使用athread 編程難以表達(dá)細(xì)粒度任務(wù)之間的點(diǎn)對點(diǎn)的數(shù)據(jù)依賴關(guān)系。

1.2 Codelet 程序執(zhí)行模型

Codelet 程序執(zhí)行模型是一種細(xì)粒度的、任務(wù)驅(qū)動的并行程序執(zhí)行模型，支持在控制流機(jī)器上使用數(shù)據(jù)流模型組織計(jì)算［14-16］。

Codelet 執(zhí)行模型中最基本的概念稱為Codelet，即一些機(jī)器指令的集合或一段代碼片段，Codelet 是該執(zhí)行模型中的基本調(diào)度單位，是原子不可中斷的。每一個(gè)Codelet 包含一個(gè)依賴計(jì)數(shù)，表示該任務(wù)在執(zhí)行前需要完成的依賴任務(wù)。

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

圖3 Codelet 程序執(zhí)行模型Fig.3 Codelet program execution model

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

圖4 Codelet 抽象機(jī)器模型Fig.4 Codelet abstract machine model

1.3 相關(guān)研究

數(shù)據(jù)流因具有天然的并行性，可以更細(xì)粒度地表達(dá)程序，消除同步開銷。越來越多的科學(xué)計(jì)算以及大數(shù)據(jù)處理開始使用數(shù)據(jù)流模型［17］，同時(shí)也出現(xiàn)了很多基于數(shù)據(jù)流的并行編程模型。

SWARM［18］是基于Codelet 模型的 一個(gè)商業(yè)實(shí)現(xiàn)。與Codelet 不同的是它沒有TP 的概念。DARTS［13］是由特 拉華大 學(xué)CAPSL 開發(fā)的 完全基 于Codelet 模型的數(shù)據(jù)流運(yùn)行時(shí)系統(tǒng)，可以在現(xiàn)有的共享存儲模型的機(jī)器上運(yùn)行。盡管使用硬件與軟件結(jié)合可以達(dá)到更高的性能，但是為了節(jié)約開發(fā)時(shí)間和成本，DARTS 僅在現(xiàn)有的硬件上進(jìn)行軟件模擬，實(shí)現(xiàn)了動態(tài)的任務(wù)調(diào)度。通過面向?qū)ο蟮木幊谭绞?，用戶可以方便地使用DARTS 的編程接口，定義自己的 Codelet Graph，然后將 Codelet Graph 交 給DARTS，自動地完成調(diào)度和執(zhí)行，但只運(yùn)行在多核上。

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

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

AceMesh［22］是一個(gè) 針對網(wǎng) 格應(yīng)用、數(shù)據(jù)驅(qū)動的并行任務(wù)編程框架，其底層有AceMesh 任務(wù)調(diào)度系統(tǒng)保證任務(wù)依賴圖的執(zhí)行過程。它基于athread 庫設(shè)計(jì)了支持神威眾核平臺的版本，根據(jù)申威體系結(jié)構(gòu)加入層次任務(wù)隊(duì)列，支持主從任務(wù)協(xié)同調(diào)度，并對并行性和緩存重用進(jìn)行相關(guān)優(yōu)化。AceMesh 使用制導(dǎo)語句來表示程序中循環(huán)的并行區(qū)域。

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

2 面向異構(gòu)眾核架構(gòu)的數(shù)據(jù)流運(yùn)行時(shí)系統(tǒng)

本節(jié)主要介紹swTasklet 數(shù)據(jù)流編程和運(yùn)行時(shí)系統(tǒng)的設(shè)計(jì)，為用戶提供面向基于Codelet 數(shù)據(jù)流模型的編程接口，將并行程序表示為數(shù)據(jù)流風(fēng)格的細(xì)粒度并行任務(wù)，運(yùn)行時(shí)系統(tǒng)自動地完成數(shù)據(jù)流計(jì)算任務(wù)在申威從核陣列上動態(tài)、高并發(fā)的調(diào)度執(zhí)行。

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

為了在新一代申威眾核平臺上實(shí)現(xiàn)基于Codelet 模型的數(shù)據(jù)流運(yùn)行時(shí)系統(tǒng)，首先需要將Codelet 模型映射到眾核處理器上。

一個(gè)核組包含1 個(gè)結(jié)構(gòu)復(fù)雜的主核（控制核心）和64 個(gè)結(jié)構(gòu)簡單的從核（運(yùn)算核心）；核組可映射為Codelet 抽象機(jī)器模型中的集群，包含兩種負(fù)責(zé)不同功能的計(jì)算核，其中：主核映射為調(diào)度單元，主要負(fù)責(zé)任務(wù)的分配和調(diào)度，也包括管理從核隊(duì)列資源；從核負(fù)責(zé)任務(wù)計(jì)算，并映射為不完全的CU。使用主核分配、調(diào)度和管理從核中的計(jì)算任務(wù)可以有效實(shí)現(xiàn)單核組內(nèi)的主從動態(tài)并行。

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

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

因?yàn)閺暮说囊恍┙Y(jié)構(gòu)特點(diǎn)，在swTasklet 中從核并不映射成具有完整功能的CU，一部分功能需要主核來完成。將從核映射成一個(gè)完整的CU，即擁有完整獨(dú)立的Tasklet 任務(wù)調(diào)度功能，會產(chǎn)生以下兩個(gè)問題：

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

2）從核不完善的原子操作。將從核映射為CU，從核完成Tasklet 的計(jì)算任務(wù)之后，需要進(jìn)行同步操作，即通知其他的Tasklet 按照數(shù)據(jù)依賴關(guān)系對依賴計(jì)數(shù)進(jìn)行減1 操作。而依賴計(jì)數(shù)屬于共享數(shù)據(jù)結(jié)構(gòu)，因?yàn)榇嬖诙鄠€(gè)從核完成計(jì)算任務(wù)之后對同一個(gè)Tasklet 的依賴計(jì)數(shù)進(jìn)行減1 操作的情況，此時(shí)需要從核提供原子操作來保證數(shù)據(jù)一致性。然而從核上對原子操作的支持不完善且開銷較大。

2.2 swTasklet 運(yùn)行時(shí)系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)

swTasklet 運(yùn)行時(shí)系統(tǒng)主要負(fù)責(zé)任務(wù)的分配調(diào)度和任務(wù)之間的同步。整個(gè)系統(tǒng)分為兩層：第一層為用戶層，為數(shù)據(jù)流編程框架提供描述，創(chuàng)建可執(zhí)行任務(wù)的接口，用戶通過接口對應(yīng)用程序進(jìn)行數(shù)據(jù)流風(fēng)格的抽象，并將細(xì)粒度任務(wù)交給第二層——運(yùn)行時(shí)執(zhí)行層；第二層負(fù)責(zé)將已滿足數(shù)據(jù)依賴關(guān)系的計(jì)算任務(wù)分配給空閑的硬件資源，將滿足依賴關(guān)系的任務(wù)放入任務(wù)隊(duì)列，并隨之啟動從核完成計(jì)算任務(wù)。

2.2.1 前端接口設(shè)計(jì)

該運(yùn)行時(shí)系統(tǒng)主要用C++語言實(shí)現(xiàn)。用戶定義細(xì)粒度計(jì)算任務(wù)主要使用3 個(gè)基本的數(shù)據(jù)結(jié)構(gòu)：Task，Tasklet，CpeTasklet，其關(guān)系如圖6 所示。

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

Task 類是程序中所有任務(wù)的抽象基類，主要包含一個(gè)或多個(gè)細(xì)粒度Tasklet 計(jì)算任務(wù)及其所需要的上下文數(shù)據(jù)。它結(jié)合了Codelet 程序執(zhí)行模型中的TP 和Codelet，當(dāng)TP 創(chuàng)建時(shí)立即執(zhí)行一段Tasklet 任務(wù)。這種結(jié)合的設(shè)計(jì)能夠減少程序運(yùn)行過程中創(chuàng)建的Tasklet 數(shù)目，降低一定的時(shí)間開銷。

Tasklet 類對應(yīng)Codelet 程序執(zhí)行模型中的Codelet，是運(yùn)行時(shí)系統(tǒng)中的基本執(zhí)行和調(diào)度單元，一旦分配計(jì)算資源執(zhí)行即不可中斷。Tasklet 由依賴計(jì)數(shù)、執(zhí)行函數(shù)和同步函數(shù)三部分組成。依賴計(jì)數(shù)記錄該Tasklet 的任務(wù)依賴個(gè)數(shù)，執(zhí)行函數(shù)為其需要完成的計(jì)算任務(wù)，同步函數(shù)是指當(dāng)執(zhí)行函數(shù)完成后Tasklet 通知其下游的Tasklet 依賴計(jì)數(shù)減1。

CpeTasklet 類是Tasklet 的子類，用于定義既可以運(yùn)行在主核也可以運(yùn)行在從核上的Tasklet 計(jì)算任務(wù)。CpeTaskelet 的功能分為兩個(gè)部分：execute（）和synchornize（）。execute（）接口就是用來定義可以在主核或者從核上執(zhí)行的計(jì)算任務(wù)。用戶需要定義execute（）函數(shù)在主核和從核上兩個(gè)版本的代碼，且不包含同步操作，并針對各自的結(jié)構(gòu)特征進(jìn)行相應(yīng)的優(yōu)化。當(dāng)CpeTasklet 被調(diào)度執(zhí)行的時(shí)候，如果沒有空閑的從核可用，則運(yùn)行時(shí)系統(tǒng)會調(diào)用主核版本的execute（）代碼執(zhí)行。當(dāng)有空閑從核時(shí)，則運(yùn)行時(shí)系統(tǒng)會調(diào)用從核版本的execute（）代碼執(zhí)行。在從核完成計(jì)算任務(wù)后，由主核調(diào)用相應(yīng)CpeTasklet 的同步操作，即synchornize（），釋放相應(yīng)Tasklet 的依賴計(jì)數(shù)。

2.2.2 運(yùn)行時(shí)系統(tǒng)設(shè)計(jì)

運(yùn)行時(shí)系統(tǒng)負(fù)責(zé)任務(wù)的分配調(diào)度和執(zhí)行并啟動、管理從核。運(yùn)行時(shí)系統(tǒng)只運(yùn)行在主核上，不在從核上。從核只負(fù)責(zé)Tasklet 子類中的計(jì)算函數(shù)execute（）的執(zhí)行，不在LDM 中維護(hù)任何共享數(shù)據(jù)結(jié)構(gòu)或任務(wù)狀態(tài)。主核負(fù)責(zé)任務(wù)的分配和調(diào)度，以及維護(hù)從核的狀態(tài)。

1）主核運(yùn)行模式

主核主要負(fù)責(zé)任務(wù)的分配和調(diào)度。運(yùn)行時(shí)系統(tǒng)在主存中維護(hù)兩個(gè)任務(wù)隊(duì)列，分別對應(yīng)Task 和Tasklet。當(dāng)計(jì)算單元完成Tasklet 的計(jì)算任務(wù)后，主核完成Tasklet 的同步操作并將下游滿足依賴關(guān)系的任務(wù)添加到對應(yīng)任務(wù)隊(duì)列中，并釋放剛完成的Tasklet 計(jì)算任務(wù)所占用的硬件資源。運(yùn)行時(shí)循環(huán)檢查Task 任務(wù)隊(duì)列，將隊(duì)首任務(wù)取出并執(zhí)行，然后循環(huán)檢查Tasklet 任務(wù)隊(duì)列，將Tasklet 任務(wù)分配到計(jì)算資源上。

運(yùn)行時(shí)通過檢測Tasklet 狀態(tài)轉(zhuǎn)換來完成任務(wù)的調(diào)度執(zhí)行。首先，Tasklet 接受必要的參數(shù)后，進(jìn)入預(yù)備狀態(tài)，即實(shí)例化；然后，當(dāng)該Tasklet 的數(shù)據(jù)依賴滿足，就會進(jìn)入就緒狀態(tài)，并被壓入任務(wù)隊(duì)列。接著，分配給主核，主核完成Tasklet 的計(jì)算任務(wù)。最后，進(jìn)行同步操作，通知與其有數(shù)據(jù)依賴的Tasklet，表示數(shù)據(jù)已就緒，被通知的Tasklet 變?yōu)轭A(yù)備狀態(tài)，其運(yùn)行模式如圖7 所示。

圖7 swTasklet 主核運(yùn)行模式Fig.7 Master core run mode in swTasklet

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

2）主從核協(xié)作模式

由于體系結(jié)構(gòu)限制，在從核上無法實(shí)現(xiàn)完整功能的CU，需要主核一起參與協(xié)作完成。在編程接口上，swTasklet 將Tasklet 中計(jì)算操作和同步操作分離，從核只負(fù)責(zé)計(jì)算操作的執(zhí)行，而同步操作由主核完成。主核通過一個(gè)從核陣列監(jiān)測器（CpeMonitor）來實(shí)現(xiàn)對從核工作狀態(tài)和CpeTasklet 執(zhí)行狀態(tài)的管理。

CpeMonitor 為從核陣列中的每個(gè)從核設(shè)置4 種狀態(tài)：初始化，空閑，繁忙，完成。運(yùn)行時(shí)系統(tǒng)采取按需啟動策略，當(dāng)用戶向運(yùn)行時(shí)系統(tǒng)提交第一個(gè)Task任務(wù)時(shí)才開始進(jìn)行初始化操作。在運(yùn)行時(shí)系統(tǒng)初始化過程中，每個(gè)從核狀態(tài)被設(shè)置為初始化狀態(tài)。當(dāng)運(yùn)行時(shí)系統(tǒng)初始化完成后，每個(gè)從核的狀態(tài)轉(zhuǎn)換為空閑狀態(tài)。當(dāng)從任務(wù)隊(duì)列頂端取出就緒CpeTasklet任務(wù)時(shí)，調(diào)度器循環(huán)檢查從核狀態(tài)。當(dāng)從核狀態(tài)為空閑時(shí)，則將其狀態(tài)改變?yōu)榉泵Γ蹐D8 中步驟（1）］，并將該任務(wù)分配給從核異步執(zhí)行［圖8 中步驟（2）］，即CpeTasklet 類從核版本的execute（）函數(shù)［圖8 中步驟（3）］。計(jì)算完成后，由從核將運(yùn)行時(shí)系統(tǒng)中該從核的狀態(tài)變量置為完成態(tài)［圖8 中步驟（4）］。完成態(tài)指該從核上執(zhí)行的CpeTasklet 完成了計(jì)算操作，但是同步操作尚未執(zhí)行。當(dāng)調(diào)度器檢測到處于完成態(tài)的從核時(shí)，說明該從核上一個(gè)CpeTasklet 同步操作尚未完成。此時(shí)主核會執(zhí)行該CpeTasklet 的synchnorize（）函數(shù)［圖8 中步驟（5）］，進(jìn)行同步操作。同步操作可能產(chǎn)生依賴滿足的Tasklet，并將其添加到任務(wù)隊(duì)列中。執(zhí)行完同步操作后，調(diào)度器將任務(wù)隊(duì)列頂端的CpeTasklet 分配給該完成態(tài)的從核，并將其狀態(tài)改為繁忙。另外，當(dāng)任務(wù)循環(huán)結(jié)束時(shí)，調(diào)度器會檢測是否存在仍處于完成態(tài)的從核，如果存在，則執(zhí)行對應(yīng)CpeTasklet 的同步操作，并將從核狀態(tài)由完成轉(zhuǎn)換為空閑。

圖8 swTasklet 主從協(xié)同運(yùn)行模式Fig.8 Master-slave coordination run mode in swTasklet

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

從核每次最多處理一個(gè)CpeTasklet 的計(jì)算任務(wù)，并不維護(hù)緩沖隊(duì)列，原因主要有兩個(gè)：如果在主存上維護(hù)該隊(duì)列，從核的訪問代價(jià)會過大；也不能存放在LDM 中，因?yàn)長DM 容量過小。且該隊(duì)列是主核和從核共享的數(shù)據(jù)資源，需要使用并發(fā)隊(duì)列或者互斥鎖來解決一致性問題，對性能影響較大。所以從核一段時(shí)間內(nèi)最多處理一個(gè)計(jì)算任務(wù)，該計(jì)算任務(wù)由主核分配，采用生產(chǎn)者-消費(fèi)者模式。這樣調(diào)度開銷較小，當(dāng)任務(wù)較多時(shí)，每一個(gè)從核都能及時(shí)得到任務(wù)。

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

實(shí)驗(yàn)在新一代申威眾核處理器單核組上進(jìn)行。主核工作頻率為2.1 GHz，從核工作頻率為2.25 GHz。主存大小為16 GB，單個(gè)從核的LDM 大小為256 KB。在本節(jié)中，選取向量-向量加和NPB LU 程序用于驗(yàn)證swTasklet 數(shù)據(jù)流運(yùn)行時(shí)系統(tǒng)的有效性。編譯器使用系統(tǒng)提供的眾核基礎(chǔ)編譯器swg++，編譯選項(xiàng)都使用-O3，生成更高級優(yōu)化的可執(zhí)行代碼。

3.1 向量-向量加

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

圖9 是兩種并行編程模型在任務(wù)數(shù)量為64 時(shí)不同規(guī)模下向量-向量加實(shí)現(xiàn)的加速比。橫坐標(biāo)為向量的元素個(gè)數(shù)，縱坐標(biāo)為兩種并行版本相較于主核實(shí)現(xiàn)的加速比。當(dāng)數(shù)據(jù)量較小時(shí)，數(shù)據(jù)流框架實(shí)現(xiàn)的加速效果一般，此時(shí)主要開銷在運(yùn)行時(shí)系統(tǒng)的任務(wù)調(diào)度上。當(dāng)數(shù)據(jù)規(guī)模增大時(shí)，運(yùn)行時(shí)系統(tǒng)的調(diào)度開銷所占比例逐漸降低，加速效果越來越顯著，最高可超過athread 版本一倍。

圖9 任務(wù)數(shù)量為64 時(shí)不同規(guī)模下向量-向量加實(shí)現(xiàn)加速比Fig.9 The speedup of vector-vector add achieved with different scales and fixed task number 64

圖10 是兩種并行編程模型在任務(wù)數(shù)量不同時(shí)所實(shí)現(xiàn)的加速比。實(shí)驗(yàn)結(jié)果表明，大部分情況下，swTasklet 實(shí)現(xiàn)的加速比與athread 手動優(yōu)化相當(dāng)。

圖10 任務(wù)數(shù)量不同時(shí)向量-向量加實(shí)現(xiàn)加速比Fig.10 The speedup of vector-vector add achieves with different task numbers

3.2 NPB LU 程序

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

分別使用athread 和swTasklet 對LU 程序中的核心代碼進(jìn)行并行化。LU 程序的數(shù)據(jù)依賴關(guān)系相對比較復(fù)雜，數(shù)據(jù)流模型較fork-join 模型能夠更好地刻畫任務(wù)間的點(diǎn)對點(diǎn)依賴關(guān)系。使用athread 編程表達(dá)LU 程序的數(shù)據(jù)依賴關(guān)系，需要用到復(fù)雜的同步操作和設(shè)置共享數(shù)據(jù)結(jié)構(gòu)，在國產(chǎn)眾核架構(gòu)上實(shí)現(xiàn)復(fù)雜，且代碼可移植性較差。

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

圖11 上下三角系統(tǒng)中的數(shù)據(jù)依賴關(guān)系Fig.11 Data dependencies in the upper and lower triangular systems

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

圖12 fork-join 模型下LU 任務(wù)依賴關(guān)系Fig.12 LU task dependencies in fork-join model

在使用fork-join 模型表達(dá)LU 程序時(shí)，如圖12 所示，將整個(gè)三維系統(tǒng)（三層循環(huán)）表示成一個(gè)二維超平面，平面中每一個(gè)點(diǎn)依賴其下方和左方的任務(wù)；在表達(dá)時(shí)，整個(gè)程序從左下方的任務(wù)向右上方任務(wù)推進(jìn)，使用大同步來維護(hù)依賴關(guān)系，即每個(gè)迭代步完成斜線上的任務(wù)。而下一個(gè)迭代步的任務(wù)只能等待上一個(gè)迭代步的任務(wù)全部完成才能被分配執(zhí)行。

使用數(shù)據(jù)流模型表達(dá)LU 程序時(shí)，也使將三維系統(tǒng)表示成一個(gè)二維平面，如圖13 所示。但用點(diǎn)對點(diǎn)同步代替了大同步，每一個(gè)點(diǎn)都表示一個(gè)任務(wù)。當(dāng)某個(gè)任務(wù)完成時(shí)，就通知其上方和右方任務(wù)，被通知任務(wù)將依賴計(jì)數(shù)減1，當(dāng)依賴計(jì)數(shù)為0 時(shí)，即等待分配執(zhí)行，不需要等斜線上所有任務(wù)完成才被分配執(zhí)行。

圖13 數(shù)據(jù)流模型下LU 任務(wù)依賴關(guān)系Fig.13 LU task dependencies in dataflow model

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

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

圖14 LU 在不同算例規(guī)模下的實(shí)現(xiàn)加速比Fig.14 The realize speedup of LU achieves at different problem sizes

4 結(jié)束語

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