Energy consumption and energy efficiency are important issues in hardware design as well as in software production. The general aim is to have an efficient energy behavior of the processor while executing the software code in reasonable time. This work investigates the energy efficiency of three Intel processors of different generations by considering a multithreaded execution of two complex numerical solution methods for timedependent partial differential equations (PDEs). The resulting execution time and energy consumption are investigated and analyzed and the energy delay product is computed to evaluate and compare the energy efficiency of the different processors.

Abstract This article provides an enhanced parallelization of the WSM7 microphysics scheme for the Weather Research and Forecasting Model (WRF). The parallelization is designed to maximize the utilization of a heterogeneous computing system consisting of CPUs, GPUs or both. Therefore the reference implementation of the WSM7 scheme is re-implemented for the heterogeneous execution model. For each time step, a dynamic load distribution is introduced which balances the computational load between the two components aiming for an overall minimum execution time. The evaluation of the parallelized implementation is done for a specific weather situation. Specifically, the precipitation of the low-pressure zone “Bernd” from July 2021 is simulated using an Intel Core i7-7700 CPU and a NVIDIA GTX 1070 GPU. The results show a speedup of up to 28.51 for the GPU version in comparison with the reference implementation. The heterogeneous dynamic load balancing increases the speedup achieved even further by introducing a distribution factor that is updated for each time step.

The combination of different parallel programming environments can be used to exploit all heterogeneous levels of parallel hardware, which might lead to an optimization of application programs. An exemplary combination is the use of the Message Passing Interface (MPI) together with vectorization based on the Advanced vector extensions (AVX), which is investigated in this article. A special emphasis lies on MPI data orderings and their influence on AVX vectorization strategies. The Jacobi method is used as case study for which several parallel program version have been implemented and analyzed.

Abstract Scientific application codes are often long-running time- and energy-consuming parallel codes, and the tuning of these methods towards the characteristics of a specific hardware is essential for a good performance. However, since scientific software is often developed over many years, the application software usually survives several hardware generations, which might make a re-tuning of the existing codes necessary. To simplify the tuning process, it would be beneficial to have software with inherent tuning possibilities. In this article, we explore the possibilities of tuning methods for time-step-based applications. Two different time-step-based application classes are considered, which are solution methods for ordinary differential equations and particle simulation methods. The investigation comprises a broad range of tuning possibilities, starting from the choice of algorithms, the parallel programming model, static implementation variants, input characteristics as well as hardware parameters for parallel execution. An experimental investigation shows the different characteristics of the application classes on different multicore systems. The results show that a combination of offline and online tuning leads to good tuning results. However, due to the different input characteristics of the two application classes, regular versus irregular, different tuning aspects are most essential.

Vectorization is a key technology to increase the performance and efficiency of computer systems, however the performance increase usually strongly depends on the specific application program. In this article, we introduce SIMD program versions of a Coulomb solver based on manual vectorization as well as automatic vectorization using the Intel C Compiler. The implementation uses the latest Advanced Vector Extensions with 512-bit vector size (AVX-512). The comparison of the performance results visualizes the reduction of the execution time achieved by the manual vectorization as well as the automatic vectorization compared to the code without vectorization. The automatic vectorization achieves a good speed up that should be sufficient for most use cases. However, we also show that the manual vectorization is able to outperform the automatic vectorization. The control over the instructions used by the manual vectorization can reduce the amount of expensive vector reduction operations which are introduced by the automatic vectorization.

Summary Scheduling is a widely used method in parallel computing, which assigns tasks to compute resources of a parallel environments. In this article, we consider independent parallel tasks to be scheduled onto a heterogeneous execution platform consisting of a set of multicores of different architecture. Each parallel task has an internal potential parallelism which allows a parallel execution on any multicore processors. However, the execution time may differ due a different computation speed of different multicores. In this article, we propose a new search‐based scheduling algorithm Heterogeneous Parallel task scheduling based on A* (called HP*) to solve the problem of scheduling independent parallel tasks onto heterogeneous multicore platforms. Specifically, we propose a heuristic cost function needed for an informed search. Also, three pruning techniques are proposed, which are shown to significantly reduce the search space of HP*. Performance measurements on a heterogeneous platform are performed and the results of HP* are compared to scheduling results of other popular scheduling methods. The performance results with benchmark tasks from the SPLASH‐3 benchmark suite demonstrate the good scheduling results and the improvements achieved by HP*.

