多級(jí)互連網(wǎng)絡(luò)的結(jié)構(gòu)、算法和可重排性.pdf

1、多級(jí)互連網(wǎng)絡(luò)在并行計(jì)算等許多實(shí)際問(wèn)題中有著重要的應(yīng)用，它對(duì)系統(tǒng)的軟硬件性能都有很大影響。位變換網(wǎng)絡(luò)是一類結(jié)構(gòu)良好、而且包含絕大部分在文獻(xiàn)中得到深入研究的多級(jí)網(wǎng)絡(luò)，本文著重對(duì)這類網(wǎng)絡(luò)的結(jié)構(gòu)、路由算法和可重排性進(jìn)行較系統(tǒng)的探討。 在第一章對(duì)背景和問(wèn)題作了簡(jiǎn)單的介紹后，我們?cè)诘诙陆o出位變換網(wǎng)絡(luò)的一個(gè)完全基于圖論術(shù)語(yǔ)的刻劃，這一結(jié)果將Bermond等人針對(duì)單一網(wǎng)絡(luò)的結(jié)論推廣到所有的位變換網(wǎng)絡(luò)，將對(duì)多級(jí)網(wǎng)絡(luò)結(jié)構(gòu)的了解大大推進(jìn)了一步，并且

2、澄清了一些對(duì)位變換網(wǎng)絡(luò)結(jié)構(gòu)的模糊認(rèn)識(shí)。 多級(jí)網(wǎng)絡(luò)的分層叉積是Even等人引進(jìn)的一個(gè)較新的概念，它不僅是研究網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)有力的工具，而且對(duì)于路由算法設(shè)計(jì)有著廣泛的應(yīng)用前景。第三章我們給出位變換網(wǎng)絡(luò)分解為一些“均勻”因子的結(jié)果，該結(jié)果使得我們?cè)诘谒恼鲁晒Φ貙⒅脫Q路由問(wèn)題轉(zhuǎn)化為一類特殊的矩陣問(wèn)題。這一轉(zhuǎn)化將Linial等人關(guān)于洗牌交換網(wǎng)絡(luò)的一個(gè)結(jié)論推廣到所有位變換網(wǎng)絡(luò)，并且由此得到可重排網(wǎng)絡(luò)的一個(gè)必要條件，部分解釋了為什么許多已有的

3、工作對(duì)2n-1級(jí)網(wǎng)絡(luò)的關(guān)注。 第五章專門討論2n-1級(jí)網(wǎng)絡(luò)的可重排性。這一領(lǐng)域最重要的問(wèn)題之一就是Bene(s)1975年提出的一個(gè)猜想，我們將這一猜想放到一個(gè)更廣泛的問(wèn)題中，并對(duì)它作了較多的討論。特別地，我們給出了包含Bene(s)猜想在內(nèi)的一類可重排性問(wèn)題一個(gè)新穎的數(shù)學(xué)描述。我們還著重對(duì)Cam關(guān)于這一猜想的證明作了深入分析，簡(jiǎn)化了他的方法，并指出他的證明是不完全的。 隨著相關(guān)科學(xué)技術(shù)的進(jìn)步，越來(lái)越多的研究興趣集中到光