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

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

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

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