面向異構(gòu)多核處理器的調(diào)度算法優(yōu)化

摘 要：當(dāng)前，異構(gòu)多核處理器在嵌入式領(lǐng)域中得到了更為廣泛的應(yīng)用。在處理器中，多核之間在進(jìn)行通信的過程中會(huì)產(chǎn)生一定的通信開銷，對(duì)異構(gòu)多核處理器的系統(tǒng)性能造成影響。因此，對(duì)異構(gòu)多核處理器的通信算法進(jìn)行研究有著非常重要的意義。本文針對(duì)異構(gòu)多核處理器通信提出了實(shí)現(xiàn)核間通信開銷降低的調(diào)度算法優(yōu)化，實(shí)現(xiàn)系統(tǒng)性能的提高。

關(guān)鍵詞：通信算法；異構(gòu)多核處理器；通信開銷

中圖分類號(hào)：TP316.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-7712 （2015） 02-0000-01

異構(gòu)多核處理器的廣泛應(yīng)用帶動(dòng)了嵌入式領(lǐng)域?qū)崟r(shí)性、高效性等方面的不斷提升，但是也給異構(gòu)多核處理器的設(shè)計(jì)提出了新的挑戰(zhàn)。在異構(gòu)多核處理器的操作系統(tǒng)進(jìn)行設(shè)計(jì)的過程中，一方面要注重應(yīng)用效率，另一方面要注重資源合理分配。在多核環(huán)境之下，不同的核上運(yùn)行的任務(wù)之間是存在一定的數(shù)據(jù)依賴性的，必須進(jìn)行核之間的通信。實(shí)現(xiàn)核間通信開銷的降低，能夠?qū)崿F(xiàn)系統(tǒng)性能指標(biāo)的改善。

一、異構(gòu)多核處理器的通信

在異構(gòu)多核處理器的過程中，核間通信所需的時(shí)間在任務(wù)執(zhí)行時(shí)間中占據(jù)一定的比例。因此，實(shí)現(xiàn)核間通信的優(yōu)化能夠促進(jìn)系統(tǒng)執(zhí)行效率的提高。在異構(gòu)多核處理器的核間通信過程中，通信方式為利用總線進(jìn)行數(shù)據(jù)的傳輸。本文將研究的重點(diǎn)集中在總線方面，對(duì)總線訪問策略與總線調(diào)動(dòng)策略的算法進(jìn)行研究。

本文針對(duì)核間通信開銷的降低提出了一種任務(wù)調(diào)度方法：實(shí)現(xiàn)計(jì)算型任務(wù)與通信型任務(wù)的重新調(diào)度，實(shí)現(xiàn)兩者的重疊執(zhí)行，從而實(shí)現(xiàn)核間通信開銷的降低。核間通信開銷降低任務(wù)調(diào)度方法的基本思想包括：第一，通過任務(wù)間存在的依賴關(guān)系對(duì)資源進(jìn)行重新的分配；第二，在任務(wù)之前進(jìn)行通信型任務(wù)與其他關(guān)聯(lián)任務(wù)的預(yù)先調(diào)度，將部分?jǐn)?shù)據(jù)在任務(wù)開始之前就完成傳輸，從而實(shí)現(xiàn)任務(wù)時(shí)間覆蓋核間通信時(shí)間的目的，實(shí)現(xiàn)系統(tǒng)任務(wù)執(zhí)行效率的提高。

二、靜態(tài)調(diào)度算法

多核任務(wù)類型主要包括兩種，一種為計(jì)算型任務(wù)，主要的作用是數(shù)據(jù)計(jì)算，另一種為通信型任務(wù)，主要的作用是數(shù)據(jù)傳輸。在對(duì)周期任務(wù)的依賴關(guān)系進(jìn)行明確之后，要對(duì)調(diào)度的優(yōu)化進(jìn)行研究。依據(jù)任務(wù)間依賴關(guān)系、通信時(shí)間等隱私實(shí)現(xiàn)DAG圖的構(gòu)建。

（一）Cycilc靜態(tài)多核調(diào)度算法

在對(duì)給定的GAD圖進(jìn)行靜態(tài)調(diào)度的過程中，一方面要任務(wù)進(jìn)行處理器分配與任務(wù)開始時(shí)間制定，另一方面依據(jù)任務(wù)間依賴關(guān)系確定任務(wù)執(zhí)行次序。Cycilc靜態(tài)多核調(diào)度算法的思想為：通過輪詢方式對(duì)任務(wù)進(jìn)行周期性的分配，將其落實(shí)到每一個(gè)處理器核。例如，如果有20個(gè)任務(wù)需要分配到10個(gè)核上，那么分配的方式就是0號(hào)任務(wù)與10號(hào)任務(wù)分配到0核上，1號(hào)任務(wù)與11號(hào)任務(wù)分配到1核上……以此類推，完成任務(wù)的分配。指定的DAG圖如圖1所示，在對(duì)其按照Cycilc靜態(tài)多核調(diào)度算法進(jìn)行分配的過程中，其任務(wù)調(diào)度時(shí)序圖如圖2所示，此時(shí)的調(diào)動(dòng)長度，也就是所有任務(wù)執(zhí)行一個(gè)周期所需要的時(shí)間為16cycle。Cycilc靜態(tài)多核調(diào)度算法在對(duì)任務(wù)進(jìn)行分配的過程中，只是簡單地按照輪詢的方式進(jìn)行分配，只能夠確保每個(gè)處理器核上的負(fù)載平衡，但是忽略了任務(wù)之間存在的依賴性與核間通信問題。如果兩個(gè)任務(wù)的核間通信較為頻繁又正好分配到不同的核上，與分配到一個(gè)核上相比，調(diào)度長度就會(huì)有所增加，導(dǎo)致任務(wù)執(zhí)行效率的降低。

