Registered: Aug 2009
Posts: 3

I noticed a previous thread at http://forum.wolframscience.com/sho...hp?threadid=886 discussing the number of minimal sorting networks for 5 inputs. I've reproduced the number of results (11790) that the original poster of that thread did and again, would be keen to find how the different figure on page 1142 of NKS (13866) was generated.

I've had trouble working out what the exact differences between the lists are as we normalise the sequences differently but suspect there may be a difference in what is considered a 'distinct' sequence. I'd be keen to see how they were generated.

My normalisation conceptually works by dividing the sequence in to parallel groups. I require that if a comparator doesn't interfere with others in two adjacent parallel groups that it appears in the first. I then require that each parallel group is internally ordered by the first (always smallest) input used by comparator. e.g. [1, 3] would appear in a group before [2, 4]. In terms of actual implementation it works by filtering the list of significant pairs if adding them would breach those rules.

My counts by length for 5 inputs:
Count for length 9: 11790
Count for length 10: 449430

My counts by length for 6 inputs:
Count for length 12: 13635
Count for length 13: 6538230
Count for length 14: 627266970
Count for length 15: 10594460565

I've attached C code implementing this procedure. These numbers were actually produced by a very similar version optimised for the Cell processor - the results for 5 are the same. I'm aware this code is slower than it needs to be - this is the portable version to which I haven't yet added several optimisations. In particular it sorts integers, not bits :) .

This one also doesn't count and print lengths. It outputs one line per network. To convert to Mathematica you could:

./network_gen | ruby -e 'print "data = {"; print STDIN.read.split("\n").join(",").gsub("[", "{").gsub("]", "}"); print "};"'

I've included those results formatted like that as sorting.m in the file. Hope it works - I based the format on the file attached to the last discussion and I don't have a copy of Mathematica to check.

Any ideas where the difference lies? The last discussion didn't seem to produce much and there was no discussion of how they were generated. I'd be keen to know if I'm missing something.

Attachment: sorting.zip
This has been downloaded 727 time(s).

Last edited by Tim Goddard on 09-02-2009 at 10:21 PM

Report this post to a moderator | IP: Logged

Registered: Aug 2009
Posts: 3

Oh, and to add yet another "it doesn't do" - sorry about the poor commenting. Happy to explain anything I can.

Report this post to a moderator | IP: Logged

Registered: Aug 2009
Posts: 3

For those who are interested, I've attached the cell-optimised version here. This one is more complete and a lot faster, but requires a cell processor (for most that means Linux on the PS3). I've also tried to improve the documentation a bit, especially in the sorting_spu.c file.

On my PS3 with 6 SPUs this can traverse the complete state space of 6-input networks in under 2 hours - just shy of 2 million networks per second. I can't see any more easy gains but would be happy to accept suggestions and improvements. I've stuck it under a GPLv3 licence - feel free to modify and play around.

At the moment I'm working on and END-like system to plug in to this and run on the Cell. Each of the cell's cores has about twice the potential speed of the original paper's entire cluster and it has 6 of them we can use. With END Hugues Juillé was the last person to reduce the size of the best known optimal network. Maybe if we could get a group interested and a bunch of modern, faster computers one of them could be improved again, or create networks with some other property of interest.

Attachment: sorting_cell.zip
This has been downloaded 656 time(s).

Report this post to a moderator | IP: Logged