Optimizing For Cache Friendliness

Since you only have 9 vertices you don't have to worry about post-T&L cache becouse cache size is usualy +12 vertices. If you will be working with larger sets of data then search for some cache optimization algorithems. Or just implement one on your own (a simple greedy (O(n^2)) works just nice).

Quote:

Original post by haro Also, is there a way ( preferably in D3D ) to determine how many vertices are being transformed and how many did not need to be transformed since they were already cached? This would make solving this problem somewhat easier.

I don't know if DX has a tool for this but writing one yourself is very simple. You just have to simulate how cache works on GPU and send it your index buffer.

for the 9 verts, not gonna make a difference.

I saw a paper on optimizing DX performance and they said to optimize the cache usage you send data down in one order on one frame (0 to n) and then the reverse order on the next frame (n to 0) since the last data would be cached and reused. This was a long time ago so possibly for DX7/8.

I dunno if this still applies though, sorry can't be more helpful

Sorry for the confusion. I am not actually sending only 9 vertices. I simply gave that example to show the way that I am winding the vertices. I am actually sending millions of vertices. If I was only sending 9 vertices I'd just be sending them immediate mode.

If you care to reference any cache optimization papers I'd love to read them, it's why I asked the question in the first place. Most papers on optimizing data, that I have been able to find, are often rather old and have hints that may or may not be applicable now days - such as attempting to send your batches in as close to 64k bytes at a time as possible.

Triangle lists in strip order are recomended by ATI while NV perfers tri-stips. Both apprently make good use of the post-T&L cache.

While this info was from an OpenGL presentation the same should apply to D3D as its the same gpus [grin]

Geforce 1/2 post-TnL cache has 16 entries, GF3 -> 24 entries.
It's FIFO(?) cache:

-----------------------------------------------------
out<<<|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|<<<-----------------------------------------------------

So if you reuse one of the last 16 processed vertices, it's very fast because this vertex is already in cache. But if you miss chache, cache is shifted left(1->out,2->1,...,16->15), new vertex is transformed and put at cache slot no 16.

If you want to optimally send tyour vertex data, nvidia has a great tri-stripper at their developer site. It's called NVTriStrip. It can also remap vertex buffer for you in order to avoid VRAM page swapping.

EDIT:

Quote:

Post below by -DarkWIng- tomek_zielinski: You have subtract a few (usualy 4) entrys from actual cache size becouse of pipelining isues.

I was thinking if I should have mentioned about it but finally I fogot:) Sorry...

[Edited by - tomek_zielinski on July 11, 2004 2:13:20 PM]

I don't have links ready, but short google should turn something up. Search also for utillitys that generate triangle strips as they often include option to generate cache optimized triangle lists. I know nVidia has a tool for this (nvTriStrip or something simmilar). And I remember seeing one or two opensource programs for this on opengl.org forums.

If you are doing this for things like terrain tiles then you might even get away without using cache optimizations. Just generate it "right" in the first place. To do so you 'll probably have to study how algorithems like this even work and apply it on a bit different problem. This should be faster since you skip the whole optimization step.

And also keep in mind pre-T&L cache. This one works in same way as the one on CPU (LRU). You might sometimes have to trade post-T&L optimization for pre-T&L.

edit: wow.. 2 replys while I was typing.
tomek_zielinski: You have subtract a few (usualy 4) entrys from actual cache size becouse of pipelining isues.