[發(fā)明專利]一種基于改進(jìn)遺傳算法的NoC映射方法

有效

• 申請?zhí)枺?/td>: 201711399053.5
• 申請日: 2017-12-22
• 公開（公告）號: CN108153592B
• 公開（公告）日: 2021-09-17
• 發(fā)明（設(shè)計(jì)）人: 方娟;宗歡;趙浩炎
• 申請（專利權(quán)）人: 北京工業(yè)大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F15/78;G06N3/12
• 代理公司: 北京思海天達(dá)知識產(chǎn)權(quán)代理有限公司 11203
• 代理人: 張慧

本發(fā)明公開一種基于改進(jìn)的遺傳算法的異構(gòu)多核處理器任務(wù)映射方法，首先建立合適的編碼方案，通過構(gòu)造優(yōu)良的初始種群的方法來提高初始種群質(zhì)量，使得IP核布局更加合理。然后，為了解決在遺傳算法中早熟，容易陷入局部最優(yōu)的問題，在迭代過程中采用自適應(yīng)的變異概率機(jī)制：既保持種群中的優(yōu)良個體，又可以實(shí)現(xiàn)種群的多樣性。面向異構(gòu)多核架構(gòu)的改進(jìn)映射算法可使任務(wù)更合理地分配到各個網(wǎng)絡(luò)節(jié)點(diǎn)，對于優(yōu)化異構(gòu)多核上網(wǎng)絡(luò)功耗具有很高的效率。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)體系結(jié)構(gòu)領(lǐng)域，具體涉及一種基于改進(jìn)遺傳算法的NoC(片上網(wǎng)絡(luò))映射方法。

背景技術(shù)

片上網(wǎng)絡(luò)的不斷發(fā)展，使得片上網(wǎng)絡(luò)系統(tǒng)芯片上集成了越來越多的處理單元(IP核)。片上系統(tǒng)處理器正朝著多核化和異構(gòu)化的方向不斷發(fā)展。異構(gòu)多核處理器作為一種多核處理器，它相比于同構(gòu)多核處理器，具有運(yùn)行速度快、面積小、功耗低等優(yōu)良特性。然而，隨著核心數(shù)目的增加，片上網(wǎng)絡(luò)的功耗已經(jīng)成為了一個不可忽視的問題。映射決定IP核在異構(gòu)多核平臺片上網(wǎng)絡(luò)中的位置，一個好的映射方案能夠有效降低NoC的功耗，而NoC映射問題是NP難解問題。對于規(guī)模較小的片上網(wǎng)絡(luò)，利用窮舉遍歷的方法可以在較短的時間尋找出最優(yōu)方案。但是對于規(guī)模較大的NoC系統(tǒng)而言，遍歷的方法顯得既笨拙又耗時。如何實(shí)現(xiàn)在異構(gòu)多核平臺上的NoC映射，使得功耗最小化的問題成為了NoC領(lǐng)域的亟待解決的問題。群體智能算法較適用于求解二次分配問題，使用群體智能算法能夠計(jì)算出較接近最優(yōu)解的解決方案。然而，目前已有的應(yīng)用程序映射算法生成的映射方案的功耗結(jié)果并不十分理想。因此，本文提出對該方案的改進(jìn)。

發(fā)明內(nèi)容

本發(fā)明的目的是在于針對目前異構(gòu)多核處理器應(yīng)用在嵌入式計(jì)算領(lǐng)域中片上網(wǎng)絡(luò)映射問題存在明顯不足的情況下，提出一種基于改進(jìn)遺傳算法的NoC(片上網(wǎng)絡(luò))映射方法，可使得任務(wù)更合理地分配到各個網(wǎng)絡(luò)節(jié)點(diǎn)，對于優(yōu)化異構(gòu)多核上網(wǎng)絡(luò)功耗具有很高的效率。

本發(fā)明對現(xiàn)有的傳統(tǒng)遺傳算法提出改進(jìn)，通過運(yùn)用改進(jìn)的遺傳算法來完成片上網(wǎng)絡(luò)的映射過程，來實(shí)現(xiàn)功耗的降低。

具體的構(gòu)建方法如下：

步驟1，將任務(wù)分解成任務(wù)圖，每一個任務(wù)代表著一個特定的功能，并由一個IP核實(shí)現(xiàn)該功能，稱之為任務(wù)節(jié)點(diǎn)(總個數(shù)為n)。

步驟2，選擇一個規(guī)則的片上網(wǎng)絡(luò)NoC的架構(gòu)(m×m)，需滿足m²＝n，其中m²為NoC的資源節(jié)點(diǎn)個數(shù)，即NoC中資源節(jié)點(diǎn)的個數(shù)必須大于或等于任務(wù)圖中要映射任務(wù)節(jié)點(diǎn)的總個數(shù)n。

步驟3，建立功耗模型：

步驟3.1：由于我們的目標(biāo)是降低整體的通信代價(jià)及系統(tǒng)功耗，采用適應(yīng)度函數(shù)來評價(jià)系統(tǒng)功耗的大小。適應(yīng)度越高，功耗越小。通信功耗模型具體公式為(3-1)所示。

E_bit＝E_Sbit+E_Bbit+E_Wbit+E_Lbit (3-1)

其中，E_bit表示路由節(jié)點(diǎn)傳輸單位數(shù)據(jù)到另一個路由節(jié)點(diǎn)所產(chǎn)生的功耗，E_Sbit表示交叉開關(guān)的功耗，E_Bbit表示單位數(shù)據(jù)存在路由節(jié)點(diǎn)內(nèi)部緩存區(qū)所消耗的功耗，E_Wbit表示內(nèi)部線路的功耗，E_Lbit則代表單位數(shù)據(jù)通過網(wǎng)絡(luò)中通信互聯(lián)鏈路所消耗的功耗。

步驟3.2：E_Sbit、E_Bbit和E_Wbit的值主要由路由節(jié)點(diǎn)的內(nèi)部設(shè)計(jì)有關(guān)，并且不會隨著網(wǎng)絡(luò)中通信狀況而變化，可以近似地看作一個常量，所以我們統(tǒng)一用E_R表示，所以上面的公式就變?yōu)楣?3-2)所示。