Epic wheel reinventing: CUDA Software Rasterizer?

[_tommo_]

Nice!

Maybe the rasterization on larrabee article would be of some interest to you?

It's very interesting and comes really close to something i thought, but real GPUs have a limit that Larrabee hasn't - memory bandwith.
I'm now doing some experiments in rasterization, and the brute force method (scanline, one thread one triangle) actually yelds very good results, reaching 60 FPS on the same scene...
the low performance peak happens when there are only few big triangles on screen, because one thread has to make thousands of memory writes, while it scales very well to 100.000+ small (2,3 pixel big) triangles... proving that the heavy maths are almost insignificant for performance.

So i thought to reverse the algorithm and have each pixel find its triangle, but the simple sort i used has proven to be even slower than the brute force approach because it actually requres more memory bandwidth, and on top of all required some thread-safe writes that completely ruined performance.
So i'm still looking for a better algorithm, but until now on GPU "brute force is better"

[jjp]

What sorting method are you using? Have you looked at the Thrust library? It includes a very efficient radix sort implementation.

[volca]

If the performance is better for smaller triangles, could you divide the triangles into smaller ones based on their array or on-screen position, for example? You'd at least get a better load balancing and maybe even better performance thanks to the parallelization.

Also, then it could be possible to reject the triangles that have no on-screen impact based on some criteria (hierarchically subdivided z buffer? I'm purely dreaming here)

[_tommo_]

I was trying to "bin" each triangle into its cell, and then zsort each bin so that each pixel can access a small subset of the triangles in the scene, allowing to traverse all of them for intersection with the "ray"...
Unfortunately the big problem is where to put the triangle in the bin, because linked list and complex containers are not viable on GPUs... because memory indirection leads to sparse reads.

Also the radixsort used in the particles demo (uber-optimized ) requires 30% of frame time for "just" 32.000 particles, so it cant be used for polygons...

I don't know about thrust, the sort i need is not so generic...

@volca that, sir, was a good idea
Combined with some algorithms it would also work as tesselation, i will investigate the thing...

[volca]

I'm really interested what you can come up with - it seems promising so far

[jjp]

Also the radixsort used in the particles demo (uber-optimized ) requires 30% of frame time for "just" 32.000 particles, so it cant be used for polygons...

Unless they also updated the particles demo in the 2.2 SDK the algorithm from Thrust is a lot better An earlier version of the nex radix sort is also included in the Linux version of the 2.2 SDK in an own project.

If you want to sort sequences in the range of 250,000 to 1,000,000 elements you get a sorting rate between (depending on the distribution of your input) 50000 and 80000 elements sorted per millisecond. So you'd still spend a significant time per frame sorting. But maybe it is worth it, I can't tell

[_tommo_]

Unless they also updated the particles demo in the 2.2 SDK the algorithm from Thrust is a lot better An earlier version of the nex radix sort is also included in the Linux version of the 2.2 SDK in an own project.

If you want to sort sequences in the range of 250,000 to 1,000,000 elements you get a sorting rate between (depending on the distribution of your input) 50000 and 80000 elements sorted per millisecond. So you'd still spend a significant time per frame sorting. But maybe it is worth it, I can't tell

I will try, if it is faster than the demo one
Anyway i got the algorithm right, so now the polygon rasterizing works fine... i will post some other screenshots when i get interpolation working.

Now it runs around 60 FPS when the whole screen is occupied by the bunny (that has few pixels per polygon) and can get to 80-90 FPS with 345.000 polygons fully visible but occupying a small part of the screen.
So it's quite different from DirectX performance-wise

[_tommo_]

Finally i fixed the normals and added the phong interpolation, that came out as quite heavy (3 lerps per pixel)
The screenshot:


There's still a little bug with interpolation that causes small uncorrect scanlines, but it's not too noticeable...
anyway now it is enough slow... 40 FPS would be a good framerate, but the ugly thing is that rasterization is taking 84% of frame time...
If it could take 10-15% like in normal renders, in fact this would be blazing fast...

[jjp]

Is this such a surprise? For normal renders the gfx card uses pretty sophisticated fixed function hardware for rasterization

[volca]

I stumbled upon this article about rasterisation. The author divides the triangle into 8x8 blocks and processes coverage masks for each of them. I think this could be applied here as well, it makes the rasterisation look "parallelizable".

[_tommo_]

Is this such a surprise? For normal renders the gfx card uses pretty sophisticated fixed function hardware for rasterization

No it wasnt' much of a surprise... in fact i thought that a low-spec GPU like an 8600GT couldn't even run that in real time
Don't forget that it is a deferred render with two lights and HDR clamping on a scene with 345.000 polygons... and the rasterizing is made with the most straightforward algorithm.

I thought that CUDA would add an overhead to everything, but except rasterization the things were faster and easier to set up... for example the whole deferred thing is 400 lines long, when i don't want to imagine what it is on DirectX.
Given that on new GPUs (particularly GT300) shaders will be emulated on top of CUDA hardware, this experiment makes more sense.

@volca: i already read that paper, and i don't think it can give any improvements... because he uses ints: GPU uses 2 clocks for an int op, while can do 8 float ops in one single clock so it's better to get directly the pixels of the scanline solving fp linear equations.
And there's another problem: he divides THE triangle
So i have to setup many coverages mask for each triangle, spawning millions of threads... surely parallel, but i don't know how fast

[:wumpus:]

It's very interesting and comes really close to something i thought, but real GPUs have a limit that Larrabee hasn't - memory bandwith.

How come Larrabee doesn't have memory bandwidth limits? I thought GPU memory throughput was usually much higher than CPU memory throughput.

[_tommo_]

How come Larrabee doesn't have memory bandwidth limits? I thought GPU memory throughput was usually much higher than CPU memory throughput.

Don't know if "memory bandwidth" is the correct term, anyway i'm meaning the fact that GPUs have no automatic cache, and accessing global data can require as much as 600 clock cycles... while it looks that larrabee, being made of x86 processors doesn't suffer this much from memory accesses.

[:wumpus:]

That's a latency.. but indeed also a bandwidth issue, as GPU memory bandwidth is optimized to a certain optimal access pattern

[jjp]

Are you already making good use of the local shared memory and possibly of constant memory as well? I think caches eventually become unattractive as the number of cores increases, at least when the cached memory is writeable. It is easier then to use a lot of threads to hide latencies.

[_tommo_]

Are you already making good use of the local shared memory and possibly of constant memory as well? I think caches eventually become unattractive as the number of cores increases, at least when the cached memory is writeable. It is easier then to use a lot of threads to hide latencies.

I'm afraid that the only optimization one can do to that algorithm is rewriting from scratch
It occupies all the 32 registers, serializes nearly always (4 mln of different instructions due to the huge for) and pages exceeding registers into global memory...
so now i'm considering again the "multi-tile" rendering that could exploit good the things you say...
for example, if i'm able to z-sort the triangles in a tile it would be possibile to cache the first n in cache memory addressing most (if not all) the reads...
the biggest obstacle here is how to do the binning of triangles, i'm still trying various ways.

EDIT: it looks also possible to access memory both as texture and as generic memory, but only if a kernel doesn't read AND write to that memory...
most of the kernels in the pipeline have 1 write-only kernel and 1 read only kernel (especially postfilters) so this could be exploited to increase much the performance?

[:wumpus:]

EDIT: it looks also possible to access memory both as texture and as generic memory, but only if a kernel doesn't read AND write to that memory...
most of the kernels in the pipeline have 1 write-only kernel and 1 read only kernel (especially postfilters) so this could be exploited to increase much the performance?

It's even "possible" if the kernel both reads and writes to the memory, but in that case you can get correctness issues because the texture cache gets in the way. The card doesn't know that the memory you're writing to is also used as texture source, so it doesn't clear the cache.
Between kernels, this is no issue, as the texture cache is cleaned then anyway.

[_tommo_]

Wrapped the texture functionality, now it looks much more fluid... while not much faster.
Too bad that the debugger can't access TMUs so you can't know how many cache misses do you have, for example.

Looking around i saw that all of the buffers (except the backbuffer) have a kernel where they are read only... so i wanted to make everything as a texture.
I don't know if there is a "saturation limit" of TMUs anyway...

[:wumpus:]

Too bad that the debugger can't access TMUs so you can't know how many cache misses do you have, for example.

I believe that I read something about the new CUDA profiler (in the Beta maybe?) having much more counters, also things like cache misses and hits, I think. It might be worth looking at.

Also, do mind that the texture cache is extremely small. It will help you within a warp, but between warps that access different parts of the texture, things are flushed from the cache pretty quickly.

[_tommo_]

Reading everything from textures and using shared memory for many registers i reduced the rasterize time to 76% or 60% without interpolation... but it's still really much

I'm thinking now to a "tree rasterization" where you subdivide each side of the screen in two, having 4,8,16,... cells that have to traverse all the triangles in their parent cell to find wich ones are contained, eventually reaching down to the pixel.
It could be fast as when you have few cells but many triangles it is possible to split the traversal into many threads...

[_tommo_]

Ook i implemented some simple raytracing, but it was unbearably slow... after all the kernel was a bit simpler, but ran on millions of threads instead than 65.000.
After some tests i found out that the current bruteforce algorithm is the most performant i can imagine as for memory bandwidth/instructions, so now i am officially waiting for some hardware revolution

It would also be cool to be able to access rasterizers from cuda runtime like we do with texture units... after all DX11 compute shaders have their point, because they get well integrated with existing FF pipeline.

[Shadow007]

Ook i implemented some simple raytracing, but it was unbearably slow... after all the kernel was a bit simpler, but ran on millions of threads instead than 65.000.
After some tests i found out that the current bruteforce algorithm is the most performant i can imagine as for memory bandwidth/instructions, so now i am officially waiting for some hardware revolution

It would also be cool to be able to access rasterizers from cuda runtime like we do with texture units... after all DX11 compute shaders have their point, because they get well integrated with existing FF pipeline.

What kind of "ray-tracing" did you try ?

[_tommo_]

It's "raytracing" only for the fact that each pixel shoots a ray to traverse the polygon structure (subdivided in cells to make the search faster) and find its containing polygon.
Anyway there were many problems because the ray required a matrix multiplication to get in mesh space, indirect access to memory (cells) and many registers, so even if each pixels had to test less than 30 triangles the thing was slower that bruteforce anyway... because pixels are 1400*900 = almost one million and half.

[:wumpus:]

NVidia announced a raytracing infrastructure on I3D 2009 (NVirt), which is due to come out later this year, maybe they'll do something clever

[mkultra333]

I stumbled upon this article about rasterisation. The author divides the triangle into 8x8 blocks and processes coverage masks for each of them. I think this could be applied here as well, it makes the rasterisation look "parallelizable".

It's funny to see that thread still alive and kicking, since I read it years ago when I needed my own triangle rasterizer. It seems to be about the best article on the web for basic rasterization code.