SOLVING TIME CONSTRAINED PROBLEMS ON THE GRID

Abstract

Solving problems that require time constraints in widely distributed heterogeneous environments such as the Grid is a challenge. We address this challenge by providing: a parallelization scheme to express the conceptual parallelism; POP-C++-a requirement-driven parallel object toolkit; and an object-oriented framework that implements the skeleton of the parallelization scheme using POP-C++. The framework allows users to automatically instantiate a suitable grain of parallelism based on the availability of heterogeneous resources so that the time constraint is satisfied. Users only need to describe their own problem by deriving new "problem" classes in each decomposition and implementing the way the problem is solved. An emulated heterogeneous environment has been built up with 130 machines of Linux/Pentium 4 and Solaris/Sparc. Tests measuring the real computing time compared to the required time have been implemented using our framework and run on the emulated heterogeneous environment. The results show the ability of the framework to exploit high performance with different level of parallelism to guarantee the time constraints.