發(fā)布時(shí)間：2024-02-27 19:45

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖1.1任務(wù)圖G1Fig1.1TaskGraphG1

值表示任務(wù)的計(jì)算開(kāi)銷(xiāo)和通訊量，可以使用集合G=V,E,W,C來(lái)完全概括一張任務(wù)圖。其中V=Ti是所有任務(wù)的集合，Ti表示單個(gè)任務(wù);E=ei,j是任務(wù)之間驅(qū)動(dòng)關(guān)系的集合，ei,j表示任務(wù)Ti是任務(wù)Tj的前驅(qū)任務(wù)(pred_task)，而任務(wù)Tj是任務(wù)Ti的后繼任務(wù)(succ_tas....

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

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

圖4.1GLPGA算法流程

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

圖4.4SPX算子Fig4.4SPXoperator

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

本文編號(hào)：3912882