[gecode-users] Managing memory footprint for large problems

Mon Apr 12 16:00:04 CEST 2010

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