王 良，付方發(fā)，劉釗池，來(lái)逢昌

(哈爾濱工業(yè)大學(xué)微電子中心，哈爾濱 1 50001)

基于NoC分布式多核系統(tǒng)中任務(wù)遷移的實(shí)現(xiàn)

王 良，付方發(fā)，劉釗池，來(lái)逢昌

(哈爾濱工業(yè)大學(xué)微電子中心，哈爾濱 1 50001)

為降低多核系統(tǒng)中任務(wù)遷移的開(kāi)銷(xiāo)，在片上網(wǎng)絡(luò)分布式多核系統(tǒng)的基礎(chǔ)上實(shí)現(xiàn)一種低開(kāi)銷(xiāo)的任務(wù)遷移方案。借助于多核消息傳遞接口模型中并行程序與任務(wù)映射無(wú)關(guān)的特點(diǎn)，采用更新任務(wù)映射表的方式完成任務(wù)的重新映射，通過(guò)在μC/OS-II操作系統(tǒng)中傳遞任務(wù)的堆棧以及任務(wù)控制塊實(shí)現(xiàn)任務(wù)狀態(tài)在多核節(jié)點(diǎn)間的傳遞，任務(wù)遷移到另一節(jié)點(diǎn)后能夠恢復(fù)原來(lái)的狀態(tài)繼續(xù)執(zhí)行，不需要傳遞任務(wù)代碼，并且任務(wù)狀態(tài)的保存不需要遷移點(diǎn)。實(shí)驗(yàn)結(jié)果證明，該任務(wù)遷移方案能夠及時(shí)響應(yīng)任務(wù)遷移請(qǐng)求，具有低開(kāi)銷(xiāo)的特點(diǎn)，可較好地滿(mǎn)足系統(tǒng)中任務(wù)的實(shí)時(shí)性要求。

分布式多核系統(tǒng)；任務(wù)遷移；低開(kāi)銷(xiāo)；多核消息傳遞接口；任務(wù)映射表；遷移點(diǎn)

1 概述

片上系統(tǒng)(System on Chip, SoC)逐漸向多核化發(fā)展，構(gòu)成了多處理器片上系統(tǒng)(Multiprocessor System o n Ch ip, MPSoC)[1]。為了能夠有效地利用多核資源，最大程度地發(fā)揮多核的性能，需要對(duì)通信和計(jì)算資源進(jìn)行有效的管理。任務(wù)遷移是一種有效的動(dòng)態(tài)資源管理方法[2]，它可以在系統(tǒng)運(yùn)行過(guò)程中把一個(gè)任務(wù)或進(jìn)程從當(dāng)前運(yùn)行的PE(Processing Element)轉(zhuǎn)移到另外一個(gè)PE并且能夠恢復(fù)執(zhí)行。目前，MPSoC中任務(wù)遷移主要用于計(jì)算和通信的負(fù)載平衡[3-4]、容錯(cuò)[5]以及溫度控制[6]等方面。任務(wù)遷移最開(kāi)始出現(xiàn)在分布式計(jì)算機(jī)領(lǐng)域并取得了廣泛的研究成果[7]?；谄暇W(wǎng)絡(luò)(Network on Chip, NoC)[8]的MPSoC充分借鑒了分布式計(jì)算機(jī)通信的特點(diǎn)，具有分布式的存儲(chǔ)結(jié)構(gòu)。與分布式計(jì)算機(jī)相比，基于NoC的MPSoC的通信資源以及各個(gè)節(jié)點(diǎn)的存儲(chǔ)資源都非常有限，而任務(wù)遷移過(guò)程中整個(gè)任務(wù)通過(guò)NoC傳輸有著較大的通信開(kāi)銷(xiāo)，因此，在并行計(jì)算機(jī)中的任務(wù)遷移研究結(jié)果并不能直接移植到MPSoC中。

