Recursive Construction of Distributors by Merging

S.-Y.R. Li and X. Tan (PRC)


Distributor, automata, circular unimodal function, Merge Distribute algorithm, 2-stage interconnection network with input exchange.


A distributor is a time-multiplexed switch that routes active input signals to output ports in the round-robin fashion. This paper presents the Merge-Distribute algorithm for the recursive construction of distributors in the form of parallel distributed-control networks, as analogous to the recursive construction of sorting networks by the Mergesort algorithm. The Merge Distribute algorithm achieves the best known depths for distribution networks of all sizes within the practical range. The rigorous algebraic formulation keeps the algorithmic construction transparent and affords many variations in the construction so as to flexibly cope with ad hoc engineering constraints in implementation.

Important Links:

Go Back