可容錯專用片上網(wǎng)絡拓撲綜合的研究.pdf

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

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

3、子問題整合到同一個整數(shù)線性規(guī)劃模型中同時求解,可以改善解的質量。該方法采用所有IP核間通信需求同時求解的方法。實驗結果表明: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)相比非容錯拓撲,K=1、K=2和K=3容錯拓撲

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

5、分配K+1條路由器不相交的路徑。對于規(guī)模較大的核間通信圖,本文需要采取對通信流依次分配的方法。實驗結果表明:與非容錯拓撲相比,K=1、K=2和K=3容錯拓撲功耗平均各增加了94.3％、192.0％和307.2％,表明路由器故障容錯拓撲的功耗隨著K值的增長呈現(xiàn)相應倍數(shù)的增長。
　　(3)基于最大團的路由器冗余端口共享方法。針對多容錯拓撲中路由器上IP核端口過多導致路由器尺寸過大的問題,提出了端口共享方法。首先,本文闡述了在滿足多容錯

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