基于NoC分布式多核系統中任務遷移的實現

王 良，付方發，劉釗池，來逢昌

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

基于NoC分布式多核系統中任務遷移的實現

王 良，付方發，劉釗池，來逢昌

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

為降低多核系統中任務遷移的開銷，在片上網絡分布式多核系統的基礎上實現一種低開銷的任務遷移方案。借助于多核消息傳遞接口模型中并行程序與任務映射無關的特點，采用更新任務映射表的方式完成任務的重新映射，通過在μC/OS-II操作系統中傳遞任務的堆棧以及任務控制塊實現任務狀態在多核節點間的傳遞，任務遷移到另一節點后能夠恢復原來的狀態繼續執行，不需要傳遞任務代碼，并且任務狀態的保存不需要遷移點。實驗結果證明，該任務遷移方案能夠及時響應任務遷移請求，具有低開銷的特點，可較好地滿足系統中任務的實時性要求。

分布式多核系統；任務遷移；低開銷；多核消息傳遞接口；任務映射表；遷移點

1 概述

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

為了能夠合理地評估任務遷移的開銷并且提出相應的方案降低遷移開銷，研究者通常在NoC模擬器模擬任務遷移或在多核平臺實現任務遷移。文獻[9]是在基于SystemC 的NoC模擬器中模擬任務遷移，使用拷貝模型作為任務遷移模型，該模型可以評估任務遷移傳輸數據和代碼的時間以及功耗，但是沒有真正地實現任務遷移。文獻[10]是在MPARM多核仿真平臺實現任務遷移，各個核運行μClinux操作系統，任務遷移是基于遷移點遷移方法，在程序中添加多個遷移點，任務執行過程中只有遇到遷移點才會檢查是否收到遷移請求，如果是，那么保存并發送任務狀態進行務遷移。文獻[6]是在基于FPGA的多核仿真平臺中實現任務遷移，每個核運行μClinux操作系統，遷移同樣也采用遷移點方法實現，與文獻[10]不同的是，該任務遷移方案不需要傳遞任務代碼，因為各個核都有一份任務代碼的復制，并且一個任務在同一時刻只能在一個核上執行，這樣雖然需要較大的存儲空間保存任務代碼，但是卻節省了遷移時傳輸代碼和分配空間的時間。文獻[11]在HeMPS多核仿真平臺上實現任務遷移，操作系統為micro kernel，與文獻[6]和文獻[10]不同，任務遷移的實現不需要遷移點，但是遷移過程中不僅把任務的數據和上下文傳遞到目的節點，還需要傳遞任務的代碼。

綜上，基于遷移點方法的任務遷移需要頻繁地檢查是否收到任務遷移請求，導致任務正常執行時間增加，并且任務只有遇到遷移點才可能進行遷移，不能及時響應任務遷移請求。而文獻[11]雖然不需要遷移點，但是與文獻[10]相比，任務代碼的傳遞增大了MPSoC的通信開銷和任務的執行時間。因此，在基于NoC的MPSoC中亟需設計一種低開銷的任務遷移機制，在完成任務遷移目的的同時，能夠對系統性能的影響達到最小。

本文提出一種低開銷的任務遷移方案，借助多核消息傳遞接口模型(MPSoC Message Passing Interface, MMPI)[12]中并行程序與任務映射無關的特點，采用更新任務映射表的方式完成任務的重新映射。針對基于NoC的 MP SoC提出一種低開銷的任務遷移方案，通過在μC/OS-II操作系統中傳遞任務的堆棧以及任務控制塊實現任務遷移，任務遷移到另一節點后能夠恢復原來的狀態繼續執行。該遷移方案不需要傳遞任務代碼，并且由于不需要在程序中添加遷移點，能夠及時響應任務遷移請求。任務遷移在之前開發的NoC分布式多核系統[13]的基礎上實現。

2 系統結構

2.1 任務遷移的內容

任務遷移即把任務從MPSoC中的一個節點遷移到另一個節點，并且能夠恢復原來的狀態繼續執行。盡管任務遷移有許多種不同的實現方式，但是大都可以歸納為以下7個步驟[14]：

(1)發出遷移請求。遷移請求可以由遷移源節點發出，也可以由多核中主節點發出。

(2)在遷移源節點掛起任務，任務進入遷移狀態。

(3)重新建立通信。遷移過程中新到來的消息暫時保存到消息隊列，在任務遷移后再發送給任務，同時其他任務需要能夠獲悉該任務遷移后的新位置。

(4)提取任務狀態，包括存儲器內容、處理器狀態(CPU寄存器)，通信狀態(消息通道)以及相關的內核信息。

(5)在目的節點創建任務。

(6)在遷移的源節點和目的節點間傳遞任務狀態。

(7)把任務狀態導入新創建的任務，恢復任務。刪除源節點的任務。

在基于NoC的MPSoC中進行任務遷移，任務狀態通過NoC傳輸會帶來較大的通信遷移開銷。本文提出的任務遷移方案借助于多核平臺的MMPI編程模型對任務遷移的開銷進行優化。下面首先介紹任務遷移實現所用的平臺以及與任務遷移緊密相關的MMPI編程模型。

