SUMMARY Programmable graphics processing units (GPUs) nowadays offer tremendous computational resources for diverse applications. In this paper, we present the implementation of the dynamics routine of the HIRLAM weather forecast model on the NVIDIA GTX 480. The original Fortran code has been converted manually to C and CUDA. Empirically, it is determined what the optimal number of grid points per thread is, and what the best thread and block structures are. A significant amount of the elapsed time consists of transferring data between CPU and GPU. To reduce the impact of these transfer costs, we overlap calculation and transfer of data using multiple CUDA streams. We developed an algorithm that enables our code generator CTADEL to generate automatically the optimal CUDA streams program. Experiments are performed to find out if the applicability of GPUs is useful for Numerical Weather Prediction, in particular for the dynamics part. Copyright © 2012 John Wiley & Sons, Ltd.

Parallel workloads in practice are far from being randomly distributed, instead they are highly repetitive because users tend to run the same applications over and over again. We refer to this phenomenon as temporal locality. In addition, the workloads exhibit a correlation between runtime and parallelism (i.e., number of processors) as is analysed in this paper. According to our best knowledge, there are very few studies on the impacts of these features on the performance of parallel systems. Since these impacts are not well known, researchers often evaluate scheduling algorithms with random workloads, which neglect the phenomenon of temporal locality and the correlation. This can result in an inaccurate scheduling evaluation for parallel systems, because our study shows that these two features can significantly affect scheduling performance. In our simulation-based experiments, an increase of the correlation can quickly degrade the parallel system performance and can change the result of comparing different scheduling policies. With respect to temporal locality, we indicate that this feature does not always seriously affect schedulers of parallel systems. Instead in particular situations, it can help to improve scheduling performance. Furthermore, we also discuss in this paper the necessity of using workloads with these features in scheduling evaluation as well as how to utilize the features to enhance the performance of schedulers.

The Bag-of-Tasks (BoT) behaviour has recently drawn the attention of scheduling researchers [2, 36, 37] and seems to be very common in workloads of parallel systems (up to 70% of jobs [27]) and grids (up to 96% of the total CPU time is consumed by BoTs [11]). To enable a reliable evaluation of BoT-oriented scheduling algorithms, researchers require realistic workload models that take BoTs into account. Regrettably, very few such models are available in the liturature. To our best knowledge, there are only two studies on modeling that incorporate BoTs into their models to generate synthetic workloads for parallel systems [27] and grids [12]. However, these models only focus on fitting the marginal distributions and neglect several other statistical properties of BoTs such as periodicity, autocorrelation and cross-correlation among BoT attributes. We believe that these crucial characteristics deserve to be taken into account in modeling research. Therefore in this paper, we will focus on characterising the BoT behaviour to further improve researchers' understanding of this well-known behaviour in parallel system workloads. In addition, we also study how BoTs affect parallel system performance. Our experimental results indicate that the presence of BoTs leads to a considerable performance degradation, but it is interesting that a realistic association between job arrivals and job runtimes helps BoTs to improve the performance of parallel systems. Moreover, we also show the necessity of using workloads with BoTs in scheduling evaluation to obtain reliable results.

Performance evaluation is a significant step in the study of scheduling algorithms in large-scale parallel systems ranging from supercomputers to clusters and grids. One of the key factors that have a strong effect on the evaluation results is the workloads (or traces) used in experiments. In practice, several researchers use unrealistic synthetic workloads in their scheduling evaluations because they lack models that can help generate realistic synthetic workloads. In this paper we propose a full model to capture the following characteristics of real parallel system workloads: 1) long range dependence in the job arrival process, 2) temporal and spatial burstiness, 3) bag-oftasks behaviour, and 4) correlation between the runtime and the number of processors. Validation of our model with real traces shows that our model not only captures the above characteristics but also fits the marginal distributions well. In addition, we also present an approach to quantify burstiness in a job arrival process (temporal) as well as burstiness in the load of a trace (spatial).

We present in this paper a novel method to predict application runtimes on backfilling parallel systems. The method is based on mining historical data to obtain important parameters. These parameters are then applied to predict the runtime of future applications. It has been shown in previous works that both underestimate and inaccuracy in prediction have adverse impacts on scheduling performance of backfilling systems. In our study, we try to reduce the number of jobs that are underestimated and reduce the prediction error as much as possible. Comparing with other predictors, experimental results show that our predictor is up to 25% better with respect to the problem of underestimate. Moreover, using the metric proposed in for the accuracy, our predictor improves up to 32%.

Workload modeling plays a significant role in performance evaluation of large-scale parallel systems such as clusters and grids. It helps to generate synthetic workloads which capture some dominant characteristics of traces (real workloads). Modeling job arrival process is an essential part of workload modeling. Although a job arrival process has many important characteristics such as long range dependence (LRD) and burstiness, most researchers, for simplicity, assume it as a Poisson process in their evaluation work. Furthermore, there is currently almost no research focusing on both LRD and burstiness at the same time according to our investigation. With respect to this research trend, the multifractal wavelet model (MWM) recently has been introduced as a good choice to yield LRD for a job arrival process. Though LRD is well controlled, we observe that a job arrival process produced by MWM does not keep burstiness. In this paper, we present our study on modifying MWM so that not only LRD but also burstiness are kept in the job arrival process. In addition, our modification also fits the marginal distribution better than MWM.

