Transcript Containers, Iterators, Algorithms, Thrust

Containers, Iterators, Algorithms,
Thrust
Richard Kelley
we want faster programs!

problem



we want to use the GPU
we don’t want to use CUDA or OpenCL
solution


use a library that “acts like” something we already know.
Thrust to the rescue!
Thrust

what is it?
from the Thrust webpage:
“Thrust is a CUDA library of parallel algorithms with an interface
resembling the C++ Standard Template Library (STL). Thrust
provides a high-level interface for GPU programming that
greatly enhances developer productivity.”


exactly what we want.

but we need to be comfortable with the STL to use
thrust.
what is the STL?


precursor to the standard library
the major parts are still around






containers
iterators
algorithms
functors
thrust is based on these abstractions
not object-oriented, but functional and generic

we don’t combine data and operations, we explicitly separate
them.
containers

STL containers are what they sound like


the primary goal (in this part of the standard library) is
efficiency


objects that hold other objects
error-checking takes a secondary role almost everywhere
there are containers for most of the data structures
you’re likely to use



dynamic arrays, deques, linked lists
balanced binary trees
hash tables (new in C++11)
container types (1/2)


three main types (as of c++11)
sequence containers




std::vector – a dynamically resizable array
std::deque – a dynamically resizable double-ended queue
std::list – a doubly linked list
associative containers (elements must implement <)




std::map – efficient key-value stores. keys must be unique
std::set – a set of things. elements must be unique
std::multimap – key-value stores, keys needn’t be unique
std::multiset – a multiset of things. elements needn’t be unique
container types (2/2)

unordered associative containers (hash tables)






std::unordered_set
std::unordered_multiset
std::unordered_map
std::unordered_multimap
they say “unordered” to avoid name conflicts with
libraries that made their own “hash_*”
this is new in C++11 – your mileage may vary.
common operations on containers










constructor, destructor
constructor(beg, end)
size()
empty()
max_size()
begin(), end()
rbegin(), rend()
insert(pos, elem)
erase(beg, end)
clear()
iterators

object that can iterate over a collection



an iterator’s value represents a position in a container
an iterator is anything that acts like an iterator:





duh
operator*
operator++ (sometimes operator--)
operators == and !=
operator=
Containers have functions that return special iterators


begin
end
iterators categories

C++ offers a few categories of iterator.





input iterators
output iterators
forward iterators
bidirectional iterators
random access iterators
algorithms



STL contains several algorithms to do stuff with
containers.
global functions
accept ranges defined by iterators
algorithm types (1/6)

nonmodifying algorithms






count()
count_if()
min_element()
max_element()
find(), find_if()
…
algorithm types (2/6)

modifying algorithms





for_each
copy, copy_backward
transform
merge
…
algorithm types (3/6)

removing algorithms


remove, remove_if
unique

removes adjacent duplicates
algorithm types (4/6)

mutating algorithms (change element orders, not values)





reverse
rotate
next_permutation, prev_permutation
random_shuffle
partition, stable_partition
algorithm types (5/6)

sorting algorithms

sort


stable_sort





probably mergesort.
partial_sort


probably quicksort. maybe introsort (quicksort+heapsort).
just do the first n elements. probably heapsort.
make_heap
push_heap
pop_heap
sort_heap
algorithm types (6/6)

algorithms for sorted ranges






binary_search
merge
set_union
set_intersection
set_difference
set_symmetric_difference
functors (function objects)

any object that has overloaded operator()




yes, you can do that
also called “function objects”
can have internal state
(probably) faster than a function pointer

I haven’t checked this
code!

let’s look at some
what does Thrust give us?

thrust aims to “look like” STL, but runs on the GPU


sequence containers





you get speedup doing little beyond what you would do in STL.
host_vector
device_vector
iterators
algorithms
functors are just like standard C++

thrust has some special functors
thrust containers


we get vectors
we have to specify location

thrust::host_vector


thrust::device_vector



resides on the CPU side
resides on the GPU
“host” and “device” are common terms to distinguish
between the CPU and the GPU.
we can build thrust containers from std containers
thrust iterators & algorithms


basic iterator usage is the same as STL
thrust also has “fancy iterators” that perform additional
functionality


thrust algorithms are similar to STL


(their name, not mine)
there are some built-ins that perform simple tasks.
let’s look at some code

add two vectors