An Improved Subsumption Testing Algorithm for the Optimal-Size Sorting Network Problem
Cristian Frasinaru Madalina Raschip
cs.DS






Faculty of Computer Science, "Alexandru Ioan Cuza" University, Iaşi, Romania
{acf, mionita}@info.uaic.ro





In this paper a new method for checking the subsumption relation for the optimal-size sorting network problem is described.
The new approach is based on creating a bipartite graph and modelling the subsumption test as the problem of enumerating all perfect matchings in this graph. 
Experiments showed significant improvements over the previous approaches when considering the number of subsumption checks and the time needed to find optimal-size sorting networks. We were able to generate all the complete sets of filters for comparator networks with 9 channels, 
confirming that the 25-comparators sorting network is optimal. 
The running time was reduced more than 10 times, compared to the state-of-the-art result described in <cit.>.



Comparator networks. Optimal-size sorting networks. Subsumption.
 






§ INTRODUCTION


Sorting networks are a special class of sorting algorithms with an active research area since the 1950's 
<cit.>, <cit.>, <cit.>.
A sorting network is a comparison network which for every input sequence produces a monotonically increasing output. 
Since the sequence of comparators does not depend on the input, the network represents an oblivious sorting algorithm. 
Such networks are suitable in parallel implementations of sorting, being applied in graphics processing units <cit.> 
and multiprocessor computers <cit.>. 

Over time, the research was focused on finding the optimal sorting networks relative to their size or depth.
When the size is considered, the network must have a minimal number of comparators, while for the second objective a minimal number of layers is required. In <cit.> a construction method for sorting network of size O(n log n) and depth O(log n) is given. This algorithm has good results in theory but it is inefficient in practice because of the large constants hidden in the big-O notation. On the other side, the simple algorithm from <cit.> which constructs networks of depth O(log^2 n) has good results for practical values of n.

Because optimal sorting networks for small number of inputs can be used to construct efficient larger networks the research in the area focused in the last years on finding such small networks. Optimal-size and optimal-depth networks are known for n ≤ 8 <cit.>. 
In <cit.> the optimal-depth sorting networks were provided for n=9 and n=10. 
The results were extended for 11 ≤ n ≤ 16 in <cit.>. The approaches use search with pruning based on symmetries on the first layers. The last results for parallel sorting networks are for 17 to 20 inputs and are given in <cit.>, <cit.>. On the other side, the paper <cit.> proved the optimality in size for the case n=9 and n=10. The proof is based on exploiting symmetries in sorting networks and on encoding the problem as a satisfiability problem. 
The use of powerful modern SAT solvers to generate optimal sorting networks is also investigated in <cit.>. Other recent results can be found in <cit.>, where a revised technique to generate, modulo symmetry, the set of saturated two-layer comparator networks is given. Finding the minimum number of comparators for n>10 is still an open problem.  In this paper, we consider the optimal-size sorting networks problem. 

 
Heuristic approaches were also considered in literature, for example approaches based on evolutionary algorithms <cit.> 
that are able to discover new minimal networks for up to 22 inputs, but these methods cannot prove their optimality.


One of the most important and expensive operation used in <cit.> is the subsumption testing. This paper presents a new better approach to implement this operation based on matchings in bipartite graphs. The results show that the  new approach makes the problem more tractable by scaling it to larger inputs.


The paper is organized as follows. Section 2 describes the basic concepts needed to define the optimal-size sorting-network problem and a new model of the subsumption problem. Section 3 presents the problem of finding the minimal-size sorting network. Section 4 discusses the subsumption problem while Section 5 the subsumption testing. Section 6 presents the new way of subsumption testing by enumerating all perfect matchings. Section 7 describes the experiments made to evaluate the approach and presents the results. 





§ BASIC CONCEPTS
        


A comparator network C_n,k with n channels (also called wires) and size k is a sequence of comparators 
c_1=(i_1,j_1);…;c_k=(i_k; j_k) where each comparator c_t specifies a pair of channels 1 ≤ i_t < j_t ≤ n.
We simply denote by C_n a comparator network with n channels, whenever the size of the network is not significant in a certain context.

Graphically, a comparator network may be represented as a Knuth diagram <cit.>. 
A channel is depicted as a horizontal line and a comparator as a vertical segment connecting two channels.



