Optimal sorting networks with respect to cost criteria​
​By Victor Zhou
Sorting networks are an oblivious scheme for sorting arbitrary inputs of a predefined number of elements by means of a network of comparators. It is a problem in computer science to find the most optimal sorting networks in terms of number of comparisons, however there are no currently known algorithms which can efficiently find arbitrarily large optimal sorting networks for number of comparisons. In this project, we explore the novel problem of finding optimal sorting networks with respect to arbitrary cost functions. We discuss exhaustive search and graph-based approaches to the optimal sorting network problem. In addition, we also explore various graph-based visualisation methods for sorting networks. Finally, we conjecture an analytical solution for the problem of finding optimal length sorting networks.

Sorting Networks

Sorting networks are composed of wires and an ordered sequence of comparators (a comparator can be defined with a pair of wires). Graphically, a set of wires with some set of initial values are operated upon by an ordered set of comparators. Each comparator compares 2 wires, swapping their values if they are out of order and doing nothing otherwise.
Sorting networks are useful for their potential applications to computer hardware. Most notably in allowing for parallel execution and implementation of sorting algorithms in graphics processing units.
We say that sorting networks are oblivious because the sequence of comparators is predetermined and constant. Unlike certain sorting algorithms where there is no predetermined sequence of comparisons made, in a sorting network, subsequent comparisons for any comparator are equivalent regardless of any former comparison results.
Sorting networks have a predetermined number of wires which corresponds to the length of their input. A predetermined sequence of comparators is also defined for any sorting network. However, independent comparators (those which operate on distinct wires) can be executed in parallel, so we can define a sorting network by an ordered list of layers, each which are a list of independent comparators.
Define comparators as pairs of wire indexes:
In[]:=
c12={1,2};​​c23={2,3};​​c34={3,4};
Define layers as lists of independent comparators:
In[]:=
l1={c12,c34};​​l2={c23};​​l3={c12,c34};​​l4={c23};
Define networks as lists of layers:
In[]:=
net={l1,l2,l3,l4}
Out[]=
{{{1,2},{3,4}},{{2,3}},{{1,2},{3,4}},{{2,3}}}
Out[]=
Function that sorts a pair of elements within a list [1]:
In[]:=
PairSort[a_,p:{_,_}]:=Block[{t=a},t〚p〛=Sort[t〚p〛];t]
Function that preforms one layer of comparators on a list [1]:
In[]:=
LayerPairSort[input_,pairs_]:=Fold[PairSort,input,pairs]
Function that operates a sorting network upon a list [1]:
In[]:=
NetworkSort[input_,net_]:=Fold[LayerPairSort,input,net]

Sorting Network Validity

