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.

Domain decomposition using a 2-level correction scheme

The PHYSICA software was developed to enable multiphysics modelling allowing for interaction between Computational Fluid Dynamics (CFD) and Computational Solid Mechanics (CSM) and Computational Aeroacoustics (CAA). PHYSICA uses the finite volume method with 3-D unstructured meshes to enable the modelling of complex geometries. Many engineering applications involve significant computational time which needs to be reduced by means of a faster solution method or parallel and high performance algorithms. It is well known that multigrid methods serve as a fast iterative scheme for linear and nonlinear diffusion problems. This papers attempts to address two major issues of this iterative solver, including parallelisation of multigrid methods and their applications to time dependent multiscale problems.

On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

A hybrid Laplace transform/finite difference boundary element method for diffusion problems

The solution process for diffusion problems usually involves the time development separately from the space solution. A finite difference algorithm in time requires a sequential time development in which all previous values must be determined prior to the current value. The Stehfest Laplace transform algorithm, however, allows time solutions without the knowledge of prior values. It is of interest to be able to develop a time-domain decomposition suitable for implementation in a parallel environment. One such possibility is to use the Laplace transform to develop coarse-grained solutions which act as the initial values for a set of fine-grained solutions. The independence of the Laplace transform solutions means that we do indeed have a time-domain decomposition process. Any suitable time solver can be used for the fine-grained solution. To illustrate the technique we shall use an Euler solver in time together with the dual reciprocity boundary element method for the space solution

A vertex-based finite volume method applied to non-linear material problems in computational solid mechanics

A vertex-based finite volume (FV) method is presented for the computational solution of quasi-static solid mechanics problems involving material non-linearity and infinitesimal strains. The problems are analysed numerically with fully unstructured meshes that consist of a variety of two- and threedimensional element types. A detailed comparison between the vertex-based FV and the standard Galerkin FE methods is provided with regard to discretization, solution accuracy and computational efficiency. For some problem classes a direct equivalence of the two methods is demonstrated, both theoretically and numerically. However, for other problems some interesting advantages and disadvantages of the FV formulation over the Galerkin FE method are highlighted.