Gestión de recursos en sistemas de cómputo heterogéneos (TIN 2008-05913)

The main goal of this project is to design a distributed computing environment based on a peer-to-peer architecture. This architecture is a non-dedicated large scale system composed of a set of processing nodes connected to Internet, where the idle processing times of nodes are used. The main characteristics of a peer-to-peer system are the following: (a) High scalability due to its complete decentralized management of resources. (b) High dynamism. Nodes can be connected and disconnected to the system in an arbitrary way. (c) Heterogeneity. Both, nodes and networks can have different characteristics.
Under this perspective, we plan to design a platform that configures a peer-to-peer architecture to carry out distributed computing. At the same time, this architecture will provide a Quality of Service (QoS) model that assures the achievement of certain performance requirements to the user. To do this, we will elaborate models and policies in the following aspects:

• Analysis of QoS requirements for distributed applications and definition of models and measures to evaluate the achievement of these requirements.
• Elaboration of decentralized mechanisms for distributing computation and resource management that take into account the system heterogeneity.
• Design of fault tolerance mechanisms that guarantee the right finish of distributed applications, making their execution transparent to system faults.
• Design of prediction policies, to be taken into account in tasks and resource management policies, that guarantee QoS requirements.

El objetivo global de este proyecto consiste en diseñar un entorno de cómputo distribuido basado en una arquitectura peer-to-peer. Dicha arquitectura constituye un sistema de cómputo a gran escala y no dedicado formado por un conjunto de nodos de procesamiento conectados a Internet, donde se aprovecha el cómputo disponible de los nodos individuales infrautilizados.

Las principales características de un sistema que opera bajo el paradigma peer-to-peer son las siguientes: (a) Alta escalabilidad del sistema debida a una gestión totalmente descentralizada del mismo. (b) Gran dinamismo. Los nodos pueden conectarse y desconectarse al sistema de forma arbitraria. (c) Heterogeneidad. Tanto los nodos como los tipos de redes que los conectan pueden ser de distintas características y ámbitos respectivamente.

Bajo esta perspectiva de cómputo distribuido, en el proyecto nos planteamos diseñar una plataforma que configure una arquitectura peer-to-peer para la distribución de cómputo, dotando al sistema de un modelo de calidad de servicio que asegure la consecución de ciertas prestaciones para el usuario. Para ello se hará hincapié en la elaboración de modelos y políticas que cubran los siguientes aspectos:

• Análisis de los requerimientos de calidad de servicio de las aplicaciones distribuidas y definición de modelos y métricas que permitan evaluar el grado de eficiencia en función de dichos requerimientos.
• Elaboración de mecanismos descentralizados de distribución de cómputo y de gestión de recursos que tengan en cuenta la heterogeneidad del sistema.
• Diseño de mecanismo de tolerancia a fallos que garanticen la correcta finalización de las aplicaciones distribuidas, haciendo que su ejecución sea transparente a los fallos acaecidos por la continua entrada y salida de nodos.
• Diseño de mecanismos de predicción que den soporte a las políticas de gestión de tareas y recursos para garantizar los requisitos de calidad de servicio demandados.

Enhancing Prediction on Non-dedicated Clusters

J. Ll. Lérida, F. Solsona, F. Giné, J.R. García, M. Hanzich and P. Hernández
August 2008

Abstract: In this paper, we present a scheduling scheme to estimate the turnaround time of parallel jobs on a heterogeneous and non-dedicated cluster or NoW(Network of Workstations). This scheme is based on an analytical prediction model that establishes the processing and communication slowdown of the execution times of the jobs based on the cluster nodes and links powerful and occupancy. Preservation of the local application responsiveness is also a goal.
We address the impact of inaccuracies in these estimates on the overall system performance. Furthermore, we demonstrate that job scheduling benefits from the accuracy of these estimates. The applicability of our proposal has been proved by measuring the efficiency of our method by comparing the predicted deviations of the parallel jobs in a real environment with respect to the most representative ones of the literature.
The additional cost of obtaining these was also evaluated and compared.The present work is implemented within the CISNE project, a previously developed scheduling framework for non-dedicated and heterogeneous cluster environments.

Resource Matching in Non-dedicated Multicluster Environments

J.Ll. Lérida, F. Solsona, F. Gine, J.R. García, P. Hernández
Juny 2008

Abstract: We are interested in making use of Multiclusters to execute parallel applications. The present work is developed within the M-CISNE project. MCISNE is a non-dedicated and heterogeneous Multicluster environment which includes MetaLoRaS, a two-level MetaScheduler that manages the appropriate job allocation to available resources.
In this paper, we present a new resource-matching model for MetaLoRaS, which is aimed at mitigating the degraded turnaround time of co-allocated jobs, caused by the contention on shared inter-cluster links. The model is linear programming based and considers the availability of computational resources and the contention of shared inter and intra-cluster links. Its goal is to minimize the average turnaround time of the parallel applications without disturbing the local applications excessively and maximize the prediction accuracy.
We also present a parallel job model that takes both computation and communication characterizations into account. By doing this, greater accuracy is obtained than in other models only focused on one of these characteristics.
Our preliminary performance results indicate that the linear programming model for on-line resource matching is efficient in speed and accuracy and can be successfully applied to co-allocate jobs across different clusters.

A New Task Graph model for Mapping Message Passing Applications

Concepció Roig, Ana Ripoll, and Fernando Guirado
December 2007 (Vol. 18, No. 12) pp. 1740-1753

Abstract:The exploitation of parallelism in a message-passing platform implies a previous modelling phase of the parallel application as a task graph, which properly reflects its temporal behaviour.

In this paper, we analyse the classical task graph models of the literature and their drawbacks when modelling message-passing programs with arbitrary task structure. We define a new task graph model called TTIG (Temporal Task Interaction Graph) that integrates the classical models used in the literature.

The TTIG allows to explicitly capture the ability of concurrency of adjacent tasks for applications where adjacent tasks can communicate at any point inside them. A mapping strategy is developed from this model, that minimizes the expected execution time by properly exploiting task parallelism.

The effectiveness of this approach has been proved in different experimentation scopes for a wide range of message-passing applications.