I work with Ashis and I have been playing with a few experiments. What I am
seeing is that the memory is constantly climbing at every node as I traverse
down the left hand side despite very high computation parameters int
c_d=1000000, int a_d=1000000). I have posted the stack trace for the code to
maybe give some insight. I see the clone method being called for each node
which seems odd since I believe it should only be doing choice, status, and
commits. I have reverted back from our custom brancher to a simple built in of
branch(*this, resources, INT_VAR_MIN_MIN, INT_VAL_MIN). If I had to venture a
guess from exploring the code, it is because the workingspace is never being
initialized and thus it keeps trying to initialize it for the first time. The
memory growth seems to scale with the number of propagators. If I reduce my
scheduling constraints but leave my number of choice the same I get a smaller
memory footprint for each clone. The same behavior happens for the default c_d
and a_d values.
AutomatedScheduler++.exe!Scheduler::Scheduler(bool share=true,
Scheduler & s={...}) Line 65 C++
AutomatedScheduler++.exe!Scheduler::copy(bool share=true) Line 79 +
0x37 bytes C++
GecodeKernel-3-3-1-d-x86.dll!Gecode::Space::_clone(bool share=true)
Line 470 + 0x18 bytes C++
GecodeGist-3-3-1-d-x86.dll!Gecode::Space::clone(bool share=true,
Gecode::CloneStatistics & __formal={...}) Line 2369 C++
>
> GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::SpaceNode::recompute(Gecode::Gist::BestNode
> * curBest=0x1dde3558, int c_d=1000000, int a_d=1000000) Line 87 + 0x14
> bytes C++
GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::SpaceNode::acquireSpace(Gecode::Gist::BestNode
* curBest=0x1dde3558, int c_d=1000000, int a_d=1000000) Line 173 + 0x14 bytes
C++
GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::SpaceNode::getNumberOfChildNodes(Gecode::Support::BlockAllocator<Gecode::Gist::VisualNode,10000>
& na={...}, Gecode::Gist::BestNode * curBest=0x1dde3558,
Gecode::Gist::Statistics & stats={...}, int c_d=1000000, int a_d=1000000) Line
291 C++
GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::TreeCanvas::inspectCurrentNode(bool
fix=true, int inspectorNo=-1) Line 605 + 0x34 bytes C++
GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::TreeCanvas::mouseDoubleClickEvent(QMouseEvent
* event=0x017bd100) Line 1129 C++
David Zaremby
Senior Software Engineer
LSS / Strategic Products
Lockheed Martin Simulation, Training & Support
12506 Lake Underhill Road, MP-823
Orlando, FL 32825
-----Original Message-----
From: Maity, Ashis K
Sent: Monday, April 12, 2010 8:48 AM
To: Zaremby, David
Subject: FW: [gecode-users] Stopping Gecode Engine gracefully
FYI!
-----Original Message-----
From: Guido Tack [mailto:[email protected]]
Sent: Saturday, April 10, 2010 5:41 AM
To: Maity, Ashis K
Subject: Re: [gecode-users] Stopping Gecode Engine gracefully
Hi Ashis,
would you mind posting your message to the mailing list? I think this might
interest others, too. Anyway, here's my answer.
Maity, Ashis K wrote:
> Yes, that was also my understanding in terms of setting c_d and a_d. I was
> not clear in my write up. I mean to say that I am setting higher c_d so that
> it can use less memory and not run out of memory. But one thing you made
> clear is that even if I do not set a_d it will default to 2. I probably
> missed seeing that in documentation. I was hoping the default behavior of a_d
> will be like setting it higher than c_d (that is a_d is not used).
The defaults are independent of each other (i.e. c_d is always 8 and a_d is
always 2). We tried to come up with something more automatic, but it's not
clear how that's supposed to work.
> In any event, yes my problem runs out of memory with default c_d and a_d. And
> it does run out with other combination of c_d and a_d as well (say c_d =
> 20000 and a_d = 10000 or c_d = 200 and a_d = 100). Strange thing is even with
> varied c_d & a_d combination, my memory consumption graph rises almost
> similar way (as observed from Windows Task Manager). To give you some
> background, I am working on Scheduler problems that contain hundreds of tasks
> with large start domains and have many choices on resource. Previously I was
> using Mozart/Oz, but recently transferred my code to Gecode hoping it will
> help my memory problem. It appeared to do so when it ran a problem with 600
> tasks rather quickly. But when I try to run a problem with 1000 tasks, it
> crashes within a couple of minutes saying "heap memory is exhausted". It may
> be that my memory problem is exhausting before it comes to choices and that's
> why c_d and a_d value are not making much of a difference! Can you please
> comment on!
> this?
You could try running your problem in Gist and double-click the root node (that
will create exactly one instance of your problem and not perform any search).
If that exhausts the memory, it's clearly a problem in the model itself.
Actually, if that doesn't exhaust the memory, then setting c_d/a_d very high
should definitely at least change the memory behavior, because with a very high
c_d/a_d, the required memory is pretty much exactly twice the memory of the
root node.
If it turns out to be a problem in the root node already, there's several
things one could try. First of all, you should check how many variables you
create. If it's quadratic in the problem size (e.g. one Boolean for every pair
of tasks could be typical for scheduling problems), that would explain the
difference between 600 and 1000 tasks - I'm also working on scheduling problems
right now and I've run into similar issues. Being very careful not to create
too many temporary variables is very important in this case.
Then, it's sometimes possible to replace a set of propagators with one custom
propagator. That can help a lot if there's a large number (say, quadratically
many) of these propagators.
Finally, reformulating the problem might help, or trying to solve a relaxation
(e.g. aggregating several tasks into bigger meta-tasks to make the problem
smaller), but that's of course very problem-specific and sometimes simply
impossible.
Cheers,
Guido
--
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
