幾種互連網(wǎng)絡(luò)上圖嵌入的研究.pdf

1、高性能并行計算機是一個國家綜合科技實力的體現(xiàn)，在銀行、科研、教育、輔助設(shè)計、醫(yī)藥、石油、氣象、信息安全等相關(guān)領(lǐng)域發(fā)揮著日益重要的作用。并行計算機中處理器連接的方式（互連網(wǎng)絡(luò)）對于并行計算機的性能至關(guān)重要。一個互連網(wǎng)絡(luò)可以用一個圖G=(V(G)，E(G))來表示，其中V(G)代表頂點集合，而E(G)代表邊集。在并行處理領(lǐng)域，研究互連網(wǎng)絡(luò)及其性質(zhì)是一個非常重要的課題。交替群圖、WK-遞歸圖和局部扭立方體是常用的互連網(wǎng)絡(luò)結(jié)構(gòu)，它們具有許多優(yōu)越

2、的性質(zhì)，因而受到研究者的廣泛關(guān)注。
　　可嵌入性是互連網(wǎng)絡(luò)的一個重要性質(zhì)，圖嵌入在并行算法的移植等方面具有重要應(yīng)用。圖嵌入問題的描述如下:給定一個主圖G2=(V2，E2)和一個客圖G1=(V1，E1)，將客圖G1嵌入到主圖G2中就是找到G1每個頂點到G2每個頂點的一個單射，以及G1每條邊到G2某一條路徑的映射。衡量嵌入效率的兩個重要指標(biāo)是擴張(Dilation)和膨脹(Expansion)。性能良好的互連網(wǎng)絡(luò)作為主圖時應(yīng)該具有理想

3、的圖嵌入能力，從而能夠使客圖上的并行算法在其上高效地遷移并運行。路徑和網(wǎng)格是并行計算中的兩種通用的互連網(wǎng)絡(luò)結(jié)構(gòu)，許多并行算法都是基于路徑和網(wǎng)格設(shè)計的。研究如何嵌入不同種類的路徑和網(wǎng)格到主圖中是一個重要的研究方向。
　　本文研究交替群圖、WK-遞歸圖和局部扭立方體三種互連網(wǎng)絡(luò)上的圖嵌入問題，本文研究的兩類主要的客圖為:不相交路徑和網(wǎng)格。具體研究內(nèi)容如下:
　　1.交替群圖上一對一頂點不相交路徑覆蓋的嵌入問題。
　　本文證

4、明了交替群圖具有良好的路徑嵌入性質(zhì):在n-維交替群圖(AGn)中，對于任意的整數(shù)n≥3，任意兩個不同的頂點μ和v之間可以嵌入m條頂點不相交路徑，且這些路徑可以覆蓋AGn的所有頂點，這里1≤m≤2n-4。因為AGn的頂點度為2n-4，所以μ和v之間最多可以嵌入2n-4條頂點不相交路徑。該嵌入的擴張和膨脹都為1，也就是在擴張和膨脹這兩個參數(shù)上該嵌入是最優(yōu)的。
　　2.WK-遞歸圖上一對一頂點不相交路徑覆蓋的嵌入問題。
　　本文證

5、明了WK-遞歸圖具有良好的路徑嵌入性質(zhì):在d基t級WK-遞歸圖（K（d,t））中，對于任意的整數(shù)d≥4和t≥1，任意兩個不同的頂點μ和v之間可以嵌入m條頂點不相交路徑，且這些路徑可以覆蓋K（d,t）的所有頂點，這里1≤m≤d-1。因為K(d，t)的連通度為d-1，所以μ和v之間最多可以嵌入d-1條頂點不相交路徑。該嵌入的擴張和膨脹都為1，也就是在擴張和膨脹這兩個參數(shù)上該嵌入是最優(yōu)的。
　　3.局部扭立方體上3D網(wǎng)格的嵌入問題。