Adaptive loops with kaapi on multicore and grid

Abstract

The parallelization of two applications in symmetric cryptography is considered: block ciphering and a new method based on random sampling for the selection of basic substitution boxes (S-box) with good algebraic properties. While both consists mainly in loops with independent computations and possibly early termination, they are subject to changing computation loads and processor speeds which can be managed by distributed workstealing. To take benefit of workstealing, we propose in this paper a generic way to rewrite loops in a recursive way, involving three complementary levels of parallelism. Dealing with early termination is performed by an amortized control, original to our knowledge. Those schemes have been embedded in STL-like parallel algorithms implemented on top of Kaapi library that provides distributed workstealing on a wide range of platforms. Experiments and performances are reported on SMP (up to 16 processors) and grid architectures (up to 2120 processors) for benchmarks (e.g. STL find if) and for the two target cryptography applications. These experiments exhibit the stability of the library and its usability by external users for effective applications.