An input to a comparator network C_n may be any sequence of n objects taken from a totally ordered set, for instance elements in ℤ^n.
Let x=(x_1,…,x_n) be an input sequence. Each value x_i is assigned to the channel i and it will "traverse" the comparator network
from left to right. Whenever the values on two channels reach a comparator c=(i,j) the following happens:
if they are not in ascending order the comparator permutes the values (x_i,x_j), otherwise the values will pass through the comparator unmodified.
Therefore, the output of a comparator network is always a permutation of the input. 
If x is an input sequence, we denote by C(x) the output sequence of the network C.

A comparator network is called a sorting network if its output is sorted ascending for every possible input.

The zero-one principle <cit.> states that if a comparator network C_n sorts correctly all 2^n sequences of zero and one, 
then it is a sorting network. Hence, without loss of generality, from now on we consider only comparator networks with binary input sequences.
In order to increase readability, whenever we represent a binary sequence we only write its bits; so 1010 is actually the sequence (1,0,1,0).

The output set of a comparator network is outputs(C)={C(x) | ∀x∈{0,1}^n}.
Let x be a binary input sequence of length n. 
We make the following notations: 
zeros(x)={1 ≤ i ≤ n | x_i = 0} and 
ones(x)={1 ≤ i ≤ n | x_i = 1}.
The output set of a comparator network C_n can be partitioned into n+1 clusters, 
each cluster containing sequences in outputs(C) having the same number of ones.
We denote by cluster(C,p) the cluster containing all sequences having p ones: 

cluster(C,p) = {x∈ outputs(C)  |  |ones(x)| = p }.

Consider the following simple network C=(1,2);(3,4).
The output clusters of C are:
cluster(C,0)={0000}, 
cluster(C,1)={0001,0100}, 
cluster(C,2)={0011,0101,1100}, 
cluster(C,3)={0111,1101},
cluster(C,4)={1111}.

The following proposition states some simple observations regarding the output set and its clusters.

Let C be a comparator network having n channels.


  (a) C is the empty network ⇔ |outputs(C)|=2^n.

  (b) C is a sorting network ⇔ |outputs(C)|=n+1 (each cluster contains exactly one element). 

  (c) |cluster(C,p)| ≤np, 1 ≤ p ≤ n-1.

  (d) |cluster(C,0)|=|cluster(C,n)|=1.



We extend the zeros and ones notations to output clusters in the following manner.
Let C be a comparator network. 
For all 0 ≤ p ≤ n we denote zeros(C,p) = ⋃{zeros(x) | x∈ cluster(C,p)} and  
ones(C,p) = ⋃{ones(x) | x∈ cluster(C,p)}.
These sets contain all the positions between 1 and n for which there is at least one sequence in the cluster having a zero, respectively an one, 
set at that position.
Considering the clusters from the previous example, we have:
zeros(C,0) = zeros(C,1) = zeros(C,2)={1,2,3,4}, zeros(C,3)={1,3}, zeros(C,4)=∅,
ones(C,0) = ∅, ones(C,1) = {2,4}, ones(C,2)=ones(C,3)=ones(C,4)={1,2,3,4}.

We introduce the following equivalent representation of the zeros and ones sets, as a sequence of length n, 
where n is the number of channels of the network, and elements taken from the set {0, 1}.
Let Γ be a cluster:


  * zeros(Γ) = (γ_1,…,γ_n), where γ_i=0 if i ∈ zeros(Γ), otherwise  γ_i=1,

  * ones(Γ) = (γ'_1,…,γ'_n), where γ'_i=1 if i ∈ ones(Γ), otherwise  γ'_i=0.

In order to increase readability, we will depict 1 values in zeros, respectively 0 values in ones 
with the symbol *.
Considering again the previous example, we have:
zeros(C,3)=(0*0*) and ones(C,1) = (*1*1).

If C is a comparator network on n channels and 1 ≤ i < j ≤ n we denote by C;(i,j) the concatenation of C and (i,j),
i.e. the network that has all the comparators of C and in addition a new comparator connecting channels i and j.
The concatenation of two networks C and C' having the same number of channels is denoted by C;C' and 
it is defined as the sequence of all comparators in C and C', first the ones in C and then the ones in C'.
In this context, C represents a prefix of the network C;C'.
Obviously, size(C;C')=size(C) + size(C').

Let π be a permutation on {1,…,n}. Applying π on a comparator network C=(i_1,j_1);…;(i_k,j_k) will produce 
the generalized network π(C)=(π(i_1),π(j_1));…;(π(i_k),π(j_k)). 
It is called generalized because it may contain comparators (i,j) with i>j, 
which does not conform to the actual definition of a standard comparator network.
An important result in the context of analyzing sorting networks (exercise 5.3.4.16 in <cit.>) states that 
a generalized sorting network can always be untangled such that the result is a standard sorting network of the same size.
The untangling algorithm is described in the previously mentioned exercise.
Two networks C_a and C_b are called equivalent if there is a permutation π such that untangling π(C_b) results in C_a.

