西電數(shù)模選修作業(yè)

1、 數(shù)學模型 2017年期末考試大作業(yè)選題:校賽A題學院：學號：姓名時間：2017年4月27日-2017年5月4日 NOC 結構的研究 摘要 片上網(wǎng)絡作為一種新的片上系統(tǒng)通信架構， 在多核處理器方面得到廣泛應用。 本文針對片上網(wǎng)絡映射時的不同拓撲結構， 分別設計了考慮能耗、 鏈路帶寬、芯片溫度時， 所對應的最優(yōu)映射方案。 針對問題一， 在 2D Mesh 拓撲結構和 2D Torus 拓撲結構中引 入曼哈頓距離來計算 IP 核之間傳遞信息所經(jīng)過的鏈路數(shù)， 由此得出傳遞信息經(jīng)過的路由器數(shù)?？紤]到曼哈頓距離在高維的局限性， 在超立方拓撲結構中， 引 入用 0, 1 賦值的四維向量來表示 IP 核在拓

2、撲圖中的位置， 進而計算出鏈路數(shù)與路由器數(shù)， 建立單目 標無約束優(yōu)化模型， 利用遺傳算法求出體系能耗最低的映射方案。 針對問題二， 對于鏈路選擇問題， 通過在鏈路表示上引 入高維向量， 將 2DMesh， 2D Torus 和超立方體拓撲結構中的鏈路分別限制在 2*4*3, 2*4*4 和4*2*2*2 向量矩陣以實現(xiàn)鏈路的具體表達， 在 the west-first and odd-even 路由算法的啟發(fā)下提出了方向限定， 對于 2D Mesh, 2D Torus 模型， 限定路徑按向下， 向右兩個次序選取， 對于超立方體模型， 限定路徑按單立方體向右， 向下，向里， 以及外立方體向內(nèi)四個

3、次序選取。 將帶寬放在目 標函數(shù)層考慮， 結合能耗最低， 建立線性加權多目 標優(yōu)化模型， 利用問題一的方法進行求解。 針對問題三， 通過定義兩個 IP 核之間的熱轉(zhuǎn)移關系即熱阻D來得到 IP 核溫度求解公式， 結合第一問的能耗最低模型， 利用 IP 核的功耗求解得到 IP 核的溫度， 并將 IP 核溫度之間的標準差作為目 標優(yōu)化函數(shù)， 利用遺傳算法進行單目 標優(yōu)化問題求解， 得到溫度分布較為均衡的映射方案。綜上所述， 本文討論了 NOC 影響因素功耗， 功耗以及帶寬， 以及溫度對映射的影響， 最后對所建立的模型及算法進行了評價。關鍵詞： 片上網(wǎng)絡 曼哈頓距離 遺傳算法 線性加權多目 標優(yōu)化 熱

4、分布 一、 問題重述1 .1 .問題的背景處理器逐漸步入多核時代， 人們?nèi)?常使用的手機已經(jīng)是四核甚至八核。 英特爾公司面向高性能計算推出了 48 核的商用芯片。 芯片上每一個核都可以獨立的執(zhí)行不同的任務， 有效的提升了處理器的計算能力。 隨著芯片上集成的IP 核數(shù)目 不斷增加， 傳統(tǒng)總線結構資源利用率低、 可擴展性差、 可重用性差等缺點也越發(fā)的突出。 為了克服總線結構的不足， 一種新的片上系統(tǒng)通信架構片上網(wǎng)絡(NoC) 應運而生。片上網(wǎng)絡映射， 是指在給定任務核圖和拓撲結構的基礎上， 針對特定設計目標和約束條件， 決定每個IP核在片上網(wǎng)絡拓撲結構上的位置， 使映射之后的系統(tǒng)達到較高的網(wǎng)絡性能

