摘  要： 用一種遺傳算法的調(diào)度策略，以大維度矩陣求逆為實(shí)驗(yàn)對(duì)象，探索在多核中如何完成任務(wù)的均衡分配問題，以達(dá)到加速效果。算法利用系統(tǒng)資源的彈性，自動(dòng)搜尋可以并行的子任務(wù)并將其合理地分配到相應(yīng)計(jì)算節(jié)點(diǎn)中，提高了多核系統(tǒng)資源調(diào)度性能，實(shí)現(xiàn)了對(duì)用戶提交的任務(wù)的優(yōu)化調(diào)度，達(dá)到了均衡系統(tǒng)各處理器計(jì)算負(fù)載和提高多核系統(tǒng)的總體性能的目標(biāo)。
關(guān)鍵詞： 多核處理器；遺傳算法；任務(wù)調(diào)度；矩陣求逆

    隨著多核系統(tǒng)硬件結(jié)構(gòu)的成熟，多核系統(tǒng)的任務(wù)調(diào)度問題已經(jīng)成為本領(lǐng)域內(nèi)最重要的研究方向。多核系統(tǒng)主要由計(jì)算資源和通信資源組成，多核系統(tǒng)的調(diào)度問題可以概括為多計(jì)算資源和通信資源在時(shí)間軸上的分配問題。優(yōu)秀的資源調(diào)度算法能合理地分配多核系統(tǒng)計(jì)算資源，有效降低處理器計(jì)算的總執(zhí)行時(shí)間和總耗費(fèi)量，從而盡可能挖掘系統(tǒng)潛在性能。在超級(jí)計(jì)算機(jī)中，已經(jīng)有很多相關(guān)問題的解決方案，例如，基于遺傳算法和螞蟻算法的啟發(fā)式智能任務(wù)調(diào)度，源自于人工智能的Agent技術(shù)，嚴(yán)格定義的數(shù)學(xué)對(duì)象Petri網(wǎng)，以及多客戶多服務(wù)器方式的各種任務(wù)調(diào)度算法。但是，以上提到的算法的應(yīng)用大多是針對(duì)超級(jí)計(jì)算機(jī)的，對(duì)于微型的多核系統(tǒng)雖有其借鑒意義，但不能直接應(yīng)用。而且，對(duì)于單個(gè)大任務(wù)的分解及調(diào)度、各子任務(wù)之間的聯(lián)絡(luò)通信等情況需特殊考慮。遺傳算法利用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，從而解決非常困難的問題，其求解過程也可看作是最優(yōu)化過程。將遺傳算法應(yīng)用于多核任務(wù)調(diào)度中，利用遺傳算法所具有的并行性和全局解空間搜索的特點(diǎn)，實(shí)現(xiàn)合理的任務(wù)分配，以達(dá)到負(fù)載平衡的目的。這樣可以有效地縮短任務(wù)的完成時(shí)間，提高多核系統(tǒng)資源的使用效率。
1 系統(tǒng)平臺(tái)
    此實(shí)驗(yàn)的系統(tǒng)平臺(tái)如圖1所示，為基于二維網(wǎng)格的NoC（Network on Chip）系統(tǒng)。選擇這種結(jié)構(gòu)的原因有：二維網(wǎng)格是主流的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，利用IC平面工藝實(shí)現(xiàn)的方便性，XY路由策略的簡易性以及網(wǎng)絡(luò)的可測量性。在這種結(jié)構(gòu)中，每個(gè)計(jì)算節(jié)點(diǎn)都與一個(gè)通信節(jié)點(diǎn)相連，網(wǎng)拓?fù)浣Y(jié)構(gòu)為二維網(wǎng)格，節(jié)點(diǎn)數(shù)目可以是2×2、3×3、4×4、M×M等。物理層采用同步握手協(xié)議，網(wǎng)絡(luò)層采用XY路由算法。圖1所示的系統(tǒng)平臺(tái)示意圖中，圓圈代表各處理器，各處理器之間的實(shí)線箭頭代表各處理器之間的通信通道，虛線箭頭為遺傳算法的配置信號(hào)，點(diǎn)橫線箭頭為監(jiān)控模塊的監(jiān)測信號(hào)。遺傳算法模塊搜尋可以并行的子任務(wù)，并將其合理地分配到相應(yīng)計(jì)算節(jié)點(diǎn)中；監(jiān)控模塊監(jiān)控各處理器的負(fù)載情況。此后的實(shí)驗(yàn)以其中兩個(gè)核的任務(wù)分配為實(shí)驗(yàn)對(duì)象，驗(yàn)證所用遺傳算法的優(yōu)化作用。

