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

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

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

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