Runge-Kutta (RK) methods are popular and well-known methods for simulations in scientific computing based on ordinary differential equations (ODEs). RK-based simulations can stem from space-discretized time-dependent partial differential equations (PDEs), which can model a large variety of phenomena in natural science or engineering. This article investigates several multithreaded versions of RK methods and studies their performance and energy consumption on a recent multicore processor. The emphasis of the analysis is on the performance and energy behavior using dynamic voltage and frequency scaling (DVFS) and the modeling of the time and energy behavior based on power models.

Summary The efficient execution of parallel programs with respect to execution time and energy consumption is a major concern, and often, scheduling methods are used to achieve a good performance. In this article, we consider the problem of scheduling a set of independent tasks on a parallel system with homogeneous execution units providing frequency scaling. The set of tasks has the property that the tasks exhibit a task‐specific inhomogeneous and non‐linear behavior of their specific time‐energy relation. In addition, it is assumed that execution time and energy consumption behave in a non‐linear manner with respect to frequency scaling. For the assignment of these tasks to execution units, we propose a scheduling selection process combining scheduling algorithms, which determine a task assignment, with a subsequent selection of frequency scaling, which we call schedule execution modes. This process builds a rich set of alternative schedule execution modes from which efficient (or Pareto‐optimal) schedule execution modes can be selected. Experiments are done for the SPEC CPU benchmarks. Experimental results illustrate that the enriched scheduling process leads to task assignments resulting in an efficient execution on DVFS processors.

The energy efficiency of program executions is an active research field in recent years and the influence of different programming styles on the energy consumption is part of the research effort.In this article, we concentrate on SIMD programming and study the effect of vectorization on performance as well as on power and energy consumption.Especially, SIMD programs using AVX instructions are considered and the focus is on the AVX load and store instruction set.Several semantically similar but different load and store instructions are selected and are used to build different program versions of for the same algorithm.As example application, the Gaussian elimination has been chosen due to its interesting feature of using arrays of varying length in each factorization step.Five different SIMD program versions of the Gaussian elimination have been implemented, each of which uses different load and store instructions.Performance, power, and energy measurements for all program versions are provided for the Intel Sandy Bridge, Haswell and Skylake architectures and the results are discussed and analyzed.

Due to the ever changing characteristics of the newly provided hardware, there is the permanent requirement of designing and re-designing software adequately to meet the basic hardware conditions.Especially for well-established software, easy portability of the functional as well as the non-functional properties, such as runtime performance or energy efficiency, would be beneficial, so that the software adapts automatically to the given hardware conditions.In this article, we explore the autotuning potential of several methods from scientific computing.In particular, we consider time-stepping methods and investigate the effect of relevant tuning parameters of the different methods.We also address the question, whether offline or online autotuning approaches are appropriate for the specific method.The methods from scientific computing considered are particle simulation methods, solution methods for differential equations, as well as sparse matrix computations.

Particle simulations are popular methods in computational science in areas, such as biology, chemistry, or astrophysics, in which the interaction of particles plays a major role. Efficient implementations of particle simulations often exploit a separation of computations by a cutoff radius. The pairwise interactions between particles are then computed only within the cutoff radius while interactions beyond the cutoff radius might be neglected or computed approximately. Thus, the efficient implementation of the calculations within the cutoff radius can be crucial for an overall efficiency. In this article, we study these computationally intensive inner cutoff radius calculations and propose a portable parallel implementation on a hybrid CPU/GPU architecture. Especially, we have chosen particle methods from the ScaFaCoS library and have implemented a parallel version of the cutoff-based algorithm in OpenCL. Performance results are shown for two different solvers of the ScaFaCoS library. The influences of the particle distribution and the utilized hardware are investigated.

Runge-Kutta methods are widely used and popular solutions method for scientific simulations based on differential equations and, thus, their efficient execution is crucial for many applications. Today, also the energy consumption is getting more and more important for high performance computing. In this article, we investigate the performance and the energy consumption of Runge-Kutta methods solving systems of ordinary differential equations on recent Intel processors. Our specific interest is the study of different program versions of multithreaded Runge-Kutta methods which result from loop transformations within the nested loops over stage vectors and systems sizes. Four program versions of the Runge-Kutta method DOPRI5 are chosen and are applied to systems of ordinary differential equations with different workload. Experiments have been performed for different numbers of threads and the performance, power and energy consumption is reported and analyzed.

