Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Is your permutation algorithm unbiased for n not equal to 2 m?
Is your permutation algorithm unbiased if n is not equal a power of 2 m?
 Wyrzykowski, Roman (Ed.): Parallel processing and applied mathematics. 9th international conference, PPAM 2011. Pt.1 : Torun, Poland, September 1114, 2011; revised selected papers Berlin: Springer, 2012 (Lecture Notes in Computer Science 7203) ISBN: 9783642314636 (Print) ISBN: 3642314635 ISBN: 9783642314643 (Online) ISSN: 03029743 pp.297306 
 International Conference on Parallel Processing and Applied Mathematics (PPAM) <9, 2011, Torun> Minisymposium on GPU Computing <2011, Torun> Workshop on Memory and Data Parallelism on Multi and Manycore Platforms <2011, Torun> Workshop on Models, Algorithms and Methodologies for Hierarchical Parallelism in New HPC Systems <2011, Torun> 

 English 
 Conference Paper 
 Fraunhofer IGD () 
 algorithm; consistency; Graphics Processing Unit (GPU); Forschungsgruppe Capturing Reality (CARE) 
Abstract
Many papers on parallel random permutation algorithms assume the input size n to be a power of two and imply that these algorithms can be easily generalized to arbitrary n. We show that this simplifying assumption is not necessarily correct since it may result in a bias. Many of these algorithms are, however, consistent, i.e., iterating them ultimately converges against an unbiased permutation. We prove this convergence along with proving exponential convergence speed. Furthermore, we present an analysis of iterating applied to a butterfly permutation network, which works inplace and is wellsuited for implementation on manycore systems such as GPUs. We also show a method that improves the convergence speed even further and yields a practical implementation of the permutation network on current GPUs.