Component Performance Modeling and Scheduling Strategies on Grids

With a Grid, networked resources, e.g. desktops, servers, storage, databases, even scientific instruments, could be combined to deploy massive computing power wherever and whenever it is needed most. In the past years, High Performance Computing (HPC) applications have taken full benefit from this power, but to completely exploit the potential of Grids, a whole new set of requirements must be handled: security, resource discovery, access and management, application deployment, heterogeneity, dynamicity, interoperability, quality of services (QoS), etc. To address such problems recently a new abstraction has been introduced: the component. Component technologies have been successfully adopted in sequential programming and distributed computing, and currently several component-based programming models have been proposed as a solution to the major problems arising when programming Grids. In this thesis, three key requirements for Grid application development software are investigated: the need of a performance model for components, in order to derive the performance of Grid applications; the need of a performance contract for components, in order to derive the requirements for the execution of component-based applications on heterogeneous platforms starting from user-level performance requirements; and the need of mapping strategies for tightly-coupled applications developed using the component paradigm, with a particular focus on the impact of communication requirements. The contributions of this thesis are structured as follows. * A compositional performance model for components interacting through streams of data is proposed. This model is derived from an analytical model of the dynamic behavior of sequential and parallel components. * A definition of performance contract for component-based applications is proposed. This definition, based on the results on the steady state limit for the performance model, is viable in general for hierarchical component models with asynchronous one-way communications. * A polynomial-time propagation algorithm for component contracts is proposed. Starting from a performance model and a performance contract, it allows to compute the performance parameters that every component must satisfy, so that the program, as a whole, will fulfill the performance contract at runtime. Two launch-time scheduling heuristics to allocate component-based applications are proposed. The applications are described by task interaction graphs whose nodes and edges are labeled according to the QoS requirements derived through the contract resolution algorithm. The goal of such heuristics is to obtain feasible mappings, dealing with computational and communication requirements. The first one, the Wide Area Scheduling hEuristics (WASE) targets hierarchically structured Grids exploiting qualitative information on the application structure, while the second one, the QoS List Scheduling hEuristics (QLSE), targets unstructured global Grids trying to exploit quantitative information on the application structure.