Time-stepping simulation methods offer potential for self-adaptivity, since the first time steps of the simulation can be used to explore the hardware characteristics and measure which of several available implementation variants leads to a good performance and energy consumption on the given hardware platform. The version with the best performance or the smallest energy consumption can then be used for the remaining time steps. However, the number of variants to test may be quite large and different simulation methods may require different approaches for self-adaptivity. In this article, we explore the potential for self-adaptivity of several methods from scientific computing. In particular, we consider particle simulation methods, solution methods for differential equations, as well as sparse matrix computations and explore the potential for self-adaptivity of these methods, considering both performance and energy consumption as target function.

Performance analysis in high performance computing (HPC) has traditionally focused on improving application programs, for example, by decreasing the overall runtime or increasing the throughput of floating point operations. However, the same approaches might also be used to influence the energy behavior. Since the increasing energy consumption of HPC platforms is gaining more and more attention, the identification of applications and platforms for which energy and performance measurement lead to differing results is of great importance. In this article, we analyze the energy and performance behavior of particle solvers from the ScaFaCoS library. Four different criteria are investigated with respect to their influence on the energy consumption and achieved performance. These criteria are the solution method chosen, the parameters of the solution method, the degree of parallelism, and the parameters of the hardware platform.

Summary The article proposes a fine‐grained all‐to‐all communication operation that can implement flexible data redistribution patterns of irregular applications, such as particle codes. The flexibility is achieved by user‐defined distribution functions, which are used to specify how data elements are to be redistributed among parallel processes on a distributed memory platform. The usage is illustrated for a particle data redistribution step of a grid‐based particle code in which the destination processes for particles are calculated from the particle positions by a specific distribution function. Additionally, the fine‐grained all‐to‐all communication operation proposed allows the duplication and modification of data elements during the data redistribution. This functionality is useful for automatically creating ghost particles for the domain decomposition of the particle code during the particle data redistribution step. The interface of the fine‐grained all‐to‐all communication operation is described and several algorithms for implementing the operation on top of existing MPI operations are presented. Performance results on an IBM Blue Gene/Q platform demonstrate the performance of the communication operation proposed with synthetic benchmark data as well as with a parallel particle code.

These workshops were organized by members of the Nesus Cost Action IC 1305: Network for Sustainable Ultrascale Computing, which is a follow-up of COST Actions IC0804 and IC0805 1. The goal of the NESUS Action is to establish an open European research network targeting sustainable solutions for ultrascale computing aiming at cross fertilization among HPC, large-scale distributed systems, and big data management. This network aims at contributing to glue disparate researchers working across different areas and provide a meeting ground for researchers in these separate areas to exchange ideas, to identify synergies, and to pursue common activities in research topics such as sustainable software solutions (applications and system software stack), data management, energy efficiency, and resilience. The selected papers cover very important scientific issues encountered nowadays such as the following: CPU/GPU execution, system-on-chip programming, parallel algorithms taking into account various constraints (energy, communication, etc.), programming models, and so on. We really hope that the reader will enjoy this high-quality issue, and we are sure that she/he will find it highly relevant to the state-of-the-art of today's heterogeneous and parallel computing.

SUMMARY Because of environmental and monetary concerns, it is increasingly important to reduce the energy consumption in all areas, including parallel and high performance computing. In this article, we propose an approach to reduce the energy consumption needed for the execution of a set of tasks computed in parallel in a fork‐join fashion. The approach consists of an analytical model for the energy consumption of a parallel computation in fork‐join form on dynamic voltage frequency scaling processors, a theoretical specification of an energy‐optimal frequency‐scaled state, and the energy minimization by computing optimal scaling factors. For larger numbers of tasks, the approach is extended by scheduling algorithms, which exploit the analytical result and aim at a reduction of the energy. Energy measurements of a complex numerical method and the SPEC CPU2006 benchmarks as well as simulations for a large number of randomly generated tasks illustrate and validate the energy modeling, the minimization, and the scheduling results. Copyright © 2014 John Wiley & Sons, Ltd.

This article investigates two particle data redistribution methods for the coupling of application-independent solvers for long range interactions with a particle dynamics simulation. The solvers rely on their own particle data processing techniques and domain decomposition schemes, but are implemented within a single parallel software library with a unique interface. Thus, efficient data reordering and redistribution methods are required for the data transfer between an application and the library interface as well as between the library interface and a solver. The first particle data redistribution method hides all data reordering and redistribution inside the library and restores the original particle order and distribution. The second method uses the solver-specific particle order and distribution for the particle dynamics simulation to reduce the communication amount of particle redistribution steps. Both methods and their effects on the different program components of a parallel particle code are described. Performance results on the parallel computing cluster JuRoPA and the IBM Blue Gene/Q system Juqueen are presented to demonstrate the performance improvements achieved within a particle dynamics simulation application.