2 實(shí)驗(yàn)及應(yīng)用
    矩陣求逆算法過程：設(shè)矩陣A的各階主子式|Aii|≠0(i=1，2，…，n)，則可以對(duì)A分解為：A=L×U。其中L為主對(duì)角線元素全為1的下三角矩陣(即單位下三角矩陣)，U為上三角矩陣。對(duì)于規(guī)模較大的矩陣，WANG K在1982年提出了塊LU分解方法[7，8]。假設(shè)輸入為一個(gè)n×n矩陣A=(aij)，分解為k2個(gè)m×m子矩陣Aij，其中i、j=1,2,…,k；n=km。輸出：k(k+1)個(gè)子矩陣Lpq，其中q≤p=1,2,…,k；子矩陣Urs，s≥r=1,2,…,k，每個(gè)子矩陣為m×m。對(duì)矩陣進(jìn)行塊LU分解后，也可以對(duì)三角矩陣進(jìn)行分塊求逆。其算法為，先對(duì)主對(duì)角線上的分塊子矩陣求逆，再對(duì)與主對(duì)角線平行的各斜列上的子矩陣進(jìn)行相應(yīng)的操作。由于A=L×U，因此A-1=U-1×L-1，為了提高算法并行度，同樣可以使用塊矩陣乘法計(jì)算。把塊U-1與L-1相乘，就可以得到所求矩陣的逆。
    根據(jù)上述的算法過程，可將算法整體分為三大步驟：分塊LU分解、三角矩陣分塊求逆和矩陣分塊相乘。雖然在同一個(gè)塊矩陣中這三步是依次進(jìn)行的，但是各矩陣塊的運(yùn)算并不是互為前提的，所以有些步驟的運(yùn)算可以并行進(jìn)行。而合適的遺傳算法可以通過搜索尋找到這些可以并行的子任務(wù)，并將其合理地分配到相應(yīng)計(jì)算節(jié)點(diǎn)中，從而減少系統(tǒng)運(yùn)算時(shí)間，提高系統(tǒng)資源利用率。
    遺傳算法執(zhí)行過程：參照參考文獻(xiàn)[1-4]，調(diào)整算法底層函數(shù)的實(shí)現(xiàn)方法和底層函數(shù)調(diào)用順序，使之適合本文的目標(biāo)任務(wù)。算法執(zhí)行過程如下：
    (1)分解：將目標(biāo)任務(wù)——5×5的矩陣塊（每個(gè)矩陣塊為3×3維的矩陣）的LU分解求逆分解成72個(gè)子任務(wù)；
    (2)高度函數(shù)[1]：為了促進(jìn)調(diào)度的產(chǎn)生和遺傳算子的構(gòu)造，定義任務(wù)圖中每個(gè)任務(wù)的高度為：

    (3)分組：依據(jù)各子任務(wù)的高度值將其分為兩組，并在此基礎(chǔ)上調(diào)用底層函數(shù)Generate_Schedule，生成初始種群；
    (4)適應(yīng)度：計(jì)算每個(gè)個(gè)體的適應(yīng)度值（運(yùn)算時(shí)間越短，適應(yīng)度值越大）；
    (5)繁殖：基于適應(yīng)度值，在繁殖的執(zhí)行過程中采用輪盤賭算法，產(chǎn)生新個(gè)體；
    (6)交叉：在區(qū)間[1，max{height}]中產(chǎn)生隨機(jī)數(shù)c，分別交換兩個(gè)體中高度值大于c的部分，一組新個(gè)體便產(chǎn)生了；
    (7)選擇：比較交叉前后兩個(gè)體的適應(yīng)度值，選擇較好的一組并將其儲(chǔ)存在新群體中；
    (8)循環(huán)：循環(huán)執(zhí)行步驟(4)～(7) maxgen次（maxgen的值已預(yù)設(shè)）；
    (9)找出最終調(diào)度循序：在最終的群體中，選擇適應(yīng)度值最大的個(gè)體即為所求。
    遺傳算法頂層調(diào)度模塊：
    T=task_graph;
    %-------------初始化--------------
    gen=0;        %代計(jì)數(shù)器
    maxgen=5;    %最大遺傳代數(shù)
    m=1;
    N=30;    %調(diào)用函數(shù)Generate_Schedule次數(shù)---pop_size
    for i=1:N
        [P_T,height]=Generate_Schedule(T);
        POP(i)={P_T};
    end
    %-----------循環(huán)迭代---------------
    while(gen<maxgen)
        for i=1:N
        [fitness_value(i),T_delt]=Fitness(POP{i},T);
        end
        New_pop = Reproduction(POP,fitness_value);
        for i=1:size(New_pop,2) %對(duì)New_pop里的每個(gè)
