無阻塞多播通信在Omega網(wǎng)上的實(shí)現(xiàn).pdf

1、多級(jí)互連網(wǎng)絡(luò)是現(xiàn)代并行計(jì)算和交換系統(tǒng)的核心,如何構(gòu)造具有良好通信能力、最優(yōu)硬件代價(jià)和路由時(shí)間復(fù)雜度并可以無阻塞傳輸多播信號(hào)的多級(jí)互連網(wǎng)絡(luò)是一個(gè)非常重要的研究課題。
　　通過探討和研究如何在Omega網(wǎng)絡(luò)上實(shí)現(xiàn)多播通信,本文將提出兩種可以實(shí)現(xiàn)多播通信的新型無阻塞Omega網(wǎng)絡(luò)結(jié)構(gòu):多-Omega網(wǎng)和3-Omega網(wǎng)。這兩種網(wǎng)絡(luò)結(jié)構(gòu)都支持超大容量交換,可以無阻塞地實(shí)現(xiàn)多播,在硬件代價(jià)和路由時(shí)間上各有千秋。
　　本文將給出的多-O

2、mega網(wǎng)以O(shè)mega和Omega×Omega-1為基礎(chǔ)網(wǎng),利用二分?jǐn)U散的Omega×Omegal-1網(wǎng)循環(huán)構(gòu)造出來,硬件成本為O(nlog2n),網(wǎng)絡(luò)深度為O(log2n),路由時(shí)間為O(log2n)。本文將給出的3-Omega網(wǎng)以“Omega-1+Omega+Omega-1”組建而成,可以實(shí)現(xiàn)任意的多源點(diǎn)多播,硬件成本為O(nlogn),路由時(shí)間為O(nlogn),傳輸時(shí)延為O(logn),符合Claude Shannon于二十世紀(jì)