為了能夠合理地評(píng)估任務(wù)遷移的開(kāi)銷(xiāo)并且提出相應(yīng)的方案降低遷移開(kāi)銷(xiāo)，研究者通常在NoC模擬器模擬任務(wù)遷移或在多核平臺(tái)實(shí)現(xiàn)任務(wù)遷移。文獻(xiàn)[9]是在基于SystemC 的NoC模擬器中模擬任務(wù)遷移，使用拷貝模型作為任務(wù)遷移模型，該模型可以評(píng)估任務(wù)遷移傳輸數(shù)據(jù)和代碼的時(shí)間以及功耗，但是沒(méi)有真正地實(shí)現(xiàn)任務(wù)遷移。文獻(xiàn)[10]是在MPARM多核仿真平臺(tái)實(shí)現(xiàn)任務(wù)遷移，各個(gè)核運(yùn)行μClinux操作系統(tǒng)，任務(wù)遷移是基于遷移點(diǎn)遷移方法，在程序中添加多個(gè)遷移點(diǎn)，任務(wù)執(zhí)行過(guò)程中只有遇到遷移點(diǎn)才會(huì)檢查是否收到遷移請(qǐng)求，如果是，那么保存并發(fā)送任務(wù)狀態(tài)進(jìn)行務(wù)遷移。文獻(xiàn)[6]是在基于FPGA的多核仿真平臺(tái)中實(shí)現(xiàn)任務(wù)遷移，每個(gè)核運(yùn)行μClinux操作系統(tǒng)，遷移同樣也采用遷移點(diǎn)方法實(shí)現(xiàn)，與文獻(xiàn)[10]不同的是，該任務(wù)遷移方案不需要傳遞任務(wù)代碼，因?yàn)楦鱾€(gè)核都有一份任務(wù)代碼的復(fù)制，并且一個(gè)任務(wù)在同一時(shí)刻只能在一個(gè)核上執(zhí)行，這樣雖然需要較大的存儲(chǔ)空間保存任務(wù)代碼，但是卻節(jié)省了遷移時(shí)傳輸代碼和分配空間的時(shí)間。文獻(xiàn)[11]在HeMPS多核仿真平臺(tái)上實(shí)現(xiàn)任務(wù)遷移，操作系統(tǒng)為micro kernel，與文獻(xiàn)[6]和文獻(xiàn)[10]不同，任務(wù)遷移的實(shí)現(xiàn)不需要遷移點(diǎn)，但是遷移過(guò)程中不僅把任務(wù)的數(shù)據(jù)和上下文傳遞到目的節(jié)點(diǎn)，還需要傳遞任務(wù)的代碼。

綜上，基于遷移點(diǎn)方法的任務(wù)遷移需要頻繁地檢查是否收到任務(wù)遷移請(qǐng)求，導(dǎo)致任務(wù)正常執(zhí)行時(shí)間增加，并且任務(wù)只有遇到遷移點(diǎn)才可能進(jìn)行遷移，不能及時(shí)響應(yīng)任務(wù)遷移請(qǐng)求。而文獻(xiàn)[11]雖然不需要遷移點(diǎn)，但是與文獻(xiàn)[10]相比，任務(wù)代碼的傳遞增大了MPSoC的通信開(kāi)銷(xiāo)和任務(wù)的執(zhí)行時(shí)間。因此，在基于NoC的MPSoC中亟需設(shè)計(jì)一種低開(kāi)銷(xiāo)的任務(wù)遷移機(jī)制，在完成任務(wù)遷移目的的同時(shí)，能夠?qū)ο到y(tǒng)性能的影響達(dá)到最小。

本文提出一種低開(kāi)銷(xiāo)的任務(wù)遷移方案，借助多核消息傳遞接口模型(MPSoC Message Passing Interface, MMPI)[12]中并行程序與任務(wù)映射無(wú)關(guān)的特點(diǎn)，采用更新任務(wù)映射表的方式完成任務(wù)的重新映射。針對(duì)基于NoC的 MP SoC提出一種低開(kāi)銷(xiāo)的任務(wù)遷移方案，通過(guò)在μC/OS-II操作系統(tǒng)中傳遞任務(wù)的堆棧以及任務(wù)控制塊實(shí)現(xiàn)任務(wù)遷移，任務(wù)遷移到另一節(jié)點(diǎn)后能夠恢復(fù)原來(lái)的狀態(tài)繼續(xù)執(zhí)行。該遷移方案不需要傳遞任務(wù)代碼，并且由于不需要在程序中添加遷移點(diǎn)，能夠及時(shí)響應(yīng)任務(wù)遷移請(qǐng)求。任務(wù)遷移在之前開(kāi)發(fā)的NoC分布式多核系統(tǒng)[13]的基礎(chǔ)上實(shí)現(xiàn)。

2 系統(tǒng)結(jié)構(gòu)

2.1 任務(wù)遷移的內(nèi)容

任務(wù)遷移即把任務(wù)從MPSoC中的一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)，并且能夠恢復(fù)原來(lái)的狀態(tài)繼續(xù)執(zhí)行。盡管任務(wù)遷移有許多種不同的實(shí)現(xiàn)方式，但是大都可以歸納為以下7個(gè)步驟[14]：

(1)發(fā)出遷移請(qǐng)求。遷移請(qǐng)求可以由遷移源節(jié)點(diǎn)發(fā)出，也可以由多核中主節(jié)點(diǎn)發(fā)出。

(2)在遷移源節(jié)點(diǎn)掛起任務(wù)，任務(wù)進(jìn)入遷移狀態(tài)。

(3)重新建立通信。遷移過(guò)程中新到來(lái)的消息暫時(shí)保存到消息隊(duì)列，在任務(wù)遷移后再發(fā)送給任務(wù)，同時(shí)其他任務(wù)需要能夠獲悉該任務(wù)遷移后的新位置。

