眾核多態(tài)實(shí)時計(jì)算模型設(shè)計(jì)及應(yīng)用

羅眉，周興社，張凱龍，胡英英

(1.西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710129；2.西安高科技研究所，陜西西安 710025)

眾核多態(tài)實(shí)時計(jì)算模型設(shè)計(jì)及應(yīng)用

羅眉1，2，周興社1，張凱龍1，胡英英1

(1.西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710129；2.西安高科技研究所，陜西西安 710025)

為了滿足復(fù)雜嵌入式實(shí)時系統(tǒng)中應(yīng)用任務(wù)對計(jì)算的需求，提高計(jì)算有效性，將多態(tài)實(shí)時計(jì)算的概念引入眾核架構(gòu)中，設(shè)計(jì)了一種眾核多態(tài)實(shí)時計(jì)算模型。提出了計(jì)算態(tài)的概念，并設(shè)計(jì)了三種計(jì)算態(tài)以適用于不同類型任務(wù)。仿真測試結(jié)果表明，在較低通信衰減的情況下，此眾核多態(tài)實(shí)時計(jì)算模型使應(yīng)用任務(wù)在以不同計(jì)算態(tài)進(jìn)行計(jì)算時均可獲得較高的加速比，從而提高了系統(tǒng)對計(jì)算量大的應(yīng)用任務(wù)的響應(yīng)速度。

多態(tài)計(jì)算，眾核，計(jì)算態(tài)，計(jì)算模型

復(fù)雜嵌入式實(shí)時系統(tǒng)具有多種應(yīng)用任務(wù)，多應(yīng)用任務(wù)對嵌入式高效能計(jì)算提出了更高需求。通用計(jì)算使系統(tǒng)響應(yīng)時間無法滿足大計(jì)算量任務(wù)的實(shí)時性需求。因此，應(yīng)依據(jù)應(yīng)用任務(wù)及其需求的具體變化，設(shè)計(jì)面向應(yīng)用驅(qū)動的計(jì)算模型，使其能夠?qū)崟r、動態(tài)地選擇合適的計(jì)算模式。

1　相關(guān)工作

目前，在飛機(jī)、智能機(jī)器人等復(fù)雜嵌入式應(yīng)用領(lǐng)域，越來越多地采用了眾核處理機(jī)。眾核處理機(jī)適用于密集計(jì)算，國內(nèi)外對眾核處理機(jī)的研究主要集中在體系結(jié)構(gòu)、資源調(diào)度、CPU＋GPU異構(gòu)系統(tǒng)相關(guān)技術(shù)以及眾核應(yīng)用模型［1-4］的研究。

多態(tài)計(jì)算技術(shù)［5］是指在復(fù)雜嵌入環(huán)境下支持系統(tǒng)多級資源重構(gòu)的技術(shù)，用來反映一種計(jì)算系統(tǒng)軟、硬件結(jié)構(gòu)和計(jì)算模式適應(yīng)任務(wù)需求變化的思想。目前國內(nèi)外對多態(tài)技術(shù)的研究熱點(diǎn)主要集中于體系結(jié)構(gòu)、資源配置和任務(wù)調(diào)度等方面［6-8］。近年來的研究結(jié)果表明，適應(yīng)不斷變化應(yīng)用需求的一種先進(jìn)模式是建立多態(tài)計(jì)算模式。文獻(xiàn)［8］提出了一種用戶滿意度驅(qū)動的多態(tài)計(jì)算模型，并將多態(tài)計(jì)算與眾核相結(jié)合，但仍是圍繞通用移動計(jì)算而開展的研究。目前，面向復(fù)雜嵌入式實(shí)時系統(tǒng)應(yīng)用，且將多態(tài)計(jì)算技術(shù)和眾核相結(jié)合的研究相對較少。因此，本文結(jié)合眾核處理機(jī)的特點(diǎn)，將多態(tài)計(jì)算的概念引入到眾核架構(gòu)中，針對復(fù)雜嵌入式實(shí)時系統(tǒng)應(yīng)用，建立了眾核多態(tài)實(shí)時計(jì)算模型，并從邏輯上實(shí)現(xiàn)了眾核的3種計(jì)算態(tài)，為快速響應(yīng)不同應(yīng)用任務(wù)提供了有效支撐。