2.2 平臺結構

本文在之前開發的NoC分布式多核系統[12]中實現了一種具體的任務遷移方案。該系統在文獻[12]中有詳細描述，這里只作簡單介紹。該多核系統基于M5模擬器，整體結構如圖1所示。

圖1 多核系統整體結構

各個節點通過2D mesh網絡結構的NoC互聯，每個節點包含一個CPU、私有存儲器、DMA-NI以及其他外設。網絡中一個節點作為主控節點上負責統計和管理全局資源，進行任務映射以及發送遷移請求。其他節點作為運算節點負責運行并行任務。主控節點上運行嵌入式Linux操作系統，運算節點運行μC/OS-II操作系統。節點間的通信通過一套定制的、針對嵌入式應用的MMPI來完成。

2.3 M MPI消息傳遞機制

分布式多核系統中節點間的通信是采用消息傳遞的方式。不同節點的任務通過調用MMPI通信原語MPI_Send() 和MPI_Recv()完成消息的發送和接收。MPI_Send()是非阻塞發送，MPI_Recv()是阻塞接收。

一個應用包含多個有通信關系的任務，可以用任務圖表示，圖2是一個簡單任務圖的示例，任務圖中每個任務可以看作擁有私有的消息隊列，稱作軟FIFO。任務t1通過MPI_Send()把消息以非阻塞的方式發送到任務t2的軟FIFO中，任務t2通過MPI_Recv()把私有軟FIFO中的消息取出，完成一次任務間的消息傳遞。如果任務t2無法在軟FIFO中找到對應的消息，那么任務t2阻塞，直接消息到來。

圖2 任務圖示例

MMPI消息傳遞的機制簡化了任務遷移過程。任務在遷移的過程中，與之通信的任務不僅可以正常執行，而且還可以向正在遷移的任務發送消息，消息直接發送到遷移目的節點的消息隊列，任務在遷移后能夠在目的節點的消息隊列找到相應消息而不會被阻塞。

2.4 M MPI并行任務

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

3 任務遷移的實現過程

本節對任務遷移的細節作具體描述。圖3是任務遷移的流程。

圖3 任務遷移流程

任務遷移主要分為以下7個步驟：

(1)主控節點發送任務請求。本遷移方案中任務遷移請求由主控節點發出。首先，主控節點根據用戶的需求運行任務遷移算法，算法的結果輸出任務遷移的請求(本文只討論任務遷移的過程，暫不考慮任務遷移算法)。任務遷移請求分為3個部分：需要遷移的任務m_task，遷移的源節點s_node和遷移的目的節點d_node。任務遷移的請求指定了一個任務如何重新映射到其他節點。主控節點產生遷移請求后，把任務遷移的請求廣播到多核系統的各個節點。

圖4表示了多核分布式系統中任務遷移實現的過程。整個系統從下到上劃分為底層硬件、操作系統和應用軟件3個層次。

圖4 多核分布式系統中的任務遷移實現

多核節點分為主控節點和運算節點，圖中左側為主控節點，中間和右側為運算節點。MMPI庫作為消息傳遞的函數庫，可以看作是操作系統的擴展。主控節點負責任務調度以及發送任務遷移請求，①表示主控節點根據任務遷移算法產生遷移請求，②表示主控節點發送遷移請求到運算節點。

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

由于主控節點向各個節點發送遷移請求并非同時發送，并且各個運算節點在NoC中位置不同，因此s_node和d_node無法同時收到遷移請求。為了保證s_node和d_node同時進行任務遷移的過程，s_node與d_node之間需要通過消息進行同步。

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

表1 M MPI并行任務的狀態

(4)傳遞任務狀態。任務遷移的源節點通過MMPI消息傳遞的方式把任務堆棧和任務控制塊傳送到目的節點。在圖4中，④表示任務狀態在遷移源節點和目的節點間的傳遞，其中任務狀態包括任務堆棧和任務控制塊。

除了任務狀態需要傳遞，任務的軟FIFO中的消息也需要傳遞。任務遷移時，任務的私有軟FIFO中可能存在尚未通過MPI_Recv()接收的消息。因此，在任務狀態傳遞后，還需檢查遷移任務的軟FIFO是否為空，若不為空，那么直接通過網絡接口把該任務軟FIFO中的消息發送到目的節點。這樣可以避免任務遷移到目的節點后可能無法在軟FIFO中找到消息而錯誤阻塞。

(5)目的節點恢復任務。目的節點根據遷移請求中m_ task的任務號分配優先級，并且根據優先級創建任務。加載接收的任務狀態，使任務遷移到目的節點可以完全從原來被中斷的狀態恢復。

(6)源節點刪除任務。源節點根據遷移請求中m_task的任務號查找該任務的優先級，并且根據任務優先級在μC/ OS-II中刪除該任務。

(7)源節點和目的節點調度任務。

