Vous pouvez vous abonner à nos annonces de séminaires
http://gallium.inria.fr/seminaires/
S E M I N A I R E
__
/ _` _ / / o /| /| __ __ __ __ _ _
/ ) __) / / / / / /\/| ----- / |/ | / )(_ / / ) ) ) __)
(___/ (_/ (_ (_ / (__/ / | / | (__/ __)(_ (__/ (_/ (_/
I N R I A - Rocquencourt
Amphi Turing du bâtiment 1
Lundi 9 décembre, 10h30
-----------
Mike Rainey
-----------
INRIA
=========================================
Theory of chunked sequences
and
applications to parallel graph algorithms
=========================================
For designing parallel algorithms, we needed a container data
structure (e.g., sequence, stack, bag, etc.) with log-time split and
concatenation operations, in addition to fast access to the ends of
the sequence. Tree data structures supporting these operations match
the required asymptotics, yet impose prohibitive constant factors. By
instantiating the leaves of these trees with chunks (i.e., arrays or
lists of items), previous work shows that the constant factors can be
significantly improved. However, these results hold only in the
typical case and degenerate in worst-case patterns.
We propose a general-purpose chunked-sequence data structure that we
are able to prove to deliver good constant factors in the worst case.
We implemented our data structure in C++ and show that it competes
well with the push and pop operations of STL vectors and deques. We
also implemented ephemeral sequences in OCaml and measured them to be
no more than twice slower than fixed-size circular arrays; we
implemented a persistent version that, on a LIFO microbenchmark, was
no more than twice slower than native lists.
We discuss only one particular application, namely parallel
DFS. However, we believe that this data structure has many more
application in the context of fork-join parallel computations, purely
functional programming, and representations of persistent strings.