2　眾核多態(tài)實(shí)時計(jì)算模型

在嵌入式實(shí)時系統(tǒng)中，主要有3類任務(wù)：一類任務(wù)是計(jì)算復(fù)雜，需要占用系統(tǒng)全部可用資源以保證其時間約束；一類任務(wù)可獨(dú)立并行執(zhí)行；還有一類任務(wù)可被分解成若干個具有前驅(qū)后繼的子任務(wù)執(zhí)行。因此根據(jù)嵌入式實(shí)時系統(tǒng)應(yīng)用特點(diǎn)，本文構(gòu)建了一種眾核多態(tài)實(shí)時計(jì)算模型，描述了眾核資源上的系統(tǒng)服務(wù)軟件及任務(wù)集，分為眾核多態(tài)任務(wù)模型和眾核多態(tài)實(shí)時服務(wù)模型。

2.1眾核多態(tài)任務(wù)模型

2.1.1相關(guān)概念

眾核多態(tài)任務(wù)模型負(fù)責(zé)接收應(yīng)用任務(wù)，并按其計(jì)算需求分為單任務(wù)、多任務(wù)分區(qū)、多任務(wù)流式3種計(jì)算模式。為有效描述眾核多態(tài)任務(wù)模型，引入如下相關(guān)定義。

定義1(計(jì)算態(tài))指眾核處理單元的核資源在不同組織形式下所對應(yīng)的并行計(jì)算模式。

定義2(應(yīng)用任務(wù))應(yīng)用任務(wù)是系統(tǒng)的宏觀行為目標(biāo)。系統(tǒng)應(yīng)用任務(wù)集由Γ＝｛T1，T2，…，Tn｝表示，?Ti∈Γ稱為一個應(yīng)用任務(wù)。

定義3(多態(tài)計(jì)算任務(wù))眾核計(jì)算平臺管理和執(zhí)行的具體任務(wù)指多態(tài)計(jì)算任務(wù)，它們能夠運(yùn)行于眾核處理機(jī)，且有不同計(jì)算形態(tài)。系統(tǒng)計(jì)算任務(wù)集由~T＝｛PT1，PT2，…，PTm｝表示，?PTi∈~T稱為一個多態(tài)計(jì)算任務(wù)。公式(1)描述了多態(tài)計(jì)算任務(wù)相關(guān)屬性。

式中，PTID為計(jì)算任務(wù)號；PTpr為計(jì)算任務(wù)的優(yōu)先級，同一計(jì)算任務(wù)在不同應(yīng)用任務(wù)集中的優(yōu)先級由系統(tǒng)指派；PTtype為任務(wù)需要的計(jì)算態(tài)，PTtype＝0時表示眾核以單任務(wù)計(jì)算態(tài)工作，PTtype＝1時表示眾核以多任務(wù)分區(qū)計(jì)算態(tài)工作，PTtype＝2時表示眾核以多任務(wù)流式計(jì)算態(tài)工作；PT~I為任務(wù)輸入數(shù)據(jù)；PT~O為任務(wù)輸出數(shù)據(jù)。

2.1.2眾核單任務(wù)計(jì)算態(tài)

單任務(wù)計(jì)算態(tài)適用于計(jì)算復(fù)雜、時間約束強(qiáng)的應(yīng)用任務(wù)，將眾核運(yùn)算單元內(nèi)部的所有核資源同時分配給單一任務(wù)。單任務(wù)計(jì)算滿足：

2.1.3眾核分區(qū)計(jì)算態(tài)

分區(qū)計(jì)算態(tài)適用于多個相互獨(dú)立并行執(zhí)行的應(yīng)用任務(wù)。由于任務(wù)間相互獨(dú)立，對眾核資源進(jìn)行劃分時，會形成不同的分區(qū)，使各任務(wù)在不同的分區(qū)內(nèi)執(zhí)行。

2.1.4眾核流式計(jì)算態(tài)