string調(diào)用函數(shù)crossover，產(chǎn)生新的個(gè)體
        P_T_new=Crossover(cell2mat(New_pop(i)),height);
        for m=1:size(P_T_new,1)
            for n=1:size(P_T_new,2)
                if(P_T_new(m,n).name==0)
                    P_T_new(m,n).name=[];
                end
            end
        end
          if(Fitness(P_T_new,T) > Fitness(cell2mat(New_pop
(i)),T))
              POP(i)={P_T_new};
          else
              POP(i)=New_pop(i);
          end
        end
        gen=gen+1;
    end
    %在最終的群里中挑選fitness_value最大的一個(gè)個(gè)體，即為所求
    for i=1:size(POP,2)
        fitness_value2(i)=Fitness(POP{i},T);
    end
    for i=1:length(fitness_value2)
        if(fitness_value2(i)==max(fitness_value2))
          T_best=POP(i);  %T_best即為所求
          min_time=1/fitness_value2(i);
        end
    end
    將優(yōu)化調(diào)度過的八核處理器的處理耗時(shí)與手動(dòng)調(diào)度的處理耗時(shí)進(jìn)行比較，如表1所示。為了使試驗(yàn)更加具有針對(duì)性，在此假設(shè)核之間的通信耗時(shí)為零，核之間通信速度對(duì)實(shí)驗(yàn)結(jié)果的影響將在以后的研究中予以深入分析。

    手動(dòng)調(diào)度的任務(wù)分配如下：前三個(gè)塊矩陣的求逆運(yùn)算放在第一個(gè)核中進(jìn)行，第四、五兩個(gè)矩陣塊的求逆運(yùn)算放在第二個(gè)核中進(jìn)行。
    實(shí)驗(yàn)結(jié)果表明，與之前的手動(dòng)的分解調(diào)度相比，應(yīng)用此遺傳算法后計(jì)算速度明顯加快，且隨著族群數(shù)量和遺傳代數(shù)的增加，優(yōu)化程度增高。
    本文針對(duì)已有的微型多核系統(tǒng)，以遺傳算法為研究手段，以多任務(wù)到多核系統(tǒng)的映射過程為研究核心，實(shí)現(xiàn)了系統(tǒng)資源的優(yōu)化分配，有效地縮短任務(wù)的完成時(shí)間，提高多核系統(tǒng)資源的使用效率；提高了多核系統(tǒng)的并行計(jì)算能力，減少了任務(wù)的平均響應(yīng)時(shí)間；提高了多核系統(tǒng)吞吐量和系統(tǒng)的資源利用率。
    由于遺傳算法本身的局限性，不可能找到最優(yōu)解，但算法可以進(jìn)一步改進(jìn)，例如增加新的算子[2]，增大最優(yōu)個(gè)體產(chǎn)生的幾率，或改進(jìn)現(xiàn)有的遺傳算法[5-6]；改進(jìn)任務(wù)調(diào)度方案，增加其實(shí)時(shí)性，即在給各個(gè)處理器分配任務(wù)時(shí)，一旦某個(gè)處理器空閑，馬上調(diào)用當(dāng)前可以處理的子任務(wù)，而不用等到全部處理器處理完當(dāng)前任務(wù)后同時(shí)啟動(dòng)下一組任務(wù)；增加計(jì)算節(jié)點(diǎn)數(shù)目，并在此基礎(chǔ)上增加更多的優(yōu)化目標(biāo)[7]。
參考文獻(xiàn)
[1] EDWIN S H，NINVAN A，Hong Ren.A genetic algorithm  for multiprocessor scheduling[J].IEEE Transactions On  Parallel And Distributed Systems，1994，5(2)：113-114.
[2] TSUJIMURA Y，GEN M.Genetic algorithms for solving  multiprocessor scheduling problems[M].Simulated Evolution  and Learning, Springer-Verlag, Heidelberg，1997：106-115.
[3] ALBERT Y，ZOMAYA，YEE H.Observations on using genetic algorithms for dynamic load-balancing[J].IEEE Transactions On Parallel And Distributed Systems，2001，12(9).
[4] SRINIVASA P，MUSICUS B R.Generalized multiprocessor scheduling and applications to matrix computations[J]. FIEEE Transactions on Parallel and Distributed systems,1996，7(6).
[5] WU A S，Han Yu，Jin Shiyuan，et al.An incremental genetic algorithm approach to multiprocessor scheduling[J]. IEEE Transactions On Parallel And Distributed Systems, 2004，15(9).
[6] MOHAMMAD R B，MOHSEN E M.A bipartite genetic algorithm for multi-processor task scheduling[J].Int J  Parallel Prog, 2009(37): 463-465.
[7] RAMANUJAM N，KALYANARAMAN K，NAGAPPAN M,  et al.Dynamic task scheduling using parallel genetic algorithms for heterogeneous distributed computing[C].Proceedings of the 2006 International Conference on Grid Computing & Applications(GCA)，Las Vegas, Nevada, USA, June 26-29, 2006.