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.

The landscape of multi-core architectures is growing more complex and diverse. Optimal application performance tuning parameters can vary widely across CPUs, and finding them in a possibly multidimensional parameter search space can be time consuming, expensive and potentially infeasible. In this work, we introduce YaskSite, a tool capable of tackling these challenges for stencil computations. YaskSite is built upon Intel's YASK framework. It combines YASK's flexibility to deal with different target architectures with the Execution-Cache-Memory performance model, which enables identifying optimal performance parameters analytically without the need to run the code. Further we show that YaskSite's features can be exploited by external tuning frameworks to reliably select the most efficient kernel(s) for the application at hand. To demonstrate this, we integrate YaskSite into Offsite, an offline tuner for explicit ordinary differential equation methods, and show that the generated performance predictions are reliable and accurate, leading to considerable performance gains at minimal code generation time and autotuning costs on the latest Intel Cascade Lake and AMD Rome CPUs.

In the Oil and Gas industry, estimating a subsurface velocity field is an essential step in seismic processing, reservoir characterization, and hydrocarbon volume calculation. Full-waveform inversion (FWI) velocity modeling is an iterative advanced technique that provides an accurate and detailed velocity field model, although at a very high computational cost due to the physics-based numerical simulations required at each FWI iteration. In this study, we propose a method of generating velocity field models, as detailed as those obtained through FWI, using a conditional generative adversarial network (cGAN) with multiple inputs. The primary motivation of this approach is to circumvent the extremely high cost of full-waveform inversion velocity modeling. Real-world data were used to train and test the proposed network architecture, and three evaluation metrics (percent error, structural similarity index measure, and visual analysis) were adopted as quality criteria. Based on these metrics, the results evaluated upon the test set suggest that the GAN was able to accurately match real FWI generated outputs, enabling it to extract from input data the main geological structures and lateral velocity variations. Experimental results indicate that the proposed method, when deployed, has the potential to increase the speed of geophysical reservoir characterization processes, saving on time and computational resources.

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.

Abstract Energy-efficient computing is especially important in the field of high-performance computing (HPC) on supercomputers. Therefore, automated optimization of energy efficiency during the execution of a compute-intensive program is desirable. In this article, a framework for the automatic improvement of the energy efficiency on NVIDIA GPUs (graphics processing units) using dynamic voltage and frequency scaling is presented. As application, the mining of crypto-currencies is used, since in this area energy efficiency is of particular importance. The framework first determines the energy-optimal frequencies for each available currency on each GPU of a computer automatically. Then, the mining is started, and during a monitoring phase it is ensured that always the most profitable currency is mined on each GPU, using optimal frequencies. Tests with different GPUs show that the energy efficiency, depending on the GPU and the currency, can be increased by up to 84% compared to the usage of the default frequencies. This in turn almost doubles the mining profit.

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.

When migrating a scientific application to a new HPC system, the program code usually has to be re-tuned to achieve the best possible performance. Auto-tuning techniques are a promising approach to support the portability of performance. Often, a large pool of possible implementation variants exists from which the most efficient variant needs to be selected. Ideally, auto-tuning approaches should be capable of undertaking this task in an efficient manner for a new HPC system and new characteristics of the input data by applying suitable analytic models and program transformations.

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.

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.

In this article, we consider diagonal-implicitly iterated Runge-Kutta (DIIRK) methods for the numerical solution of stiff ordinary differential equations (ODEs) and investigate their performance behavior on a modern cluster system using MPI. DIIRK methods are implicit methods and require the solution of non-linear equation systems in each iteration step. In particular, we are interested in the parallel execution behavior when using different basis Newton methods for solving the resulting non-linear equation systems of different versions of the DIIRK method. We explore the use of direct solution methods based on LU factorization for the resulting linear equation systems as well as the use of Krylov subspace methods and investigate the resulting performance and accuracy.

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.