流式計(jì)算態(tài)適用于關(guān)聯(lián)并行處理的應(yīng)用任務(wù)，任務(wù)之間由一組具有前驅(qū)后繼關(guān)系的子任務(wù)并行執(zhí)行，依據(jù)計(jì)算需求及全局優(yōu)化策略，將眾核資源劃分為多個分區(qū)，每個分區(qū)執(zhí)行一個子任務(wù)，各子任務(wù)間通過共享存儲機(jī)制實(shí)現(xiàn)數(shù)據(jù)的快速交換。

其中“·”表示用多個計(jì)算步組成一個計(jì)算任務(wù)。流式計(jì)算由多個這樣的計(jì)算任務(wù)組成，每個計(jì)算任務(wù)將輸入數(shù)據(jù)流Isti經(jīng)由m個計(jì)算步，最終產(chǎn)生輸出數(shù)據(jù)流Osti。式中“→”表示依賴關(guān)系，表示第b個計(jì)算步對第i個數(shù)據(jù)流的處理必須依賴于第a個計(jì)算步對第i個數(shù)據(jù)流的處理結(jié)果，即同一數(shù)據(jù)流必須依次執(zhí)行各個具有前驅(qū)后繼關(guān)系的計(jì)算步。

2.2眾核多態(tài)實(shí)時服務(wù)模型

眾核多態(tài)實(shí)時服務(wù)模型負(fù)責(zé)屏蔽底層硬件資源的異構(gòu)性，使得系統(tǒng)各組成部分之間可以無差別地進(jìn)行數(shù)據(jù)通信。同時，為應(yīng)用提供運(yùn)行時系統(tǒng)服務(wù)，有可用資源時通過通信接口進(jìn)行數(shù)據(jù)傳輸。

本文基于通信有限狀態(tài)機(jī)模型(communicating finite state machines，CFSM)［9］構(gòu)建了一種多態(tài)實(shí)時服務(wù)模型，其形式化描述如下：

圖1　基于CFSM的多態(tài)實(shí)時服務(wù)模型通信過程

圖中的阻塞發(fā)送方式是指發(fā)送方一直阻塞直到所要發(fā)送數(shù)據(jù)傳輸完成后返回，非阻塞發(fā)送是指發(fā)送方在給底層協(xié)議發(fā)送數(shù)據(jù)的指令后立即返回，真正的數(shù)據(jù)傳輸由底層協(xié)議完成。

3　仿真測試

仿真測試分為2個方面：①測試眾核多態(tài)任務(wù)模型的有效性；②測試眾核多態(tài)實(shí)時服務(wù)模型的通信效率。

3.1實(shí)驗(yàn)設(shè)置

1)眾核多態(tài)任務(wù)模型

眾核多態(tài)任務(wù)模型包含3種計(jì)算態(tài)，分別用于不同類型的應(yīng)用任務(wù)。以加速比為衡量依據(jù)，測試多態(tài)任務(wù)模型中3種計(jì)算態(tài)的有效性。

硬件環(huán)境為眾核控制單元采用2塊Intel Sandy-Bridge E5-2609的4核CPU，每塊CPU主頻為2.4 GHz，15M緩存，眾核計(jì)算單元采用基于Kepler K20架構(gòu)的GPU，時鐘頻率0.71 GHz，CUDA核心數(shù)2 496。

(1)單任務(wù)計(jì)算態(tài)：測試用例如表1所示。當(dāng)同一計(jì)算任務(wù)在計(jì)算規(guī)模增大時，分別記錄運(yùn)行在多核CPU和GPU上的計(jì)算時間，取加速比為多核CPU執(zhí)行時間/GPU執(zhí)行時間。

表1　單任務(wù)計(jì)算態(tài)測試用例

(2)多任務(wù)分區(qū)計(jì)算態(tài)：測試2個獨(dú)立的應(yīng)用任務(wù)，如表2所示，一個應(yīng)用任務(wù)包含6個計(jì)算任務(wù)，另一個應(yīng)用任務(wù)包含32個計(jì)算任務(wù)。為驗(yàn)證方便，計(jì)算任務(wù)的輸入輸出仍采用表1中的數(shù)據(jù)，當(dāng)計(jì)算規(guī)模變化時，測試多個計(jì)算任務(wù)并發(fā)執(zhí)行和分區(qū)執(zhí)行時間，取加速比為多任務(wù)并發(fā)時間/多任務(wù)分區(qū)執(zhí)行時間。

