多級互連網絡的結構、算法和可重排性.pdf

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

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

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