Title :
Multicast bitonic network
Author :
Al-Hajery, Majed Z. ; Batcher, Kenneth E.
Author_Institution :
Dept. of Math. & Comput. Sci., Kent State Univ., OH, USA
Abstract :
This paper presents a new multicasting network constructed with a bit-level cost complexity of O(N log2N) and a bit-level time complexity of O(log2 N) using comparators with bit-level I(1) time and cost complexities. The requested addresses for connection are sorted in a pipeline fashion (worm-hole routed) bit-serially most-significant-bit first through the network Bitonic sorter. The sorted addresses and the source nodes´ addresses are merged through a Bitonic merger. The comparators and their links in both the Bitonic sorter and merger are bi-directional so two-way paths are formed
Keywords :
computational complexity; merging; multiprocessor interconnection networks; pipeline processing; sorting; Bitonic merger; Bitonic sorter; Multicast bitonic network; addresses; bit-level cost complexity; bit-level time complexity; comparators; pipeline; worm-hole routed; Broadcasting; Computer science; Corporate acquisitions; Costs; Mathematics; Message passing; Multicast algorithms; Pipelines; System recovery; Unicast;
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
DOI :
10.1109/SPDP.1993.395516
