Parallelization of a Monte Carlo particle transport simulation code

We have developed a high performance version of the Monte Carlo particle transport simulation code MC4. The original application code, developed in Visual Basic for Applications (VBA) for Microsoft Excel, was first rewritten in the C programming language for improving code portability. Several pseudo-random number generators have been also integrated and studied. The new MC4 version was then parallelized for shared and distributed-memory multiprocessor systems using the Message Passing Interface. Two parallel pseudo-random number generator libraries (SPRNG and DCMT) have been seamlessly integrated. The performance speedup of parallel MC4 has been studied on a variety of parallel computing architectures including an Intel Xeon server with 4 dual-core processors, a Sun cluster consisting of 16 nodes of 2 dual-core AMD Opteron processors and a 200 dual-processor HP cluster. For large problem size, which is limited only by the physical memory of the multiprocessor server, the speedup results are almost linear on all systems. We have validated the parallel implementation against the serial VBA and C implementations using the same random number generator. Our experimental results on the transport and energy loss of electrons in a water medium show that the serial and parallel codes are equivalent in accuracy. The present improvements allow for studying of higher particle energies with the use of more accurate physical models, and improve statistics as more particles tracks can be simulated in low response time.     

A KEY-SEARCH ATTACK ON MACLAREN-MARSAGLIA SYSTEMS

The MacLaren-Marsaglia algorithm combines two pseudo-random sequence generators to form a “more random” generator. A method of attacking stream ciphers which use this algorithm is described. It operates by searching for the key to one of the generators without using the other.     

A Scalable Parallel Algorithm for Self-Organizing Maps with Applications to Sparse Data Mining Problems

We describe a scalable parallel implementation of the self organizing map (SOM) suitable for data-mining applications involving clustering or segmentation against large data sets such as those encountered in the analysis of customer spending patterns. The parallel algorithm is based on the batch SOM formulation in which the neural weights are updated at the end of each pass over the training data. The underlying serial algorithm is enhanced to take advantage of the sparseness often encountered in these data sets. Analysis of a realistic test problem shows that the batch SOM algorithm captures key features observed using the conventional on-line algorithm, with comparable convergence rates.Performance measurements on an SP2 parallel computer are given for two retail data sets and a publicly available set of census data.These results demonstrate essentially linear speedup for the parallel batch SOM algorithm, using both a memory-contained sparse formulation as well as a separate implementation in which the mining data is accessed directly from a parallel file system. We also present visualizations of the census data to illustrate the value of the clustering information obtained via the parallel SOM method.     

Effective State Exploration for Model Checking on a Shared Memory Architecture

In this paper we present results from experimental studies investigating implementation strategies for explicit-state temporal-logic model checking on a virtual shared-memory high-performance parallel machine architecture. In particular, a parallel state exploration algorithm using a two-queue structure for load balancing is proposed and its performance analysed at the hand of experimental studies. We then discuss implementation issues for parallel automata-theoretic model checking using this parallel state exploration algorithm.     

Pseudo-random trees in Monte Carlo

We present the concept of a pseudo-random tree, and generalize the Lehmer pseudo-random number generator as an efficient implementation of the concept. Pseudo-random trees can be used to give reproducibility, as well as speed, in Monte Carlo computations on parallel computers with either the SIMD architecture of the current generation of supercomputer or the MIMD architecture characteristic of the next generation. Monte Carlo simulations based on pseudo-random trees are free of certain pitfalls, even for sequential computers, which can make them considerably more useful.     

Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions

A pseudo-random function is a fundamental cryptographic primitive that is essential for encryption, identification, and authentication. We present a new cryptographic primitive called pseudo-random synthesizer and show how to use it in order to get a parallel construction of a pseudo-random function. We show severalNC¹implementations of synthesizers based on concrete intractability assumptions as factoring and the Diffie–Hellman assumption. This yields the first parallel pseudo-random functions (based on standard intractability assumptions) and the only alternative to the original construction of Goldreich, Goldwasser, and Micali. In addition, we show parallel constructions of synthesizers based on other primitives such as weak pseudo-random functions or trapdoor one-way permutations. The security of all our constructions is similar to the security of the underlying assumptions. The connection with problems in computational learning theory is discussed.     

A new shape preserving parallel thinning algorithm for 3D digital images

This paper is concerned with a new parallel thinning algorithm for three-dimensional digital images that preserves the topology and maintains their shape. We introduce an approach of selecting shape points and outer-layer used for erosion during each iteration. The approach produces good skeleton for different types of corners. The concept of using two image versions in thinning is introduced and its necessity in parallel thinning is justified. The robustness of the algorithm under pseudo-random noise as well as rotation with respect to shape properties is studied and the results are found to be satisfactory.     