(4)提取任務(wù)狀態(tài)，包括存儲(chǔ)器內(nèi)容、處理器狀態(tài)(CPU寄存器)，通信狀態(tài)(消息通道)以及相關(guān)的內(nèi)核信息。

(5)在目的節(jié)點(diǎn)創(chuàng)建任務(wù)。

(6)在遷移的源節(jié)點(diǎn)和目的節(jié)點(diǎn)間傳遞任務(wù)狀態(tài)。

(7)把任務(wù)狀態(tài)導(dǎo)入新創(chuàng)建的任務(wù)，恢復(fù)任務(wù)。刪除源節(jié)點(diǎn)的任務(wù)。

在基于NoC的MPSoC中進(jìn)行任務(wù)遷移，任務(wù)狀態(tài)通過(guò)NoC傳輸會(huì)帶來(lái)較大的通信遷移開(kāi)銷(xiāo)。本文提出的任務(wù)遷移方案借助于多核平臺(tái)的MMPI編程模型對(duì)任務(wù)遷移的開(kāi)銷(xiāo)進(jìn)行優(yōu)化。下面首先介紹任務(wù)遷移實(shí)現(xiàn)所用的平臺(tái)以及與任務(wù)遷移緊密相關(guān)的MMPI編程模型。

2.2 平臺(tái)結(jié)構(gòu)

本文在之前開(kāi)發(fā)的NoC分布式多核系統(tǒng)[12]中實(shí)現(xiàn)了一種具體的任務(wù)遷移方案。該系統(tǒng)在文獻(xiàn)[12]中有詳細(xì)描述，這里只作簡(jiǎn)單介紹。該多核系統(tǒng)基于M5模擬器，整體結(jié)構(gòu)如圖1所示。

圖1 多核系統(tǒng)整體結(jié)構(gòu)

各個(gè)節(jié)點(diǎn)通過(guò)2D mesh網(wǎng)絡(luò)結(jié)構(gòu)的NoC互聯(lián)，每個(gè)節(jié)點(diǎn)包含一個(gè)CPU、私有存儲(chǔ)器、DMA-NI以及其他外設(shè)。網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)作為主控節(jié)點(diǎn)上負(fù)責(zé)統(tǒng)計(jì)和管理全局資源，進(jìn)行任務(wù)映射以及發(fā)送遷移請(qǐng)求。其他節(jié)點(diǎn)作為運(yùn)算節(jié)點(diǎn)負(fù)責(zé)運(yùn)行并行任務(wù)。主控節(jié)點(diǎn)上運(yùn)行嵌入式Linux操作系統(tǒng)，運(yùn)算節(jié)點(diǎn)運(yùn)行μC/OS-II操作系統(tǒng)。節(jié)點(diǎn)間的通信通過(guò)一套定制的、針對(duì)嵌入式應(yīng)用的MMPI來(lái)完成。

2.3 M MPI消息傳遞機(jī)制

分布式多核系統(tǒng)中節(jié)點(diǎn)間的通信是采用消息傳遞的方式。不同節(jié)點(diǎn)的任務(wù)通過(guò)調(diào)用MMPI通信原語(yǔ)MPI_Send() 和MPI_Recv()完成消息的發(fā)送和接收。MPI_Send()是非阻塞發(fā)送，MPI_Recv()是阻塞接收。

一個(gè)應(yīng)用包含多個(gè)有通信關(guān)系的任務(wù)，可以用任務(wù)圖表示，圖2是一個(gè)簡(jiǎn)單任務(wù)圖的示例，任務(wù)圖中每個(gè)任務(wù)可以看作擁有私有的消息隊(duì)列，稱(chēng)作軟FIFO。任務(wù)t1通過(guò)MPI_Send()把消息以非阻塞的方式發(fā)送到任務(wù)t2的軟FIFO中，任務(wù)t2通過(guò)MPI_Recv()把私有軟FIFO中的消息取出，完成一次任務(wù)間的消息傳遞。如果任務(wù)t2無(wú)法在軟FIFO中找到對(duì)應(yīng)的消息，那么任務(wù)t2阻塞，直接消息到來(lái)。

圖2 任務(wù)圖示例

MMPI消息傳遞的機(jī)制簡(jiǎn)化了任務(wù)遷移過(guò)程。任務(wù)在遷移的過(guò)程中，與之通信的任務(wù)不僅可以正常執(zhí)行，而且還可以向正在遷移的任務(wù)發(fā)送消息，消息直接發(fā)送到遷移目的節(jié)點(diǎn)的消息隊(duì)列，任務(wù)在遷移后能夠在目的節(jié)點(diǎn)的消息隊(duì)列找到相應(yīng)消息而不會(huì)被阻塞。