5、。 對于既定的片上網(wǎng)絡拓撲結構， 映射性能的好壞決定著網(wǎng)絡最終實現(xiàn)后的整體性能， 不同的映射匹配結果會導致網(wǎng)絡性能差異較大。 映射的目 的就是要找到盡可能優(yōu)的分配方案， 使系統(tǒng)的性能達到最優(yōu)。 衡量映射方案性能好壞的主要指標有能耗、 時延、 吞吐、 熱量均衡以及服務質(zhì)量以及算法的時間復雜度等。IP核在運行過程中會產(chǎn)生熱量， 當大量IP核集成在芯片上時， 運行過程中芯片的溫度將迅速升高， 而過高的芯片溫度會影響系統(tǒng)的性能。 而當系統(tǒng)到達穩(wěn)定狀態(tài)時， 每個IP核的溫度取決于IP核的功耗和IP核之間的熱阻。1 .2.問題的提出（1） 以題目 所給的任務圖為例， 針對每種拓撲結構建立映射優(yōu)化模型， 并

6、采用優(yōu)化算法求解最低能耗開銷。 已知信息傳播過程中的能耗主要考慮路由器和鏈路上的能耗開銷， 1bit信息在鏈路和路由器的能耗分別為 5. 445pJ和 0. 43pJ。（2） 全網(wǎng)路由器之間的鏈路帶寬是一個定值（例如 500Mbps） ， 如果在一條鏈路上傳輸?shù)男畔⒘恐统^這一定值， 則該段鏈路會出現(xiàn)阻塞。 在問題 1的基礎上， 建立多目 標優(yōu)化模型實現(xiàn)低能耗開銷的無阻塞映射方案。（3） 請查找資料對參數(shù)進行合理假設， 針對每種拓撲結構設計相應的映射方案使得片上網(wǎng)絡中IP核的溫度分布較為均衡。二、 問題分析2.1 .問題一的分析問題一要求在信息傳播過程中僅考慮路由器和鏈路上的能耗開銷時， 針

7、對不同的拓撲結構尋找一種IP核到片上網(wǎng)絡節(jié)點的一對一的映射關系， 使得信息傳播過程中的能耗開銷最小。要在給定核圖和拓撲圖的情況下求解最小的能耗開銷。 而路由器的能耗開銷與路由器的數(shù)量成正比， 鏈路的能耗開銷與其曼哈頓距離成正比， 所以可以用路由器的數(shù)量和鏈路的曼哈頓距離分別與其能量權重相乘后再與傳輸?shù)男畔⒘肯喑藖肀硎久恳幌⑼返哪芎拈_銷。 將每一消息通路的能耗相加便可得總的能耗開銷， 接下來再進行目 標優(yōu)化， 求得最小能耗， 因此采用基于遺傳算法的片上網(wǎng)絡算法 1 來求解信息傳播過程中能耗開銷最小的映射。2.2.問題二的分析問題二引 入鏈路帶寬， 要求在信息傳播過程中， 在不超過鏈路帶寬的情

8、況下，求一種從核圖到拓撲圖的最佳映射， 使得能量開銷和鏈路帶寬兩個目 標最優(yōu)。 解決該問題應先尋求一種鏈路的表達方式。 在此基礎上結合問題一， 我們建立線性多目 標優(yōu)化模型， 采用基于遺傳算法的片上網(wǎng)絡算法來實現(xiàn)低能耗開銷的無阻塞方案。2.3.問題三的分析芯片在實際應用過程中由于局部溫度過高會嚴重影響整個芯片， 而在片上網(wǎng)絡中局部溫度過高， 會導致系統(tǒng)的可靠性下降， 因此需要同時考慮各節(jié)點間的溫度標準差， 使得片上網(wǎng)絡中 IP 核的溫度較為均衡。 每個 IP 核的溫度取決于 IP 核的功耗和 IP 核之間的熱阻， 而熱阻則受 IP 核位置和其物理特性的影響。 為使得片上網(wǎng)絡中 IP 核的溫度分

