Three parallel programming paradigms: Comparisons on an archetypal PDE computation

Three paradigms for distributed-memory parallel computation that free the application programmer from the details of message passing are compared for an archetypal structured scientific computation -- a nonlinear, structured-grid partial differential equation boundary value problem -- using the same algorithm on the same hardware. All of the paradigms -- parallel languages represented by the Portland Group's HPF, (semi-)automated serial-to-parallel source-to-source translation represented by CAP-Tools from the University of Greenwich, and parallel libraries represented by Argonne's PETSc -- are found to be easy to use for this problem class, and all are reasonably effective in exploiting concurrency after a short learning curve. The level of involvement required by the application programmer under any paradigm includes specification of the data partitioning, corresponding to a geometrically simple decomposition of the domain of the PDE. Programming in SPMD style for the PETSc library requires writing only the routines that discretize the PDE and its Jacobian, managing subdomain-to-processor mappings (affine global-to-local index mappings), and interfacing to library solver routines. Programming for HPF requires a complete sequential implementation of the same algorithm as a starting point, introduction of concurrency through subdomain blocking (a task similar to the index mapping), and modest experimentation with rewriting loops to elucidate to the compiler the latent concurrency. Programming with CAPTools involves feeding the same sequential implementation to the CAPTools interactive parallelization system, and guiding the source-to-source code transformation by responding to various queries about quantities knowable only at runtime. Results representative of "the state of the practice" for a scaled sequence of structured grid problems are given on three of the most important contemporary high-performance platforms: the IBM SP, the SGI Origin 2000, and the CRAYY T3E.

Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM

We present a dynamic distributed load balancing algorithm for parallel, adaptive Finite Element simulations in which we use preconditioned Conjugate Gradient solvers based on domain-decomposition. The load balancing is designed to maintain good partition aspect ratio and we show that cut size is not always the appropriate measure in load balancing. Furthermore, we attempt to answer the question why the aspect ratio of partitions plays an important role for certain solvers. We define and rate different kinds of aspect ratio and present a new center-based partitioning method of calculating the initial distribution which implicitly optimizes this measure. During the adaptive simulation, the load balancer calculates a balancing flow using different versions of the diffusion algorithm and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. Experimental results for Bramble's preconditioner and comparisons to state-of-the-art load balancers show the benefits of the construction.

Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.

Can density functional theory (DFT) be used as an aid to a deeper understanding of tandem mass spectrometric fragmentation pathways?

Prediction of tandem mass spectrometric (MS/MS) fragmentation for non-peptidic molecules based on structure is of immense interest to the mass spectrometrist. If a reliable approach to MS/MS prediction could be achieved its impact within the pharmaceutical industry could be immense. Many publications have stressed that the fragmentation of a molecular ion or protonated molecule is a complex process that depends on many parameters, making prediction difficult. Commercial prediction software relies on a collection of general heuristic rules of fragmentation, which involve cleaving every bond in the structure to produce a list of 'expected' masses which can be compared with the experimental data. These approaches do not take into account the thermodynamic or molecular orbital effects that impact on the molecule at the point of protonation which could influence the potential sites of bond cleavage based on the structural motif. A series of compounds have been studied by examining the experimentally derived high-resolution MS/MS data and comparing it with the in silico modelling of the neutral and protonated structures. The effect that protonation at specific sites can have on the bond lengths has also been determined. We have calculated the thermodynamically most stable protonated species and have observed how that information can help predict the cleavage site for that ion. The data have shown that this use of in silico techniques could be a possible way to predict MS/MS spectra. Copyright (C) 2009 John Wiley & Sons, Ltd.

C-H activations on a 1H-1,4-benzodiazepin-2(3H)-one template

Air stable benzodiazepine containing palladacycles were synthesized by a C-H activation reaction and studied by mass spectrometry and X-ray crystallography. Catalytic C-H functionalizations of 1-methyl-5-phenyl-1H-1,4-benzodiazepin-2(3H)-one with diphenyliodonium hexafluorophosphate led to a mixture, which included the starting material and the expected product 1-methyl-5-(2'-biphenyl)-1H-1,4-benzodiazepin-2(3H)-one. (C) 2008 Elsevier Ltd. All rights reserved.