2.4 M MPI并行任務(wù)

基于MMPI的并行程序在編寫(xiě)時(shí)不包含任務(wù)到節(jié)點(diǎn)的映射信息，即并行程序與任務(wù)映射無(wú)關(guān)。在MMPI程序執(zhí)行前主控節(jié)點(diǎn)指定任務(wù)到節(jié)點(diǎn)的映射關(guān)系，MMPI程序在初始化MPI_Init()時(shí)獲取任務(wù)映射表，在執(zhí)行時(shí)根據(jù)任務(wù)映射執(zhí)行MMPI程序的不同部分，從而實(shí)現(xiàn)了依據(jù)任務(wù)映射的結(jié)果，不同任務(wù)在不同節(jié)點(diǎn)上的并行執(zhí)行。在這種機(jī)制下，當(dāng)任務(wù)發(fā)生遷移時(shí)，主控節(jié)點(diǎn)只需要重新向各個(gè)運(yùn)算節(jié)點(diǎn)發(fā)送任務(wù)映射，即可保證任務(wù)在遷移后仍能夠與其他任務(wù)保持正確的通信。同時(shí)，由于各個(gè)運(yùn)算節(jié)點(diǎn)保存同樣的MMPI程序，因此任務(wù)遷移時(shí)可以不需要傳遞任務(wù)代碼，降低了任務(wù)遷移的開(kāi)銷(xiāo)。

3 任務(wù)遷移的實(shí)現(xiàn)過(guò)程

本節(jié)對(duì)任務(wù)遷移的細(xì)節(jié)作具體描述。圖3是任務(wù)遷移的流程。

圖3 任務(wù)遷移流程

任務(wù)遷移主要分為以下7個(gè)步驟：

(1)主控節(jié)點(diǎn)發(fā)送任務(wù)請(qǐng)求。本遷移方案中任務(wù)遷移請(qǐng)求由主控節(jié)點(diǎn)發(fā)出。首先，主控節(jié)點(diǎn)根據(jù)用戶(hù)的需求運(yùn)行任務(wù)遷移算法，算法的結(jié)果輸出任務(wù)遷移的請(qǐng)求(本文只討論任務(wù)遷移的過(guò)程，暫不考慮任務(wù)遷移算法)。任務(wù)遷移請(qǐng)求分為3個(gè)部分：需要遷移的任務(wù)m_task，遷移的源節(jié)點(diǎn)s_node和遷移的目的節(jié)點(diǎn)d_node。任務(wù)遷移的請(qǐng)求指定了一個(gè)任務(wù)如何重新映射到其他節(jié)點(diǎn)。主控節(jié)點(diǎn)產(chǎn)生遷移請(qǐng)求后，把任務(wù)遷移的請(qǐng)求廣播到多核系統(tǒng)的各個(gè)節(jié)點(diǎn)。

圖4表示了多核分布式系統(tǒng)中任務(wù)遷移實(shí)現(xiàn)的過(guò)程。整個(gè)系統(tǒng)從下到上劃分為底層硬件、操作系統(tǒng)和應(yīng)用軟件3個(gè)層次。

圖4 多核分布式系統(tǒng)中的任務(wù)遷移實(shí)現(xiàn)

多核節(jié)點(diǎn)分為主控節(jié)點(diǎn)和運(yùn)算節(jié)點(diǎn)，圖中左側(cè)為主控節(jié)點(diǎn)，中間和右側(cè)為運(yùn)算節(jié)點(diǎn)。MMPI庫(kù)作為消息傳遞的函數(shù)庫(kù)，可以看作是操作系統(tǒng)的擴(kuò)展。主控節(jié)點(diǎn)負(fù)責(zé)任務(wù)調(diào)度以及發(fā)送任務(wù)遷移請(qǐng)求，①表示主控節(jié)點(diǎn)根據(jù)任務(wù)遷移算法產(chǎn)生遷移請(qǐng)求，②表示主控節(jié)點(diǎn)發(fā)送遷移請(qǐng)求到運(yùn)算節(jié)點(diǎn)。

(2)更新任務(wù)映射表。與通常任務(wù)遷移方法不同的是，本文提出的任務(wù)遷移方案采用更新任務(wù)映射表的方式使其他任務(wù)獲悉任務(wù)遷移后所在的節(jié)點(diǎn)。由于對(duì)于MMPI程序，不同的運(yùn)算節(jié)點(diǎn)根據(jù)任務(wù)映射表執(zhí)行不同的任務(wù)，當(dāng)運(yùn)算節(jié)點(diǎn)收到主控節(jié)點(diǎn)的遷移請(qǐng)求時(shí)，更新任務(wù)映射表，不僅可以完成任務(wù)的重新映射，而且還可以使得應(yīng)用中的其他任務(wù)獲知任務(wù)遷移后所處的節(jié)點(diǎn)，保證了任務(wù)在遷移后與其他任務(wù)間的消息仍能夠正確地傳遞。在圖4中，task1遷移至另一運(yùn)算節(jié)點(diǎn)成為task1’，③表示任務(wù)task0通過(guò)更新映射表的方式與task1’重新建立通信。