9、布較為均衡， 要先求出 IP 核的溫度， 再通過最小化各核溫度的標準差來實現(xiàn)溫度均衡。 因此， 仍采用基于遺傳算法的片上網(wǎng)絡算法，來求得 IP 核溫度分布較為均衡的映射。三、 模型假設1. 鏈路的能耗開銷主要集中在鏈路的建立過程， 因此忽略鏈路長度的影響， 直接將鏈路能耗開銷正比于鏈路數(shù)量2. 5.445 和 0.43 分別表示單位信息通過單條鏈路和單個路由器的能耗開銷權重3. 信息傳播中的能耗只考慮鏈路和路由器上的能耗4. NoC 系統(tǒng)始終以理想穩(wěn)定狀態(tài)運行四、 符號說明符號 說明C IP 核的集合ci 第 i 個 IP 核A IP 核圖中有向邊集合aij IP 核 i 與 IP 核 j 之

10、間通信vol(aij) IP 核 i 與 IP 核 j 之間的通信量N 拓撲圖中節(jié)點的集合ni 拓撲圖中的第 i 個節(jié)點L 鏈路的集合lij 節(jié)點 i到j 的鏈路bwij 路由器 i 到路由器 j 的通信帶寬ei 第 i 個核的功耗E 能耗開銷Ti IP 核 i 的溫度Rij IP 核 i 與 IP 核 j 間的熱阻五、 模型的建立與求解分析可知， 問題一只考慮功耗， 問題二考慮功耗和帶寬， 問題三只考慮溫度，所以建立三個不同模型進行求解。5.1 問題一的模型建立與求解問題需要建立模型， 尋求以低功耗為目 標的最優(yōu)映射， 而功耗只與鏈路數(shù)量和路由數(shù)量有關， 據(jù)此建立如下模型。5. 1. 1 2

11、D Mesh 拓撲結構5. 1. 1. 1 模型建立 該模型需要尋找映射 map()： 使得能夠由 C映射到 N 即 將 map(ci) 到 map(c j) 的曼哈頓距離記為 MDij ， 即鏈路的曼哈頓距離可由MDij 表示， 而每一消息通路所經(jīng)過的路由器的數(shù)量可由 (MDij +1) 來表示， 由題目 可知路由器上的能量權重為 0. 43， 鏈路上的能量權重為 5. 445， 所以目 標函數(shù)可寫為åE=節(jié)點ni 的坐標可表示為（xi, yi） ， 節(jié)點 n j 的坐標可表示為（x j, y j) ， 由此可得，MDij =| x j -xi |+ | y j - yi | （2

12、）而優(yōu)化問題就變?yōu)閷ふ乙粋€映射 map 使得能耗開銷E1 最小5. 1. 1. 2 模型分析與求解本模型的變異操作采用如下方式: 隨機選擇兩個基因, 然后交換這兩個基因，這樣便能確保染色體上的基因不重復。用 Matlab 實現(xiàn)， 在 4×4 的 2D Mesh 拓撲結構上對題目 所給的 IP 核圖做 200 次映射， 取交配概率 pc = 0.25 和變異概率 pm =0.02 ,用遺傳算法對該映射的收斂性分析結果如下圖 1 .3 所示。 圖1.3heng5.2 問題二的模型建立與求解5.2.1 模型建立在本模型中， 先計算任意 IP 核 i 映射到的節(jié)點（xi, yi） 到任意 I

13、P 核 j 映射到的節(jié)點（ x j, y j ）的所經(jīng)過的鏈路， 再分別乘兩 IP 核間的通信量 vol(aij) ， 可得在一條信息傳輸過程中， 所經(jīng)過的每條鏈路需要傳輸?shù)哪芰俊?在此基礎上， 便可求出 IP核圖中所給的 21 條信息傳輸通路在每條鏈路上所需傳輸能耗和， 若使其小于每條鏈路所設定的帶寬， 便能夠讓系統(tǒng)處于無阻塞狀態(tài)。 接下來建立線性多目 標優(yōu)化模型， 來實現(xiàn)低能耗開銷的無阻塞方案。 設鏈路與路由器總能耗開銷與每條鏈路所需帶寬的權重分別為 k和（1 - k） 。 分別求得每一條鏈路所需帶寬， 取其中最大值進行優(yōu)化， 得到其最小值從而能夠讓鏈路帶寬所有值均降低。 得到線性加權多目

