Hi all,
On Fri, 10 Feb 2012 16:07:04 +0200
Shlomi Fish <shlomif_at_shlomifish.org> wrote:
> 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.
>
After a lot of work on reducing memory fragmentation and excessive
calls to malloc()/realloc()/free(), we've ran the FCC-based solver again on
Amadiro's machine, and it again ran out of memory, this time after 2,027,372,039
iterations. The problem now is that this time we waste 8-bytes of RAM (pointer
sized) for every 8-bytes (or sometimes less) of moves-stack-moves, which makes
matters worse. So either we find a machine with more RAM available to it, or we
think of a better way to determine whether 982 is solvable or not. I suspect
part of the problem is that with advanced states, the free columns cause the
number of positions in an FCC to expand considerably, and maybe there's a way
to prune them somehow (more about it later).
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Stop Using MSIE - http://www.shlomifish.org/no-ie/
I used to be arrogant. Now I’m simply Perfect.
— one of Shlomi Fish’s relatives.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Fri Mar 02 2012 - 03:45:33 IST