Parallel Hybrid Monte Carlo Algorithms for Matrix Computations

In this paper we consider hybrid (fast stochastic approximation and deterministic refinement) algorithms for Matrix Inversion (MI) and Solving Systems of Linear Equations (SLAE). Monte Carlo methods are used for the stochastic approximation, since it is known that they are very efficient in finding a quick rough approximation of the element or a row of the inverse matrix or finding a component of the solution vector. We show how the stochastic approximation of the MI can be combined with a deterministic refinement procedure to obtain MI with the required precision and further solve the SLAE using MI. We employ a splitting A = D – C of a given non-singular matrix A, where D is a diagonal dominant matrix and matrix C is a diagonal matrix. In our algorithm for solving SLAE and MI different choices of D can be considered in order to control the norm of matrix T = D –1C, of the resulting SLAE and to minimize the number of the Markov Chains required to reach given precision. Further we run the algorithms on a mini-Grid and investigate their efficiency depending on the granularity. Corresponding experimental results are presented.

Parallel Monte Carlo algorithms for information retrieval

In any data mining applications, automated text and text and image retrieval of information is needed. This becomes essential with the growth of the Internet and digital libraries. Our approach is based on the latent semantic indexing (LSI) and the corresponding term-by-document matrix suggested by Berry and his co-authors. Instead of using deterministic methods to find the required number of first "k" singular triplets, we propose a stochastic approach. First, we use Monte Carlo method to sample and to build much smaller size term-by-document matrix (e.g. we build k x k matrix) from where we then find the first "k" triplets using standard deterministic methods. Second, we investigate how we can reduce the problem to finding the "k"-largest eigenvalues using parallel Monte Carlo methods. We apply these methods to the initial matrix and also to the reduced one. The algorithms are running on a cluster of workstations under MPI and results of the experiments arising in textual retrieval of Web documents as well as comparison of the stochastic methods proposed are presented. (C) 2003 IMACS. Published by Elsevier Science B.V. All rights reserved.

A sparse parallel hybrid Monte Carlo algorithm for matrix computations

In this paper we introduce a new algorithm, based on the successful work of Fathi and Alexandrov, on hybrid Monte Carlo algorithms for matrix inversion and solving systems of linear algebraic equations. This algorithm consists of two parts, approximate inversion by Monte Carlo and iterative refinement using a deterministic method. Here we present a parallel hybrid Monte Carlo algorithm, which uses Monte Carlo to generate an approximate inverse and that improves the accuracy of the inverse with an iterative refinement. The new algorithm is applied efficiently to sparse non-singular matrices. When we are solving a system of linear algebraic equations, Bx = b, the inverse matrix is used to compute the solution vector x = B(-1)b. We present results that show the efficiency of the parallel hybrid Monte Carlo algorithm in the case of sparse matrices.

Computational complexity of weighted splitting schemes on parallel computers

In models of complicated physical-chemical processes operator splitting is very often applied in order to achieve sufficient accuracy as well as efficiency of the numerical solution. The recently rediscovered weighted splitting schemes have the great advantage of being parallelizable on operator level, which allows us to reduce the computational time if parallel computers are used. In this paper, the computational times needed for the weighted splitting methods are studied in comparison with the sequential (S) splitting and the Marchuk-Strang (MSt) splitting and are illustrated by numerical experiments performed by use of simplified versions of the Danish Eulerian model (DEM).

Parallel implementation and one year experiments with the Danish Eulerian Model

Large scale air pollution models are powerful tools, designed to meet the increasing demand in different environmental studies. The atmosphere is the most dynamic component of the environment, where the pollutants can be moved quickly on far distnce. Therefore the air pollution modeling must be done in a large computational domain. Moreover, all relevant physical, chemical and photochemical processes must be taken into account. In such complex models operator splitting is very often applied in order to achieve sufficient accuracy as well as efficiency of the numerical solution. The Danish Eulerian Model (DEM) is one of the most advanced such models. Its space domain (4800 × 4800 km) covers Europe, most of the Mediterian and neighboring parts of Asia and the Atlantic Ocean. Efficient parallelization is crucial for the performance and practical capabilities of this huge computational model. Different splitting schemes, based on the main processes mentioned above, have been implemented and tested with respect to accuracy and performance in the new version of DEM. Some numerical results of these experiments are presented in this paper.

A comparative study of Java and C performance in two large-scale parallel applications

In the 1990s the Message Passing Interface Forum defined MPI bindings for Fortran, C, and C++. With the success of MPI these relatively conservative languages have continued to dominate in the parallel computing community. There are compelling arguments in favour of more modern languages like Java. These include portability, better runtime error checking, modularity, and multi-threading. But these arguments have not converted many HPC programmers, perhaps due to the scarcity of full-scale scientific Java codes, and the lack of evidence for performance competitive with C or Fortran. This paper tries to redress this situation by porting two scientific applications to Java. Both of these applications are parallelized using our thread-safe Java messaging system—MPJ Express. The first application is the Gadget-2 code, which is a massively parallel structure formation code for cosmological simulations. The second application uses the finite-domain time-difference method for simulations in the area of computational electromagnetics. We evaluate and compare the performance of the Java and C versions of these two scientific applications, and demonstrate that the Java codes can achieve performance comparable with legacy applications written in conventional HPC languages. Copyright © 2009 John Wiley & Sons, Ltd.

A parallel convolutional coder including embedded puncturing with application to consumer devices