表2　多任務(wù)分區(qū)計(jì)算態(tài)測試用例

(3)多任務(wù)流式計(jì)算態(tài)：測試2個應(yīng)用任務(wù)，一個由3個計(jì)算任務(wù)組成，另一個由32個計(jì)算任務(wù)組成，如表3所示。為驗(yàn)證方便，計(jì)算任務(wù)的輸入輸出仍采用表1中的數(shù)據(jù)，記錄當(dāng)計(jì)算規(guī)模變化時，多任務(wù)串行執(zhí)行和多任務(wù)流式執(zhí)行時間，加速比為多任務(wù)串行執(zhí)行時間/多任務(wù)流式執(zhí)行時間。

表3　多任務(wù)流式計(jì)算態(tài)測試用例

2)眾核多態(tài)實(shí)時服務(wù)模型

多態(tài)實(shí)時服務(wù)模型的作用是實(shí)現(xiàn)應(yīng)用任務(wù)和硬件之間的通信交互，因此以通信接口的通信速率相比于理論峰值的衰減程度來測試多態(tài)實(shí)時服務(wù)性能。測試方法為使用1/5 000 s為時鐘周期，每次傳送4MB字節(jié)數(shù)據(jù)并接收到確認(rèn)信息后記錄1次所用的周期數(shù)，共傳輸128MB數(shù)據(jù)。通信速率理論峰值為1.25 Gbit/s。多態(tài)實(shí)時服務(wù)運(yùn)行在主控處理機(jī)上，采用Curtiss-Wright公司VPX6-185的PowerPC。

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

根據(jù)3.1的設(shè)置，得到眾核多態(tài)任務(wù)模型及多態(tài)實(shí)時服務(wù)模型測試結(jié)果，分別如圖1、圖2所示。

圖2　眾核多態(tài)任務(wù)模型測試結(jié)果

圖3　眾核多態(tài)實(shí)時服務(wù)模型測試結(jié)果

圖1顯示了眾核多態(tài)任務(wù)模型在以不同計(jì)算態(tài)工作時獲得的加速比，實(shí)驗(yàn)結(jié)果表明：

1)眾核工作于單任務(wù)計(jì)算態(tài)時，從圖1a)中看出，當(dāng)計(jì)算規(guī)模較小時，由于啟動GPU上的內(nèi)核需占用一定時間，因此和多核CPU相比，獲得的加速比較小，但隨著計(jì)算規(guī)模增大，采用GPU計(jì)算單個任務(wù)可取得較高的加速比。

2)眾核工作于多任務(wù)分區(qū)計(jì)算態(tài)時，從圖1b)中看出，當(dāng)任務(wù)數(shù)增多，計(jì)算規(guī)模增大，由于任務(wù)組中的某些計(jì)算任務(wù)占用了較多的計(jì)算資源，雖然不能達(dá)到最大的任務(wù)級并行，但在滿足系統(tǒng)負(fù)載的情況下，分區(qū)計(jì)算態(tài)可較好的適應(yīng)多個獨(dú)立任務(wù)需求，縮短計(jì)算時間，提高系統(tǒng)對多個任務(wù)的響應(yīng)速度。

3)眾核多任務(wù)流式計(jì)算態(tài)適應(yīng)于多個具有前驅(qū)后繼關(guān)系的任務(wù)，從圖1c)中可以看出，隨著任務(wù)計(jì)算規(guī)模增大，任務(wù)之間需要傳送數(shù)據(jù)和同步，采用流式計(jì)算，當(dāng)后續(xù)計(jì)算任務(wù)數(shù)據(jù)到達(dá)時，前驅(qū)計(jì)算任務(wù)已經(jīng)完成，該計(jì)算態(tài)不僅使GPU全局存儲器充分利用，也獲得了較高的加速比。

圖2表明，多態(tài)實(shí)時服務(wù)相對于系統(tǒng)接口的通信速率有一定的影響，但平均衰減在12%左右，能夠保持通信的高效性。

4　結(jié) 論