綜上所述，本文實現的任務遷移方案與通常的任務遷移主要有以下4點不同：(1)遷移請求由主節點發出，運算節點采用更新任務映射表的方式完成任務重新映射，使得任務遷移后仍能與其他任務正確通信；(2)其他任務可以向正在遷移的任務發送消息；(3)任務狀態包括任務堆棧和任務控制塊，不包括任務代碼；(4)在μC/OS-II操作系統中任務狀態自動保存，不需要遷移點檢查任務遷移請求，能夠對遷移請求及時做出響應。

4 實驗結果與分析

在基于M5模擬器的多核平臺上實現了任務遷移，多核平臺采用網絡規模2×2、拓撲結構為2D mesh的NoC結構。多核各節點的處理器頻率均為1 G Hz。網絡中0號節點作為主控節點，1～3號節點為運算節點，主控節點運行Linux操作系統，運算節點運行μC/OS-II操作系統。MMPI并行任務是由一個矩陣乘法拆分成多個互相通信的任務，每個任務的運行時間均約為5 ms，堆棧大小為512 Byte。任務被分配到各個運算節點執行，任務到網絡節點的映射關系以及任務遷移結果如表2所示，任務遷移分別把任務1從節點1遷移到節點3、把任務3從節點3遷移到節點2、把任務4從節點2遷移到節點1。

表2 任務映射

本文主要對任務遷移的時間開銷進行評估。評估主要分為3個部分內容：

(1)測試了任務遷移不同階段的時間。表3顯示了測試案例中不同任務遷移的各個階段的開銷，時間單位為時鐘周期。

表3 任務遷移各階段開銷 cycle

為了能夠更直觀地評估各個階段的開銷，將以上3個任務各階段遷移開銷取平均值，可以得到如圖5所示任務遷移各個階段所占的比重?？梢钥吹剑蝿諣顟B傳遞由于需要傳輸大量的數據，占遷移總開銷的50%左右。任務遷移請求接收由于主控節點需要多次啟動DMA-NI進行數據傳輸，因此達到了遷移總開銷的36%左右。

圖5 任務遷移各個階段的比重

(2)將本文的遷移方案與文獻[11]的遷移方案進行對比。文獻[11]提出的遷移方案同樣不需要遷移點，但是遷移過程需要傳遞任務的代碼。圖6對比了任務遷移包括與不包括任務代碼2種情況的任務遷移時間開銷，分別包括任務狀態傳遞的時間和遷移延時。

圖6 遷移開銷對比

其中，遷移延時表示任務的執行時間受任務遷移影響而增加的時間。經過測試，對于本測試案例，任務狀態的傳輸時間為7 309個時鐘周期，遷移延時為1 045時鐘周期。由圖6可見，遷移時不傳遞任務代碼可以使得任務狀態傳遞的時間降低約35%，遷移延時可以降低約28%。

(3)將本文的遷移方案與基于遷移點的遷移方案進行對比。為了能夠在M5平臺上模擬遷移點方法，創建一個較高優先級的任務，每隔一段時間檢查是否收到任務遷移請求。將本文方案命名為方案1，遷移點的間隔分別為20 μs、50 μs、100 μs、200 μs，分別命名為方案2～方案5。其中，運行的MMPI任務的執行時間約為5 ms。圖7是本文任務遷移方案與遷移點方法進行對比的結果，分別從任務遷移后執行時間增加和遷移請求響應時間進行對比。當遷移點間隔較小時，頻繁地檢查任務遷移請求使任務的正常執行時間增加；當遷移點間隔較大時，任務則不能及時響應任務遷移請求，響應時間與遷移點間隔成正比?？梢钥闯?，本文提出的任務遷移方案對任務執行時間影響很小，能夠很好地滿足實時系統中任務的實時性要求，同時本任務遷移方案能夠及時響應主控節點任務遷移的請求。

圖7 各方案遷移情況的對比結果

5 結束語

本文提出了一種低開銷的任務遷移方案，并且在NoC分布式多核系統中實現。多核系統中的MMPI編程模型具有并行程序與任務映射無關的特點，同時運算節點采用μC/OS-II操作系統，使得任務遷移不需要傳輸任務代碼，并且不需要遷移點，因此，該任務遷移方案具有較低的任務遷移開銷。實驗結果表明，任務狀態的傳輸對任務遷移開銷影響最大，并且當任務狀態不包括任務代碼時，遷移延時可以降低28%左右。同時，與基于遷移點的任務遷移相比，該任務遷移機制對任務執行時間影響很小，并且能及時響應任務遷移請求。下一步工作將在此基礎上繼續研究任務遷移算法相關的內容，把任務遷移應用于容錯、負載平衡等方面。

[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] 張 苗, 張德賢. 基于異構感知靜態調度與動態線程遷移的異構多核調度機制[J]. 計算機應用, 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的研究任務遷移, C++對象分布并行及Capability實現[D]. 成都: 電子科技大學, 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的分布式多核系統編程模型實現[D].哈爾濱: 哈爾濱工業大學, 2010.

[13] 胡新安, 付方發, 孫 俊, 等. 基于NoC的多核分布式操作系統[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

中央高校基本科研業務費專項基金資助項目(HIT.NSRIF.2014039)；國防重點學科實驗室開放基金資助項目。

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

2013-04-15

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

1000-3428(2014)05-0289-06

A

TP391

book=294,ebook=299