Playing with Sorting Networks
Recently I’ve been playing around with sorting networks. So far I’ve developed:
- sorting.rb generates sorting networks of a given size slowly
- network_gen.c generates them about 300 times faster
- sorting.5.gz (19MB) is a file containing all valid, non-redundant 5-input sorting networks. Each line is a network as a JSON list of pairs to compare. Was generated with functions from the Ruby script (the commented out main routine). Took about 6 hours on an EC2 large instance (reasonably fast dual-core computer).
- git clone git://goddard.net.nz/sorting will get the latest version of the sorting network generator code. Check out the cell branch – contains a version optimised for the Cell processor (a PS3 for me). This splits the work across the 6 available SPUs and can generate 6-input networks at about 2 million per second. Man that processor is amazing!