Applying a permutation π on a binary sequence x=(x_1,…,x_n) will permute the corresponding values:
π(x) = (x_π(1),…,x_π(n)).
Applying π on a set of sequences S (either a cluster or the whole output set) will permute the values of all the sequences in the set:
π(S) = {π(x) | ∀x∈ S }.
For example, consider the permutation π=(4,3,2,1) and the set of sequences S={0011,0101,1100}.
Then, π(S)={1100,1010,0011}





§ OPTIMAL-SIZE SORTING NETWORKS
 


The optimal size problem regarding sorting networks is: 
"Given a positive integer n, what is the minimum number of comparators s_n needed to create a sorting network on n channels?".

Since even the problem of verifying whether a comparator network is a sorting network is known to be Co-𝒩𝒫 complete <cit.>,
we cannot expect to design an algorithm that will easily answer the optimal size problem. On the contrary.

In order to prove that s_n ≤ k, for some k, it is enough to find a sorting network of size k. 
On the other hand, to show that s_n > k one should prove that no network on n channels having at most k comparators is a sorting network.

Let R^n_k denote the set of all comparator networks having n channels and k comparators.
The naive approach to identify the sorting networks is by generating the whole set R^n_k, 
starting with the empty network and adding all possible comparators.



The algorithm to generate R^n_k


In order to find a sorting network on n channels of size k, 
one could iterate through the set R^n_k and inspect the output set of each network.
According to proposition <ref> (b), if the size of the output is n+1 then we have found a sorting network.
If no sorting network is found, we have established that s_n > k.

Unfortunately, the size of R^n_k grows rapidly since |R^n_k|= (n(n-1)/2)^k 
and constructing the whole set R^n_k is impracticable even for small values of n and k.

We are actually interested in creating a set of networks N^n_k that does not include all possible networks but contains only "relevant" elements.

A complete set of filters <cit.> is a set N^n_k of comparator networks on n channels and of size k, 
satisfying the following properties:


  (a) If s_n = k then N^n_k contains at least one sorting network of size k.

  (b) If k < s_n = k' then ∃ C^opt_n,k' an optimal-size sorting network 
  and ∃ C_n,k∈ N^n_k such that C is a prefix of C^opt.


Since the existence of N^n_k is guaranteed by the fact that R^n_k is actually a complete set of filters,
we are interested in creating such a set that is small enough (can be computed in a "reasonable" amount of time).





§ SUBSUMPTION
        

In order to create a complete set of filters in <cit.> it is introduced the relation of subsumption.
 
Let C_a and C_b be comparator networks on n channels. 
If there exists a permutation π on {1,…,n} such that π(outputs(C_a)) ⊆ outputs(C_b) we say that C_a subsumes C_b,
and we write C_a ≼ C_b (or C_a ≤_π C_b to indicate the permutation).


For example, consider the networks C_a=(0,1);(1,2);(0,3) and 
 C_b=(0,1);(0,2);(1,3).
Their output sets are: 

ouputs(C_a)={{0000},{0001,0010},{0011,0110},{0111,1011},{1111}}, 

ouputs(C_b)={{0000},{0001,0010},{0011,0101},{0111,1011},{1111}}. 

It is easy to verify that π=(0,1,3,2) has the property that C_a ≤_π C_b.

 
Let C_a and C_b be comparator networks on n channels, having |outputs(C_a)|=|outputs(C_b)|.
Then, C_a ≼ C_b ⇔ C_b ≼ C_a.


Assume that C_a ≤_π C_b ⇒π(outputs(C_a)) ⊆ outputs(C_b)
and since |outputs(C_a)|=|outputs(C_b)| ⇒π(outputs(C_a)) = outputs(C_b). 
That means that π is actually mapping each sequence in outputs(C_a) to a distinct sequence in outputs(C_b).
The inverse permutation π^-1 is also a mapping, this time from outputs(C_b) to outputs(C_a), 
implying that π^-1(outputs(C_b)) = outputs(C_a) ⇒ C_b ≤_π^-1 C_a.


The following result is the key to creating a complete set of filters:

Let C_a and C_b be comparator networks on n channels, both having the same size, and C_a ≼ C_b.
Then, if there exists a sorting network C_b;C of size k, there also exists a sorting network C_a;C' of size k.