（二）基于核間通信的SSC靜態(tài)調(diào)度算法

針對(duì)Cycilc靜態(tài)多核調(diào)度算法中存在的不足，本文提出了基于核間通信的靜態(tài)SSC（simple schedule algorithm based on communication）調(diào)度算法。基于核間通信的靜態(tài)SSC調(diào)度算法的思想為：依據(jù)已有的任務(wù)DAG圖，依據(jù)核間通信市場對(duì)存在依賴關(guān)系的任務(wù)進(jìn)行分配，盡量將核間通信市場較長的兩個(gè)任務(wù)分配到相同的核上進(jìn)行串行執(zhí)行，從而降低核間通信開銷。

當(dāng)對(duì)任務(wù)M進(jìn)行分配的過程中，如果M任務(wù)與其他任務(wù)之間不存在同時(shí)依賴同一個(gè)任務(wù)的情況，那么M在分配的過程中按照Cycilc算法進(jìn)行輪詢分配。如果M任務(wù)與其他任務(wù)之間存在同時(shí)依賴同一個(gè)任務(wù)的情況，第一，如果M同時(shí)對(duì)多個(gè)任務(wù)存在依賴，選取多個(gè)通信型任務(wù)中最長通信時(shí)間的任務(wù)與M同時(shí)分配到同一個(gè)核上；第二，如果M與其他多個(gè)任務(wù)同時(shí)依賴同一個(gè)任務(wù)A，選取多個(gè)任務(wù)中最長通信時(shí)間的任務(wù)與A分配到同一個(gè)核上，其他的任務(wù)按照Cycilc方式分配。

（三）基于核間通信的靜態(tài)SSC調(diào)度算法的優(yōu)化

為了實(shí)現(xiàn)調(diào)度長度的進(jìn)一步縮短，實(shí)現(xiàn)流水線思想與SSC調(diào)度算法的相互結(jié)合，從而實(shí)現(xiàn)不同核上的任務(wù)之間的相互制約關(guān)系進(jìn)一步削弱，提高任務(wù)的并行執(zhí)行程度。因此，本文對(duì)基于核間通信的靜態(tài)SSC調(diào)度算法進(jìn)行了優(yōu)化，提出了基于核間通信的靜態(tài)OSSC（optimized simple schedule algorithm based on communication）調(diào)度算法。通過OSSC調(diào)度算法實(shí)現(xiàn)不同周期內(nèi)任務(wù)的重新的組織與調(diào)度，從而實(shí)現(xiàn)核間通信的降低，提高任務(wù)執(zhí)行效率。

三、結(jié)束語

在異構(gòu)多核處理器平臺(tái)中，核間的通信是必然存在的。針對(duì)多核周期性任務(wù)的調(diào)動(dòng)，本文針對(duì)核間通信開銷的減少而提出了優(yōu)化策略：第一，依據(jù)任務(wù)在不同核上的通信時(shí)間實(shí)現(xiàn)處理器核的分配，如果任務(wù)所需要的通信時(shí)長都較長，那么將這兩個(gè)任務(wù)分配到同一個(gè)處理器核上進(jìn)行運(yùn)行；第二，通過對(duì)任務(wù)調(diào)度時(shí)序圖進(jìn)行分析，找出任務(wù)中占用總線市場最長的通信型任務(wù)，通過核間數(shù)據(jù)傳輸?shù)奶崆巴瓿桑瑢?shí)現(xiàn)核間通信任務(wù)與計(jì)算型任務(wù)并行執(zhí)行，實(shí)現(xiàn)調(diào)度長度的有效縮短。本文將Cyclic算法為基礎(chǔ)，通過基于核間通信的SSC靜態(tài)調(diào)度算法與基于核間通信的靜態(tài)SSC調(diào)度算法的優(yōu)化兩次優(yōu)化，在一定程度上降低了核間通信開銷，即提高了任務(wù)執(zhí)行效率。

參考文獻(xiàn)：

[1]蔣建春，汪同慶.一種異構(gòu)多核處理器嵌入式實(shí)時(shí)操作系統(tǒng)構(gòu)架設(shè)計(jì)[J].計(jì)算機(jī)科學(xué)，2011（14）：298-303.

[2]陸小虎，于東，胡毅.基于異構(gòu)多核處理器的嵌入式數(shù)控系統(tǒng)研究[J].中國機(jī)械工程，2013（14）：2623-2628.