The article presents two efficient in-place algorithms for the symmetric all-to-all exchange of the MPI_Alltoallv operation. The first algorithm performs a series of pairwise data exchanges similar to the existing algorithm used by MPICH, but with fewer consecutive communication steps and idle processes. The second algorithm uses hierarchical sets of processes that lead to a better locality of communication. Exploiting additionally available memory for performance improvements is described. Performance results for an InfiniBand cluster and an IBM Blue Gene/Q system demonstrate the performance benefits of the algorithms within a generic benchmark program and an FFT application.

In this article, we use an analytical energy model based on frequency scaling to model the energy consumption of tasks in a fork-join pattern of parallelism. In particular, tasks that may be executed concurrently to each other are considered, and the resulting energy consumption for different processor assignments is investigated. Frequency scaling factors that lead to a minimum energy consumption are derived and used in task-based scheduling algorithms. An experimental evaluation provides simulations for a large number of randomly generated task sets as well as energy measurements on a Intel Sandy Bridge architecture using a complex application from numerical analysis.

Many particle simulation codes use interaction lists to store interacting particles. Depending on the physical parameters of the simulations those interaction lists may occupy a large amount of physical memory, which may limit the number of particles of the simulation. This article discusses several methods that try to reduce the size of interaction lists while maintaining the number of particle interactions per second or even increase it. Different techniques are discussed for a parallel shared memory algorithm on multicore architectures. On those architectures, the memory bandwidth is shared by multiple cores. Since the interaction list is a large shared data structure, it cannot be stored in CPU caches and has to be streamed into the processor several times. A reduction of the size of the interaction list will therefore reduce the number of elements to be reloaded resulting in more efficient implementations.

Parallel sorting methods for distributed memory systems often use partitioning algorithms to prepare the redistribution of data items. This article proposes a partitioning algorithm that calculates a redistribution specified by the number of data items to be finally located on each process. This partitioning algorithm can also be used for data items with weights, which might express a computational load to be expected, and to produce a redistribution with an individual accumulated weight of data items specified for each process. Another important feature is that data sets with duplicated data keys can be handled. Parallel sorting with those properties is often needed for parallel scientific application codes, such as particle simulations, in which the dynamics of the simulated system may destroy locality and load balance required for an efficient computation. It is applied to random sample data and to a particle simulation code requiring a sorting. Performance results have been obtained on an IBM Blue Gene/P platform with up to 32768 cores. The results show that the proposed parallel sorting method performs well in comparison to other existing algorithms.

Modular parallel applications can be structured by parallel tasks that implement the modules. The dependence structure of such parallel applications gives rise to a scheduling problem, which is determined either statically at compile-time, e.g. by using a suitable compiler tool, or dynamically at runtime. In this article, we present a semi-dynamic execution scheme for applications structured by parallel tasks. This execution scheme combines a statically computed schedule with a dynamic load balancing that can adapt the schedule at runtime of the application. In this way, it is possible to reduce load imbalances between processor groups that may exist in the static schedule resulting from platform heterogeneity or from an imprecise cost prediction. Experimental results for several scientific applications show that the semi-dynamic execution scheme leads to lower execution times compared to a static execution on a tightly coupled heterogeneous platform.

Abstract Programming with parallel tasks leads to task graphs with dependencies representing a parallel program. Scheduling algorithms are employed to find an efficient execution order of the parallel tasks. A large variety of scheduling algorithms exist, including layer‐based scheduling algorithms for homogeneous target platforms that build consecutive layers of independent parallel tasks and schedule each layer separately. Although these scheduling algorithms provide good results in terms of scheduling algorithm runtime and schedule execution time, the resulting schedules leave room for optimization. This article proposes an optimization for arbitrary layer‐based scheduling algorithms, which is called Move‐blocks algorithm. Given a layer‐based schedule of the parallel tasks, this algorithm moves blocks of parallel tasks into preceding layers in order to reduce the overall execution time of a task‐based application. Suitable blocks of parallel tasks are identified by the algorithm Find‐blocks, which is employed together with the Move‐blocks algorithm. The algorithm Move‐blocks is applied to four well‐known scheduling algorithms. A detailed evaluation for a wide range of test cases is given. Copyright © 2010 John Wiley & Sons, Ltd.

