本文關(guān)鍵詞：幾種互連網(wǎng)絡(luò)上圖嵌入的研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：高性能并行計(jì)算機(jī)是一個(gè)國(guó)家綜合科技實(shí)力的體現(xiàn),在銀行、科研、教育、輔助設(shè)計(jì)、醫(yī)藥、石油、氣象、信息安全等相關(guān)領(lǐng)域發(fā)揮著日益重要的作用。并行計(jì)算機(jī)中處理器連接的方式(互連網(wǎng)絡(luò))對(duì)于并行計(jì)算機(jī)的性能至關(guān)重要。一個(gè)互連網(wǎng)絡(luò)可以用一個(gè)圖G=(V(G),E(G))來(lái)表示,其中V(G)代表頂點(diǎn)集合,而E(G)代表邊集。在并行處理領(lǐng)域,研究互連網(wǎng)絡(luò)及其性質(zhì)是一個(gè)非常重要的課題。交替群圖、WK-遞歸圖和局部扭立方體是常用的互連網(wǎng)絡(luò)結(jié)構(gòu),它們具有許多優(yōu)越的性質(zhì),因而受到研究者的廣泛關(guān)注。可嵌入性是互連網(wǎng)絡(luò)的一個(gè)重要性質(zhì),圖嵌入在并行算法的移植等方面具有重要應(yīng)用。圖嵌入問(wèn)題的描述如下:給定一個(gè)主圖G2=(V2,E2)和一個(gè)客圖G1=(V1,E1),將客圖G1嵌入到主圖G2中就是找到G1每個(gè)頂點(diǎn)到G2每個(gè)頂點(diǎn)的一個(gè)單射,以及G1每條邊到G2某一條路徑的映射。衡量嵌入效率的兩個(gè)重要指標(biāo)是擴(kuò)張(Dilation)和膨脹(Expansion)。性能良好的互連網(wǎng)絡(luò)作為主圖時(shí)應(yīng)該具有理想的圖嵌入能力,從而能夠使客圖上的并行算法在其上高效地遷移并運(yùn)行。路徑和網(wǎng)格是并行計(jì)算中的兩種通用的互連網(wǎng)絡(luò)結(jié)構(gòu),許多并行算法都是基于路徑和網(wǎng)格設(shè)計(jì)的。研究如何嵌入不同種類(lèi)的路徑和網(wǎng)格到主圖中是一個(gè)重要的研究方向。本文研究交替群圖、WK-遞歸圖和局部扭立方體三種互連網(wǎng)絡(luò)上的圖嵌入問(wèn)題,本文研究的兩類(lèi)主要的客圖為:不相交路徑和網(wǎng)格。具體研究?jī)?nèi)容如下:1.交替群圖上一對(duì)一頂點(diǎn)不相交路徑覆蓋的嵌入問(wèn)題。本文證明了交替群圖具有良好的路徑嵌入性質(zhì):在n-維交替群圖(AGn)中,對(duì)于任意的整數(shù)n≥3,任意兩個(gè)不同的頂點(diǎn)μ和ν之間可以嵌入m條頂點(diǎn)不相交路徑,且這些路徑可以覆蓋AGn的所有頂點(diǎn),這里1≤m≤2n-4。因?yàn)锳Gn的頂點(diǎn)度為2n-4,所以μ和ν之間最多可以嵌入2n-4條頂點(diǎn)不相交路徑。該嵌入的擴(kuò)張和膨脹都為1,也就是在擴(kuò)張和膨脹這兩個(gè)參數(shù)上該嵌入是最優(yōu)的。2.WK-遞歸圖上一對(duì)一頂點(diǎn)不相交路徑覆蓋的嵌入問(wèn)題。本文證明了WK-遞歸圖具有良好的路徑嵌入性質(zhì):在d基t級(jí)WK-遞歸圖(K(d,t))中,對(duì)于任意的整數(shù)d≥4和t≥1,任意兩個(gè)不同的頂點(diǎn)μ和ν之間可以嵌入m條頂點(diǎn)不相交路徑,且這些路徑可以覆蓋K(d,t)的所有頂點(diǎn),這里1≤m≤d-1。因?yàn)镵(d,t)的連通度為d-1,所以μ和ν之間最多可以嵌入d-1條頂點(diǎn)不相交路徑。該嵌入的擴(kuò)張和膨脹都為1,也就是在擴(kuò)張和膨脹這兩個(gè)參數(shù)上該嵌入是最優(yōu)的。3.局部扭立方體上3D網(wǎng)格的嵌入問(wèn)題。本文證明了局部扭立方體具有良好的網(wǎng)格嵌入性。在n-維局部扭立方體(LTQn)中,本文得到兩個(gè)主要的結(jié)果如下:(1)對(duì)于任意的整數(shù)n≥4,大小為2×2×2n-3的2個(gè)頂點(diǎn)不相交的3D網(wǎng)格可以擴(kuò)展1和膨脹2嵌入LTQn中。(2)對(duì)于任意的整數(shù)n≥6,大小為4×2×2n-5的4個(gè)頂點(diǎn)不相交的3D網(wǎng)格可以擴(kuò)展1和膨脹4嵌入LTQn中。上述結(jié)果在擴(kuò)張方面是最優(yōu)的,因?yàn)槠鋽U(kuò)張都為1。
【關(guān)鍵詞】：并行計(jì)算 互連網(wǎng)絡(luò) 圖嵌入 不相交路徑 網(wǎng)格
【學(xué)位授予單位】：蘇州大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TP338.6
【目錄】：