由于主控節(jié)點(diǎn)向各個(gè)節(jié)點(diǎn)發(fā)送遷移請(qǐng)求并非同時(shí)發(fā)送，并且各個(gè)運(yùn)算節(jié)點(diǎn)在NoC中位置不同，因此s_node和d_node無(wú)法同時(shí)收到遷移請(qǐng)求。為了保證s_node和d_node同時(shí)進(jìn)行任務(wù)遷移的過(guò)程，s_node與d_node之間需要通過(guò)消息進(jìn)行同步。

(3)源節(jié)點(diǎn)保存任務(wù)狀態(tài)。通常在一個(gè)分布式的系統(tǒng)中進(jìn)行任務(wù)遷移，傳遞任務(wù)的狀態(tài)包括CPU寄存器、任務(wù)代碼、任務(wù)數(shù)據(jù)以及操作系統(tǒng)內(nèi)核維護(hù)的任務(wù)控制信息[15]。本文實(shí)現(xiàn)的任務(wù)遷移是在分布式多核系統(tǒng)的運(yùn)算節(jié)點(diǎn)之間進(jìn)行，根據(jù)2.2節(jié)可知，運(yùn)算節(jié)點(diǎn)運(yùn)行μC/OS-II操作系統(tǒng)。表1表示了任務(wù)遷移時(shí)需要傳遞的任務(wù)狀態(tài)以及任務(wù)狀態(tài)所在的位置。在μC/OS-II操作系統(tǒng)中，任務(wù)被切換時(shí)，任務(wù)對(duì)應(yīng)的CPU寄存器信息自動(dòng)保存到任務(wù)堆棧中，并且任務(wù)的數(shù)據(jù)也保存到任務(wù)堆棧。此外，μC/OS-II通過(guò)任務(wù)控制塊(Task Control Block, TCB)維護(hù)著任務(wù)控制相關(guān)信息，主要記錄了任務(wù)堆棧的當(dāng)前指針等信息。同時(shí)各個(gè)運(yùn)算節(jié)點(diǎn)保存同樣的MMPI程序，僅通過(guò)修改任務(wù)映射表，即可實(shí)現(xiàn)任務(wù)的重新映射，因此，任務(wù)遷移時(shí)可以不需要傳遞任務(wù)代碼，任務(wù)遷移的開(kāi)銷(xiāo)也由于免去傳遞任務(wù)代碼而得到一定程度降低。綜上，任務(wù)遷移時(shí)任務(wù)狀態(tài)僅包括任務(wù)堆棧和任務(wù)控制塊。

表1 M MPI并行任務(wù)的狀態(tài)

(4)傳遞任務(wù)狀態(tài)。任務(wù)遷移的源節(jié)點(diǎn)通過(guò)MMPI消息傳遞的方式把任務(wù)堆棧和任務(wù)控制塊傳送到目的節(jié)點(diǎn)。在圖4中，④表示任務(wù)狀態(tài)在遷移源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的傳遞，其中任務(wù)狀態(tài)包括任務(wù)堆棧和任務(wù)控制塊。

除了任務(wù)狀態(tài)需要傳遞，任務(wù)的軟FIFO中的消息也需要傳遞。任務(wù)遷移時(shí)，任務(wù)的私有軟FIFO中可能存在尚未通過(guò)MPI_Recv()接收的消息。因此，在任務(wù)狀態(tài)傳遞后，還需檢查遷移任務(wù)的軟FIFO是否為空，若不為空，那么直接通過(guò)網(wǎng)絡(luò)接口把該任務(wù)軟FIFO中的消息發(fā)送到目的節(jié)點(diǎn)。這樣可以避免任務(wù)遷移到目的節(jié)點(diǎn)后可能無(wú)法在軟FIFO中找到消息而錯(cuò)誤阻塞。

(5)目的節(jié)點(diǎn)恢復(fù)任務(wù)。目的節(jié)點(diǎn)根據(jù)遷移請(qǐng)求中m_ task的任務(wù)號(hào)分配優(yōu)先級(jí)，并且根據(jù)優(yōu)先級(jí)創(chuàng)建任務(wù)。加載接收的任務(wù)狀態(tài)，使任務(wù)遷移到目的節(jié)點(diǎn)可以完全從原來(lái)被中斷的狀態(tài)恢復(fù)。

