Graphics Reference
In-Depth Information
uint_32_t getNext
(
uint64_t cell
)
{
1
return
cell
;
// extract least significant 32 bits
2
}
3
4
5
void
insertSorted
(
x
,
y
,
uint32_t depth
,
Data data
)
{
const int
fresh
=
atomicCounterIncrement
(
firstFreeCell
);
6
buffer
[
fresh
]
= ;
// 64
−
bits zero
7
memoryBarrier
() ;
// make sure init is visible
8
databuf
[
fresh
]
=
data
;
9
uint64_t record
=
pack
(
depth
,
fresh
),
old
,
pos
;
10
pos
=
gScreenW
y
+
x
;
// start of the search
11
while
((
old
=
atomicMax64
(
buffer
+
pos
,
record
))
>
0)
{
12
if
(
old
>
record
)
{
// go to next
13
pos
=
getNext
(
old
);
14
}
else
{
// inserted ! update record itself
15
pos
=
getNext
(
record
);
16
record
=
old
;
17
}}}
18
Listing 1.3.
Insertion-sort in a linked list.
1.2.3 Building Sorted Lists with Insertion-Sort (
Pre-Lin
)
It is also possible to perform parallel insertions at any position inside a linked
list, and therefore, to implement a parallel version of “insertion-sort.” General
solutions to this problem have been proposed. In particular, our approach is
inspired by that of Harris [Harris 01], albeit in a simplified setting since there is
no deletion of single items. A sample implementation is provided in Listing 1.3.
The idea is to walk along the linked list until we find the proper place to
insert the fragment. Contrary to the implementation of Harris, which relies on
an atomic compare-and-swap, we use an atomic max operation on the cells of the
main buffer at each step of the walk (line 12). Since the
depth
is packed in the
most significant bits of a cell (line 10), the
atomicMax
operation will overwrite the
fragment stored in the buffer if and only if the new fragment depth is larger. In
all cases the value in the buffer prior to the max is returned in the variable
old
.
If the new fragment has smaller depth (line 13) then the buffer has not changed
and the new fragment has to be inserted further down the list: we advance to the
next cell (line 14).
If the new fragment has a larger depth (line 15) then it has been inserted
by the
atomicMax
. At this point the new fragment has been inserted, but the
remainder of the list has been cut out: the new fragment has no follower (line 7).
We therefore restart the walk (line 16), this time trying to insert
old
as the
next element of
record
(line 17). That walk will often succeed immediately: the
atomicMax
operation will be applied at the end of the first part of the list and
will return zero (line 12). This single operation will merge back both parts of the
list. However there is an exception: another thread may have concurrently in-
serted more elements, in which case the walk will continue until all elements have