Because the numerical solution of initial value problems (IVPs) of systems of ordinary differential equations (ODEs) can be computationally intensive, several parallel methods have been proposed in the past.One class of modern parallel IVP methods are the peer methods proposed by Schmitt and Weiner, some of which are publicly available in the software package EPPEER released in 2012.Since they possess eight independent stages, these methods offer natural parallelism across the method suitable for the typical numbers of CPU cores in modern multicore workstations.EPPEER is written in FORTRAN95 and uses OpenMP as parallel programming model.In this paper, we investigate the influence of the locality of memory references on the scalability of method-and systemparallel explicit peer methods.In particular, we investigate the interplay between the linear combination of the stages and the function evaluations by applying different program transformations to the loop structure and by evaluating their performance in detailed runtime experiments.These experiments point out that loop tiling is required to improve cache utilization while still allowing the compiler to vectorize along the system dimension.To show that for certain classes of right-hand-side functions a stage-parallel execution is not optimal, and to enhance the scalability of the peer methods to core numbers larger than the number of stages of a method, system-parallel implementations have been derived.Runtime experiments show that there are IVPs for which these new implementations outperform stage-parallel implementations on numbers of cores less than or equal to the number of stages.Moreover, by exploiting the ability to utilize higher core numbers, higher speedups than the number of stages have been reached.

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.

The usage of remote compute and storage resources is becoming popular to assist mobile devices. However, existing frameworks that support mobile client/server applications do not consider the provision of resources in a large scale. Although a cloud-based infrastructure may provide a large number of resources on demand, most cloud offerings do not provide the right level of abstraction to assist mobile devices. Infrastructure-as-a-Service (IaaS) offerings are too complex to set up on demand and Platform-as-a-Service (PaaS) offerings are not flexible enough regarding Quality-of-Service (QoS) adjustment. To overcome these issues, we propose a middleware named Mobile Assistance Platform (MAP), which serves as an extended PaaS layer. It provides an on-demand execution platform for program code, but with the additional ability to select the underlying VM quality for execution. Furthermore, each mobile request is assigned to a single VM instance for processing. MAP provides configurable compute resources for mobile users in a large scale. For this demo, we have set up MAP on the Amazon EC2 infrastructure and we present two mobile applications that can benefit from the on-demand resource quality selection.

Mobile devices such as netbooks, smartphones, and tablets have made computing ubiquitous. However, such battery powered devices often have limited computing power for the benefit of an extended runtime. Nevertheless, despite the reduced processing power, users expect to perform the same types of operations as they could do using their desktop or laptop computers. We address mobile devices's lack of computing power by leveraging cloud computing resources. We present a middleware that relocates computing-intensive parts of Java applications to cloud re-sources. Consequently, our middleware enables the execution of computing-intensive applications on mo-bile devices. We present a case study on which we adapt Sunflow, an open-source ray tracing application, to use our middleware and show the results obtained by deploying it on Amazon EC2. We show, via simulations, a cost analysis of using the different resource allocation strategies available on our solution.

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.

Future micro-processors are expected to contain an increasing number of cores. Different models exist for efficiently organizing the cores of the resulting many-core processors. The Single-Chip Cloud Computer (SCC) is an experimental processor created by Intel Labs. It is optimized for providing to each core a programming model similar to that of the nodes of a message-passing distributed system. We have examined the performance of a memory-intensive application on the SCC. The application solves Initial Value Problems (IVPs) of Ordinary Differential Equations (ODEs). Experiments with different configurations and optimizations of this application have been performed. The evaluation of these experiments reveals bottlenecks and provides hints for optimizing applications for similar many-core architectures.

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.

This paper describes an efficient self-adaptive procedure for iterated Runge-Kutta (IRK) methods, a class of solution methods for initial value problems (IVPs) of ordinary differential equations (ODEs). IRK methods execute a potentially large number of discrete time steps to compute the solution of the IVP. The performance of an IRK solver may strongly depend on the specific characteristics of the given IVP and the hardware architecture on which the solver is executed. To address this problem, this paper applies dynamic auto-tuning to the sequential execution of IRK methods. Auto-tuning is a promising technique to avoid time consuming and extensive manual tuning. Our self-adaptive IRK solver utilizes the time-stepping nature of the IRK method. It selects the fastest implementation variant for the given IVP on the target architecture from a candidate pool during the first time steps. Then, the fastest implementation variant is used to compute all remaining time steps. The different implementation variants in the candidate pool have been developed by modifications of the loop structure of the basic algorithm. For those implementation variants that use loop tiling, we consider different tile sizes during the auto-tuning phase to further improve the performance of the self-adaptive IRK solver. Runtime experiments demonstrate the efficiency of the self-adaptive IRK solver for different IVPs on different hardware architectures.

