Re: [Algorithms] Cache-oblivious layout (was: BSP tree, or what?)

[<gd...@er...>]

> My colleagues Sung-Eui Yoon and Peter Lindstrom did a very
> thorough study of various cache-efficiency metrics for

Nice coincidence, I met up with Sung-Eui Yoon in Seoul a few weeks ago, and 
discussed his cache oblivious methods in the context of tree traversals. 

To quote part of our conversation: 

"In fact, you can think that cache-oblivious layout is a kind of hybrid
between breadth-first and depth-first layout.
Its key idea is to find a cluster of nodes that are likely to access
together and store them in one cache block; this method is optimized
for a particular cache block size so this is a cache-aware layout.
For cache-oblivious layouts, we simply recursively perform clustering
for each computed cluster and order those clusters in order to make
them works well with geometrically increasing cache block sizes." 

For the AABB tree implementation in Bullet, I chose to optimize the 
depth-first traversal with chunks that fit in SPU memory (around 32kb), 
because for collision detection purposes the order to visit children doesn't 
matter much. Each chunk (sub-tree) automatically contains triangles that are 
closeby, so if you render them in different colors, you get a nice looking 
patchwork. 

Hope this helps,
Erwin 

 

Mark Duchaineau writes: 

> My colleagues Sung-Eui Yoon and Peter Lindstrom did a very
> thorough study of various cache-efficiency metrics for
> a variety of space-filling variants in a paper
> "Mesh Layouts for Block-Based Caches" from IEEE Vis 2006,
> pdf here: 
> 
> http://www.cc.gatech.edu/~lindstro/papers/blockcache/paper.pdf 
> 
> Looks like some special variants on Hilbert and a block
> interpretation of Sierpinski do very well, depending on the
> way you define efficiency (will vary by application requirements
> a bit, in other words). 
> 
> Cheers, 
> 
> --Mark D. 
> 
> Daniel Vollmer wrote:
>> On Jun 6, 2008, at 01:07 , Tom Forsyth wrote: 
>> 
>> 
>>>After experience with Morton vs Hilbert in a bunch of areas  
>>>(rasterization,
>>>texture storage, vertex caching, etc), my gut feeling is that a  
>>>Hilbert
>>>curve very rarely gives a worse cache-traversal pattern than Morton.  
>>>Note
>>>the very precise statement! However, it can be a pain to implement  
>>>(whereas
>>>Morton is pretty trivial), and whether it's actually a significant  
>>>*win*
>>>depends a lot on a bazillion things.
>>  
>> 
>> I'd agree with Tom's gut impression. :) 
>> 
>> For a wavelet image compression algorithm (shameless plug: http://www.maven.de/code/wavelet/) 
>>   I went with Morton / Z first, and then later on went ahead and  
>> implemented a Hilbert curve variant. The Hilbert curve gave slightly,  
>> but consistently better results (i.e. smaller images) which means it  
>> extracted locality better than the other space-filling curves, and as  
>> I stored the curve in a table anyhow the computational cost was  
>> irrelevant. Of course, there were also cases where the Morton curve  
>> fared better, but they were very much in the minority (and from and  
>> Information Theory viewpoint they *have* to exist).
>> The above-linked code has a nice, self-contained 2D Hilbert Curve  
>> generation (which gets optimized to a simple loop due to tail- 
>> recursion), which is quite easy to extend to 3D (as was done in the  
>> paper referenced in the source). 
>> 
>> 
>> 	Daniel. 
>> 
>> -------------------------------------------------------------------------
>> Check out the new SourceForge.net Marketplace.
>> It's the best place to buy or sell services for
>> just about anything Open Source.
>> http://sourceforge.net/services/buy/index.php
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list 
>> 
> 
> -------------------------------------------------------------------------
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list