論文結(jié)合不同類型任務(wù)需求，提出了一種眾核多態(tài)實(shí)時計(jì)算模型及3種計(jì)算態(tài)，并對所設(shè)計(jì)的模型進(jìn)行了測試。測試結(jié)果表明，眾核多態(tài)實(shí)時計(jì)算模型能較好地適應(yīng)復(fù)雜嵌入式實(shí)時系統(tǒng)的應(yīng)用需求，實(shí)現(xiàn)快速計(jì)算，保證對不同類型任務(wù)的快速響應(yīng)。

［1］ Gibson D，Wood D A.Forwardflow：a Scalable Core for Power-Constrained CMPs［J］.ACM SIGARCH Computer Architecture News，2010，38(3)：14-25

［2］ 曹仰杰，錢德沛，伍衛(wèi)國，等.眾核處理器系統(tǒng)核資源動態(tài)分組的自適應(yīng)調(diào)度算法［J］.軟件學(xué)報(bào)，2012，23(2)：240-252

Cao YangJie，Qian Depei，Wu Weiguo，et al.Adaptive Scheduling Algorithm Based on Dynamic Core-Resource Partitions for Many-Core［J］.Journal of Software，2012，23(2)：240-252(in Chinese)

［3］ Anderson Boettge Pinheiro，F(xiàn)rancisco Heron de Carvalho Junior，Neemias Gabriel Pena Batista Arruda，et al.Fusion：Abstractions for Multicore/Manycore Heterogenous Parallel Programming Using GPUs［J］.Lecture Notes in Computer Science，2014， 8771：109-123

［4］ Stephane Louise，Paul Dubrulle，Thierry Goubier.A Model of Computation for Real-Time Applications on Embedded Manycores［C］//2014 IEEE 8th International Symposium on Embedded Multicore/Manycore SoCs，2014：333-340

［5］ Fernando J.Dynamically Reconfigurable Processing Engine for Polymorphic Embedded System［D］.Martinez Vallina，Chicago， Illinois，2007

［6］ Wu Yi，Zhou Xingshe，Wu Xiao，et al.An Embedded Real-Time Polymorphic Computing Platform Architecture［C］//2013 International Conference on Mechatronic Sciences，Electric Engineering and Computer，2013：2326-2330

［7］ Arshdeep Bahga，Vijay K.Madisetti.A Dynamic Resource Management and Scheduling Environment for Embedded Multimedia and Communications Platforms［J］.IEEE Embedded Systems Letters，2011，3(1)：24-27

［8］ Zhang Zhang，Swamy D.Ponpandi and Akhilesh Tyagi.An Evaluation of User Satisfaction Driven Scheduling in a Polymorphic Embedded System［C］//2014 IEEE 28th International Parallel＆Distributed Processing Symposium Workshops，2014：263-268

［9］ Brand D，Zafiropulo P.On Communicating Finite-State Machines［J］.Journal of the ACM，1983，30(2)：323-342

Design and APPlication of PolymorPhic Real-time ComPutational Model Using Many-Core Architecture

Luo Mei1，2，Zhou Xingshe1，Zhang Kailong1，Hu Yingying1

(1.Department of Computer Science and Engeenring，Northwestern Polytechnical University，Xi′an 710129，China
2.Xi′an Research Inst of Hi-Tech Hongqing Town，Xi′an 710025，China)

In order to improve the computational efficiency and fit the needs of complex embedded real time systems，the concept of polymorphic real time computing is introduced in many-core parallel architectures.A polymorphic real time computational model is designed and the concept of computating mode is proposed.The paper design and test three types of computing mode for computational model.The results and their analysis show preliminarily that the proposed model in different computing modes can obtain higher speedup under lower attenuation of communication and the response time of tasks is reduced.

computational efficiency，conceptual design，design of experiments，embedded software，intelligent systems，mathematical models，parallel architetures，real time systems，scalability；computing mode， many-core，polymorphic computing

TP399

A

1000-2758(2016)02-0338-05

2015-09-08基金項(xiàng)目：國家自然科學(xué)基金(61572403)與中國高?；A(chǔ)研究基金(3102015JSJ0002)資助

羅眉(1978—)，女，西北工業(yè)大學(xué)博士研究生，主要從事多態(tài)計(jì)算與分布式并行計(jì)算研究。