Correctness verification and minimum cost calculating algorithm of comparison network
Wei Min Dong, Tingting Wang · 2022
Comparison Network (CN) is a kind of special structure for parallel sorting. There are two important problems in CN: Verifying the correctness of a given CN and finding the minimum cost CN. For the two problems, this paper establishes a verification model similar to Petri Net for CN based on [0,1] principle, and provides two algorithms for them. The deduplication and pruning strategies are introduced in the algorithms which make better execution efficiency compared with results in the existing literature.