Information Theory Based Analysis and Design of Sorting Networks

In this paper the concepts of information theory are utilized to perform the performance analysis of the sorting networks which is selected as an example of the parallel architectures. It is shown that using this method, the source of the redundancy and the short comings of the performance can be monitored specifically and an analytical proving for efficiency of designs can be presented. Also it is expected that the optimum design can be obtained at first try in design stage instead of some try and error methods. It may have more contribution in the large size and complicated approximate working architectures. More accurate bounds for the performance characteristics can be determined using this method to anticipate the time to stop attempt to increase in the performance with definite condition. Some example is presented and future works are introduced.