Parallel Processing Letters

Current associative classification (AC) algorithms generate only the most obvious class linked with a rule in the training data set and ignore all other classes. We handle this problem by proposing a learning algorithm based on AC called Multi-label Classifiers based Associative Classification (MCAC) that learns rules associated with multiple classes from single label data. MCAC algorithm extracts classifiers from the whole training data set discovering all possible classes connected with a rule as long as they have sufficient training data representation. Another distinguishing feature of the MCAC algorithm is the classifier building method that cuts down the number of rules treating one known problem in AC mining which is the exponential growth of rules. Experimentations using real application data related to a complex scheduling problem known as the trainer timetabling problem reveal that MCAC's predictive accuracy is highly competitive if contrasted with known AC algorithms.

Randomization is a technique to improve efficiency and computability of distributed computing. In this paper, we investigate fault tolerance of distributed computing against faults of random number generators. We introduce an RNG (Random Number Generator)-fault as a new class of faults; a random number generator on an RNG-faulty process outputs the same number deterministically. This paper is the first work that considers faults of randomness in distributed computing.

We investigate the role of randomization by observing the impact of RNG-faults on performance of a self-stabilizing token circulation algorithm on unidirectional n-node ring networks. In the analysis, we assume there exist n_f (0 ≤ n_f ≤ n−1) RNG-faulty nodes and each RNG-faulty node always transfers a token to the next node. Our results are threefold: (1) We derive the upper bound on the expected convergence time in the case of n_f = n − 1. (2) Our simulation result shows that the expected convergence time is maximum when n_f = n − 1. (3) We derive the expected token circulation time for each n_f (0 ≤ n_f ≤ n − 1).

For many scientific applications, Graphics Processing Units (GPUs) can be an interesting alternative to conventional CPUs as they can deliver higher memory bandwidth and computing power. While it is conceivable to re-write the most execution time intensive parts using a low-level API for accelerator programming, it may not be feasible to do it for the entire application. But, having only selected parts of the application running on the GPU requires repetitively transferring data between the GPU and the host CPU, which may lead to a serious performance penalty. In this paper we assess the potential of compiler directives, based on the OpenACC standard, for porting large parts of code and thus achieving a full GPU implementation. As an illustrative and relevant example, we consider the climate and numerical weather prediction code COSMO (Consortium for Small Scale Modeling) and focus on the physical parametrizations, a part of the code which describes all physical processes not accounted for by the fundamental equations of atmospheric motion. We show, by porting three of the dominant parametrization schemes, the radiation, microphysics and turbulence parametrizations, that compiler directives are an efficient tool both in terms of final execution time as well as implementation effort. Compiler directives enable to port large sections of the existing code with minor modifications while still allowing for further optimizations for the most performance critical parts. With the example of the radiation parametrization, which contains the solution of a block tri-diagonal linear system, the required code modifications and key optimizations are discussed in detail. Performance tests for the three physical parametrizations show a speedup of between 3× and 7× for execution time obtained on a GPU and on a multi-core CPU of an equivalent generation.

We analyze the parallel performance of randomized interpolative decomposition by decomposing low rank complex-valued Gaussian random matrices of about 100 GB. We chose a Cray XMT supercomputer as it provides an almost ideal PRAM model permitting quick investigation of parallel algorithms without obfuscation from hardware idiosyncrasies. We obtain that on non-square matrices performance scales almost linearly with runtime about 100 times faster on 128 processors. We also verify that numerically discovered error bounds still hold on matrices two orders of magnitude larger than those previously tested.

We present a simple, work-optimal and synchronization-free solution to the problem of stably merging in parallel two given, ordered arrays of m and n elements into an ordered array of m+n elements. The main contribution is a new, simple, fast and direct algorithm that determines, for any prefix of the stably merged output array, the exact prefixes of each of the two input arrays needed to produce this output prefix. More precisely, for any given index in the resulting, but not yet constructed output array, representing the desired output prefix, the algorithm computes the indices (called co-ranks) in each of the two input arrays representing the required input prefixes without having to merge the input arrays. The co-ranking algorithm takes time steps, and uses O(1) space. Co-ranking is used in parallel to partition the input arrays into a collection of as many pairs as desired, each pair with exactly the same number of elements. Any stable, sequential merge algorithm can be used to merge pairs independently. The result is a perfectly load-balanced, stable, parallel merge algorithm. Co-ranking and sequential merging of pairs can be done without synchronization. Compared to other, linear speed-up approaches to the parallel merge problem, the algorithm is considerably simpler and can be up to a factor of two faster. Compared to previous algorithms for solving the co-ranking problem, the new algorithm works for arbitrary output array indices and maintains stability in the presence of repeated elements at no extra space or time cost. When the number of processing elements p does not exceed (m + n)/ log min(m, n), the parallel merge algorithm has perfect, linear speedup p. Furthermore, it is easy to implement on both shared and distributed memory systems.