Bit-level bitonic sorting networks and their role in wormholes multicast routing
Majed Z. Al-Hajery · 1995
When the Bitonic sorter was first introduced, it was constructed with a bit-level cost complexity of O(N $\rm log\sp2$ N) and a bit-level time complexity of $\rm O(log\sp2$ N) using comparators with bit-level O(1) time and cost complexities. A new improvement, up to a factor of log N in the cost complexity, is achieved. Items to be sorted are pipelined (worm-hole routed) bit-serially most-significant-bit first through the network. This achievement is made possible by recirculating items of length k bits each through $\lceil{k\over\log N}\rceil$ log N stages. Using both the modified bit-level comparators and the bitonic sorting algorithm, four multicast routing networks are introduced. The first two are dynamic networks, which possess a time complexity of $\rm O(log\sp2$ N). One is a circuit and the other is a packet switching network with cost complexities of O(N $\rm log\sp2$ N) and O(N log N) respectively. The last two are Hypercube and 2D-MESH static topology networks. A new type of wormhole router is adopted to achieve a general multicast time complexity of $\rm O(log\sp2$ N) and O($\sqrt{N})$ for the Hypercube and 2D-MESH respectively.