Finite length white noise generation with an immuno inspired algorithm

In this paper an immuno-inspired algorithm is proposed to generate sequences of data close to the ideal white noise. The motivation to propose the algorithm is that in many cases there is a necessity to generate white noises with a small number of samples, and the pseudo-random generators may fail to perform this task. The proposed algorithm is based on the maximization of the whiteness criterion, clearly defined in this paper, and is different from other immuno-inspired algorithms because it presents an automatic regulation of the suppression threshold, that is an important control variable of the algorithm. This feature allows the proposed algorithm to reach good results, even for different sizes of candidate solutions.To test the proposed algorithm, the results obtained from it are compared to the results obtained from a known pseudo-random generator and it is shown that the solutions obtained with the proposed algorithm are better, for time and frequency domain, if the number of samples required is limited. It is also shown that the proposed algorithm consumes a time comparable to the pseudo-random generator to reach solutions that are better than the ones obtained with that kind of algorithm.     

The parallel downhill simplex algorithm for unconstrained optimisation

In this paper we present a parallel implementation of a well-known heuristic optimisation algorithm (the downhill simplex algorithm developed by Nelder and Mead in 1965) which is well suited for unconstrained optimisation. We present the sequential algorithm as well as the parallel algorithm which we used to generate numerical results. They include numerical results of experiments on neural networks and a test suite of functions which demonstrate the parallel algorithm's increased robustness and convergence rate for high-dimensional problems compared to the sequential algorithm. © 1998 John Wiley & Sons, Ltd.     

An OpenCL library for parallel random number generators

The Journal of Supercomputing - We present a library of 22 pseudo-random number generators on the GPU. The library is implemented in OpenCL and all generators are tested using the TestU01 and...     

Assessing the Quality of Pseudo-Random Number Generators

In this article, we describe a new yet simple statistical procedure to better assess the quality of pseudo-random number generators. The new procedure builds on the statistical test suite proposed by the National Institute of Standards and Technology (NIST) and is especially useful for applications in economics. Making use of properties of the binomial distribution, we estimate the conjoint significance level of the test. We apply the proposed procedure to several well-known pseudo-random number generators, and the results confirm its effectiveness.     

基于MPI的伪随机序列并行加密算法研究

伪随机序列并行加密算法是科学与工程领域中极为重要的问题，拥有广泛的应用领域。而MPI是现在最流行的并行编程的工具，基于MPI的并行计算是现在被关注的热点。伪随机序列并行加密算法存在研究和实现上的困难，主要原因就是没有一个有效对它进行支持的工具。本文将伪随机序列并行加密算法与MPI结合起来，研究如何提高伪随机序列并行加密算法的效率。通过实验模拟和算法分析，证明这是有效的。因此，基于MPI的伪随机序列并行加密算法将会为相关应用和研究领域提供新的方法和方向。     

Generating good pseudo-random numbers

A widely used pseudo-random number generator has been shown to be inadequate by today's standards. In producing a revised generator, extensive use has been made of a test package TestU01 for random number generators. Using this, criteria have been devised for the revised generator—also other high-quality generators have been identified. Facilities have been devised to allow the new generator to be used in a highly parallel environment, which is likely to be a feature of many future applications.     

URNG: A portable optimization technique for software applications requiring pseudo-random numbers

Research software involving stochastic behaviour often requires millions of random numbers. In addition to the quality of the pseudo-random number generator (PRNG), the speed of the algorithm and the ease of its implementation are common practical aspects. In this work we will discuss how to optimize the access speed to random numbers independently from the generation algorithm. We propose an additional implementation technique in order to speed up any kind of PRNG taking into account the capacities of current computers and microcomputers. The speed of our solution stems from the classical unrolling optimization technique, it is named the URNG technique (unrolled random number generator). Random numbers are first generated in source code, then precompiled and stored inside the RAM of inexpensive computers at the executable loading time. With this technique random numbers need to be computed only once. The URNG technique is compliant with parallel computing. Limits and effects on speed and sensitivity are explored over four computer generations with a simple Monte Carlo simulation. Every research field using stochastic computation can be concerned by this software optimization technique which is currently limited to applications requiring not more than a few hundred millions of pseudo-random numbers.     

Color image encryption based on one-time keys and robust chaotic maps

