面向層次形全連通的片上網絡的核映射方法
2023-05-18 19:26:56 3
專利名稱：面向層次形全連通的片上網絡的核映射方法
技術領域：
本發明涉及系統級晶片和片上網絡領域，特別是涉及一種層次形全連通的 片上網絡上的核映射方法。
背景技術：
隨著納米級CMOS集成電路技術和片上系統(SoC)技術的不斷發展，片上多 處理器(CMP)技術開始朝多核化(幾十或上百個核)和異構化(即包含不同類型的 核)的方向發展。目前，SoC設計中廣泛採用的共享總線結構存在許多問題，是 影響CMP性能的主要瓶頸-
(1) 帶寬限制。總線是一種共享介質的互連結構，某一時刻只允許一個設備 使用總線，仲裁邏輯允許高優先級的設備獲得總線的使用權。在總線被佔用期 間，其他所有請求被阻塞，直到總線空閒。當很多部件爭用一條總線時，會造 成嚴重阻塞，並會降低總線頻率等。
(2) 信號集成度。更低的電源電壓及更小的特徵線寬使得整個SoC系統對電 流中的噪聲更加敏感，而共享介質上的功能部件則進一步加重了噪聲。
(3) 信號延遲。隨著集成特徵尺寸的下降，連線延遲成為影響信號延遲的主 要因素。總線結構是全局控制的，在10億電晶體時代，全局連線延遲大於時鐘 周期，因此，總線結構的全局連線使得時鐘的偏移很難管理。
(4) 全局同步。全局連線上的信號延遲決定了系統的時鐘周期，為了保持甚 至提高系統時鐘頻率，只能對全局連線進行分布式流水線模式，或採用全局異 步局部同步(GALS)的時鐘模式。
由於共享總線結構己經無法滿足SoC系統的需要，因此把互連網絡用於片 上系統設計，解決片上組件之間的通信問題，即片上網絡(Network-on-chip, NoC)。 NoC技術以其支持同時訪問、可靠性高、可重用性高等特點成為更理想的 大規模CMP互連技術。NoC克服了總線結構可擴展性差的缺點，為10億電晶體 時代提供了一種可行的片上系統通信機制。它除了可以連接更多的IP組件，與 總線結構相比，還有高可重用性等特點。可重用性是SoC設計的一個重要設計 原則。可重用性設計可以節省設計成本、提高設計的可靠性、縮短產品的上市 周期。在基於總線的SoC設計中，各個IP組件是可重用的，但通信結構無法重 用，必須重新設計；在NoC中，各組件是可重用的，片上通信結構及片上通信服務也是可重用的。設計新系統時，只須在原系統上添加路由部件和功能部件， 大大加快了設計的進度。
NoC上的核映射是NoC設計中的一個重要步驟，確定了SoC所選用的IP核之 後，核映射就決定了從IP核到NoC體系結構的對應關係。不同的映射結果，對於 系統的通信時延、通信能耗等性能有著重要的影響。為了減小NoC上的通信能耗， 需要找到一種核映射結果使得所有核之間的通信帶寬要求與通信距離的乘積和 要儘可能的小。NoC上的核映射等同於受約束的二次分配問題，直接的做法是用 智能算法來尋找較優的映射結果。但是當NoC規模變大時，智能算法的執行時間 會呈指數級增長。因此，許多研究者提出了各種算法來縮短尋找映射結果的時 間。但目前只有在二維網格結構的片上網絡上來尋找映射結果的算法，還沒有 針對層次形全連通的片上網絡提出一種快速尋找映射結果的算法。
發明內容
本發明的目的在於提供一種面向層次形全連通的片上網絡的核映射方法。 本發明解決其技術問題採用的技術方案如下
1) 快速產生初始核映射
第一步，根據片上網絡中全連通網絡結構來對核進行聚類，使得通信帶寬 要求大的核聚集到同一個類中，類的個數等於全連通網絡結構中的節點數，每 個類中的核的數量相等；
第二步，對第一步中產生的類進行聚類，重複執行第一步中的聚類過程， 直到新產生的類中核的數量等於片上網絡中全連通網絡結構的節點數；
第三步，計算下一次聚類產生的每個類與不是自己所在的上一次聚類產生 的每個類之間的通信帶寬要求來確定下一次聚類產生的每個類在片上網絡上的 映射位置；重複進行迭代計算過程，直到確定了每個核在片上網絡上的映射位
2) 用遺傳算法優化初始核映射
用初始核映射作為遺傳算法的種子，設定遺傳算法的迭代次數，在迭代過 程結束後產生最終的核映射結果。
與現有技術相比，本發明的有益效果是-
(1)高效性。本發明實現了一種面向層次形全連通的片上網絡的核映射方 法，在片上網絡規模變大時，用遺傳算法來尋找映射結果時隨機產生遺傳算法 的種子的時間會呈指數級增長，而本發明的方法能夠快速地產生初始核映射作為遺傳算法的種子，因此明顯縮短了層次形全連通的片上網絡的核映射時間。 而且本發明的方法產生的初始核映射把通信帶寬要求大的核放到相臨較近的位 置，比隨機產生的核映射的結果要好，因此產生相等的核映射結果本發明的方 法中遺傳算法需要的迭代次數要少，縮短了遺傳算法的運行時間，從而縮短了 層次形全連通的片上網絡的核映射時間。
(2) 可靠性。本發明通過對層次形全連通的片上網絡的結構進行仔細的分 析，仔細地設計了產生層次形全連通的片上網絡的初始核映射的過程，並仔細 地設計了遺傳算法的運行過程，保證了算法最終能夠產生核映射結果。
(3) 實用性。本發明提出的一種面向層次形全連通的片上網絡的核映射方 法，可以稍做修改用於不同拓撲結構的片上網絡中。
圖1是16個節點的層次形全連通的片上網絡的示意圖。 圖2是64個節點的層次形全連通的片上網絡的示意圖。 圖3是產生層次形全連通的片上網絡的核映射結果的算法示意圖。
具體實施例方式
1) 層次形全連通的片上網絡
層次形全連通的片上網絡(WK-recursive NoC)是一種非常重要拓撲結構的 片上網絡。層次形全連通的片上網絡是由基本單元遞歸地構造，基本單元可以 是任意節點數的全連通網絡。下面為了方便，用WK(d，t)來表示一個有t層網絡， 基本單元是d個節點的全連通網絡的層次形全連通的片上網絡，其中d>l, 21. 圖1是16個節點的層次形全連通的片上網絡，可以用WK(4,2)表示，4表示基 本單元是4個節點相互之間都連通的網絡，2表示整個層次形全連通的片上網絡 有兩層遞歸的網絡結構。圖2是64個節點的層次形全連通的片上網絡，可以用 WK(4,3)表示，3表示整個層次形全連通的片上網絡有三層遞歸的網絡結構。
2) 快速產生初始核映射
下面用WK(4,3)的層次形全連通的片上網絡來說明整個算法的運算過程，如 圖3所示
第一步，根據片上網絡中全連通網絡結構來對核進行聚類，使得通信帶寬 要求大的核聚集到同一個類中,類的個數等於全連通網絡結構中的節點數，每 個類中的核的數量相等
WK(4，3)的層次形全連通的片上網絡中的全連通網絡結構的節點數是4，所 以把64個核分成4類，每個類中有16個核。首先，從64個核中選出相互之間
5通信帶寬要求最大的兩個核，然後從剩下的62個核中選出一個與前面已經選出 的兩個核通信帶寬要求的和最大的核，接著選出一個與前面已經選出的三個核 通信帶寬要求的和最大的核，直到選出了16個核，這樣就構成了一個類。把第 一個選出的類放到圖2中標號以"0"為開頭的WK(4,2)的層次形全連通的片上 網絡中，重複前面的過程，把接著選出的三個類按先後順序分別放到標號以"l" 為開頭、以"2"為開頭、以"3"為開頭的WK(4，2)的層次形全連通的片上網絡 中.
第二步，對第一步中產生的類進行聚類，重複執行第一步中的聚類過程， 直到新產生的類中核的數量等於片上網絡中全連通網絡結構的節點數
對第一步中產生的4個類都重複第一步的過程，把每個類都再分成4個類。 因為這樣新產生的每個類中都包含4個核，等於全連通網絡結構的節點數4，所 以第二步的運算完成。如果是WK(4，4)的層次形全連通的片上網絡，第二步就需 要重複執行兩次第一步中的聚類過程。
第三步，計算第二次聚類產生的每個類與不是自己所在的第一次聚類產生 的每個類之間的通信帶寬要求來確定第二次聚類產生的每個類在片上網絡上的 映射位置
現在要調整每個基本單元在WK(4,2)中的位置。分別計算標號以"0"為開 頭的WK(4,2)的層次形全連通的片上網絡中的4個基本單元與不是自己所在的 另外三個WK(4,2)之間的通信帶寬要求。把通信帶寬要求最大的基本單元放到位 置最近的位置上，假如前面的計算得到基本單元(000，001，002,003)和標號以"2" 為開頭的WK(4,2)的通信帶寬要求最大，則把原來基本單元(000，001，002，003)上 的核放到基本單元(020,021,022，023).接著分別調整通信帶寬要求第二和第三大 的基本單元的位置來縮短通信距離，最後把通信帶寬要求最小的核放到基本單 元(000，001,002,003).重複前面的過程，分別調整另外三個WK(4,2)的層次形全連 通的片上網絡中的基本單元的位置。
第四步，在第三步的映射結果基礎上，重複進行第三步的迭代計算過程， 直到確定了每個核在片上網絡上的映射位置
在每個WK(4,2)的層次形全連通的片上網絡中，計算每個核與不是自己所在 的另外三個基本單元之間的通信帶寬要求，按照第三步的過程來調整每個核的 位置。
3)用遺傳算法優化初始核映射
用初始核映射作為遺傳算法的種子，設定遺傳算法的迭代次數，在迭代過程結束後產生最終的核映射結果。
遺傳算法的所有種子都是前面產生的初始核映射，根據核映射結果的要求 來設定遺傳算法的迭代次數，在遺傳算法運算結束時產生最終的核映射結果。
權利要求
1. 一種面向層次形全連通的片上網絡的核映射方法，其特徵在於1)快速產生初始核映射第一步，根據片上網絡中全連通網絡結構來對核進行聚類，使得通信帶寬要求大的核聚集到同一個類中，類的個數等於全連通網絡結構中的節點數，每個類中的核的數量相等；第二步，對第一步中產生的類進行聚類，重複執行第一步中的聚類過程，直到新產生的類中核的數量等於片上網絡中全連通網絡結構的節點數；第三步，計算下一次聚類產生的每個類與不是自己所在的上一次聚類產生的每個類之間的通信帶寬要求來確定下一次聚類產生的每個類在片上網絡上的映射位置；重複進行迭代計算過程，直到確定了每個核在片上網絡上的映射位置；2)用遺傳算法優化初始核映射用初始核映射作為遺傳算法的種子，設定遺傳算法的迭代次數，在迭代過程結束後產生最終的核映射結果。
全文摘要
本發明公開了一種面向層次形全連通的片上網絡的核映射方法。本發明實現了快速產生初始核映射和用遺傳算法來優化初始核映射。本發明是充分利用了層次形全連通網絡拓撲的片上網絡的特點從而有效地實現了層次形全連通的片上網絡上的核映射方法。在遺傳算法運行前快速產生一種比隨機產生要好的初始核映射，明顯地縮短了層次形全連通的片上網絡的核映射時間。本發明可用於不同拓撲結構的片上網絡中。
文檔編號G06N3/00GK101505271SQ20091009595
公開日2009年8月12日 申請日期2009年2月26日 優先權日2009年2月26日
發明者吳斌斌, 居立晗, 施青松, 滿 曹, 超 王, 威 胡, 度 陳, 陳天洲, 馬建良 申請人:浙江大學