sorting networks for (already) partly sorted data

[henkjan-sneller]

I'm investigating the following: what is the impact on the number of layers when e.g. the first 32 elements of a total 48 elements are already sorted. I'm generating AVX512 assembly to sort floats in HPC context, and I'm considering to adopt this project to find such networks. But only if the number of layers is somewhat smaller.

Q: Have you ever seen such results? And would the method in SorterHunter be suitable to change to find such networks?

[henkjan-sneller]

Never mind, I see that the FixedPrefix is used for precisely what I need!

[bertdobbelaere]

I tried your example using the config file attached. I found that with 48 inputs of which 32 are already sorted, 16 layers can be achieved (maybe with longer search time, 15 layers is feasible ? Best known for a full 48-sorter is 18 layers). Example solution pasted in the config file.
In the example the centered 32 inputs had to be sorted (so two outermost groups of 8 inputs are unrestricted), but these can be relocated if needed by a transformation.
48_henkjan.txt

[henkjan-sneller]

Thank you, that helps a lot! I also tried something by plugging in an existing network (but used inputs 0..31), and I was analyzing the results. I'll look at your results next.

Small question: what tool do you use to print the end results. In your repo is (AFAICT) no code to separate the swaps into layers. Another project I tried has issues to do this (brianpursley/sorting-network#2)

[bertdobbelaere]

Indeed I did not commit auxiliary routines, I use a simple Python function for the layer separation (see attached). Should be easy to port to other languages. In essence, the network is scanned linearly. The layer number assigned to (both inputs of) an element is just one more than the highest layer number previously assigned to either input.
LinearToLayers.py.txt