Welcome to the 10th IEEE International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC-09), held on 29 May 2009 in Rome, Italy, in conjunction with the 23rd IEEE Int. Parallel and Distributed Processing Symposium (IPDPS 2009).

The efficient scheduling of large mixed parallel applications is challenging. Most existing algorithms utilize scheduling heuristics and approximation algorithms to determine a good schedule as basis for an efficient execution in large scale scientific computing. This paper concentrates on the scheduling of mixed parallel applications represented by task graphs with parallel tasks and precedence constraints between them. Layer-based scheduling algorithms for homogeneous target platforms are improved by adding a move-blocks phase that further reduces the resulting parallel runtime.The layer-based scheduling approach is described and the move-blocks algorithm is introduced in detail.The move-blocks extension provides better scheduling results for small as well as for large problems but has only a small increase in runtime.This is shown by a comparison of the modified and the original algorithms over a wide range of test cases.

In this article, we address the problem of modularizing legacy applications with monolithic structure, primarily focusing on business software written in an object-oriented programming language. We introduce theTransFormr toolkit that guides the developer through the entire incremental transformation process. It is the goal of the transformation to separate the original software into several independent replaceable components to support the migration of legacy code to new hardware or to integrate legacy components into modern enterprise applications. We show the effectiveness of our approach by demonstrating a pattern-based transformation of classes in a case study.

In this paper, we explore the use of hierarchically structured multiprocessor tasks (M-tasks) for programming multi-core cluster systems.These systems often have hierarchically structured interconnection networks combining different computing resources, starting with the interconnect within multi-core processors up to the interconnection network combining nodes of the cluster or supercomputer. M-task programs can support the effective use of the computing resources by adapting the task structure of the program to the hierarchical organization of the cluster system and by exploiting the available data parallelism within the M-tasks. In particular, we consider different mapping algorithms for M-tasks and investigate the resulting efficiency and scalability. We present experimental results for different application programs and different multi-core systems.

Task pools can be used to achieve the dynamic load balancing that is required for an efficient parallel implementation of irregular applications. However, the performance strongly depends on a task pool implementation that is well suited for the specific application. This paper introduces an adaptive task pool implementation that enables a stepwise transition between the common strategies of central and distributed task pools. The influence of the task size on the parallel performance is investigated and it is shown that the adaptive implementation provides the flexibility to adapt to different situations. Performance results from benchmark programs and from an irregular application for anomalous diffusion simulation are presented to demonstrate the need for an adaptive strategy. It is shown that profiling information about the overhead of the task pool implementation can be used to determine an optimal task pool strategy.

Many large application programs suffer from a bad utilization of cache and memory hierarchy. Known transformation techniques change loop structures and/or data layout in order to improve the performance. However, those techniques are usually adapted to either regular or irregular computations. In this paper, we investigate a combination of transformations suitable for algorithms with both irregular and regular features. The transformations are composed of computational loop reordering and data storage reorderings. We show how the different transformations interact in terms of cache utilization. Experiments on different clusters show performance gains for the sequential as well as for the parallel version.

In this article, we investigate how the distribution of dense matrices in a cluster of multi-core systems affects the performance of linear algebra codes. These codes have the property of communicating only within rows or columns of a processor grid. Especially, we consider orthogonalization methods like the Gram-Schmidt orthogonalization. Experiments show the performance for different topology aware mappings on two different multi-core clusters connected with InfiniBand. We show how the performance is influenced by these mappings.

Parallel programming models based on a mixture of task and data parallelism have shown to be successful in addressing the increasing communication overhead of distributed memory platforms with a large number of processors. In these models, an application is decomposed into a set of parallel tasks that can run on an arbitrary number of processors. The communication between different tasks is allowed only at the start and the end of a task, thus limiting the possible communication patterns and the potential granularity of the tasks. In this paper, we consider an extended parallel programming model that additionally supports communication between running parallel tasks. We describe a specification language for applications in the new programming model and propose a transformation framework for a step-wise derivation of an executable message passing program from the specification language. The advantages of the approach are demonstrated for solution methods for ordinary differential equations.