We designed a stream-cipher algorithm based on one-time keys and robust chaotic maps, in order to get high security and improve the dynamical degradation. We utilized the piecewise linear chaotic map as the generator of a pseudo-random key stream sequence. The initial conditions were generated by the true random number generators, the MD5 of the mouse positions. We applied the algorithm to encrypt the color image, and got the satisfactory level security by two measures: NPCR and UACI. When the collision of MD5 had been found, we combined the algorithm with the traditional cycle encryption to ensure higher security. The ciphered image is robust against noise, and makes known attack unfeasible. It is suitable for application in color image encryption.     

Particle swarm optimization algorithm driven by multichaotic number generator

In this paper, the utilization of different chaotic systems as pseudo-random number generators (PRNGs) for velocity calculation in the PSO algorithm are proposed. Two chaos-based PRNGs are used alternately within one run of the PSO algorithm and dynamically switched over when a certain criterion is met. By using this unique technique, it is possible to improve the performance of PSO algorithm as it is demonstrated on different benchmark functions.     

Suggestions of efficient self-similar generators

The growth of Grid computing and the Internet has been exponential in recent years. These high-speed communication networks have had a tremendous impact on our civilisation. High-speed communication networks offer a wide range of applications, such as multimedia and data intensive applications, which differ significantly in their traffic characteristics and performance requirements. Many analytical studies have shown that self-similar network traffic can have a detrimental impact on network performance, including amplified queueing delays and packet loss rates in broadband wide area networks. Thus, full understanding of the self-similar nature in teletraffic engineering is an important issue.This paper presents a detailed survey of self-similar generators proposed for generating sequential and fixed-length self-similar pseudo-random sequences for simulation in communication networks. We evaluate and compare the operational properties of the fixed-length and sequential generators of self-similar pseudo-random sequences. The statistical accuracy and time required to produce long sequences are discussed theoretically and studied experimentally. The evaluation of the generators concentrated on two aspects: (i) how accurately self-similar processes can be generated (assuming a given mean, variance and self-similarity parameter H), and (ii) how quickly the generators can generate long self-similar sequences. Overall, our results have revealed that the fastest and most accurate generators of the six sequential and five fixed-length sequence generators considered are the SRP-FGN, FFT and FGN-DW methods.     

DEMCMC-GPU: An Efficient Multi-Objective Optimization Method with GPU Acceleration on the Fermi Architecture

In this paper, we present an efficient method implemented on Graphics Processing Unit (GPU), DEMCMC-GPU, for multi-objective continuous optimization problems. The DEMCMC-GPU kernel is the DEMCMC algorithm, which combines the attractive features of Differential Evolution (DE) and Markov Chain Monte Carlo (MCMC) to evolve a population of Markov chains toward a diversified set of solutions at the Pareto optimal front in the multi-objective search space. With parallel evolution of a population of Markov chains, the DEMCMC algorithm is a natural fit for the GPU architecture. The implementation of DEMCMC-GPU on the pre-Fermi architecture can lead to a ^~25 speedup on a set of multi-objective benchmark function problems, compare to the CPU-only implementation of DEMCMC. By taking advantage of new cache mechanism in the emerging NVIDIA Fermi GPU architecture, efficient sorting algorithm on GPU, and efficient parallel pseudorandom number generators, the speedup of DEMCMC-GPU can be aggressively improved to ^~100.     

Automatic test pattern generation on parallel processors

Test generation for combinational circuits is an important step in the VLSI design process. Unfortunately, the problem is highly computation-intensive and for circuits encountered in practice, test generation time can often be enormous. In this paper, we present a parallel formulation of the backtrack search algorithm called PODEM, which is a highly used algorithm for this problem. It is known that the sequential PODEM algorithm consumes most of its execution time in generating tests for ‘hard-to-detect’ (HTD) faults and is often unable to detect them even after a large number of backtracks. Our parallel formulation overcomes these limitations by dividing the search space and searching it concurrently using multiple processes.

We present a number of experimental results and show that these match our theoretical results presented elsewhere. We show that the search efficiency of the parallel algorithm improves and even beats that of the sequential algorithm as the ‘hardness’ of a fault increases. We present speedup results and performance analyses of our formulation on a 128 processor Symult s2010 multicomputer. We also present preliminary results on a network of Sun workstations. Our results show that parallel search techniques provides good speedups as well as high fault coverage of the HTD faults in reasonable time when compared to the uniprocessor implementation. Our experimental validation of most of our theoretical results builds confidence in the following theoretical prediction: our parallel formulation of PODEM is highly scalable on a variety of commercially-available, large MIMD parallel processors (in additions to the ones with which we experimented).