  In this paper, we study a parallel version of Galton-Watson processes for the
random generation of tree-shaped structures. Random trees are useful in many
situations (testing, binary search, simulation of physics phenomena,...) as
attests more than 49000 citations on Google scholar. Using standard analytic
combinatorics, we first give a theoretical, average-case study of the random
process in order to evaluate how parallelism can be extracted from this
process, and we deduce a parallel generation algorithm. Then we present how it
can be implemented in a task-based parallel paradigm for shared memory (here,
Intel Cilk). This implementation faces several challenges, among which
efficient, thread-safe random bit generation, memory management and algorithmic
modifications for small-grain parallelism. Finally, we evaluate the performance
of our implementation and the impact of different choices and parameters. We
obtain a significant efficiency improvement for the generation of big trees. We
also conduct empirical and theoretical studies of the average behaviour of our
algorithm.