(6)源節(jié)點(diǎn)刪除任務(wù)。源節(jié)點(diǎn)根據(jù)遷移請(qǐng)求中m_task的任務(wù)號(hào)查找該任務(wù)的優(yōu)先級(jí)，并且根據(jù)任務(wù)優(yōu)先級(jí)在μC/ OS-II中刪除該任務(wù)。

(7)源節(jié)點(diǎn)和目的節(jié)點(diǎn)調(diào)度任務(wù)。

綜上所述，本文實(shí)現(xiàn)的任務(wù)遷移方案與通常的任務(wù)遷移主要有以下4點(diǎn)不同：(1)遷移請(qǐng)求由主節(jié)點(diǎn)發(fā)出，運(yùn)算節(jié)點(diǎn)采用更新任務(wù)映射表的方式完成任務(wù)重新映射，使得任務(wù)遷移后仍能與其他任務(wù)正確通信；(2)其他任務(wù)可以向正在遷移的任務(wù)發(fā)送消息；(3)任務(wù)狀態(tài)包括任務(wù)堆棧和任務(wù)控制塊，不包括任務(wù)代碼；(4)在μC/OS-II操作系統(tǒng)中任務(wù)狀態(tài)自動(dòng)保存，不需要遷移點(diǎn)檢查任務(wù)遷移請(qǐng)求，能夠?qū)w移請(qǐng)求及時(shí)做出響應(yīng)。

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

在基于M5模擬器的多核平臺(tái)上實(shí)現(xiàn)了任務(wù)遷移，多核平臺(tái)采用網(wǎng)絡(luò)規(guī)模2×2、拓?fù)浣Y(jié)構(gòu)為2D mesh的NoC結(jié)構(gòu)。多核各節(jié)點(diǎn)的處理器頻率均為1 G Hz。網(wǎng)絡(luò)中0號(hào)節(jié)點(diǎn)作為主控節(jié)點(diǎn)，1～3號(hào)節(jié)點(diǎn)為運(yùn)算節(jié)點(diǎn)，主控節(jié)點(diǎn)運(yùn)行Linux操作系統(tǒng)，運(yùn)算節(jié)點(diǎn)運(yùn)行μC/OS-II操作系統(tǒng)。MMPI并行任務(wù)是由一個(gè)矩陣乘法拆分成多個(gè)互相通信的任務(wù)，每個(gè)任務(wù)的運(yùn)行時(shí)間均約為5 ms，堆棧大小為512 Byte。任務(wù)被分配到各個(gè)運(yùn)算節(jié)點(diǎn)執(zhí)行，任務(wù)到網(wǎng)絡(luò)節(jié)點(diǎn)的映射關(guān)系以及任務(wù)遷移結(jié)果如表2所示，任務(wù)遷移分別把任務(wù)1從節(jié)點(diǎn)1遷移到節(jié)點(diǎn)3、把任務(wù)3從節(jié)點(diǎn)3遷移到節(jié)點(diǎn)2、把任務(wù)4從節(jié)點(diǎn)2遷移到節(jié)點(diǎn)1。

表2 任務(wù)映射

本文主要對(duì)任務(wù)遷移的時(shí)間開(kāi)銷(xiāo)進(jìn)行評(píng)估。評(píng)估主要分為3個(gè)部分內(nèi)容：

(1)測(cè)試了任務(wù)遷移不同階段的時(shí)間。表3顯示了測(cè)試案例中不同任務(wù)遷移的各個(gè)階段的開(kāi)銷(xiāo)，時(shí)間單位為時(shí)鐘周期。

表3 任務(wù)遷移各階段開(kāi)銷(xiāo) cycle

為了能夠更直觀(guān)地評(píng)估各個(gè)階段的開(kāi)銷(xiāo)，將以上3個(gè)任務(wù)各階段遷移開(kāi)銷(xiāo)取平均值，可以得到如圖5所示任務(wù)遷移各個(gè)階段所占的比重?？梢钥吹?，任務(wù)狀態(tài)傳遞由于需要傳輸大量的數(shù)據(jù)，占遷移總開(kāi)銷(xiāo)的50%左右。任務(wù)遷移請(qǐng)求接收由于主控節(jié)點(diǎn)需要多次啟動(dòng)DMA-NI進(jìn)行數(shù)據(jù)傳輸，因此達(dá)到了遷移總開(kāi)銷(xiāo)的36%左右。

圖5 任務(wù)遷移各個(gè)階段的比重

(2)將本文的遷移方案與文獻(xiàn)[11]的遷移方案進(jìn)行對(duì)比。文獻(xiàn)[11]提出的遷移方案同樣不需要遷移點(diǎn)，但是遷移過(guò)程需要傳遞任務(wù)的代碼。圖6對(duì)比了任務(wù)遷移包括與不包括任務(wù)代碼2種情況的任務(wù)遷移時(shí)間開(kāi)銷(xiāo)，分別包括任務(wù)狀態(tài)傳遞的時(shí)間和遷移延時(shí)。