Abstract In this paper, we present an adaptive extension library that combines the advantage of using a portable MPI library with the ability to optimize the performance of specific collective communication operations. The extension library is built on top of MPI and can be used with any MPI library. Using the extension library, performance improvements can be achieved by an orthogonal organization of the processors in 2D or 3D meshes and by decomposing the collective communication operations into several consecutive phases of MPI communication. Additional point‐to‐point‐based algorithms are also provided. The extension library works in two steps, an a priori configuration phase detecting possible improvements for implementing collective communication for the MPI library used and an execution phase selecting a better implementation during execution time. This allows an adaptation of the performance of MPI programs to a specific execution platform and communication situation. The experimental evaluation shows that significant performance improvements can be obtained for different MPI libraries by using the library extension for collective MPI communication operations in isolation as well as in the context of application programs. Copyright © 2007 John Wiley & Sons, Ltd.

In this article we tackle the problem of scheduling a dynamically generated DAG of multi-processor tasks (M-tasks). At first, we outline the need of such a scheduling approach in the context of TGrid. TGrid is an M-task runtime system for heterogeneous clusters. Then, we propose a dynamic scheduling algorithm called reuse processors algorithm (RePA). The main objective of RePA is to reduce the communication and redistribution costs by trying to map child tasks to processors which are assigned to parent tasks (reuse processors). The algorithm is implemented using the SimGrid toolkit and is evaluated by comparing the makespan of the schedules produced by RePA and M-HEFT.

The raising need for e-government applications leads to many new approaches in this sector. To fulfill the requirement for a flexible government-to-government (G2G) software system being adaptable for the usage in many sectors of e-government applications we introduce the reference architecture for e-government (RAfEG) in this paper. The key features of the system are flexibility, security, adaptability and interoperability between authorities. The efficient usage of heterogeneous systems and heterogeneous hardware platforms, respectively, allows the execution of large interactive applications in e-government. Because security is a critical issue in e-government applications our solution uses different types of authentication and authorization methods and also supports secure communication between the interoperating heterogeneous systems. Due to the fact that the electronically supported execution of government procedures is the main aspect of the RAfEG system, an approach where these procedures are modeled as workflows and executed by an underlying workflow management system (WfMS) is the solution we present in this paper. Although many e-government applications exist at present, the RAfEG system is a new approach because it is able to cope with a wide range of internal official procedures and also highly adaptable to new procedures within e-government.

In this article we introduce a grid runtime system called TGrid which is designed to run hierarchically structured task-parallel programs on heterogenous environments and can also be used for common component-based grid programming. TGrid is built on top of a location-aware communication layer which enables the runtime system to cluster grid nodes. As a result, the component scheduler assigns a multi-processor task to a set of processors taking into account the spatial locality within the available processors. The multi-processor task directly benefits from having less network overhead and thus, the overall runtime of a grid-enabled multi-processor program is reduced

MPI provides a portable message passing interface for many parallel execution platforms but may lead to inefficiencies for some platforms and applications. In this article, we show that the performance of both, standard libraries and vendor-specific libraries, can be improved by an orthogonal organization of the processors in 2D or 3D meshes and by decomposing the collective communication operations into several phases. We describe an adaptive approach with a configuration phase to determine for a specific execution platform and a specific MPI library which decomposition leads to the best performance. This may also depend on the number of processors and the size of the messages to be transferred. The decomposition approach has been implemented in the form of a library extension which is called for each activation of a collective MPI operation. This has the advantage that neither the application programs nor the MPI library need to be changed while leading to significant performance improvements for many collective MPI operations.

Heterogeneous distributed environments or grid environments provide large computing resources for the execution of large scientific applications. The effective use of those platforms requires a suitable representation of the application algorithm which makes a distribution of parts of the application across the distributed environment possible. A representation of an application algorithm in form of interacting tasks has been shown to be a suitable programming model for those distributed environments, where tasks can be shipped to remote computing resources for execution. The efficient execution of an application also depends on the time for sending tasks and data to remote resources, which adds an additional overhead to the distributed execution time. In this paper, we propose a method to overlap the execution of current tasks with the shipping time for tasks to be executed later. The efficient overlapping is achieved by an anticipated scheduling algorithm for the placement of future task executions