There are many ways to construct a sequence of comparators, but not every sequence of comparators constitutes a valid sorting network. We define a "valid" sorting network as one which for its input size can sort every possible input that it can take, and an "invalid" sorting network as one which cannot sort every input (i.e., a valid sorting network is one that is always able to sort correctly and an invalid sorting network is one that is unable to always sort correctly). The most intuitive way to check for the validity of a sorting network is simply to check all possible sequences of inputs. This would constitute sorting and verifying
n!
sequences, where
n
is the number of wires the sorting network takes, thus the time complexity for this method of validation is
O(n!)
.
Tests the validity of a sorting network by checking its ability to sort the set of all
n!
possible input sequences:
In[]:=
ExhaustiveValidNetworkQ[wires_, net_] := And @@ ((NetworkSort[#, net] == Range[wires]) & /@ Permutations[Range[wires]])
The zero-one principle
Despite that the method of checking all permutations of inputs is very simple, factorial time is computationally intractable and infeasible to be computed in a reasonable amount of time for large inputs. As an alternative, we can employ the zero-one principle to verify validity while checking fewer cases [4].
Zero-one Principle: If an n-wire sorting network sorts all
n
2
possible sequences of 0’s and 1’s correctly, then it sorts all sequences of arbitrary numbers correctly.
Gives all sequences of 0’s and 1’s for some length
n
:
In[]:=
AllCases[length_]:=Tuples[{0,1},length]
Gives all sorted sequences of 0’s and 1’s for some length
n
:
In[]:=
SortedCases[length_]:=DeleteDuplicates[Sort/@AllCases[length]]
Tests the validity of a sorting network by checking its ability to sort all possible sequences of 0’s and 1’s:
In[]:=
ValidNetworkQ[wires_,net_]:=And@@((MemberQ[SortedCases[wires],NetworkSort[#,net]])&/@AllCases[wires])
Prove the validity of the sorting network {{{1,2}}}:
In[]:=
ValidNetworkQ[2,{{{1,2}}}]
Out[]=
True
Prove the invalidity of an empty sorting network for a non-trivial number of wires:
In[]:=
ValidNetworkQ[2,{{{}}}]
Out[]=
False
This algorithm for proving the validity of a sorting network has time complexity
O(
n
2
)
. The number of sequences that must be tested can be reduced to at most
n
2
-n-1
. As a result, this exponential time algorithm will still be computationally intractable for large inputs, but testing
n
2
sequences is much more efficient than testing
n!
sequences.

Graphical Representations

In addition to visualizing a sorting network as a sequence of comparators applied in succession to a parallel set of wires, there are also many ways in which we can represent a sorting network as a graph. Understanding the graph-like properties of sorting networks may aid us in understanding their behaviour and effective global and local optimization methods.

"Picking-up" a Sorting Network

We can express a sorting network as a graph by defining starting points of wires, ending points of wires, and intersections between wires and comparators as vertices and defining wires and comparators as edges. Then we can imagine "picking-up" this sorting network and seeing how the wires and comparators might "untangle" themselves. We can connect the beginnings and ends of wires with edges to form closed loop graphs. The topologies of these various graphs may inform us about the structure of their corresponding sorting networks.
2D and 3D graph visualizations of select sorting networks (note that in this case "optimal" means optimal for number of comparators):
Out[]=
​
algorithm
Optimal
Batcher
dimensions
Graph3D
Graph
loop
Closed
Open
wires
Out[]=
​
algorithm
Insertion
Transposition
dimensions
Graph3D
Graph
loop
Closed
Open
wires
2
4
8
16

Underlying Graphs

It is not very intuitive for us to see the connections between comparators when a sorting network is expressed as a network. Instead we can define an "underlying graph" for sorting networks which has comparators as vertices and directed edges indicating comparators which feed directly into other comparators. Using this underlying graph it is easy for us to notice which comparators may be affecting each other. From the perspective of underlying graphs, we can consider the problem of finding optimal sorting networks to be the problem of finding edges that optimally connect given vertices in an underlying graph (i.e., the problem of finding optimal network topology) [3].
Underlying graph for a 5-wire optimal comparator sorting network:
Out[]=

Finding Optimal Networks

The problem of finding optimal sorting networks for some arbitrary criterion can be generalized to an optimization problem for minimizing an arbitrary function which maps some sorting network to a numerical "cost". For this optimization problem, we have generally deemed analytical solutions to be too "difficult" to find, thus we have mainly directed our search to methods of exhaustive search and graph-based approaches.

Minimal Length Networks

Outputs the length of a comparator:
Outputs the length of a layer of comparators:
Outputs the length of a sorting network:
We can find the length of the following network using NetworkLength:
Define the network:
Network visualizations:
Find the above network's length:

Exhaustive Search

With the exception of analytical solutions, the only known method of finding necessarily optimal sorting networks is through exhaustive search. There are many ways in which we can set up our problem space of networks to be verified for this problem.
Function that verifies the independence of a layer of comparators:
Find all valid sorting networks of 3 wires up to 4 layers:
Find the set of most optimal sorting networks with respect to length of the above list:
Compute the total number of networks of 4 wires up to 5 layers which must be tested for validity:
Find all valid sorting networks of 4 wires up to 5 layers (note this may take a few seconds to run):
Find the set of most optimal sorting networks with respect to length of the above list:
Compute the total number of networks of 5 wires up to 5 layers which must be tested for validity:
Find all valid sorting networks of 5 wires up to 7 layers (note the following cell has been made intentionally unevaluatable, run at your own risk):
A rule that we can employ to limit the size of our problem space and remove the need to arbitrarily select an upper bound for the number of layers is to define a length upper bound by using an algorithm which we know will always generate the shortest valid sorting network of all other known algorithms. This algorithm is insertion sort, and by defining this upper bound we only need to check the validity of sorting networks with length less than this upper bound. If there exists shorter valid sorting networks, then the set of shortest sorting networks are optimal. However, if all shorter sorting networks are proved to be invalid, the upper bound (insertion sort) must itself be an optimal sorting network.

Optimal Balance Networks

For various applications in computer hardware we might want to find optimal sorting networks which fulfill certain criteria such as:
1
.
Having the least number of comparators
2
.
Taking the least time to compute
3
.
Having the least total length of comparators
4
.
Having the most balanced voltage across all wires
We are particularly interested in the last of these criteria. In order to find optimal sorting networks for the criterion of balance, we can define a "weight" for each wire on a sorting network which is equal to the number of comparators which is connected to it. Furthermore, we must define a cost function which maps the variability of the weights of sorting network to some numerical value. However, we are not only interested in optimal balance, and we may also be interested in an optimal number of comparators or optimal length (i.e., we do not want very long but balanced networks to be comparably optimal to much shorter but still similarly balanced networks). As a result we can view this as a multi-objective optimization problem with balance and an arbitrary number of other criteria as objectives.
In this project, we will only choose balance and number of comparators to be our objectives for optimization. With this, we can write our cost function as some arbitrary linear combination of a measure for balance and a measure for number of comparators. There are many measures for the balance of a sorting network such as the standard deviation or average absolute deviation of the weights of the wires. For this project we will define our cost function in the following way:
Function that outputs the balance of a sorting network as defined by the cost function above:

Exhaustive Search

We can repeat the exhaustive search procedure previously used to find optimal length sorting networks to instead find optimal balance sorting networks.
Visualization of the optimal balance sorting network {{{1,3}},{{2,3}},{{1,2}}}:
Visualization of the optimal balance sorting network {{{1,2},{3,4}},{{1,3},{2,4}},{{2,3}}}:

Optimal Networks as Shortest Paths

We can think of the problem space of some binary sequence input to a sorting network by considering a weighted directed graph with vertices as permutations of the binary sequence and directed edges as comparators which transform a binary sequence into one of its permutations [2]. In this way, each path from a starting to the ending vertex is a sorting network which sorts the sequence corresponding to the starting vertex. To find sorting networks which have the ability to sort distinct sequences, we combine their problem space graphs. With this approach, we can interpret the problem of finding optimal sorting networks as the problem of finding the shortest path from the starting point to the ending point of a problem space graph.
Problem space graph of {1,1,0,0} with edges weights as comparator lengths and a shortest path highlighted:

Analytic Solutions

Although in general, analytical solutions to finding optimal sorting networks have been deemed too difficult to find, for the specific problem of finding sorting networks with optimal length, we conjecture that insertion sort is always the most optimal sorting network.
Conjecture: An insertion sort sorting network will have a network length at least as short as any other valid sorting network for all numbers of wires.
A rigorous proof for the former conjecture has not yet been formalized, however no known counterexample exists. We justify our belief in this conjecture with the following by informally following the steps that we might take to develop a formal proof of this conjecture using induction.
A formal proof via induction for the former conjecture should roughly be able to follow from these intermediate statements if a proof can be provided for the latter conjecture. These informal arguments are insufficient in rigour to qualify as true theorems, but we hope that they may shed some insight onto this problem. In the future, we hope that they might potentially pave the way for a formal proof of this conjecture or for a counterexample to be found.

Discussion

In this project we discussed the problem of optimization for sorting networks with respect to arbitrary criteria. We focused on the specific criteria of network length and network balance, applying a brute force exhaustive search approach to both and finding optimal sorting networks for the 3 and 4 wire cases. We explored the time complexity of algorithms for finding optimal sorting networks and discussed the intractability of deterministic algorithms to find large optimal sorting networks. We displayed various graph-based visualization approaches and how they can be used to solve the optimal sorting network problem. Finally, we conjectured an analytical solution for the optimal length sorting network problem.
Despite the developments demonstrated in this project, there is still significant work to be done for this novel sorting network optimization problem. In the future, we aim to develop efficient local search and optimization schemes in order to reduce the time it takes for us to find optimal sorting networks. We aim to further investigate graph-based optimization methods as well as analyze the topologies of sorting networks and their graphical representations. As a result of the lack of deterministic algorithms which can efficiently find optimal sorting networks, it was infeasible for us to find optimal networks even for input sizes even as small as 5 inputs. Historically, only non-deterministic algorithms have been able to reliably find near-optimal sorting networks of large input sizes. Stochastic search methods such as evolving non-determinism and genetic algorithms have been used to find optimal sorting networks for input sizes as large as 16 wires. We aim to apply genetic algorithms to this problem of finding optimal sorting networks with respect to arbitrary criteria through graph-based encoding and local optimization heuristics.

References