Hi all,
well, after I've written the specification for the Fully Connected Components
solver (see the preliminary SPEC posted to the list at
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1093 ),
I set out to implement it. This was done in steps, while doing some unit-tests
and testing individual functions.
In the course of this work, the initial SPEC changed in two important ways:
1. I found a way to handle Horne's Prune by keeping all the FCC-depths in an
array, and applying the steps in the Horne's Prune to the array.
2. We now perform the Fully Connected Component Breadth First Search (BrFS)
scan once instead of twice, by merging its two functionalities.
The up-to-date SPEC is in:
http://code.google.com/p/fc-solve/source/browse/fc-solve/trunk/fc-solve/docs/fully-connected-components-based-solver-planning.txt
In any case, after everything was ready, we deployed the fcc_fc_solver on
Amadiro's university's HPC machine and let it try to solve deal No. 982, with a
cache of 64 million states. It took it a while to run, and while it reached
2,370,371,079 positions (which is better than the so-called "DBM-FC-Solver"'s
reached 1,704,551,170 positions),
it ended up running out of RAM. A simple linear regression on the ratio of
checked states vs. those remaining in the collection for the DBM-FC-Solver
predicts that the deal will be saturated at ~2.94 milliard positions.
All is not lost, because based on the percentage of the consumed memory in the
run, it seems that memory consumption had grown significantly towards the end
without yielding substantial results. I suspect this may have been caused by
memory fragmentation
(see
http://en.wikipedia.org/wiki/Fragmentation_%28computing%29 ), and have
started implementing some code to reduce this and re-use previously allocated
RAM. I have some other memory optimisations in mind, as well, but they are
relatively minor.
Hopefully, this will allow us to handle deal No. 982 and future deals that are
currently intractable.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
UNIX Fortune Cookies - http://www.shlomifish.org/humour/fortunes/
Modern Perl — the 3‐D Movie. In theatres near you.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Fri Feb 10 2012 - 06:22:48 IST