DOTMIX-Pro: faster and more efficient variants of DOTMIX for dynamic-multithreading platforms

Many concurrency platforms offer a processor oblivious model of computation, where the scheduler dynamically distributes work across threads. While this is convenient, it introduces non-determinism at runtime, which complicates debugging, because a program may have different outputs after each run. Leiserson et. al. [PPoPP ’12] persuaded Intel to modify its C/C++ compiler, which provided the Cilk Plus concurrency platform, to include a feature called pedigrees, which enables determinism by uniquely identifying strands with low overhead. They used pedigrees to design a DPRNG called DOTMIX, which hashes a pedigree, then mixes the result into a random number for a given strand. Improving the efficiency of DOTMIX by using a faster hash function is an open problem put forth by Leiserson et al. [PPoPP ’12]. We address this problem by introducing DOTMIX-Pro, which replaces the compression function used in DOTMIX with a faster universal hash function family called Square Hash due to Etzel et al. [CRYPTO ’99] and some of its variants, as well as other optimizations, which can be up to $$31\%$$ faster. Additionally, we introduce a generalization of Square Hash which works with arbitrary moduli.