Employing Sorting Nets for Designing Reliable Computing Nets
Mariana Nagy, Vlad Drăgoi, Valeriu C. Beiu · 2020
Recently, it was suggested that optimal sorting nets (which can trivially be mapped onto hardware) could be used to design highly reliable networks/systems. Sorting nets correspond to particular sorting algorithms, but it is their associated connectivity graph which seems to lead to highly reliable (minimal) two-terminal networks. Using the concept of associated connectivity graph we were able to link a reliability polynomial to any (optimal) sorting net. Here, we are going to thoroughly compare the two-terminal reliability polynomials associated to the connectivity graphs of very small optimal sorting nets, with the reliability polynomials of Moore-Shannon hammocks of similar size, as well as with size-equivalent compositions of series and parallel networks. These meticulous comparisons were done for getting a better understanding of the reliability of particular optimal sorting nets. The main conclusion is that small optimal sorting networks should be considered and might be useful for designing highly reliable computing systems.