Computer aided parallelisation tools (CAPTools) — conceptual overview and performance on the parallelisation of structured mesh codes

Computer Aided Parallelisation Tools (CAPTools) is a toolkit designed to automate as much as possible of the process of parallelising scalar FORTRAN 77 codes. The toolkit combines a very powerful dependence analysis together with user supplied knowledge to build an extremely comprehensive and accurate dependence graph. The initial version has been targeted at structured mesh computational mechanics codes (eg. heat transfer, Computational Fluid Dynamics (CFD)) and the associated simple mesh decomposition paradigm is utilised in the automatic code partition, execution control mask generation and communication call insertion. In this, the first of a series of papers [1–3] the authors discuss the parallelisations of a number of case study codes showing how the various component tools may be used to develop a highly efficient parallel implementation in a few hours or days. The details of the parallelisation of the TEAMKE1 CFD code are described together with the results of three other numerical codes. The resulting parallel implementations are then tested on workstation clusters using PVM and an i860-based parallel system showing efficiencies well over 80%.

Automatic and effective multi-dimensional parallelisation of structured mesh based codes

The most common parallelisation strategy for many Computational Mechanics (CM) (typified by Computational Fluid Dynamics (CFD) applications) which use structured meshes, involves a 1D partition based upon slabs of cells. However, many CFD codes employ pipeline operations in their solution procedure. For parallelised versions of such codes to scale well they must employ two (or more) dimensional partitions. This paper describes an algorithmic approach to the multi-dimensional mesh partitioning in code parallelisation, its implementation in a toolkit for almost automatically transforming scalar codes to parallel form, and its testing on a range of ‘real-world’ FORTRAN codes. The concept of multi-dimensional partitioning is straightforward, but non-trivial to represent as a sufficiently generic algorithm so that it can be embedded in a code transformation tool. The results of the tests on fine real-world codes demonstrate clear improvements in parallel performance and scalability (over a 1D partition). This is matched by a huge reduction in the time required to develop the parallel versions when hand coded – from weeks/months down to hours/days.

Dynamic mesh partitioning and load-balancing for parallel computational mechanics codes

In this Chapter we discuss the load-balancing issues arising in parallel mesh based computational mechanics codes for which the processor loading changes during the run. We briefly touch on geometric repartitioning ideas and then focus on different ways of using a graph both to solve the load-balancing problem and the optimisation problem, both locally and globally. We also briefly discuss whether repartitioning is always valid. Sample illustrative results are presented and we conclude that repartitioning is an attractive option if the load changes are not too dramatic and that there is a certain trade-off between partition quality and volume of data that the underlying application needs to migrate.

On efficient data integrity and data origin authentication for wireless sensor networks utilising block cipher design techniques

Analysis of the generic attacks and countermeasures for block cipher based message authentication code algorithms (MAC) in sensor applications is undertaken; the conclusions are used in the design of two new MAC constructs Quicker Block Chaining MAC1 (QBC-MAC1) and Quicker Block Chaining MAC2 (QBC-MAC2). Using software simulation we show that our new constructs point to improvements in usage of CPU instruction clock cycle and energy requirement when benchmarked against the de facto Cipher Block Chaining MAC (CBC-MAC) based construct used in the TinySec security protocol for wireless sensor networks.

A scalable strategy for the parallelization of multiphysics unstructured mesh-iterative codes on distributed-memory systems

Realizing scalable performance on high performance computing systems is not straightforward for single-phenomenon codes (such as computational fluid dynamics [CFD]). This task is magnified considerably when the target software involves the interactions of a range of phenomena that have distinctive solution procedures involving different discretization methods. The problems of addressing the key issues of retaining data integrity and the ordering of the calculation procedures are significant. A strategy for parallelizing this multiphysics family of codes is described for software exploiting finite-volume discretization methods on unstructured meshes using iterative solution procedures. A mesh partitioning-based SPMD approach is used. However, since different variables use distinct discretization schemes, this means that distinct partitions are required; techniques for addressing this issue are described using the mesh-partitioning tool, JOSTLE. In this contribution, the strategy is tested for a variety of test cases under a wide range of conditions (e.g., problem size, number of processors, asynchronous / synchronous communications, etc.) using a variety of strategies for mapping the mesh partition onto the processor topology.

