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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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