Graphics Reference
In-Depth Information
called
heads
, is necessary to store the address of the head cell of the linked list of
each pixel.
Having a lot of threads increment a single global counter would be a bot-
tleneck in a generic programing setting (compute API). Fortunately, GLSL frag-
ment shaders feature dedicated counters for this task, via the
ARB_shader_atomic_
counters
extension. If these are not available, it is possible to relieve some of the
contention on the counter by allocating
K
cells at once for a list (typically
K
=4).
To obtain such a paged allocation scheme, the thread atomically increases the
global counter by
K
and uses a single bit in each head pointer as a local mutex
when inserting fragments in this page of
K
cells. The technique is described
in full detail by Crassin [Crassin 10], and is implemented in the accompanying
code (see
implementations.fp
, function
allocate_paged
). In our tests, the dedi-
cated counters always outperformed the paging mechanism. However, if a generic
atomic increment is used instead then the paging mechanism is faster. We use a
single dedicated atomic counter in all our performance tests (Section 1.7).
We now describe the two techniques based on the Lin-alloc cell allocation
strategy: Post-Lin and Pre-Lin.
1.2.1 Building Unsorted Lists (
Post-Lin
)
The simplest approach to building an unsorted list of fragments is to insert new
fragments at the head of the pixel list. A sample implementation is provided in
Listing 1.1.
In line 7, a cell position
fresh
is reserved and the counter is incremented.
The operation must be done atomically so that no two threads reserve the same
position in the buffer. It is then safe to fill the cell with relevant fragment data
in lines 8 and 9. Finally, indices are exchanged so that the cell
buffer[fresh]
becomes the new head of the list.
Later, in Section 1.4.1, we describe how the fragments associated with each
pixel are gathered in a thread's local memory and sorted before rendering.
const int
gScreenSize
=
gScreenW
gScreenH
;
1
atomic_uint firstFreeCell
=0;
2
int
heads
[
gScreenSize
];
3
LinkedListCell_t buffer
[
gBufferSize
];
4
5
6
void
insertFront
(
x
,
y
,
float
depth
,
Data data
)
{
const int
fresh
=
atomicCounterIncrement
(
firstFreeCell
);
7
buffer
[
fresh
].
depth
=
depth
;
8
buffer
[
fresh
].
data
=
data
;
9
buffer
[
fresh
].
next
=
atomicExchange
(&
heads
[
x
+
y
gScreenW
],
fresh
);
10
}
11
Listing 1.1.
Insertion at the head of a linked list.
