VU AmsterdamAfdeling Wiskunde   Faculteit der Exacte Wetenschappen Afdeling Wiskunde Vrije Universiteit Amsterdam
Wiskunde Studeren


Effective Prediction of Job Processing Times in a Large-Scale Grid Environment

Menno Dobber, Rob van der Mei, Ger Koole

in proceedings HPDC 2006, Paris

Grid applications that use a considerable number of processors for their computations need effective predictions of the expected computation times on the different nodes. Currently, there are no effective prediction methods available that satisfactorily cope with those ever-changing dynamics of computation times in a grid environment. Motivated by this, in this paper we develop the Dynamic Exponential Smoothing (DES) method to predict job processing times in a grid environment. To compare predictions of DES to those of the existing prediction methods, we have performed extensive experiments in a real large-scale grid environment. The results illustrate a strong and consistent improvement of DES in comparison with the existing prediction methods.

Statistical Properties of Task Running Times in a Global-Scale Grid Environment

Menno Dobber, Rob van der Mei, Ger Koole

in proceedings CCGrid 2006, Singapore

Grid computing technology connects globally distributed processors to develop an immense source of computing power, which enables us to run applications in parallel that would take orders of magnitude more time on a single processor. Key characteristics of a global-scale grid are the strong burstiness in the amount of load on the resources and on the network capacities, and the fact that processors may be appended to or removed from the grid at any time. To cope with these characteristics, it is essential to develop techniques that make applications robust against the dynamics of the grid environment. For these techniques to be effective, it is important to have an understanding of the statistical properties of the dynamics of a grid environment. Today, however, the statistical properties of the dynamic behavior of real global-scale grid environments are not well understood. Our main focus is on highly CPU-intensive grid applications that require huge amounts of processor power for running tasks. Motivated by this, we have performed extensive measurements in a real, global-scale grid environment to study the statistical properties of the running times of tasks on processors. We observe (1) a strong burstiness of the running times over different time scales, (2) a strong heterogeneity of the running-time characteristics among the different hosts, (3) a strong heterogeneity of the running-time characteristics for the same host over different time intervals, and (4) the occurrence of sudden level-switches in the running times, amongst others. These observations are used to develop effective techniques for the prediction of running times. They can be used to develop effective control schemes for robust grid applications.

Dynamic Load Balancing Experiments in a Grid

Menno Dobber, Ger Koole, Rob van der Mei

in proceedings CCGrid 2005, Cardiff, Wales

Connected world-widely distributed computers and data systems establish a global source of processing power and data, called a grid. Key properties of a grid are the fact that computers providing processing power may connect and disconnect at any time, and that demands for processing power may highly fluctuate over time. This has raised the need for the development of applications that are robust against changing circumstances. In [4] fluctuations in processing speeds on running times has been investigated, and it was found that dynamic load balancing methods provide a promising means to deal with the ever-changing environment in the grid. In this paper we demonstrate with extensive experiments in a real grid environment, Planetlab, that dynamic load balancing based on predictions via Exponential Smoothing indeed lead to significant reductions in running times of parallel applications in a randomly changing grid environment. (1.5mb) ccgrid05.pdf (850kb)

Dynamic Load Balancing for a Grid Application

Menno Dobber, Ger Koole, Rob van der Mei

in proceedings HiPC 2004, Bangalore, India

Grids functionally combine globally distributed computers and information systems for creating a universal source of computing power and information. A key characteristic of grids is that resources (e.g., CPU cycles and network capacities) are shared among numerous applications, and therefore, the amount of resources available to any given application highly fluctuates over time. In this paper we analyze the impact of the fluctuations in the processing speed on the performance of grid applications. Extensive lab experiments show that the burstiness in processing speeds has a dramatic impact on the running times, which heightens the need for dynamic load balancing schemes to realize good performance. Our results demonstrate that a simple dynamic load balancing scheme based on forecasts via exponential smoothing is highly effective in reacting to the burstiness in processing speeds. HiPC.pdf Springerlink

Your browser does not fully support CSS. This may result in visual artifacts.