1、隨著半導(dǎo)體尺寸工藝的提升,越來越多的IP核(Intellectual Property core)集成到單一芯片中,芯片內(nèi)部的互連通信也成為了一大挑戰(zhàn)。基于包交換的片上網(wǎng)絡(luò)通信架構(gòu)有著高可擴展性、并行性等優(yōu)勢,是解決未來片上系統(tǒng)設(shè)計中內(nèi)部通信問題的選擇。然而,高度集成的芯片同時增加了片上網(wǎng)絡(luò)中不同組件(如物理鏈接、路由器等)的故障率。片上網(wǎng)絡(luò)中的某條物理鏈接或路由器發(fā)生故障會阻斷IP核間的通信,從而導(dǎo)致整個芯片失效。因此,片上網(wǎng)絡(luò)可靠性

2、成為保證芯片內(nèi)部正常通信的關(guān)鍵,研究可容錯的片上網(wǎng)絡(luò)對提高片上網(wǎng)絡(luò)的可靠性有著重要意義。片上網(wǎng)絡(luò)包括規(guī)則拓?fù)浜筒灰?guī)則拓?fù)鋬煞N,相比于規(guī)則拓?fù)?不規(guī)則的拓?fù)渲饕獞?yīng)用于專用芯片,有著面積和功耗等優(yōu)勢。本論文設(shè)計了一種多容錯的專用片上網(wǎng)絡(luò)拓?fù)渚C合方法,其主要貢獻如下:
　　(1)物理鏈接多故障容錯拓?fù)渖煞椒?。對于用戶定義的最大容錯數(shù)K(≥1),本方法給出了可容許片上網(wǎng)絡(luò)中最多K個物理鏈接故障的拓?fù)渖煞椒?其將IP核映射和路徑分配兩個

3、子問題整合到同一個整數(shù)線性規(guī)劃模型中同時求解,可以改善解的質(zhì)量。該方法采用所有IP核間通信需求同時求解的方法。實驗結(jié)果表明:a)與FTTG算法相比,功耗平均降低了10.58％,平均跳數(shù)平均降低了6.25％,體現(xiàn)了同時求解IP核映射和路徑分配兩個子問題方法的全局最優(yōu)性;b)與DBG算法相比,功耗平均降低了21.72％,平均跳數(shù)平均降低了9.35％,體現(xiàn)了整數(shù)線性規(guī)劃算法尋找最優(yōu)解的有效性;c)相比非容錯拓?fù)?K=1、K=2和K=3容錯拓?fù)?/p>

4、功耗平均各增加了11.9％、23.8％和52.1％,表明可容錯拓?fù)涞墓碾S著K值的增加而增加。
　　(2)路由器多故障容錯拓?fù)渖煞椒?。對于用戶定義的最大容錯數(shù)K(≥1),本文給出了一種可容許專用片上網(wǎng)絡(luò)中最多存在K個物理鏈接或路由器故障的拓?fù)渖煞椒?。針對給定的IP核間通信需求以及IP核和路由器的位置信息,本文利用基于最小費用最大流算法來建立IP核和路由器之間的物理鏈接;然后使用基于整數(shù)線性規(guī)劃的算法依次為每個IP核間的通信需求

5、分配K+1條路由器不相交的路徑。對于規(guī)模較大的核間通信圖,本文需要采取對通信流依次分配的方法。實驗結(jié)果表明:與非容錯拓?fù)湎啾?K=1、K=2和K=3容錯拓?fù)涔钠骄髟黾恿?4.3％、192.0％和307.2％,表明路由器故障容錯拓?fù)涞墓碾S著K值的增長呈現(xiàn)相應(yīng)倍數(shù)的增長。
　　(3)基于最大團的路由器冗余端口共享方法。針對多容錯拓?fù)渲新酚善魃螴P核端口過多導(dǎo)致路由器尺寸過大的問題,提出了端口共享方法。首先,本文闡述了在滿足多容錯

6、的性質(zhì)時可進行端口共享的條件;其次,給出了一種基于最大團的啟發(fā)式算法共享路由器的冗余端口,降低路由器的尺寸,進而降低功耗。實驗結(jié)果表明:(1)相比非端口共享拓?fù)?端口共享拓?fù)湓贙=1、K=2和K=3容錯情況下功耗平均各降低27.25％、36.83％和39.81％;(2)相比非容錯拓?fù)?考慮端口共享的容錯拓?fù)湓贙=1、K=2和K=3容錯情況下功耗平均各增加了41.70％、85.15％和146.53％,也證明了端口共享方法的有效性。