圖6 遷移開(kāi)銷(xiāo)對(duì)比

其中，遷移延時(shí)表示任務(wù)的執(zhí)行時(shí)間受任務(wù)遷移影響而增加的時(shí)間。經(jīng)過(guò)測(cè)試，對(duì)于本測(cè)試案例，任務(wù)狀態(tài)的傳輸時(shí)間為7 309個(gè)時(shí)鐘周期，遷移延時(shí)為1 045時(shí)鐘周期。由圖6可見(jiàn)，遷移時(shí)不傳遞任務(wù)代碼可以使得任務(wù)狀態(tài)傳遞的時(shí)間降低約35%，遷移延時(shí)可以降低約28%。

(3)將本文的遷移方案與基于遷移點(diǎn)的遷移方案進(jìn)行對(duì)比。為了能夠在M5平臺(tái)上模擬遷移點(diǎn)方法，創(chuàng)建一個(gè)較高優(yōu)先級(jí)的任務(wù)，每隔一段時(shí)間檢查是否收到任務(wù)遷移請(qǐng)求。將本文方案命名為方案1，遷移點(diǎn)的間隔分別為20 μs、50 μs、100 μs、200 μs，分別命名為方案2～方案5。其中，運(yùn)行的MMPI任務(wù)的執(zhí)行時(shí)間約為5 ms。圖7是本文任務(wù)遷移方案與遷移點(diǎn)方法進(jìn)行對(duì)比的結(jié)果，分別從任務(wù)遷移后執(zhí)行時(shí)間增加和遷移請(qǐng)求響應(yīng)時(shí)間進(jìn)行對(duì)比。當(dāng)遷移點(diǎn)間隔較小時(shí)，頻繁地檢查任務(wù)遷移請(qǐng)求使任務(wù)的正常執(zhí)行時(shí)間增加；當(dāng)遷移點(diǎn)間隔較大時(shí)，任務(wù)則不能及時(shí)響應(yīng)任務(wù)遷移請(qǐng)求，響應(yīng)時(shí)間與遷移點(diǎn)間隔成正比。可以看出，本文提出的任務(wù)遷移方案對(duì)任務(wù)執(zhí)行時(shí)間影響很小，能夠很好地滿(mǎn)足實(shí)時(shí)系統(tǒng)中任務(wù)的實(shí)時(shí)性要求，同時(shí)本任務(wù)遷移方案能夠及時(shí)響應(yīng)主控節(jié)點(diǎn)任務(wù)遷移的請(qǐng)求。

圖7 各方案遷移情況的對(duì)比結(jié)果

5 結(jié)束語(yǔ)

本文提出了一種低開(kāi)銷(xiāo)的任務(wù)遷移方案，并且在NoC分布式多核系統(tǒng)中實(shí)現(xiàn)。多核系統(tǒng)中的MMPI編程模型具有并行程序與任務(wù)映射無(wú)關(guān)的特點(diǎn)，同時(shí)運(yùn)算節(jié)點(diǎn)采用μC/OS-II操作系統(tǒng)，使得任務(wù)遷移不需要傳輸任務(wù)代碼，并且不需要遷移點(diǎn)，因此，該任務(wù)遷移方案具有較低的任務(wù)遷移開(kāi)銷(xiāo)。實(shí)驗(yàn)結(jié)果表明，任務(wù)狀態(tài)的傳輸對(duì)任務(wù)遷移開(kāi)銷(xiāo)影響最大，并且當(dāng)任務(wù)狀態(tài)不包括任務(wù)代碼時(shí)，遷移延時(shí)可以降低28%左右。同時(shí)，與基于遷移點(diǎn)的任務(wù)遷移相比，該任務(wù)遷移機(jī)制對(duì)任務(wù)執(zhí)行時(shí)間影響很小，并且能及時(shí)響應(yīng)任務(wù)遷移請(qǐng)求。下一步工作將在此基礎(chǔ)上繼續(xù)研究任務(wù)遷移算法相關(guān)的內(nèi)容，把任務(wù)遷移應(yīng)用于容錯(cuò)、負(fù)載平衡等方面。

[1] W olf W, J erraya A A, Martin G. Multiprocessor Systemon-Chip(MPSoC) T echnology[J]. IEE E T ransactions on Computer-aided Design of Integrated Circuits an d Systems, 2008, 27(1): 1701-1713.

[2] Nollet V, Marescaux T, Avasare P, et al. Centralized Run-time Resource Man agement in a Network-on-Chip Containing Reconfigurable Hard ware T iles[C]//Proc. of Co nference on Design, Automation and Test in Europe. Munich, Germany: [s. n.], 2005: 234-239.

