摘  要： 用一種遺傳算法的調度策略，以大維度矩陣求逆為實驗對象，探索在多核中如何完成任務的均衡分配問題，以達到加速效果。算法利用系統資源的彈性，自動搜尋可以并行的子任務并將其合理地分配到相應計算節點中，提高了多核系統資源調度性能，實現了對用戶提交的任務的優化調度，達到了均衡系統各處理器計算負載和提高多核系統的總體性能的目標。
關鍵詞： 多核處理器；遺傳算法；任務調度；矩陣求逆

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

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

    (3)分組：依據各子任務的高度值將其分為兩組，并在此基礎上調用底層函數Generate_Schedule，生成初始種群；
    (4)適應度：計算每個個體的適應度值（運算時間越短，適應度值越大）；
    (5)繁殖：基于適應度值，在繁殖的執行過程中采用輪盤賭算法，產生新個體；
    (6)交叉：在區間[1，max{height}]中產生隨機數c，分別交換兩個體中高度值大于c的部分，一組新個體便產生了；
    (7)選擇：比較交叉前后兩個體的適應度值，選擇較好的一組并將其儲存在新群體中；
    (8)循環：循環執行步驟(4)～(7) maxgen次（maxgen的值已預設）；
    (9)找出最終調度循序：在最終的群體中，選擇適應度值最大的個體即為所求。
    遺傳算法頂層調度模塊：
    T=task_graph;
    %-------------初始化--------------
    gen=0;        %代計數器
    maxgen=5;    %最大遺傳代數
    m=1;
    N=30;    %調用函數Generate_Schedule次數---pop_size
    for i=1:N
        [P_T,height]=Generate_Schedule(T);
        POP(i)={P_T};
    end
    %-----------循環迭代---------------
    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) %對New_pop里的每個
string調用函數crossover，產生新的個體
        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最大的一個個體，即為所求
    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
    將優化調度過的八核處理器的處理耗時與手動調度的處理耗時進行比較，如表1所示。為了使試驗更加具有針對性，在此假設核之間的通信耗時為零，核之間通信速度對實驗結果的影響將在以后的研究中予以深入分析。

    手動調度的任務分配如下：前三個塊矩陣的求逆運算放在第一個核中進行，第四、五兩個矩陣塊的求逆運算放在第二個核中進行。
    實驗結果表明，與之前的手動的分解調度相比，應用此遺傳算法后計算速度明顯加快，且隨著族群數量和遺傳代數的增加，優化程度增高。
    本文針對已有的微型多核系統，以遺傳算法為研究手段，以多任務到多核系統的映射過程為研究核心，實現了系統資源的優化分配，有效地縮短任務的完成時間，提高多核系統資源的使用效率；提高了多核系統的并行計算能力，減少了任務的平均響應時間；提高了多核系統吞吐量和系統的資源利用率。
    由于遺傳算法本身的局限性，不可能找到最優解，但算法可以進一步改進，例如增加新的算子[2]，增大最優個體產生的幾率，或改進現有的遺傳算法[5-6]；改進任務調度方案，增加其實時性，即在給各個處理器分配任務時，一旦某個處理器空閑，馬上調用當前可以處理的子任務，而不用等到全部處理器處理完當前任務后同時啟動下一組任務；增加計算節點數目，并在此基礎上增加更多的優化目標[7]。
參考文獻
[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.