The proof of the lemma is presented in <cit.> (Lemma 2) and <cit.> (Lemma 7).

The previous lemma "suggests" that when creating the set of networks R^n_k using the naive approach, 
and having the goal of creating actually a complete set of filters, we should not add two networks in this set if one of them subsumes the other.



The algorithm to generate N^n_k


A comparator c is redundant relative to the network C if adding it at the end of C does not modify the output set:
outputs(C;c) = outputs(C).
Testing if a comparator c=(i,j) is redundant relative to a network C can be easily implemented by inspecting the values x_i and x_j 
in all the sequences x∈ outputs(C). If x_i ≤ x_j for all the sequences then c is redundant.

The key aspect in implementing the algorithm above is the test for subsumption.






§ SUBSUMPTION TESTING


Let C_a and C_b be comparator networks on n channels. According to definition <ref>, in order to check if C_a subsumes C_b 
we must find a permutation π on {1,…,n} such that π(outputs(C_a)) ⊆ outputs(C_b).
If no such permutation exists then C_a does not subsume C_b.

In order to avoid iterating through all n! permutations, 
in <cit.> several results are presented that identify situations when subsumption testing can be implemented efficiently. 
We enumerate them as the tests ST_1 to ST_4.

(ST_1) Check the total size of the output 

If |outputs(C_a)| > |outputs(C_b)| then C_a cannot subsume C_b.

(ST_2) Check the size of corresponding clusters (Lemma 4 in <cit.>) 

If there exists 0≤ p ≤ n such that |cluster(C_a,p)| > |cluster(C_b, p)| then C_a cannot subsume C_b. 
When applying a permutation π on a sequence in outputs(C_a), the number of bits set to 1 remains the same, only their positions change.
So, if π(outputs(C_a))⊆ outputs(C_b) then ∀ 0≤ p ≤ n π(cluster(C_a),p) ⊆ cluster(C_b,p), 
which implies that |cluster(C_a)| = |π(cluster(C_a),p)| ≤ 
 |cluster(C_b,p)|  for all 0≤ p ≤ n.




(ST_3) Check the ones and zeros (Lemma 5 in <cit.>)

Recall that zeros and ones represent the sets of positions that are set to 0, respectively to 1.
If there exists 0≤ p ≤ n such that |zeros(C_a,p)| > |zeros(C_b,p)| or |ones(C_a,p)| > |ones(C_b,p)| then C_a cannot subsume C_b. 

For example, consider the networks C_a=(0,1);(2,3);(1,3);(0,4);(0,2) and C_b=(0,1);(2,3);(0,2);(2,4);(0,2).
cluster(C_a, 2)={0011,00110,01010}, cluster(C_b, 2)={00011,01001,01010},
ones(C_a, 2)={2,3,4,5}, ones(C_b, 2)={2,4,5}, therefore C_a ⋠C_b.




(ST_4) Check all permutations (Lemma 6 in <cit.>) 

The final optimization presented in <cit.> states that 
if there exists a permutation π such that π(outputs(C_a)) ⊆ outputs(C_b) then
∀ 0≤ p ≤ n zeros(π(C_a,p)) ⊆ zeros(C_b,p) and ones(π(C_a, p)) ⊆ ones(C_b, p). 
So, before checking the inclusion for the whole output sets, we should check the inclusion for the zeros and ones sets, 
which is computationally cheaper.

The tests (ST_1) to (ST_3) are very easy to check and are highly effective in reducing the search space.
However, if none of them can be applied, we have to enumerate the whole set of n! permutations, verify (ST_4) and eventually
the definition of subsumption, for each one of them.
In <cit.> the authors focused on n=9 which means verifying 362,880 permutations for each subsumption test.
They were successful in creating all sets of complete filters N^9_k for k=1,…,25 and actually proved that s_9=25.
Using a powerful computer and running a parallel implementation of the algorithm on 288 threads, 
the time necessary for creating these sets was measured in days (more than five days only for N^9_14).

Moving from 9! to 10!=3,628,800 or 11!=39,916,800 does not seem feasible.
We have to take in consideration also the size of the complete filter sets, for example |N^9_14|=914,444.

We present a new approach for testing subsumption, which greatly reduces the number of permutations which must be taken into consideration.
Instead of enumerating all permutations we will enumerate all perfect matchings in a bipartite graph created for the networks C_a and C_b being tested.





§ ENUMERATING PERFECT MATCHINGS
 