As consumers demand more functionality) from their electronic devices and manufacturers supply the demand then electrical power and clock requirements tend to increase, however reassessing system architecture can fortunately lead to suitable counter reductions. To maintain low clock rates and therefore reduce electrical power, this paper presents a parallel convolutional coder for the transmit side in many wireless consumer devices. The coder accepts a parallel data input and directly computes punctured convolutional codes without the need for a separate puncturing operation while the coded bits are available at the output of the coder in a parallel fashion. Also as the computation is in parallel then the coder can be clocked at 7 times slower than the conventional shift-register based convolutional coder (using DVB 7/8 rate). The presented coder is directly relevant to the design of modern low-power consumer devices

Applying autonomic computing concepts to parallel computing using intelligent agents

The work reported in this paper is motivated by the fact that there is a need to apply autonomic computing concepts to parallel computing systems. Advancing on prior work based on intelligent cores [36], a swarm-array computing approach, this paper focuses on ‘Intelligent agents’ another swarm-array computing approach in which the task to be executed on a parallel computing core is considered as a swarm of autonomous agents. A task is carried to a computing core by carrier agents and is seamlessly transferred between cores in the event of a predicted failure, thereby achieving self-ware objectives of autonomic computing. The feasibility of the proposed swarm-array computing approach is validated on a multi-agent simulator.

Diacylglycerol-induced protection against injury during ischemia and reperfusion can be achieved without activation of protein kinase C in the rat heart: Comparative studies with ischemic preconditioning

The role of protein kinase C (PKC) activation in ischemic preconditioning remains controversial. Since diacylglycerol is the endogenous activator of PKC and as such might be expected cardioprotective, we have investigated whether: (i) the diacylglycerol analog 1,2-dioctanoyl-sn-glycerol (DOG) can protect against injury during ischemia and reperfusion; (ii) any effect is mediated via PKC activation; and (iii) the outcome is influenced by the time of administration. Isolated rat hearts were perfused with buffer at 37°C and paced at 400 bpm. In Study 1, hearts (n=6/group) were subjected to one of the following: (1) 36 min aerobic perfusion (controls); (2) 20 min aerobic perfusion plus ischemic preconditioning (3 min ischemia/3 min reperfusion+5 min ischemia/5 min reperfusion); (3) aerobic perfusion with buffer containing DOG (10 μM) given as a substitute for ischemic preconditioning; (4) aerobic perfusion with DOG (10 μM) during the last 2 min of aerobic perfusion. All hearts then were subjected to 35 min of global ischemia and 40 min reperfusion. A further group (5) were perfused with DOG (10 μM) for the first 2 min of reperfusion. Ischemic preconditioning improved postischemic recovery of LVDP from 24±3% in controls to 71±2% (P<0.05). Recovery of LVDP also was enhanced by DOG when given just before ischemia (54±4%), however, DOG had no effect on the recovery of LVDP when used as a substitute for ischemic preconditioning (22±5%) or when given during reperfusion (29±6%). In Study 2, the first four groups of study were repeated (n=4–5/group) without imposing the periods of ischemia and reperfusion, instead hearts were taken for the measurement of PKC activity (pmol/min/mg protein±SEM). PKC activity after 36 min in groups (1), (2), (3) and (4) was: 332±102, 299±63, 521±144, and 340±113 and the membrane:cytosolic PKC activity ratio was: 5.6±1.5, 5.3±1.8, 6.6±2.7, and 3.9±2.1 (P=NS in each instance). In conclusion, DOG is cardioprotective but under the conditions of the present study is less cardioprotective than ischemic preconditioning, furthermore the protection does not appear to necessitate PKC activation prior to ischemia.

Phorbol ester, but not ischemic preconditioning, activates protein kinase D in the rat heart

The signal transduction pathways that mediate the cardioprotective effects of ischemic preconditioning remain unclear. Here we have determined the role of a novel kinase, protein kinase D (PKD), in mediating preconditioning in the rat heart. Isolated rat hearts (n=6/group) were subjected to either: (i) 36 min aerobic perfusion (control); (ii) 20 min aerobic perfusion plus 3 min no-flow ischemia, 3 min reperfusion, 5 min no-flow ischemia, 5 min reperfusion (ischemic preconditioning); (iii) 20 min aerobic perfusion plus 200 nmol/l phorbol 12-myristate 13-acetate (PMA) given as a substitute for ischemic preconditioning. The left ventricle then was excised, homogenized and PKD immunoprecipitated from the homogenate. Activity of the purified kinase was determined following bincubation with [γ32P]-ATP±syntide-2, a substrate for PKD. Significant PKD autophosphorylation and syntide-2 phosphorylation occurred in PMA-treated hearts, but not in control or preconditioned hearts. Additional studies confirmed that recovery of LVDP was greater and initiation of ischemic contracture and time-to-peak contracture were less, in ischemic preconditioned hearts compared with controls (P<0.05). Our results suggest that the early events that mediate ischemic preconditioning in the rat heart occur via a PKD-independent mechanism.

Design of highly parallel architecture with Alpha and Handel

We propose a bridge between two important parallel programming paradigms: data parallelism and communicating sequential processes (CSP). Data parallel pipelined architectures obtained with the Alpha language can be embedded in a control intensive application expressed in CSP-based Handel formalism. The interface is formally defined from the semantics of the languages Alpha and Handel. This work will ease the design of compute intensive applications on FPGAs.