Coscheduling Techniques for Non-Dedicated Cluster Computing

Abstract

Los esfuerzos de esta tesis se centran en onstruir una máquina virtual sobre un sistema Cluster que proporcione la doble funcionalidad de ejecutar eficientemente tanto trabajos tradicionales (o locales) de estaciones de trabajo<br/>así como aplicaciones distribuidas. <br/>Para solucionar el problema, deben tenerse en cuenta dos importantes consideraciones: <br/>* Como compartir y planificar los recursos de las diferentes estaciones de trabajo (especialmente la CPU) entre las aplicaciones locales y distribuidas. <br/><br/>* Como gestionar y controlar la totalidad del sistema para<br/> conseguir ejecuciones eficientes de ambos tipos de aplicaciones.<br/><br/>Coscheduling es el principio básico usado para compartir<br/>y planificar la CPU. Cosche-duling se basa en la reducción<br/>del tiempo de espera de comunicación de aplicaciones distribuidas,<br/>planificando simultáneamente todas (o un subconjunto de)<br/>las tareas que la componen. Por lo tanto, mediante el uso<br/>de técnicas de coscheduling, únicamente se puede incrementar<br/>el rendimiento de aplicaciones distribuidas con comunicación<br/>remota entre las tareas que la componen. <br/><br/>Las técnicas de Coscheduling se clasifican en dos grandes<br/>grupos: control-explícito y control-implícito. Esta clasificación<br/>se basa en la forma de coplanificar las tareas distribuidas.<br/>En control-explícito, la coplanificación es realizada por<br/>procesos y (o) procesadores especializados. En cambio, en<br/>control-implícito, las técnicas de coscheduling se realizan<br/>tomando decisiones de planificación localmente, dependiendo<br/>de los eventos que ocurren en cada estación de trabajo. <br/><br/>En este proyecto se presentan dos mecanismos de coscheduling,<br/>los cuales siguen las dos diferentes filosofías explicadas<br/>anteriormente, control-implícito y control-explí-cito. También<br/>proporcionan características adicionales incluyendo un buen<br/>rendimiento en la ejecución de aplicaciones distribuidas,<br/>ejecución simultánea de varias aplicaciones distribuidas,<br/>bajo overhead y también bajo impacto en el rendimiento de<br/>la carga local.<br/><br/>También se presenta un modelo de coscheduling, el cual proporciona<br/>una base teórica para el desarrollo de nuevas técnicas de<br/>control-implícito. La técnica de control-implícito propuesta<br/>se basa en este modelo. <br/><br/>El buen comportamiento de las técnicas de coscheduling presentadas<br/>en este trabajo se analiza en primer lugar por medio de<br/>simulación. También se ha realizado un gran esfuerzo en<br/>la implementación de estas técnicas de coscheduling en un<br/>Cluster real. El estudio de los resultados obtenidos proporciona<br/>una orientación importante para la investigación futura<br/>en el campo de coscheduling. <br/><br/>En la experimentación en el Cluster real, se han utilizado<br/>varios benchmarks distribuidos con diversos patrones de<br/>comunicación de paso de mensajes: regulares e irregulares,<br/>anillos lógicos, todos-a-todos, etc. También se han utilizado<br/>benchmarks que medían diferentes primitivas de comunicación,<br/>tales como barreras, enlaces uni y bidireccionales, etc.<br/>El uso de esta amplia gama de aplicaciones distribuidas<br/>ha servido para demostrar la aplicabilidad de las técnicas<br/>de coscheduling en computación distribuida basados en Clusters.

Efforts of this Thesis are centered on constructing a Virtual<br/>Machine over a Cluster system that provides the double functionality<br/>of executing traditional workstation jobs as well as distributed<br/>applications efficiently.<br/><br/>To solve the problem, two major considerations must be addressed:<br/><br/>* How share and schedule the workstation resources (especially<br/> the CPU) between the local and distributed applications. <br/><br/>* How to manage and control the overall system for the efficient<br/> execution of both application kinds. <br/><br/>Coscheduling is the base principle used for the sharing and<br/>scheduling of the CPU. Coscheduling is based on reducing<br/>the communication waiting time of distributed applications<br/>by scheduling their forming tasks, or a subset of them at<br/>the same time. Consequently, non-communicating distributed<br/>applications (CPU bound ones) will not be favored by the<br/>application of coscheduling. Only the performance of distributed<br/>applications with remote communication can be increased<br/>with coscheduling.<br/><br/>Coscheduling techniques follow two major trends: explicit<br/>and implicit control. This classification is based on the<br/>way the distributed tasks are managed and controlled. Basically,<br/>in explicit-control, such work is carried out by specialized<br/>processes and (or) processors. In contrast, in implicit-control,<br/>coscheduling is performed by making local scheduling decisions<br/>depending on the events occurring in each workstation.<br/><br/>Two coscheduling mechanisms which follow the two different<br/>control trends are presented in this project. They also<br/>provide additional features including usability, good performance<br/>in the execution of distributed applications, simultaneous<br/>execution of distributed applications, low overhead and<br/>also low impact on local workload performance. The design<br/>of the coscheduling techniques was mainly influenced by<br/>the optimization of these features.<br/><br/>An implicit-control coscheduling model is also presented.<br/>Some of the features it provides include collecting on-time<br/>performance statistics and the usefulness as a basic scheme<br/>for developing new coscheduling policies. The presented<br/>implicit-control mechanism is based on this model.<br/><br/>The good scheduling behavior of the coscheduling models presented<br/>is shown firstly by simulation, and their performance compared<br/>with other coscheduling techniques in the literature. A<br/>great effort is also made to implement the principal studied<br/>coscheduling techniques in a real Cluster system. Thus,<br/>it is possible to collect performance measurements of the<br/>different coscheduling techniques and compare them in the<br/>same environment. The study of the results obtained will<br/>provide an important orientation for future research in<br/>coscheduling because, to our knowledge, no similar work<br/>(in the literature) has been done before. <br/><br/>Measurements in the real Cluster system were made by using<br/>various distributed benchmarks with different message patterns:<br/>regular and irregular communication patterns, token rings,<br/>all-to-all and so on. Also, communication primitives such<br/>as barriers and basic sending and receiving using one and<br/>two directional links were separately measured. By using<br/>this broad range of distributed applications, an accurate<br/>analysis of the usefulness and applicability of the presented<br/>coscheduling techniques in Cluster computing is performed.