An automatable generic strategy for dynamic load balancing in parallel structured mesh CFD codes

Parallel computing is now widely used in numerical simulation, particularly for application codes based on finite difference and finite element methods. A popular and successful technique employed to parallelize such codes onto large distributed memory systems is to partition the mesh into sub-domains that are then allocated to processors. The code then executes in parallel, using the SPMD methodology, with message passing for inter-processor interactions. In order to improve the parallel efficiency of an imbalanced structured mesh CFD code, a new dynamic load balancing (DLB) strategy has been developed in which the processor partition range limits of just one of the partitioned dimensions uses non-coincidental limits, as opposed to coincidental limits. The ‘local’ partition limit change allows greater flexibility in obtaining a balanced load distribution, as the workload increase, or decrease, on a processor is no longer restricted by the ‘global’ (coincidental) limit change. The automatic implementation of this generic DLB strategy within an existing parallel code is presented in this chapter, along with some preliminary results.

Parallelisation of electromagnetic simulation codes

In this paper results obtained from the parallelisation of existing 3D electromagnetic Finite Element codes within the ESPRIT HPCN project PARTEL are presented. The parallelisation procedure, based on the Bulk Synchronous Parallel approach, is outlined and the encouraging results obtained in terms of speed-up on some industrially significant test cases are described and discussed.

Results of parallelisation of existing electromagnetic finite codes on some different parallel architectures

In this paper the results obtained from the parallelisation of some 3D industrial electromagnetic Finite Element codes within the ESPRIT Europort 2 project PARTEL are presented. The basic guidelines for the parallelisation procedure, based on the Bulk Synchronous Parallel approach, are presented and the encouraging results obtained in terms of speed-up on some selected test cases of practical design significance are outlined and discussed.

On the coupling of Navier–Stokes and linearised Euler equations for aeroacoustic simulation

Aerodynamic generation of sound is governed by the Navier–Stokes equations while acoustic propagation in a non-uniform medium is effectively described by the linearised Euler equations. Different numerical schemes are required for the efficient solution of these two sets of equations, and therefore, coupling techniques become an essential issue. Two types of one-way coupling between the flow solver and the acoustic solver are discussed: (a) for aerodynamic sound generated at solid surfaces, and (b) in the free stream. Test results indicate how the coupling achieves the necessary accuracy so that Computational Fluid Dynamics codes can be used in aeroacoustic simulations.

CAPLib - A 'thin layer' message passing library to support computational mechanics codes on distributed memory parallel systems

The Computer Aided Parallelisation Tools (CAPTools) [Ierotheou, C, Johnson SP, Cross M, Leggett PF, Computer aided parallelisation tools (CAPTools)-conceptual overview and performance on the parallelisation of structured mesh codes, Parallel Computing, 1996;22:163±195] is a set of interactive tools aimed to provide automatic parallelisation of serial FORTRAN Computational Mechanics (CM) programs. CAPTools analyses the user's serial code and then through stages of array partitioning, mask and communication calculation, generates parallel SPMD (Single Program Multiple Data) messages passing FORTRAN. The parallel code generated by CAPTools contains calls to a collection of routines that form the CAPTools communications Library (CAPLib). The library provides a portable layer and user friendly abstraction over the underlying parallel environment. CAPLib contains optimised message passing routines for data exchange between parallel processes and other utility routines for parallel execution control, initialisation and debugging. By compiling and linking with different implementations of the library, the user is able to run on many different parallel environments. Even with today's parallel systems the concept of a single version of a parallel application code is more of an aspiration than a reality. However for CM codes the data partitioning SPMD paradigm requires a relatively small set of message-passing communication calls. This set can be implemented as an intermediate `thin layer' library of message-passing calls that enables the parallel code (especially that generated automatically by a parallelisation tool such as CAPTools) to be as generic as possible. CAPLib is just such a `thin layer' message passing library that supports parallel CM codes, by mapping generic calls onto machine specific libraries (such as CRAY SHMEM) and portable general purpose libraries (such as PVM an MPI). This paper describe CAPLib together with its three perceived advantages over other routes: - as a high level abstraction, it is both easy to understand (especially when generated automatically by tools) and to implement by hand, for the CM community (who are not generally parallel computing specialists); - the one parallel version of the application code is truly generic and portable; - the parallel application can readily utilise whatever message passing libraries on a given machine yield optimum performance.

