Four Input Sorter Good, Larger Ones Not So Good
Vlad Drăgoi, Simon Robin Cowell, Valeriu C. Beiu · IEEE Transactions on Nanotechnology · 2021
Our own fresh results have suggested that the smallest size optimal sorting networks/graphs (which can be mapped onto hardware) might be the most appropriate entities (building blocks) for designing highly reliable computing systems. Sorting networks correspond to particular sorting algorithms, while their associated connectivity graphs can embody (minimal) two-terminal networks. Relying on these concepts one can associate a reliability polynomial to any sorting network. Here, we are going to extend on the work we have recently started on sorting networks by studying larger optimal sorting networks. Comparing the two-terminal reliability polynomials associated to these larger sorting connectivity graphs with those of Moore-Shannon hammocks of the same size will follow. In-depth comparisons will be done using both classical as well as novel figures-of-merit targeting the reliability enhancements of networks when performing computations. The results reported here will shed light on our previous findings, confirming that the optimal sorting network of four inputs is ideal for designing highly reliable computing systems, but also that its advantages, although of theoretical importance, are only marginal and fading quickly. In particular, the analyses of sorting networks with larger number of inputs reveals that hammocks are catching up with sorting networks at five and six inputs, and clearly overtaking sorting networks of seven inputs. All these simulations and detailed comparisons provide compelling arguments for why hammock networks are the ones we should rely upon (at more than one level) for 2D reliable computations (including the current quantum computing quest).