Re: [BGL] Using BGL for huge graphs

From: Jeppe N. Madsen (yg-boost-users_at_[hidden])
Date: 2003-02-03 09:55:29

>  
>  Chris Russell wrote:
> > Erik, how huge is huge? Heap requirements in excess of 2^64 bytes
> > huge? If so, that's one _massive_ graph and some supercomputer
> > programmer will have to help.
>  
>  Well, 2^64 bytes is several orders of magnitude larger than I had
>  in mind. I guess my graph would be something like 1000 GB
>  tops. It's still a pretty massive graph though...

I think the term you're looking for is "External-Memory Graph
Algorithms".....googling turns up some stuff which may be
interesting. Note that this is an active area of research so it
may not be easy to make these algorithms work with BGL....

 
> > If not, then why not leverage the full virtual memory space
> > allocated to your process and let the OS worry about paging the
> > data in/out of physical memory?
>  
>  This is definitely an alternative, but my worry is that this
>  solution might be much slower than it needs to be. When swapping
>  back and forth, the OS doesn't really know what's going on, whereas
>  I might have the knowledge of the order in which the different
>  parts of the graph are processed etc.

Letting the OS worry about paging is usually not a good idea if you
have some advance knowledge on how you'll use your data. Running times
can be decreased by several orders of magnitude by paying attention to
how memory is used. Check out papers on cache aware/cache
oblivious/external memory/ algorithms for further details....

rgds
Jeppe