Multiphase mesh partitioning for parallel computational mechanics codes

We consider the load-balancing problems which arise from parallel scientific codes containing multiple computational phases, or loops over subsets of the data, which are separated by global synchronisation points. We motivate, derive and describe the implementation of an approach which we refer to as the multiphase mesh partitioning strategy to address such issues. The technique is tested on example meshes containing multiple computational phases and it is demonstrated that our method can achieve high quality partitions where a standard mesh partitioning approach fails.

The semi-automatic parallelisation of scientific application codes using a computer aided parallelisation toolkit

The shared-memory programming model can be an effective way to achieve parallelism on shared memory parallel computers. Historically however, the lack of a programming standard using directives and the limited scalability have affected its take-up. Recent advances in hardware and software technologies have resulted in improvements to both the performance of parallel programs with compiler directives and the issue of portability with the introduction of OpenMP. In this study, the Computer Aided Parallelisation Toolkit has been extended to automatically generate OpenMP-based parallel programs with nominal user assistance. We categorize the different loop types and show how efficient directives can be placed using the toolkit's in-depth interprocedural analysis. Examples are taken from the NAS parallel benchmarks and a number of real-world application codes. This demonstrates the great potential of using the toolkit to quickly parallelise serial programs as well as the good performance achievable on up to 300 processors for hybrid message passing-directive parallelisations.

Investigation into the performance of turbulence models for fluid flow and heat transfer phenomena in electronic applications

Heat is extracted away from an electronic package by convection, conduction, and/or radiation. The amount of heat extracted by forced convection using air is highly dependent on the characteristics of the airflow around the package which includes its velocity and direction. Turbulence in the air is also important and is required to be modeled accurately in thermal design codes that use computational fluid dynamics (CFD). During air cooling the flow can be classified as laminar, transitional, or turbulent. In electronics systems, the flow around the packages is usually in the transition region, which lies between laminar and turbulent flow. This requires a low-Reynolds number numerical model to fully capture the impact of turbulence on the fluid flow calculations. This paper provides comparisons between a number of turbulence models with experimental data. These models included the distance from the nearest wall and the local velocity (LVEL), Wolfshtein, Norris and Reynolds, k-ε, k-ω, shear-stress transport (SST), and kε/kl models. Results show that in terms of the fluid flow calculations most of the models capture the difficult wake recirculation region behind the package reasonably well, although for packages whose heights cause a high degree of recirculation behind the package the SST model appears to struggle. The paper also demonstrates the sensitivity of the models to changes in the mesh density; this study is aimed specifically at thermal design engineers as mesh independent simulations are rarely conducted in an industrial environment.

Unstructured staggered mesh methods for fluid flow, heat transfer and phase change

Unstructured grid meshes used in most commercial CFD codes inevitably adopt collocated variable solution schemes. These schemes have several shortcomings, mainly due to the interpolation of the pressure gradient, that lead to slow convergence. In this publication we show how it is possible to use a much more stable staggered mesh arrangement in an unstructured code. Several alternative groupings of variables are investigated in a search for the optimum scheme.

Airborne transport of Saharan dust to the Mediterranean and to the Atlantic

The Sahara desert is a significant source of particulate pollution not only to the Mediterranean region, but also to the Atlantic and beyond. In this paper, PM 10 exceedences recorded in the UK and the island of Crete are studied and their source investigated, using Lagrangian Particle Dispersion (LPD) methods. Forward and inverse simulations identify Saharan dust storms as the primary source of these episodes. The methodology used allows comparison between this primary source and other possible candidates, for example large forest fires or volcanic eruptions. Two LPD models are used in the simulations, namely the open source code FLEXPART and the proprietary code HYSPLIT. Driven by the same meteorological fields (the ECMWF MARS archive and the PSU/NCAR Mesoscale model, known as MM5) the codes produce similar, but not identical predictions. This inter-model comparison enables a critical assessment of the physical modelling assumptions employed in each code, plus the influence of boundary conditions and solution grid density. The outputs, in the form of particle concentrations evolving in time, are compared against satellite images and receptor data from multiple ground-based sites. Quantitative comparisons are good, especially in predicting the time of arrival of the dust plume in a particular location.