Pseudo-periodicity is one of the basic job arrival patterns on data-intensive clusters and Grids. In this paper, a signal decomposition methodology called matching pursuit is applied for analysis and synthesis of pseudo-periodic job arrival processes. The matching pursuit decomposition is well localized both in time and frequency, and it is naturally suited for analyzing non-stationary as well as stationary signals. The stationarity of the processes can be quantitatively measured by permutation entropy, with which the relationship between stationarity and modeling complexity is excellently explained. Quantitative methods based on the power spectrum are also provided to measure the degree of periodicity present in the data. Matching pursuit is further shown to be able to extract patterns from signals, which is an attractive feature from a modeling perspective. Real world workload data from production clusters and Grids are used to empirically evaluate the proposed measures and methodologies.

We propose a new model for workload attributes on spaceshared computer systems, which is able to fit both marginal distributions and second order statistics such as the autocorrelation function (ACF). The modeling process is formed by a two-stage approach: Firstly, a mixture of Gaussians model is used to fit the probability density function (PDF), whose parameters are estimated via a framework called model based clustering (MBC). The MBC framework can further cluster the data according to the Gaussian components, which plays an important role in creating correlations in the next stage. Secondly, a novel localized sampling algorithm is proposed to generate correlations in the synthetic data series. It is discovered that the number of repetitions of cluster labels obtained via MBC empirically follow a Zipf-like (power law) distribution. Sampling repeatedly from a certain cluster according to the Zipf law is able to create correlations in the series. Furthermore, a cluster permutation procedure is introduced so that the autocorrelations in the synthetic data can be controlled to match those in the real trace via a single parameter. Our approach can generalize to more than one dimension, which means multiple correlated workload attributes can be modeled simultaneously. Experimental studies are conducted to evaluate the proposed algorithm using real workload traces on production systems such as Grids and supercomputers.

This paper presents a comprehensive statistical analysis of workloads collected on data-intensive clusters and grids. The analysis is conducted at different levels, including virtual organization (VO) and user behavior. The aggregation procedure and scaling analysis are applied to job arrival processes, leading to the identification of several basic patterns, namely, pseudo-periodicity, long range dependence (LRD), and (multi)fractals. It is shown that statistical measures based on interarrivals are of limited usefulness and count based measures should be trusted instead when it comes to correlations. We also study workload characteristics like job run time, memory consumption, and cross correlations between these characteristics. A "bag-of-tasks" behavior is empirically proved, strongly indicating temporal locality. We argue that pseudo-periodicity, LRD, and "bag-of-tasks" behavior are important workload properties on data-intensive clusters and grids, which are not present in traditional parallel workloads. This study has important implications on workload modeling and performance predictions in data-intensive grid environments.

Local learning has been proposed as a common framework to predict both application run times and queue wait times based on workload traces [8]. The queue wait time is shown to be more difficult and expensive to predict because its distance calculations typically involve not only job attributes but also resource states. In this paper methods and algorithms are investigated to improve prediction accuracy and prediction performance for queue wait times. Firstly, the so-called "local tuning" is adopted to tune parameters for each training subset divided by a pivot attribute (e.g., group or queue name). Bias-variance analysis of error is conducted on local tuning and its global counterparts - tuning parameters on the whole training set. A method is then developed to select tuning type adaptively based on the generalization error and bias-variance decomposition. Secondly, an efficient search tree structure called "M-Tree" is integrated into our algorithm to speed up k-nearest neighbor search. Experimental studies are conducted to evaluate the proposed methods and algorithms using real-world workload traces, which are collected from the NIKHEF production cluster on the LHC Computing Grid and Blue Horizon in the San Diego Supercomputer Center (SDSC). The results show that adaptive tuning can reduce the average prediction error by 3 to 10 percents compared to global tuning, and that the M-Tree nearest neighbor search is up to 8 times faster than the sequential search.

In this paper we present an initial analysis of job failures in a large-scale data-intensive Grid. Based on three representative periods in production, we characterize the interarrival times and life spans of failed jobs. Different failure types are distinguished and the analysis is carried out further at the Virtual Organization (VO) level. The spatial behavior, namely where job failures occur in the Grid, is also examined. Cross-correlation structures, including how arrivals correlate with life spans of job failures, are analyzed and illustrated. We further investigate statistical models to fit the failure data and propose several failureaware scheduling strategies at the Grid level. Our results show that the overall failure rates in the Grid are quite significant, ranging from 25% to 33% of all submitted jobs. However, only 5% to 8% of the jobs failed after running on a certain Computing Element (CE). The rest of failed jobs are aborted or cancelled without running. A majority of failed jobs come from several large production VOs and a large amount of these failures are centered around several main CEs. The interarrival time processes of failed jobs are shown to be bursty, and the life spans exhibit strong autocorrelations. Based on the failure patterns we argue that it is important for the Grid resource brokers to track historical failure and take it into account in decision making. Some proactive measures and accountability issues are also discussed.

