在多核技術的發(fā)展過程中,如何優(yōu)化任務調(diào)度問題,提升多核并行計算能力一直是人們關注的重點問題。在傳統(tǒng)的任務調(diào)度問題研究中,諸如任務復制、任務聚簇、列表調(diào)度等傳統(tǒng)方法,往往不能完全反映解空間的構(gòu)成情況,很難從可能的調(diào)度解中一次性獲得較好的調(diào)度結(jié)果,因此針對此類問題的搜索算法成為這方面研究的主要方向。本文以智能搜索算法中的遺傳算法作為搜索最優(yōu)調(diào)度解的方法,設計了基于全局列表和聚簇-列表混合的兩種搜索算法GLPGA和CLGA。GLPGA算法使用并行遺傳算法中的島式模型,使用不同遺傳算子并行搜索全局調(diào)度列表,通過遷移的方式,擴大較優(yōu)解空間的搜索范圍;CLGA算法使用聚簇和列表調(diào)度相結(jié)合的方式,求解任務到計算單元較優(yōu)分配方式,通過全局任務列表確定各簇中任務的執(zhí)行優(yōu)先級,并使用一種自適應收斂判斷標志主動結(jié)束搜索過程的方法尋找最優(yōu)解。在多核系統(tǒng)模型上,本文采用了基于片上網(wǎng)絡通訊架構(gòu)中2D-Mesh結(jié)構(gòu)的多核模型,對任務處理中通訊過程進行行為級建模。算法使用大量隨機靜態(tài)任務圖在2D-mesh結(jié)構(gòu)模型下模擬調(diào)度結(jié)果,測試表明,算法在片上的規(guī)范化調(diào)度長度在低于1.9,并行度加速比Speedup可達3.9,具...

【文章頁數(shù)】：59 頁

【學位級別】：碩士

【部分圖文】：

圖1.1任務圖G1Fig1.1TaskGraphG1

值表示任務的計算開銷和通訊量，可以使用集合G=V,E,W,C來完全概括一張任務圖。其中V=Ti是所有任務的集合，Ti表示單個任務;E=ei,j是任務之間驅(qū)動關系的集合，ei,j表示任務Ti是任務Tj的前驅(qū)任務(pred_task)，而任務Tj是任務Ti的后繼任務(succ_tas....

圖2.2全互聯(lián)多核模型

第三章NoC下基于遺傳算法的靜態(tài)任務調(diào)度方案112.2任務調(diào)度算法的多核模型全互聯(lián)模型是現(xiàn)有的調(diào)度算法大量使用的一種多核模型，如圖2.2所示。在這種多核模型下，每個計算單元都有互相連接的通路，不同計算單元間的通訊可獨立進行，互不干擾。全互聯(lián)模型完全消除了通訊中的擁堵和等待，是通訊....

圖4.1GLPGA算法流程

第四章NoC下基于遺傳算法的靜態(tài)任務調(diào)度算法26圖4.1GLPGA算法流程Fig4.1GLPGAalgorithmflow4.1.2GLPGA算法的編碼GLPGA算法的優(yōu)化目標是尋找到更為合理的任務列表，使得在任務調(diào)度過程中，處于關鍵位置的任務能夠盡可能優(yōu)先被調(diào)度，提高任務并行性....

圖4.4SPX算子Fig4.4SPXoperator

第四章NoC下基于遺傳算法的靜態(tài)任務調(diào)度算法274.1.3GLPGA算法的遺傳算子遺傳算子一般由突變算子和交叉算子兩種構(gòu)成。通過突變算子可以快速產(chǎn)生豐富的新基因型，通常作用于一條基因上；交叉算子能夠?qū)崿F(xiàn)兩條基因?qū)恢蒙掀蔚慕粨Q，可以用于整合不同的基因特征。GLPGA算法是一種....

本文編號：3912882