Let C_a and C_b be comparator networks on n channels.
The subsumption graph G(C_a,C_b) is defined as the bipartite graph (A, B; E(G)) 
with vertex set V(G)=A ∪ B,  where A=B={1,…,n} and the edge set E(G) defined as follows.
Any edge e∈ E(G) is a 2-set e={i,j} with i∈ A and j∈ B (also written as e=ij) having the properties:


  * i ∈ zeros(C_a,p) ⇒ j ∈ zeros(C_b,p), ∀ 0 ≤ p ≤ n;

  * i ∈ ones(C_a,p)  ⇒ j ∈ ones(C_b,p),  ∀ 0 ≤ p ≤ n.


So, the edges of the subsumption graph G represent a relationship between positions in the two output sets of C_a and C_b. 
An edge ij signifies that the position i (regarding the sequences in outputs(C_a)) and the position j (regarding C_b) 
are "compatible", meaning that a permutation π with the property π(outputs(C_a)) ⊆ outputs(C_b) might have the mapping i to j as a part of it.



As an example, consider the following zeros and ones sequences, 
corresponding to C_a=(0,1);(2,3);(1,3);(1,4) and C_b=(0,1);(2,3);(0,3);(1,4).
zeros(C_a)={00000,00000,000-0,000–,000–,—–},

zeros(C_b)={00000,00000,00000,000–,000–,—–},

ones(C_a)={—–,—11,1-111,11111,11111,11111},

ones(C_b)={—–,—11,-1111,11111,11111,11111}.

The subsumption graph G(C_a,C_b) is pictured below:


A matching M in the graph  G is a set of independent edges (no two edges in the matching share a common node).
If ij ∈ M we say that i and j are saturated. 
A perfect matching is a matching that saturates all vertices of the graph.


Let C_a and C_b be comparator networks on n channels. 
If C_a ≤_π C_b then π represents a perfect matching in the subsumption graph G(C_a,C_b).



Suppose that C_a ≤_π C_b, π(i)=j and ij ∉E(G). 
That means that ∃ 0≤ p ≤ n such that i ∈ zeros(C_a,p) ∧ j ∉zeros(C_b,p)
or i ∈ ones(C_a,p) ∧ j ∉ones(C_b,p). We will asumme the first case.
Let x a sequence in cluster(C_a,p) such that x(i)=0. 
Since π(outputs(C_a)) ⊆ outputs(C_b) ⇒π(x) ∈ cluster(C_b, p).
But π(i)=j, therefore in cluster(C_b, p) there is the sequence π(x) having the bit at position j equal to 0,
contradiction.


The previous lemma leads to the following result:
 
Let C_a and C_b be comparator networks on n channels.
Then C_a subsumes C_b if and only if there exists a perfect matching π in the subsumption graph G(C_a,C_b).


The graph in figure <ref> has only four perfect matchings: (2,1,3,4,5), (3,1,2,4,5), (2,1,3,5,4), (3,1,2,5,4).
So, when testing subsumption, instead of verifying 5!=120 permutations it is enough to verify only 4 of them.

If two clusters are of the same size, then we can strengthen the previous result even more.
If there is a permutation π such that π(cluster(C_a, p)) = cluster(C_b, p) then π^-1(cluster(C_b, p) = cluster(C_a, p).
Using the same reasoning, when creating the subsumption graph C(G_a,C_b) we add the following two condition when defining an edge ij:


  * j ∈ zeros(C_b,p) ⇒ i ∈ zeros(C_a,p), ∀ 0 ≤ p ≤ n such that |cluster(C_a,p)|=|cluster(C_b,p)|,

  * j ∈ ones(C_b,p) ⇒ i ∈ ones(C_a,p), ∀ 0 ≤ p ≤ n such that |cluster(C_a,p)|=|cluster(C_b,p)|.


In order to enumerate all perfect matchings in a bipartite graph, we have implemented the algorithm described in <cit.>.
The algorithm starts with finding a perfect matching in the subsumption graph G(C_a,C_b). 
Taking into consideration the small size of the bipartite graph, we have chosen the Ford-Fulkerson algorithm which is very simple and does not
require elaborate data structures. Its time complexity is O(n|E(G)|).
If no perfect matching exists, then we have established that C_a does not subsume C_b.
Otherwise, the algorithm presented in <cit.> identifies all other perfect matchings, taking only O(n) time per matching.




§ EXPERIMENTAL RESULTS
 


We implemented both variants of subsumption testing: 


  * (1) enumerating all permutations and checking the inclusions described by (ST_4) before verifying the actual definition of subsumption;

  * (2) verifying only the permutations that are actually perfect matchings in the subsumption graph, according to Corollary <ref>.




We made some simple experiments on a regular computer (Intel i7-4700HQ @2.40GHz), using 8 concurrent threads.
The programming platform was Java SE Development Kit 8.

Several suggestive results are presented in the table below:


t]|l|r|r|r|r|r|r|r|
(n,k)				   	|N^n_k|	    total		    sub		    perm_1			   	time_1	   	perm_2	   	time_2	
 (7,9)  			    	678		    1,223,426	    5,144	    26,505,101		   	2.88		   	33,120	   	0.07		
 (7,10)  			    	510		    878,995		    5,728	    25,363,033		   	2.82		   	24,362	   	0.06		
 (8,7)  			    	648		    980,765		    2,939	    105,863,506		   	13.67		   	49,142	   	0.14		
 (8,8)  			    	2088		    9,117,107	    9,381	    738,053,686		   	94.50		   	283,614	   	0.49		
 (8,9)  			    	5703		    24,511,628	    29,104	    4,974,612,498	   	650.22	   	1,303,340	   	1.96		
 




