Parallel Processing Letters

The splitting of Quasi-Monte Carlo (QMC) point sequences into interleaved substreams has been suggested to raise the speed of distributed numerical integration and to lower the traffic on the network. The usefulness of this approach in GRID environments is discussed. After specifying requirements for using QMC techniques in GRID environments in general we review and evaluate the proposals made in literature so far. In numerical integration experiments we investigate the quality of single leaped QMC point sequence substreams, comparing the respective properties of Sobol', Halton, Faure, Niederreiter-Xing, and Zinterhof sequences in detail. Numerical integration results obtained on a distributed system show that leaping sensitivity varies tremendously among the different sequences and we provide examples of deteriorated results caused by leaping effects, especially in heterogeneous settings which would be expected in GRID environments.

An earlier suggested parallel "ring" algorithm for solving the spatially one-dimensional initial-boundary-value problem (IBVP) for a parabolic equation using an explicit difference method is shortly described. Theoretical estimates for both of the speed-up function and the communication complexity of this parallel algorithm are studied. The speed-up function is determined as the ratio between times for realization of the algorithm in sequentional and parallel cases. Theoretical estimates of the speed-up function show the significant speed-up of the parallel algorithm in comparison with the serial one for a large number of values computed by one processor during one time level and it is shown that the the speed-up tends to the number of used processors. Communication complexity is determined as a ratio between the number of interchanges and the number of arithmetical operations. It has been proven that the coefficient of the communication complexity for spatially m-dimensional IBVP tends in general to ¾.

High performance parallel computers provide computational rates necessary for computer simulations and intensive computing applications. An important part of a parallel computer program is an MPI software library, which implements communication within parallel applications. Several MPI implementations exist, most widely used among them are LAM/MPI and MPICH. This paper presents results of four basic synthetic tests and two real simulations in LAM/MPI and MPICH environments. Tests were made on a computer cluster composed of 17 dual-processor nodes connected by a toroidal mesh. Results show that on the investigated cluster, LAM outperformed MPICH especially by bidirectional ring communication, and that appropriate trimming of communication parameters significantly contributes to the final parallel performance.

Much work has been done to optimize wavelet transforms for SIMD extensions of modern CPUs. However, these approaches are mostly restricted to the vertical part of 2-D transforms with line-wise organized memory layouts because this leads to a rather straight forward SIMD-implementation. This work shows for an example of a common wavelet filter new approaches to use SIMD operations on 1-D transforms that are able to produce reasonable speedups. As a result, the performance of algorithms that use wavelet transforms, such as JPEG2000, can be increased significantly. Various variants of parallelization are presented and compared. Their advantages and disadvantages for general filters are discussed.

In this paper we study different parallel implementations of the Savings based Ant System algorithm developed for solving the Vehicle Routing Problem. We analyze the effects of low-level parallelization, multiple search strategies and domain decomposition approaches. For the different strategies speedup and efficiency as well as solution quality are reported. Different information exchanges are analyzed within the multiple search strategies.

We show experimentally, that the QR factorization with the complete column pivoting, optionally followed by the LQ factorization of the R-factor, can lead to a substantial decrease of the number of outer parallel iteration steps in the parallel block-Jacobi SVD algorithm, whereby the details depend on the condition number and on the shape of spectrum, including the multiplicity of singular values. Best results were achieved for well-conditioned matrices with a multiple minimal singular value, where the number of parallel iteration steps has been reduced by two orders of magnitude. However, the gain in speed, as measured by the total parallel execution time, depends decisively on how efficient is the implementation of the distributed QR and LQ factorizations on a given parallel architecture. In general, the reduction of the total parallel execution time up to one order of magnitude has been achieved.

It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function are exhibited that cannot be computed on any machine that is capable of only a finite and fixed number of operations per step. This remains true even if the machine is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute . It also remains true if, in addition, is given an indefinite amount of time to compute . This result applies not only to idealized models of computation, such as the Turing Machine and the like, but also to all known general-purpose computers, including existing conventional computers (both sequential and parallel), as well as contemplated unconventional ones such as biological and quantum computers. Even accelerating machines (that is, machines that increase their speed at every step) cannot be universal.