DocumentCode :
2717421
Title :
On the bisection width and expansion of butterfly networks
Author :
Bornstein, Claudson ; Litman, Ami ; Maggs, Bruce M. ; Sitaraman, Ramesh K. ; Yatzkar, Tal
Author_Institution :
Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear :
1998
fDate :
30 Mar-3 Apr 1998
Firstpage :
144
Lastpage :
150
Abstract :
The paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. Previously it was known that the bisection width of an n-input butterfly with wraparound is n. We show that without wraparound, the bisection width is 2(√2-1)n+o(n)≈.82 n. This result is surprising because it contradicts the prior “folklore” belief that the bisection width is n in both cases. We also show that for every set A of k nodes in a butterfly with wraparound there are at least (4+o(1))k/log k edges from A to A¯, provided that k=o(n)
Keywords :
graph theory; hypercube networks; parallel architectures; bisection width; butterfly network expansion; wraparound; Ambient intelligence; Asynchronous transfer mode; Computer networks; Computer science; Concurrent computing; Contracts; Dairy products; Read only memory; Routing; Switches;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998
Conference_Location :
Orlando, FL
ISSN :
1063-7133
Print_ISBN :
0-8186-8404-6
Type :
conf
DOI :
10.1109/IPPS.1998.669902
Filename :
669902
Link To Document :
بازگشت