Clusters of symmetric multiprocessors (SMPs) are popular platforms for parallel programming since they provide large computational power for a reasonable price. For irregular application programs with dynamically changing computation and data access behavior, a flexible programming model is needed to achieve efficiency. In this paper we propose Task Pool Teams as a hybrid parallel programming environment to realize irregular algorithms on clusters of SMPs. Task Pool Teams combine task pools on single cluster nodes by an explicit message passing layer. They offer load balance together with multi-threaded, asynchronous communication. Appropriate communication protocols and task pool implementations are provided and accessible by an easy-to-use application programmer interface. As application examples we present a branch and bound algorithm and the hierarchical radiosity algorithm. Copyright © 2006 John Wiley & Sons, Ltd.

Matrix-matrix multiplication is one of the core computations in many algorithms from scientific computing or numerical analysis and many efficient realizations have been invented over the years, including many parallel ones. The current trend to use clusters of PCs or SMPs for scientific computing suggests to revisit matrix-matrix multiplication and investigate efficiency and scalability of different versions on clusters. In this paper we present parallel algorithms for matrix-matrix multiplication which are built up from several algorithms in a multilevel structure. Each level is associated with a hierarchical partition of the set of available processors into disjoint subsets so that deeper levels of the algorithm employ smaller groups of processors in parallel. We perform runtime experiments on several parallel platforms and show that multilevel algorithms can lead to significant performance gains compared with state-of-the-art methods.

Summary form only given. Performance prediction is necessary and crucial in order to deal with multidimensional performance effects on parallel systems. The increasing use of parallel supercomputers and cluster systems to solve large-scale scientific problems has generated a need for tools that can predict scalability trends of applications written for these machines. In this paper, we describe a compiler tool to automate performance prediction for execution times of parallel programs by runtime formulas in closed form. For an arbitrary parallel MPI source program the tool generates a corresponding runtime function modeling the CPU execution time and the message passing overhead. The environment is proposed to support the development process and the performance engineering activities that accompany the whole software life cycle. The performance prediction tool is shown to be effective in analyzing a representative application for varying problem sizes on several platforms using different numbers of processors.

Summary form only given. The simultaneous exploitation of task and data parallelism is often beneficial for the execution of computation-intensive applications on large parallel machines with a distributed address space, since the concurrent execution of independent program parts may significantly reduce the communication overhead. This article outlines the realization of a programming environment to support the development of programs with mixed task and data parallelism, emphasising the use of transformations for generating efficient target programs using MPI. We explore the characteristics of several approaches for such an environment, and discuss their strengths and weaknesses. We discuss an approach based on a functional coordination specification, and show how the final imperative target program can be generated by several transformation steps.

Abstract Many programs for message‐passing machines can benefit from an implementation in a group‐SPMD programming model due to the potential to reduce communication overhead and to increase scalability. In this paper, we consider group‐SPMD programs exploiting different orthogonal processor partitions in one program. For each program this is a fixed set of predefined processor partitions given by the parallel hyperplanes of a two‐ or multi‐dimensional virtual processor organization. We introduce a library built on top of MPI to support the programming with those orthogonal processor groups. The parallel programming model is appropriate for applications with a multi‐dimensional task grid and task dependencies mainly aligned in the dimensions of the task grid. The library can be used to specify the appropriate processor partitions, which are then created by the library, and to define the mapping of tasks to the processor hyperplanes. Examples from numerical analysis illustrate the programming style and show that the runtime on distributed memory machines can be considerably reduced by using the library. Copyright © 2004 John Wiley & Sons, Ltd.

Using Haskell as a digital circuit description language, we transform a ripple carry adder that requires $O(n)$ time to add two $n$ -bit words into a parallel carry lookahead adder that requires $O(\log n)$ time. The ripple carry adder uses a scan function to calculate carry bits, but this scan cannot be parallelized directly since it is applied to a non-associative function. Several techniques are applied in order to introduce parallelism, including partial evaluation and symbolic function representation. The derivation given here constitutes a semi-formal correctness proof, and it also brings out explicitly each of the ideas underlying the algorithm.

The paper considers the modular programming with hierarchically structured multi-processor tasks on top of SPMD tasks for distributed memory machines. The parallel execution requires a corresponding decomposition of the set of processors into a hierarchical group structure onto which the tasks are mapped. This results in a multi-level group SPMD computation model with varying processor group structures. The advantage of this kind of mixed task and data parallelism is a potential to reduce the communication overhead and to increase scalability. We present a runtime library to support the coordination of hierarchically structured multi-processor tasks. The library exploits an extended parallel group SPMD programming model and manages the entire task execution including the dynamic hierarchy of processor groups. The library is built on top of MPI, has an easy-to-use interface, and leads to only a marginal overhead while allowing static planning and dynamic restructuring.