The columns of the table have the following significations:


  * (n,k) - n is the number of channels, k is the number of comparators;

  * |N^n_k| - the size of the complete set of filters generated for the given n and k;

  * total - the total number of subsumption checks;

  * sub - the number of subsumptions that were identified;

  * perm_1 - how many permutations were checked, using the variant (1);

  * time_1 - the total time, measured in seconds, using the variant (1);

  * perm_2 - how many permutations were checked, using the variant (2);

  * time_2 - the total time, measured in seconds, using the variant (2);


As we can see from this results, using the variant (2) the number of permutations that were verified in order to establish subsumption is greatly reduced.
Despite the fact that it is necessary to create the subsumption graph and to iterate through its set of perfect matchings, 
this leads to a much shorter time needed for the overall generation of the complete set of filters.

This new approach enabled us to reproduce the state-of-the-art result concerning optimal-size sorting networks, described in <cit.>.
Using an Intel Xeon E5-2670 @ 2.60GHz computer, with a total of 32 cores,
we generated all the complete set of filters for n=9. The results are presented in the table below.





t]|l|r|r|r|r|r|r|r|r|r|
k			   	1	    2	    3	    4	    5	    6	    7	    8		   	
 |N^9_k|	   	1	    3	    7	    20	    59	    208	    807	    3415	   	
 time(s)	   	0	    0	    0	    0	    0	    0	    0	    0		   	
 k			   	9		    10		    11		    12		    13		   	14	    15		    16		    
 |N^9_k|	   	14343	    55991	    188730	    490322	    854638	   	914444    607164	    274212	    
 time(s)	   	4		    48		    769		    6688	    25186	   	40896	    24161	    5511	    
 k			   	17	    18		    19		    20		    21	    22	    23	    24	    25 	
 |N^9_k|	   	94085	    25786	    5699	    1107	    250	    73	    27	    8	    1 	
 time(s)	   	610	    36	    2		    0		    0	    0	    0	    0	    0 	
 




In <cit.> the necessary time required to compute |N^9_14| using the generate-and-prune approach 
was estimated at more than 5 days of computation on 288 threads. 
Their tests were performed on a cluster with a total of 144 Intel E8400 cores clocked at 3 GHz.
In our experiments, the same set was created in only 11 hours, which is actually a significant improvement.




§ ACKNOWLEDGMENTS


We would like to thank Michael Codish for introducing us to this research topic and Cornelius Croitoru for his valuable comments. 
Furthermore, we thank Mihai Rotaru for providing us with the computational resources to run our experiments.




§ CONCLUSIONS


In this paper we have extended the work in <cit.>, further investigating the relation of subsumption.
In order to determine the minimal number of comparators needed to sort any input of a given length, a systematic BFS-like algorithm
generates incrementally complete sets of filters, that is sets of comparator networks that have the potential to prefix an optimal-size sorting network.
To make this approach feasible it is essential to avoid adding into these sets networks that subsume one another.
Testing the subsumption is an expensive operation, invoked a huge number of times during the execution of the algorithm.
We described a new approach to implement this test, based on enumerating perfect matchings in a bipartite graph, called the subsumption graph.
Computer experiments have shown significant improvements, greatly reducing the number of invocations and the overall running time.
The results show that, using appropriate hardware, it might be possible to approach in this manner the optimal-size problem 
for sorting networks with more than 10 channels.

plain


