Graphics Reference
In-Depth Information
and the search for a free cell for
f
p
proceeds at age
i
+1intheprobe
sequence of pixel
p
.
This
eviction
mechanism, whereby an “old” fragment evicts a younger fragment,
has been demonstrated to effectively reduce the maximum age of the fragments
stored in the main buffer, over all pixels. This property was discovered by Celis
and Munro in their technique called
Robin Hood Hashing
[Celis et al. 85].
1.3.2 Building Unsorted Lists (
Post-Open
)
In this section, we give the full details of the construction of unsorted lists of
fragments using the allocation scheme described above.
In the rest of this chapter, we assume that a cell of the main buffer occupies
64 bits, which lets us use atomic operations on a cell, and that the age of a
fragment is stored in the most significant bits of the cell:
age: 8 bits empty: 24 bits data: 32 bits
.
In this way, the eviction mechanism described above can be safely accomplished
using a single call to
atomicMax
.
We use an auxiliary 2D table
A
that stores, for each pixel
p
, the age of the
oldest fragment associated with
p
in the main buffer. Thus,
A
[
p
] indicates the
end of the list of
p
's fragments; from which we can start the search for an empty
cell for the new fragment
f
p
to be inserted.
The insertion procedure is shown in Listing 1.4. It increments a counter
age
starting from
A
[
p
] + 1 (line 2) until it finds an empty cell at position
h
(
p,
age
)
void
insertBackOA
(
p
,
depth
,
data
)
{
1
age
=
A
[
p
]+1;
uint
2
uint64_t record
=
OA_PACK
(
age
,
depth
,
data
);
3
int
iter
=0;
4
while
(
iter
++
<
MAX_ITER
)
{
5
=(
p
+
offsets
[
age
])%
gBufSz
;
uvec2
h
6
uint64_t old
=
atomicMax
(&
buffer
[
h
],
record
);
7
if
(
old
<
record
)
{
8
atomicMax
(&
A
[
p
],
age
);
9
if
(
old
== 0 )
break
;
10
uint32_t oage
=
OA_GET_AGE
(
old
);
11
=(
h
+
gBufSz
−
offsets
[
oage
]) %
gBufSz
;
p
12
age
=
A
[
p
];
13
record
=
OA_WRITE_AGE
(
old
,
age
);
14
}
15
++
age
;
16
record
=
record
+
OA_INC_AGE
;
17
}}
18
Listing 1.4.
Insertioninalistwithopenaddressing.
