The de Bruijn multiprocessor network
M. R. Samatham, Dhiraj K. Pradhan · ACM SIGARCH Computer Architecture News · 1985
Recent work [I] has classified sorting architectures as: (A) Sequential input/Sequentlal output, (B) Parallel input/Sequentlal output, (C) Parallel Input/Parallel output, (D) Sequential input/Parallel output and (E) Hybrid input/Hybrld output.The classification is based, not only on the I/O method, but also on the interconnection network, the sorting algorithm and the type of keys used.This paper demonstrates that the architectures based on the undirected de BrulJn graphs (DGs) can sort data items in all of the above mentioned categories.To the best of our knowledge, no other single network which can sort data items in all the categories is known.Sorting algorithms and time complexities that correspond to each of these categories are given here.It is shown that these architectures can achieve the previously known best upper bound times, in all of the categories.Also, it is proven that they work as sorting networks, even in the presence of some faults.