14、 標優(yōu)化模型計算公式 4 如下所示：5.2.2 模型求解與結果分析5.2.2.1 2D Mesh 拓撲結構考慮到無向線段的雙向性， 為了方便討論參考 the west-first and odd-even 路由算法 5 做出以下規(guī)定： 選取向右， 向下兩個方向作為路徑選擇的標準方向分別如下圖 2.1 所示，在該拓撲結構上對題目 所給的 IP 核圖做 200 次映射， 仍取交配概率 pc = 0.25和變異概率 pm = 0.02 ,用遺傳算法對該映射的收斂性分析如下圖 2.2 所示該圖表明， 在 100 次迭代前后基本實現(xiàn)低能耗開銷的無阻塞映射， 并將迭代 200次時的映射模型輸出， 得到如下

15、圖 2.6 所示的 IP 核 2D-Torus 映射的最優(yōu)排布。5.3 問題三模型建立與求解5.3.1 模型建立HotSpot 軟件 6 能夠有效的得到芯片級的 IP 核的熱阻， 并模擬其溫度， 在該模擬器中， 定義某一 IP 核的熱阻Ri 等于自 身溫度增量與相鄰節(jié)點的能耗增量的比值， 通過查找資料 7 設定每個片上處理單元規(guī)格為 2mm ´ 2mm ， 位于面積為20.13um 的區(qū)域上， 芯片厚度為 0.15um ， 利用熱阻模擬器 HotSpot 得到熱傳導阻抗矩陣 R ， 接下來利用如下公式 8 計算出溫度分布利用遺傳算法最小化各核溫度的標準差， 便可映射方案使得片上網(wǎng)絡中

16、 IP核的溫度分布較為均衡。5.3.2 模型求解與結果分析本模型提出的遺傳算法用 Matlab 實現(xiàn)， 在三種不同的拓撲結構上對題目 所給的 IP 核圖做 200 次映射， 取交配概率 pc= 0.25 和變異概率 pm = 0.02 ,用遺傳算法分別對 2D Mesh 拓撲結構、 2D Torus 拓撲結構和超立方體拓撲結構的收斂性分析結果如下圖 3.1 所示六、 模型改進對于問題一： 首先引 入了曼哈頓距離，算法完成最優(yōu)化求解， 得到所求映射。 優(yōu)點在于運用啟發(fā)式搜索， 強化了優(yōu)秀個體基因的遺傳引 導概率， 而非盲目 窮舉。 缺點在于容易產(chǎn)生過早收斂， 因為一旦少數(shù)個體的適應度函數(shù)值遠大于

17、其他個體， 少數(shù)迭代即會導致這些個體占據(jù)群體， 而且由于未對各代最優(yōu)進行保護， 反而可能導致種群退化。 對于問題二： 首先借鑒 路由算法， 設計了規(guī)定路線來解決路線選擇問題， 然后采用線性加權多目 標優(yōu)化映射來尋求多目 標優(yōu)化。通過目 標函數(shù)的線性組合將多目 標優(yōu)化問題轉(zhuǎn)換成單目 標問題， 然后采用單目 標優(yōu)化算法求解。 優(yōu)點在于： 這種方法達到了快速計算的目 的， 并且可以尋求單獨某個目 標函數(shù)的最優(yōu)化解。 但是缺點在于由于各目 標函數(shù)的權重分配具有較大的主觀性， 而且作為先驗信息必須在優(yōu)化之前給出使所找到的最優(yōu)解即為真正。的非劣解。 在查找大量文獻后， 發(fā)現(xiàn)基于 Pareto 最優(yōu)的多目 標優(yōu)化映射較好的可以解決該問題 對于問題三： 首先參考 Hotspot 算法給出熱阻矩陣， 然后利用熱阻定義得到各 IP 核的溫度， 最終采用計算并優(yōu)化 IP 核溫度標準差來尋求溫度均衡， 優(yōu)點在于選用了溫度標準差， 減小了極端溫度的出現(xiàn)， 同時更加