幾種BC網(wǎng)絡(luò)上完全二叉樹的嵌入研究

幾種BC網(wǎng)絡(luò)上完全二叉樹的嵌入研究并行計(jì)算在教育、科研、石油、生物、氣象等相關(guān)領(lǐng)域發(fā)揮著日益重要的作用。多處理器互連網(wǎng)絡(luò)(簡(jiǎn)稱互連網(wǎng)絡(luò))在很大程度上決定了并行計(jì)算系統(tǒng)的性能。因此,互連網(wǎng)絡(luò)及其性質(zhì)的研究是并行處理領(lǐng)域中的一個(gè)重要課題。互連網(wǎng)絡(luò)可以表示為一個(gè)簡(jiǎn)單圖,其中頂點(diǎn)代表處理器,邊代表處理器之間的通信鏈路。在互連網(wǎng)絡(luò)的設(shè)計(jì)和分析中,圖嵌入能力是衡量一個(gè)互連網(wǎng)絡(luò)性能優(yōu)劣的重要指標(biāo)。給定兩個(gè)圖G和H,由G到H的一個(gè)嵌入定義為由G到H的一個(gè)單射。圖G和圖H分別稱為嵌入的客圖和主圖。理想的互連網(wǎng)絡(luò)(主圖)應(yīng)該擁有優(yōu)秀的圖嵌入能力,使得擁有規(guī)則任務(wù)圖(客圖)的并行算法能夠在該網(wǎng)絡(luò)上高效的執(zhí)行。擴(kuò)張、膨脹、擁塞和負(fù)載是衡量圖嵌入性能的常用指標(biāo),圖嵌入的最優(yōu)性能求解問題是NP難問題。由于完全二叉樹具有優(yōu)越性能和廣泛應(yīng)用,因此將其作為客圖嵌入互連網(wǎng)絡(luò)具有十分重要的研究意義。盡管完全二叉樹到一般互連網(wǎng)絡(luò)以最優(yōu)性能嵌入的求解問題是NP難問題,但在一些特殊互連網(wǎng)絡(luò)中以最優(yōu)性能嵌入完全二叉樹已經(jīng)得到解決。迄今為止,關(guān)于將完全二叉樹嵌入多種互連網(wǎng)絡(luò)如網(wǎng)孔、星圖、網(wǎng)格、蝶網(wǎng)等的研究已經(jīng)取得了較多成果。超立方體作為一種常用的互連網(wǎng)絡(luò)得到了眾多研究者的青睞,其具有許多優(yōu)越性質(zhì)比如低直徑、高連通性、對(duì)稱性、遞歸構(gòu)造性等。然而,完全二叉樹不能以最優(yōu)性能嵌入超立方體,卻能以最優(yōu)性能嵌入某些超立方體變型,如交叉立方體和折疊立方體。超立方體及其若干變型均具有一一對(duì)應(yīng)連接和可遞歸構(gòu)造性質(zhì),研究者依據(jù)這兩個(gè)性質(zhì)將它們歸結(jié)為一類互連網(wǎng)絡(luò)——BC網(wǎng)絡(luò)。然而,關(guān)于將完全二叉樹嵌入BC網(wǎng)絡(luò)的研究成果相對(duì)較少。本文中,我們主要研究幾種BC網(wǎng)絡(luò)——莫比烏斯立方體、奇偶立方體和局部扭立方體上完全二叉樹的嵌入問題。我們證明了完全二叉樹能以最優(yōu)性能嵌入莫比烏斯立方體和奇偶立方體,以及以較優(yōu)性能嵌入和容錯(cuò)嵌入局部扭立方體。具體包括以下內(nèi)容:1.n維莫比烏斯立方體(M_n)上完全二叉樹的嵌入與交叉立方體不同的是,M_n是由兩個(gè)不同構(gòu)的子莫比烏斯立方體組成(n≥5)。因此,在M_n上嵌入完全二叉樹將面對(duì)更復(fù)雜的情形。我們研究了M_n上完全二叉樹以最優(yōu)性能嵌入的問題,取得了如下研究結(jié)果:(1)證明了莫比烏斯立方體中滿足的一個(gè)重要性質(zhì)——由不相交子立方體構(gòu)成的立方體對(duì)同構(gòu)于子莫比烏斯立方體。(2)基于M_n上存在同構(gòu)立方體對(duì)的性質(zhì),提出了一種對(duì)M_n上的完全二叉樹嵌入進(jìn)行類型劃分的構(gòu)造方法。(3)證明了完全二叉樹能以擴(kuò)張1、負(fù)載1、擁塞1和膨脹趨近于1嵌入M_n。2.n維奇偶立方體(PQ_n)上完全二叉樹的嵌入與M_n上完全二叉樹的嵌入方法不同,我們給出了PQ_n上完全二叉樹以最優(yōu)性能嵌入的證明方法。進(jìn)一步,我們還設(shè)計(jì)了相應(yīng)的嵌入算法和模擬實(shí)驗(yàn),取得了如下研究結(jié)果:(1)證明了完全二叉樹能以擴(kuò)張1、負(fù)載1、擁塞1和膨脹趨近于1嵌入PQ_n。(2)給出了時(shí)間復(fù)雜度為O(NlogN)的完全二叉樹嵌入算法,其中N為PQ_n的頂點(diǎn)個(gè)數(shù),并給出了算法的正確性證明。(3)設(shè)計(jì)了在PQ_n上嵌入完全二叉樹的模擬實(shí)驗(yàn)。3.n維局部扭立方體(LTQ_n)上完全二叉樹的容錯(cuò)嵌入隨著互連網(wǎng)絡(luò)規(guī)模的不斷增大,處理器和通信鏈路將不可避免地出現(xiàn)故障。因此,我們有必要去評(píng)估互連網(wǎng)絡(luò)的容錯(cuò)嵌入能力。我們研究了LTQ_n上完全二叉樹的嵌入以及容錯(cuò)嵌入問題,取得了如下研究結(jié)果:(1)證明了以任意頂點(diǎn)為根的完全二叉樹能以擴(kuò)張2、負(fù)載1、擁塞1和膨脹1嵌入LTQ_n。(2)證明了當(dāng)LTQ_n上的任意一個(gè)頂點(diǎn)發(fā)生故障時(shí),LTQ_n上嵌入的完全二叉樹能以擴(kuò)張2和擁塞2動(dòng)態(tài)重建。(3)證明了當(dāng)LTQ_n上的任意兩個(gè)頂點(diǎn)發(fā)生故障時(shí),LTQ_n上嵌入的