Abstract Time‐dependent processes can often be modeled by systems of ordinary differential equations (ODEs). Solving such a system for a detailed model can be highly computationally intensive. We investigate explicit extrapolation methods for solving such systems efficiently on current highly parallel supercomputer systems with shared‐or distributed‐memory architecture. We analyze and compare the scalability of several parallelization variants, some of them using multiple levels of parallelization. For a large class of ODE systems, data access costs are reduced considerably by exploiting the special structure of the ODE system. Furthermore, by employing a pipeline‐like loop structure, the locality of memory references is increased for such systems resulting in a better utilization of the cache hierarchy. Runtime experiments show that the optimized implementations can deliver a high scalability. Copyright © 2011 John Wiley & Sons, Ltd.

Extrapolation methods belong to the class of one-step methods for the solution of systems of ordinary differential equations (ODEs). In this paper, we present parallel implementation variants of extrapolation methods for large shared-memory computer systems which exploit pure data parallelism or mixed task and data parallelism and make use of different load balancing strategies and different loop structures. In addition to general implementation variants suitable for ODE systems with arbitrary access structure, we devise specialized implementation variants which exploit the specific access structure of a large class of ODE systems to reduce synchronization costs and to improve the locality of memory references. We analyze and compare the scalability and the locality behavior of the implementation variants on an SGI Altix 4700 using up to 500 threads.

The shift to multicore processors demands efficient parallel programming on a diversity of architectures, including homogeneous and heterogeneous chip multiprocessors (CMPs). Task parallel programming is one approach that maps well to CMPs. In this model, the programmer focuses on identifying parallel tasks within an application, while a runtime system takes care of managing, scheduling, and balancing the tasks among a number of processors or cores. Heterogeneous CMPs, such as the Cell Broadband Engine, present new challenges to task parallel programming and corresponding runtime systems. In this paper, we present a library based on task pools for dynamic task scheduling and load balancing on Cell processors. In contrast to other approaches, our task pools include support for creating tasks using the Synergistic Processing Elements (SPEs), which enables the implementation of a wide range of task parallel applications. Our experiments show that task pools provide flexible and efficient support for task parallel programming on Cell processors. In addition, we show that offloading the process of task creation from the PPE to the SPEs provides much potential for exploiting fine-grained parallelism.

Embedded Runge-Kutta methods are well-known and efficient solution methods for initial value problems of ordinary differential equations (ODEs). In this paper, we discuss the parallel implementation of embedded Runge-Kutta methods for distributed address space. Our focus lies on the exploitation of a special structure of commonly appearing ODE systems to improve scalability and memory usage. We show how the memory space of a pipeline-like computation scheme can be reduced to less than three storage registers by an overlapping of vectors without compromising the choice of method coefficients or the potential for efficient stepsize control. We analyze and compare the scalability of different implementation strategies in detailed runtime experiments on different modern parallel architectures. These experiments show that our approach leads to a good scalability behavior even on large numbers of processors.

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).

In this article, we revisit the problem of scheduling dynamically generated directed acyclic graphs (DAGs) of multi-processor tasks (M-tasks). A DAG is a basic model for expressing workflows applications where each node represents a task of the workflow. We present a novel algorithm (DMHEFT) for scheduling dynamically generated DAGs onto a heterogeneous collection of clusters. The scheduling decisions are based on the predicted runtime of an M-task as well as the estimation of the redistribution costs between data-dependent tasks. The algorithm also takes care of unfavorable placements of M-tasks by considering the postponing of ready tasks even if idle processors are available. We evaluate the scheduling algorithm by comparing the resulting makespans to the results obtained by using other scheduling algorithms, such as RePA and MHEFT.

Applications raising in many scientific fields exhibit both data and task parallelism that have to be exploited efficiently. A classic approach is to structure those applications by a task graph whose nodes represent parallel computations. Scheduling such mixed-parallel applications is challenging even on a single homogeneous platform, such as a cluster. Most of the mixed-parallel application scheduling algorithms rely on two decoupled steps: allocation and mapping. This separation can induce unnecessary or costly data redistributions that have an impact on the overall performance. This is particularly true for data intensive applications. In this paper, we propose an original approach in which the allocations determined in the first step can be adapted during the second step in order to minimize the impact of these data redistributions. Two redistribution aware mapping strategies are detailed and a study of their impact on the schedule length is proposed through a comparison with an efficient two step algorithm over a broad range of experimental scenarios.

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.

