[發明專利]一種改進的遺傳退火的片上網絡映射方法

在審

• 申請號: 201710902013.1
• 申請日: 2017-09-29
• 公開（公告）號: CN109582985A
• 公開（公告）日: 2019-04-05
• 發明（設計）人: 魏瑩
• 申請（專利權）人: 魏瑩
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

為滿足帶寬約束的低能耗片上網絡映射問題，發明一種基于災變遺傳退火的映射算法．該算法以標準遺傳算法為基礎，引入Boltzmann選擇方法，對遺傳操作后的較優個體采用多鄰域的模擬退火操作進行優化，對處于停滯狀態的種群使用災變操作重新初始化部分較差個體，該發明能根據當前種群適應度的計算結果動態調整個體被選擇的概率，使得算法搜索向適應度最優的方向靠攏，跳出局部極值．該發明具有優化性能好，收斂速度快，通信能耗低的優點。

所屬技術領域

本發明涉及片上網絡中映射算法的設計。

背景技術

隨著納米級CMOS集成電路技術的發展，集成度的提高，片上系統將集成更多的異源處理器核來實現更復雜的功能．傳統片上系統采用的總線通信結構將難以滿足眾多處理器核的通信需求，成為限制系統性能提高的關鍵因素．借鑒了分布式計算系統的通信方式、采用路由和分組交換技術替代傳統總線的片上網絡結構被認為是最有希望解決復雜片上通信問題的新方法，成為研究的熱點。NoC 由計算資源與通信網絡兩部分組成。計算資源由IP 核與本地內存構成，可獨立完成廣義的“計算”任務。IP核可以是 CPU、DSP、RAM、高帶寬的I/O設備、可重構硬件單元等，通過網絡接口（Network Interface，NI）與網絡相連。通信網絡主要包括路由器與網絡接口，路由器與路由器、路由器與網絡接口之間鏈路連接，實現資源節點間的高速數據通信。

隨著集成度的不斷提高，系統的功耗也會在不斷的增加，如何有效地降低整個系統功耗成為片上網絡設計的關鍵問題．IP核映射是片上網絡設計中的一個重要步驟．不同的映射結果對系統的執行效率、通信能耗、通信時延等性能有著重要的影響．通過各種方法實現IP 核映射以降低通信能耗變得越來越重要。映射就是將任務圖中的IP核放置在拓撲結構的資源上的過程，決定了IP核與網絡中的路由器的連接關系。在給定網絡拓撲結構和具體應用通信任務圖的情況下，IP核在網絡中的相對位置對系統的性能有著重要的影響。映射可分為動態映射和靜態映射。在動態映射中，任務或IP核映射的位置可以隨著片上網絡資源分配需要而改變，各任務之間的通信量也可能是隨機的。在靜態映射中，在給定特定應用并將其分解為通信任務圖后，在從IP核到處理單元的映射過程中，包括通信量、時延等在內的所有通信特征都保持不變，映射結果與IP核的映射位置也不會改變，即不能進行遷移。

標準遺傳算法和模擬退火是映射問題中經典的算法，其中標準遺傳算法（GeneticAlgorithm，GA）是進化計算中最初形成的一種具有普遍影響性的隨機化搜索方法，它借鑒生物界的進化規律演化而來，屬于啟發式算法的一種，采用概率化的尋找方法在較大空間進行有效搜索，由于其良好的全局尋優能力和簡單的操作流程。遺傳算法的基本操作包括：算法初始化、選擇操作、交叉操作和變異操作等。其中，選擇操作是指從群體中選擇優勝的個體，淘汰劣勢個體的過程。選擇的目的主要是把優化的個體或解直接遺傳到下一代或通過其它遺傳操作產生的新個體遺傳到下一代。而交叉操作和變異操作則以一定概率執行，交叉操作主要是將兩個父代個體的部分結構加以替換重組而產生的新個體操作，從而期望提升個體的適應度。變異操作主要是對群體中特定個體編碼串上的某些基因值進行變動，在每個染色體上自發地產生隨機變化替換一個或多個基因，它的引入主要是為提升算法的局部搜索能力以及解的多樣性。

模擬退火算法（Simulated Annealing，SA）來源于固體退火原理，是一種基于MonteCarlo 迭代求解策略的隨機尋優算法，其物理背景是固體退火的物理現象和統計力學模型，即將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫度上升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小[71]。模擬退火算法從某一較高初溫出發，伴隨溫度參數的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數的全局最優解，即能概率性地跳出局部最優解并最終趨于全局最優。由于算法在理論上具有概率的全局優化性能，目前已在工程中得到了廣泛的應用。模擬退火算法有兩個主要操作：一是稱為冷卻流程的熱靜力學操作，用于設定溫度 t 的下降幅度；另一個用于在每個溫度下搜索最優解的隨機松弛過程。