wildmyron wrote:The even width-18 search with zfind-s finished over the weekend. Alas, it too found no spaceships at that search width.
wildmyron wrote:This is an interesting idea to explore. Do you have some method in mind for determining which rows will be allowed to be at the full width?
I have a few ideas I want to test out. My first thought was simply to allow only a certain number of rows to be full-width and allow them to occur anywhere in the spaceship. Another idea is to have parameters that say a full-width row must occur by row N and no full-width rows can occur after row N.
wildmyron wrote:Whilst such a search will be faster than the complete full width search, I'm not sure that it "won't take too much longer than a standard search at the lower width" - like the ships with small full-width sections, there is a significant fraction of the search space which only has a small number of rows at the full width.
This is a good point. It's hard to know how these modifications will affect search length, and their purpose is for searches that are already reaching the edge of what is possible in a reasonable amount of time. A combination of the modifications described above may be necessary to get reasonable search lengths.
wildmyron wrote:Will the full-width portion be required to be contiguous? If not, you could constrain the search with a maximum number of full width rows and they would be allowed to occur anywhere in the current search state. Once the limit was reached all further rows would be constrained to the lower width.
This is how I first envisioned the modification.
Sokwe wrote:I have a farther-off plan of rewriting zfind as a breadth-first search with depth-first pruning, similar to gfind. I also plan to use openMP for distributing the depth-first pruning. This is a more ambitious endeavor than simple zfind modifications, so I don't plan to start it for at least a couple of months.
I sure am looking forward to this development. I suspect it will deliver a significant step change in the performance of spaceship search programs.
This has been my plan ever since I figured out that zfind works basically the same as gfind. I've noticed from running gfind that most of the time is taken in the depth-first stage.
gfind works as a breadth-first search with a limited queue size. Once the queue fills up, it takes each element (which represents a particular partial result), and tries to extend it to a specified depth. If it reaches that depth, the element is kept, but if no extension is found then the element is thrown away. Once it has gone through the whole queue, it repacks the remaining nodes of the search tree to save space and goes back to the breadth-first search.
It should be simple to split the depth-first portion among multiple processors. Just give each processor an element of the queue to check. A bit of care must be taken to avoid false sharing and potentially other issues. I don't have much knowledge of computer architecture or parallel computing, so if anyone has suggestions on what to watch out for, I would like to hear them.
Of course, the breadth-first portion can be split too, but that's a bit more complicated. I'll stick with the easiest implementation to begin with.
Other possibilities that I have no plans for at the moment:
- Distributed computing: parts of the breadth-first search queue could be sent out to multiple computers to perform the depth-first pruning. Besides just being a lot of work, I don't know enough about networks to do this.
- GPU computing: since zfind uses large lookup tables to find successive rows, I'm not sure if a GPU version could easily be written. gfind doesn't rely on large lookup tables, so it might work better. I might be completely wrong here, since I know very little about GPU programming.