Designing Minimal Sorting Networks using a Bio-inspired Technique
Abstract
Sorting Networks (SN) are efficient tools to order an input data sequence.
They are of interest due to their application to almost all the Computer Science areas and applications.
Sorting Networks are composed by a set of comparison and exchange operations called comparators.
The comparators are fixed a priori. Further, Sorting Networks can execute some independent comparators at the same time. The efficiency of the SN can be measured in two ways: 1) the number of comparators needed to order $n$-input data, and 2) the parallel execution time spent.
Designing Sorting Networks with minimal set of comparators is an NP-hard problem.
It is a classical problem studied since more than 50 years.
In this paper we propose a biological inspired technique to find the comparators to design an efficient Sorting Network.
Different fitness functions are analyzed to select the more promising comparators.
Three new designs for optimal Sorting Networks are presented.
They are of interest due to their application to almost all the Computer Science areas and applications.
Sorting Networks are composed by a set of comparison and exchange operations called comparators.
The comparators are fixed a priori. Further, Sorting Networks can execute some independent comparators at the same time. The efficiency of the SN can be measured in two ways: 1) the number of comparators needed to order $n$-input data, and 2) the parallel execution time spent.
Designing Sorting Networks with minimal set of comparators is an NP-hard problem.
It is a classical problem studied since more than 50 years.
In this paper we propose a biological inspired technique to find the comparators to design an efficient Sorting Network.
Different fitness functions are analyzed to select the more promising comparators.
Three new designs for optimal Sorting Networks are presented.