The efficient use of the cache hierarchy of an execution platform often has a major impact on the performance of an application. It is often difficult for the application programmer or the compiler to determine a suitable memory layout for the application data, since the interactions between the memory accesses cannot be fully anticipated before the program execution. This paper introduces an approach to improve the cache efficiency by dynamically padding memory allocations by a post-compilation tool. Data structures like histograms are used to evaluate cache simulations of memory traces of the application considered and to compute optimized pad sets. These can then be used for later runs of the application with different data sets. The accumulated representation of the references' memory accesses additionally offers a visualization interface to the algorithm-specific memory access pattern of each reference captured. As implied above, the advantage of the method is that it also allows for an improvement of the cache usage of binary only applications for which no source code is available. Post optimization cache behavior analyses as well as run-time measurements show that the cache hit rates of the runtime-modified applications are considerably increased by applying the generated pad set.

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.

Data mining in biological structure libraries can be a powerful tool to better understand biochemical processes. This article introduces the LISA algorithm which enables the researcher to search substructures in PDB files describing the 3D structure of protein molecules. The use of constraints such as atomic distances, torsion angles, or the distance of residues within the linear amino acid sequence, allows for great flexibility in defining and searching specific structures, which could not be found with other tools. Data mining in biological databases, e.g. scanning the entire PDB database for structures that match user-defined criteria, is a massively computation-intensive task. Thus, we present a parallel implementation of LISA and show that the algorithm achieves good parallel efficiency on homogeneous clusters.

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

DSM systems provide an easy-to-use programming model for parallel and distributed systems, but it is sometimes difficult to reach the performance characteristics of low-level message-passing programs, in particular if these have been optimized towards a specific architecture. In this article, we propose a multi-layered realization of a DSM system which provides different programming abstractions, including a level which allows an explicit control of the data placement. The programmer can select an appropriate level of abstraction for his application and it is even possible to mix program parts realized at different abstraction levels. The article gives a description of the multi-layered model, describes a prototype realization of the system and presents some preliminary experimental results on a heterogeneous system.

We consider the task-based execution of parallel irregular applications, which are characterized by an unpredictable computational structure induced by the input data. The dynamic load balancing required to execute such applications efficiently can be provided by task pools. Thus, the performance of a task-based irregular application is tightly coupled to the scalability and the overhead of the task pool used to execute it. In order to reduce this overhead this article considers the use of the hardware-specific synchronization operations compare & swap and load & reserve/store conditional. We present several different realizations of task pools using these operations. Runtime experiments on two shared-memory machines, a SunFire 6800 and an IBM p690, show that the new implementations obtain a significantly higher performance than implementations relying on the POSIX thread library for synchronization.

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.

A task-based execution provides a universal approach to dynamic load balancing for irregular applications. Tasks are arbitrary units of work that are created dynamically at run-time and that are stored in a parallel data structure, the task pool, until they are scheduled onto a processor for execution. In this paper, we evaluate the performance of different task pool implementations for shared-memory computer systems using several realistic applications. We consider task pools with different data structures, different load balancing strategies and a specialized memory management. In particular, we use synchronization operations based on hardware support that is available on many modern micro-processors. We show that the resulting task pool implementations lead to a much better performance than implementations using Pthreads library calls for synchronization. The applications considered are parallel quicksort, volume rendering, ray tracing, and hierarchical radiosity. The target machines are an IBM p690 server and a SunFire 6800.

Abstract Since a static work distribution does not allow for satisfactory speed‐ups of parallel irregular algorithms, there is a need for a dynamic distribution of work and data that can be adapted to the runtime behavior of the algorithm. Task pools are data structures which can distribute tasks dynamically to different processors where each task specifies computations to be performed and provides the data for these computations. This paper discusses the characteristics of task‐based algorithms and describes the implementation of selected types of task pools for shared‐memory multiprocessors. Several task pools have been implemented in C with POSIX threads and in Java. The task pools differ in the data structures to store the tasks, the mechanism to achieve load balance, and the memory manager used to store the tasks. Runtime experiments have been performed on three different shared‐memory systems using a synthetic algorithm, the hierarchical radiosity method, and a volume rendering algorithm. Copyright © 2004 John Wiley & Sons, Ltd.

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.

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.