PARALLEL RANDOM NUMBER GENERATIONOutlineSlide 3Random NumbersSlide 5Why To Prefer Pseudo- Random NumbersApplication AreasSlide 8The Linear Congruential GeneratorsThe Linear Congruential GeneratorsPeriod of Linear Congruential SequenceApproaches to the Generation of Random Numbers on Parallel ComputersCentralized ApproachReplicated ApproachDistributed ApproachDistributed ApproachesThe Random Tree MethodPowerPoint PresentationRandom Tree MethodThe Leapfrog MethodSlide 21Slide 22Slide 23Modified LeapfrogSlide 25Some Tests For Random Number GeneratorsFrequency TestRuns TestSlide 29Testing Parallel Random Number GeneratorsSlide 31Fourier Transform TestBlocking TestSPRNGSlide 35Refences:References (continued)PARALLEL RANDOM NUMBER GENERATIONAhmet DuranCISC 879OutlineRandom Numbers–Why To Prefer Pseudo- Random Numbers–Application Areas–The Linear Congruential Generators–Period of Linear Congruential SequenceApproaches to the Generation of Random Numbers on Parallel Computers–Centralized –Replicated–DistributedOutlineSome Tests For Random Number GeneratorsTesting Parallel Random Number GeneratorsSPRNG (Scalable Library for Pseudorandom Number Generation)Random NumbersWell-known sequential techniques exist for generating, in a deterministic fashion, The number sequences are largely indistinguishable from true random sequencesThe deterministic nature is important because it provides for reproducibility in computations.Efficiency is needed by preserving randomness and reproducibilityRandom NumbersConsider the following experiment to verify the randomness of an infinite sequence of integers in [1,d]. –Suppose we let you view as many numbers from the sequence as you wished to. –You should then guess any other number in the sequence. –If the likelihood of your guess being correct is greater than 1/d, then the sequence is not random.–In practice, to estimate the winning probabilities we must play this guessing game several times.Why To Prefer Pseudo- Random NumbersTrue random numbers are rarely used in computing because:–difficult to generate reliably–the lack of reproducibility would make the validation of programs that use them extremely difficultComputers use pseudo-random numbers: –finite sequences generated by a deterministic process –but indistinguishable, by some set of statistical tests, from a random sequence.Application AreasSimulation: When we simulate natural phenomena, random numbers are required to make things realistic. For example: Operations research (where people come into airport at random intervals.)Sampling: It is often impractical to examine all possible cases, but a random sample will provide insight into what constitutes "typical" behaviour. Computer Programming: Random values make good source of data for testing the effectiveness of computer algorithms.Application AreasNumerical AnalysisDecision Making: There are reports that many executives make their decisions by flipping a coin or by throwing darts, etc.Aesthetics: A little bit randomness makes computer-generated graphics and music seem more lively.Recreation: "Monte Carlo method", a general term used to describe any algorithm that employs random numbers.The Linear Congruential Generators Generator is a function, when applied to a number, yields the next number in the sequence. For example,X_k+1 = (a * X_k + c) mod m where X_k is the k th element of the sequence and X_0, a, c , and m define the generator.As numbers are taken from a finite set (for example, integers between 1 and 2^31), any generator will eventually repeat itself.The Linear Congruential GeneratorsThe length of the repeated cycle is called the period of the generator. A good generator is one with a long period and no discernible correlation between elements of the sequence. Example: X_k+1 = (3 * X_k + 4) mod 8E = {1, 7, 1, 7, …} is bad.Period of Linear Congruential Sequence Theorem: The linear congruential sequence has period m if and only if–c is relatively prime to m;–b = a - 1 is a multiple of p, for every prime p dividing m;–b is a multiple of 4, if m is a multiple of 4. Example: X_k+1 = (7 * X_k + 5) mod 18E = {1, 12, 17, 16, 9, 14, 13, 6, 11, 10, 3, 8, 7, 0, 5, 4, 15, 2, 1,…}Approaches to the Generation of Random Numbers on Parallel ComputersCentralized ReplicatedDistributedCentralized ApproachA sequential generator is encapsulated in a task from which other tasks request random numbers.Advantages:–Avoids the problem of generating multiple independent random sequencesDisadvantages:–Unlikely to provide good performance–Makes reproducibility hard to achieve: the response to a request depends on when it arrives at the generator, and the result computed by a program can vary from one run to the next.Replicated ApproachMultiple instances of the same generator are created (for example, one per task). Each generator uses either the same seed or a unique seed, derived, for example, from a task identifier. Advantages:–Efficiency–Ease of implementation Disadvantages:–Not guaranteed to be independent and, can suffer from serious correlation problems.Distributed ApproachResponsibility for generating a single sequence is partitioned among many generators, which can then be parcelled out to different tasks.Advantages:–The analysis of the statistical properties of the distributed generator is simplified because the generators are all derived from a single generator–EfficiencyDisadvantages:–Difficult to implement on parallel computersDistributed ApproachesThe techniques described here are based on an adaptation of the linear congruential algorithm called the random tree method.This facility is particularly valuable in computations that create and destroy tasks dynamically during program execution.The Random Tree Method The Leapfrog MethodModified LeapfrogThe Random Tree Method The random tree method employs two linear congruential generators, L and R , that differ only in the values used for a . L_k+1 = a_L L_k mod mR_k+1 = a_R R_k mod m R1LR0R2Application of the left generator L to a seed generates one random sequence; application of the right generator R to the same seed generates a different sequence. By applying the right generator to elements of the left generator's sequence (or vice versa), a tree of random numbers can be generated. By