[gecode-users] Managing memory footprint for large problems

Tue Apr 13 11:39:52 CEST 2010

Hi,

I wouldn't really know what to say off my head with the level of detail you
provide. Did you check the recent programming part in Modeling and
Programming with Gecode?

Domain sizes only matter if they have holes and are very, very large. Then
the number of variables and propagators matter. So, without some numbers of
how many propagators and variables your problem has I really can't say
anything.

Cheers
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 5:25 PM
To: Guido Tack; Christian Schulte
Cc: users at gecode.org gecode
Subject: Re: [gecode-users] Managing memory footprint for large problems

This does seem to be just a gist issue. I guess looking at that was throwing
me off. I used the MinimizeScript and it seems to behave as described as far
as cloning. I suppose our issue is just the number of propagators and the
size of the domains. I suppose we will have to look into defining our own
propagators. Do you have any recommendations for what to aim for in defining
our own propagators to reduce the memory usage and get the most bang for our
buck. What actually consumes the memory, common pitfalls, optimization
tricks?

As an example, We are doing things to constrain tasks that are somewhat
complicated such as you can only have 3 tasks or 10 hours worth of usage in
a period of time and these periods repeat over a specified interval. 

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: Guido Tack [mailto:tack at gecode.org] 
Sent: Monday, April 12, 2010 10:05 AM
To: cschulte at kth.se
Cc: Zaremby, David; users at gecode.org gecode
Subject: Re: [gecode-users] Managing memory footprint for large problems

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/

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users