In a computational Grid which consists of many computer clusters, job start time predictions are useful to guide resource selections and balance the workload distribution. However, the basic Grid middleware available today either has no means of expressing the time that a site will take before starting a job or uses a simple linear scale. In this paper we introduce a system for predicting job start times on clusters. Our predictions are based on statistical analysis of historical job traces and simulation of site schedulers. We have deployed the system on the EDG (European Data-Grid) production cluster at NIKHEF. The experimental results show that acceptable prediction accuracy is achieved to reflect real site states and site-specific scheduling policies. We find that the average error of our job start time predictions is 18.9 percent of the average job queue wait time and this is around 20 times smaller than the average prediction error using the EDG solution.

The use of semi-Lagrangian formulations in numerical weather predication models (NWP) allows for an increase in time step size. Use of this method can increase performance of these models. However, on parallel architectures, communication between processors can become a huge bottleneck, limiting speedup. Furthermore, the communication pattern is dependent on the application's execution. We discus a novel strategy, called Halo on Demand, which dynamically drives the communication between the processors by examining the content of the data at runtime in order to reduce communication costs. With an extensive performance analysis of the execution of the model we show that our strategy can decrease communication time and thus decrease total execution time.

The size of a time step is important for numerical weather prediction models (NWP) since forecasts need to be available within the fraction of time that may considered to be valid. However, time step size is often limited by the numerical stability of the used advection schemes. Available schemes include semi-implicit Eulerian and semi-Lagrangian schemes. In principal, semi-Lagrangian formulations result in irregular communications on parallel architectures. In this paper we describe automatic code generation for a semi-implicit scheme with a semi-Lagrangian formulation. We describe how code can be generated from a mathematical specification of the advection model and we show results from preliminary experiments we have conducted with the generated code and the reference code from a production NWP on a number of different architectures.

In this paper we describe how to extend CTADEL, a Problem Solving Environment, in order to generate code for a turbulence scheme, in our case, within a numerical weather prediction model (NWP). Common for these schemes is the presence of implicit equations. We describe how to generate efficient codes for a particular class of implicit differential equations, that is encountered in the turbulence scheme of the HIRLAM NWP model. This extension to CTADEL enables the code generation for a particular solution method for these implicit equations. This solution method is also used in the original hand-written (reference) code. We address problems like how to recognize the type of equations and how to generate efficient code for a prescribed solution method. Finally, we compare the generated code for the turbulence scheme with the hand-written reference code.

In this paper we focus on generating efficient parallel codes for solving scientific problems within large-scale performance-critical applications. More specifically we present techniques for high-level symbolic optimization for automatic generation of efficient codes that numerically solve sets of computationally expensive right-hand sides (RHSs) of systems of partial differential equations (PDEs). These type of PDE problems can be found in application areas like numerical weather prediction, ocean circulation modeling, and climate modeling. To solve the PDEs describing the physical problem, high-performance software environments and computer platforms are required. The CTADEL application driver is a software environment for generating optimized codes for serial, vector, or parallel architectures from a high-level PDE problem description of a weather forecast model. The advantage of the high-level problem description is that all of the high-level information can be exploited for parallelization, restructuring, and optimization from the highest descriptive level to the low-level generated code.

In this paper, we demonstrate the necessity of including high-level information for automatic generation of efficient codes for serial, vector, and parallel computer architectures with the CTADEL code generation tool.The CTADEL Codegeneration Tool for Applications based on Differential Equations using high-level Language specifications is a programming environment developed for the generation of efficient codes for PDEbased problems.The tool has been adopted as an application driver for the HIRLAM numerical weather forecast system.More specifically, we present a framework for high-level code restructuring based on monotonicity information about the data structures used.This information is not available in state-of-the-art vectorizing and parallelizing compilers but it is of vital importance for the generation of efficient architecture-specific codes.The performance of the generated codes for a typical example problem encountered in the so-called physics routines of the HIRLAM system are compared to the hand-written production code.The performance results demonstrate the usefulness of the presented technique.

The CTADEL system provides an automated means of generating specific high performance scientific codes optimized for serial, vector, or shared virtual memory and distributed memory parallel computer architectures.

In this paper the impact of parallel programming paradigms and data distributions on the performance of a parallel finite difference application is investigated.The finite difference application is one of the kernel routines of a limited area numerical weather forecast model that is in use for producing routine weather forecasts at several European meteorological institutes.Results are shown for CRAY T3D and MasPar systems.

A data-parallel implementation on a SIMD platform of an operational numerical weather forecast model is presented. The performances of two popular numerical techniques within these models are discussed, namely finite difference (gridpoint) methods and spectral methods. In this paper in particular the performance achieved for a full production run is investigated. Also the price/performance ratios of several compute platforms for this forecast model are shown.