[3] 張 苗, 張德賢. 基于異構(gòu)感知靜態(tài)調(diào)度與動(dòng)態(tài)線(xiàn)程遷移的異構(gòu)多核調(diào)度機(jī)制[J]. 計(jì)算機(jī)應(yīng)用, 2011, 31(7): 1808- 1810.

[4] Yaghoubi H, Modarresi M, Sarbazi A H. A Distributed Task Migration Scheme for Mesh-based Chip-multiprocessors[C]// Proc. of the 12th International Conference on P arallel and Distributed Computing, Applications and Technologie. Gwangju, Korea: [s. n.], 2011: 24-29.

[5] Thilo S, Christian S, Christian H, et al. Dynamic Task Binding for Hardware/Software Reconfigurable Networks[C]//Proc. of the 19th Annual Symposium on Integrated Circuits and Systems Design. Ouro Preto, Brazil: [s. n.], 2006: 38-43.

[6] Cuesta D, Ayala J L, Hidalgo J I, et al. Adaptive Task Migration Policies for Thermal Control in M PSoCs[C]//Proc. of the IEEE Computer Society Annual Symposium on VLSI. Lixouri Kefalonia, Greece: [s. n.], 2010: 110-115.

[7] 李 毅. 基于PVM的研究任務(wù)遷移, C++對(duì)象分布并行及Capability實(shí)現(xiàn)[D]. 成都: 電子科技大學(xué), 2001.

[8] Benini L, De M G. Networks on Chips: A New So C Paradigm[J]. Computer, 2002, 35(1): 70-78.

[9] Eduardo W B, Daniel B, W ronski F, et al. Impact of Task Migration in NoC-based MPSoC s for Soft Real-time Applications[C]//Proc. of International Co nference on Very Large Scale Integration. Atlanta, USA: [s. n.], 2007: 296-299.

[10] Bertozzi S, Acquaviva A, Be rtozzi D, et al. S upporting Task Migration in Multi-processor Syst ems-on-Chip: A Feasibility Study[C]//Proc. of Conference o n Design, Automation and Test in Europe. Leuven, Belgium: [s. n.], 2006: 1-6.

[11] Moraes F G, Madalozzo G A, Castilhos G M, et al. Prop osal and Evaluation o f a T ask Migration Protocol for NoC-based MPSoCs[C]//Proc. of IEEE International Symposium on Circuits and Systems. Seoul, Korea: [s. n.], 2012: 644-647.

[12] 孫思月. 基于NoC的分布式多核系統(tǒng)編程模型實(shí)現(xiàn)[D].哈爾濱: 哈爾濱工業(yè)大學(xué), 2010.

[13] 胡新安, 付方發(fā), 孫 俊, 等. 基于NoC的多核分布式操作系統(tǒng)[J]. 計(jì)算機(jī)工程, 2012, 38(5): 259-261.

[14] Dejan S, Fred D, Yves P, et al. Process Mig ration[J]. ACM Computing Surveys, 2000, 32(3): 241-299.

[15] Robinson J, Russ S H, Flachs B K, et al. A Task Migration Implementation of the M essage-passing Interface[C]//Proc. of the 5th I EEE International Symposium on High Performance Distributed Computing. Syracuse, Italy: [s. n.], 1996: 61-68.

編輯 顧逸斐

Implementation of Task Migration in Distributed Multi-core System Based on NoC

WANG Liang, FU Fang-fa, LIU Zhao-chi, LAI Feng-chang

(Microelectronics Center, Harbin Institute of Technology, Harbin 150001, China)

In order to decrease task migration overh ead in distributed multi-core system, a low-cost task migration scheme is implemented on the distributed multi-core system ba sed on Network on Chip(NoC). The task migration scheme depends on the distributed multi-core system message passing interface, in which program is independent of task mapping. Task is remapped by updating task mapping table. The task state including task stack and task control block in μC/OS-II operating system is transferred to another node, on which the migrated task restores execution. The task migration scheme needs not transfer task code, and task state saving does not use checkpoints. Experimental results show that in this migration scheme, the task m igration scheme has little influence on task executi on and i mmediate response to migration request. Therefore, the task migration scheme is low cost and can meet real-time requirements in system.

distributed multi-core system; task migration; low-cost; multi-core message passing interface; task mapping table; transfer point

10.3969/j.issn.1000-3428.2014.05.060

中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)基金資助項(xiàng)目(HIT.NSRIF.2014039)；國(guó)防重點(diǎn)學(xué)科實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目。

王 良(1989－)，男，碩士研究生，主研方向：多核通信，多核任務(wù)調(diào)度與遷移；付方發(fā)，講師、博士；劉釗池，碩士研究生；來(lái)逢昌，副教授。

2013-04-15

2013-06-17E-mail：wl23189@163.com

1000-3428(2014)05-0289-06

A

TP391

book=294,ebook=299