[gecode-users] Managing memory footprint for large problems

Mon Apr 12 16:05:00 CEST 2010

That was actually a small bug in Gist that only occurred when using interactive search.  I just fixed it in the trunk version.

Cheers,
	Guido

Christian Schulte wrote:

> Dear David,
> 
> could you (or Ashis) please check whether you observe the same behavior when
> not using Gist, but a simple search engine?
> 
> Thanks
> Christian
> 
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
> 
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Zaremby, David
> Sent: Monday, April 12, 2010 3:41 PM
> To: users at gecode.org; Guido Tack
> Subject: [gecode-users] Managing memory footprint for large problems
> 
> 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 defaul
> t 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::Gis
> t::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(Ge
> code::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(Q
> MouseEvent * 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:tack at gecode.org] 
> 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 o
> n!
>> 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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/