• 摘要4-6
• Abstract6-10
• 第一章 緒論10-16
• 1.1 研究背景10-12
• 1.2 研究?jī)?nèi)容12-13
• 1.3 研究意義13-14
• 1.4 文章組織結(jié)構(gòu)14-16
• 第二章 相關(guān)知識(shí)16-26
• 2.1 圖論基本概念和符號(hào)表示16-19
• 2.2 互連網(wǎng)絡(luò)19-20
• 2.3 圖嵌入問(wèn)題20-25
• 2.4 本章小結(jié)25-26
• 第三章 交替群圖上一對(duì)一頂點(diǎn)不相交路徑覆蓋的嵌入26-59
• 3.1 交替群圖的定義26-27
• 3.2 交替群圖上性質(zhì)的研究27-28
• 3.3 交替群圖上一對(duì)一頂點(diǎn)不相交路徑覆蓋的嵌入28-58
• 3.4 本章小結(jié)58-59
• 第四章 WK-遞歸圖上一對(duì)一頂點(diǎn)不相交路徑覆蓋的嵌入59-82
• 4.1 WK-遞歸圖的定義59-60
• 4.2 WK-遞歸圖上性質(zhì)的研究60-61
• 4.3 WK-遞歸圖上一對(duì)一頂點(diǎn)不相交路徑覆蓋的嵌入61-81
• 4.4 本章小結(jié)81-82
• 第五章 局部扭立方體上3D網(wǎng)格的嵌入82-96
• 5.1 局部扭立方體介紹82-85
• 5.2 相關(guān)定義和符號(hào)表示85-86
• 5.3 嵌入2個(gè)頂點(diǎn)不相交的2 × 2 × 2n?3網(wǎng)格至n-維局部扭立方體86-90
• 5.4 嵌入4個(gè)頂點(diǎn)不相交的4 × 2 × 2n?5網(wǎng)格至n-維局部扭立方體90-95
• 5.5 本章小結(jié)95-96
• 第六章 總結(jié)與展望96-98
• 6.1 總結(jié)96-97
• 6.2 展望97-98
• 參考文獻(xiàn)98-111
• 攻讀博士學(xué)位期間發(fā)表的論文和參與的科研項(xiàng)目111-113
• 致謝113-115

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 劉敏;劉紅美;;PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS[J];Acta Mathematica Scientia;2013年01期

  本文關(guān)鍵詞：幾種互連網(wǎng)絡(luò)上圖嵌入的研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：336514