
Accession Number : ADA319255
Title : Improved Routing and Sorting on Multibutterflies.
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Maggs, Bruce M. ; Voecking, Berthold
PDF Url : ADA319255
Report Date : NOV 1996
Pagination or Media Count : 20
Abstract : This paper shows that an Nnode AKS network can be embedded in a (3N/2)node degree8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting and finding the median of n log n keys on an ninput multibutterfly in O(log n) time, a workefficient algorithm for finding the median of n log2 n log log n keys on an ninput multibutterfly in O(log n log log n) time, and a threedimensional VLSI layout for the ninput AKS network with volume O(n3/2). While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly networks. We also present a separate, and more practical, deterministic algorithm for routing h relations on an ninput multibutterfly in O(h + log n) time. Previously, only algorithms for solving h onetoone routing problems were known. Finally, we show that a 2folded butterfly, whose individual splitters do not exhibit expansion, can emulate a boundeddegree multibutterfly with an (a,b) expansion property, for any a.b < 1/4.
Descriptors : *COMPUTER NETWORKS, ALGORITHMS, OPTIMIZATION, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, VERY LARGE SCALE INTEGRATION, INPUT OUTPUT PROCESSING, SYSTEMS ANALYSIS.
Subject Categories : Computer Systems
Distribution Statement : APPROVED FOR PUBLIC RELEASE