2D-MESH及其變型的幾個性質(zhì)研究.pdf

1、對稱性，直徑，頂點度，對分寬度，路由算法，哈密頓性質(zhì)，度量維度，廣播等是評價一個網(wǎng)絡(luò)拓撲的重要參數(shù)。2D-Mesh是NoC研究中最常見的網(wǎng)絡(luò)拓撲，它結(jié)構(gòu)簡單且易于實現(xiàn)。蜂巢網(wǎng)格和HDN網(wǎng)絡(luò)是2D-Mesh的兩個重要變型。本文主要研究了2D-Mesh，蜂巢網(wǎng)格和HDN網(wǎng)絡(luò)的一些性質(zhì)：2D-Mesh中的容錯路由算法，蜂巢網(wǎng)格的哈密頓性質(zhì)，HDN網(wǎng)絡(luò)的度量維度。
　　（1）路由算法決定了消息包從源結(jié)點到目的結(jié)點的路由路徑。本文提出了一種

2、在2D-Mesh上只使用2條虛通道的容錯路由算法，少于Boppana等人提出的需要4條虛通道的算法，以及Duan等人提出的需要3條虛通道的算法。算法基于塊故障模型，其中故障塊可以是f-ring也可以是f-chain。無故障時算法使用最短路徑路由，當消息被故障塊阻塞時使用繞道策略進行路由。在不重疊和重疊故障區(qū)兩種情況下本文分別給出了算法無死鎖性的證明過程。
　?。?）經(jīng)過圖G中所有頂點恰好一次的路徑（圈）稱為哈密頓路徑（哈密頓圈）。

3、迄今沒有關(guān)于蜂巢網(wǎng)格哈密頓性質(zhì)的研究結(jié)果。本文研究了蜂巢網(wǎng)格的哈密頓性質(zhì)，主要貢獻如下：（a）在蜂巢網(wǎng)格中，我們給出了任意兩個頂點之間存在哈密頓路徑的充分必要條件；（b）我們研究了存在一個故障點情況下蜂巢網(wǎng)格的哈密頓性質(zhì)；（c）證明過程是構(gòu)造性的，從而如果存在哈密頓路徑，根據(jù)我們的證明過程可以構(gòu)造出這樣的路徑。
　　（3）設(shè)頂點集WV(G)，若對于任意兩頂點u和v∈V(G)，存在頂點w∈W，使得d(u, w) d(v, w)，則稱