Runge-Kutta methods are popular methods for the solution of systems of ordinary differential equations and are provided by many scientific libraries. The performance of Runge-Kutta methods does not only depend on the specific application problem to be solved but also on the characteristics of the target machine. For processors with memory hierarchy, the locality of data referencing pattern has a large impact on the efficiency of a program. In this paper, we describe program transformations for Runge-Kutta methods resulting in programs with improved locality behavior. The transformations are based on properties of the solution method but are independent from the specific application problem or the specific target machine, so that the resulting implementation is suitable as library function. We show that the locality improvement leads to performance gains on different target machines. We also demonstrate how the locality of memory references can be further increased by exploiting the dependence structure of the right hand side function of specific ordinary differential equations.

Many implementations on message-passing machines can benefit from an exploitation of mixed task and data parallelism. A suitable parallel programming model is a group-SPMD model, which requires a structuring of the processors into subsets and a partition of the program into multi-processor tasks. In this paper, we introduce a library support for the specification of message-passing programs in a group-SPMD style allowing different partitions in a single program. We describe the functionality and the implementation of the library functions and illustrate the library programming style with example programs. The examples show that the runtime on distributed memory machines can be considerably reduced by using the library.

Many implementations on message-passing machines can benefit from an exploitation of mixed task and data parallelism. A suitable parallel programming model is a group-SPMD model which requires a structuring of the processors in to subsets and a partition of the program into multi-processor tasks. In this paper, we introduce a library support for the specification of message-passing programs in a group-SPMD style allowing different partitions in a single program. We describe the implementation of the library functions and illustrate the programming style.

The construction of efficient parallel programs usually requires expert knowledge in the application area and a deep insight into the architecture of a specific parallel machine. Often, the resulting performance is not portable, i.e., a program that is efficient on one machine is not necessarily efficient on another machine with a different architecture. Transformation systems provide a more flexible solution. They start with a specification of the application problem and allow the generation of efficient programs for different parallel machines. The programmer has to give an exact specification of the algorithm expressing the inherent degree of parallelism and is released from the low-level details of the architecture. We propose such a transformation system with an emphasis on the exploitation of the data parallelism combined with a hierarchically organized structure of task parallelism. Starting with a specification of the maximum degree of task and data parallelism, the transformations generate a specification of a parallel program for a specific parallel machine. The transformations are based on a cost model and are applied in a predefined order, fixing the most important design decisions like the scheduling of independent multitask activations, data distributions, pipelining of tasks, and assignment of processors to task activations. We demonstrate the usefulness of the approach with examples from scientific computing.

In this paper, we consider the parallel solution of non-stiff ordinary differential equations with two different classes of Runge–Kutta (RK) methods providing embedded solutions: classical embedded RK methods and iterated RK methods which were constructed especially for parallel execution. For embedded Runge–Kutta methods, mainly the potential system parallelism is exploited. Iterated RK methods provide an additional source of parallelism in the form of independent function evaluations, but they usually require a higher number of function evaluations. We put the emphasis on the parallel execution time of these methods. Copyright © 1999 John Wiley & Sons, Ltd.

Modeling the performance behavior of parallel machines is important for compiler support of efficient parallel programming. For parallel machines with a distributed memory organization this includes the simulation of the communication behavior. In this article, we investigate the communication behavior of the Intel Paragon for point-to-point and collective communication operations like single-broadcast and multi-broadcast operations. We derive run-time formulae for these operations that depend on some machine parameters and the message size. Experiments show that the predicted runtimes differ by only a small amount from the measured runtimes.

Solving initial value problems (IVPs) for ordinary differential equations (ODEs) has long been believed to be an inherently sequential procedure. But IVP solvers using the extrapolation method provide high quality solutions and offer a great potential for parallelism. In this paper, we present algorithms for extrapolation methods on distributed memory multiprocessors that combine different levels of parallelism. These algorithms differ mainly in the partitioning of the processors into groups which are responsible for the execution of the independent tasks of the extrapolation method. We present the algorithms in a compute–communicate scheme using appropriate primitives for the communication. A detailed analysis shows that a sophisticated load balancing scheme is required to achieve good speedup. We describe an optimal method based on Lagrange multipliers, investigate several simple heuristic schemes, and compare the heuristic schemes with an estimation for the optimal solution. An implementation of these schemes on an Intel iPSC\860 confirms the predicted runtimes. © 1997 by John Wiley & Sons, Ltd.