Planificador consciente del almacenamiento para Multiwork ows en Cluster Galaxy

Author

Acevedo Giménez, César Esteban

Director

Hernández Budé, Porfidio

Espinosa Morales, Antonio Miguel

Date of defense

2017-07-19

ISBN

9788449074455

Pages

123 p.



Department/Institute

Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius

Abstract

En l'àmbit bioinformàtic, l'experimentació es realitza a través de seqüències d'execucions d'aplicacions, cada aplicació utilitza com a arxiu d'entrada el generat per l'aplicació anterior. Aquest procés d'anàlisi format per una llista d'aplicacions descrivint una cadena de dependència es diu Workflow. Dues característiques rellevants dels workflows bioinformàtics, fan referència al maneig de grans volums de dades i de la complexitat de les dependències de dades. Molts dels gestors de recursos actuals, ignoren la ubicació dels arxius, això implica un elevat cost si els elements de processament no estan propers als arxius i se'ls ha de moure. El model de graf dirigit acíclic (DAG), utilitzat per representar l'ordre d'execució dels treballs del workflow, no ajuda a establir la millor ubicació dels arxius d'entrada o temporals per a una execució eficient. La solució per a aquest desafiament, pot ser la planificació de recursos conscient de l'emmagatzematge, on una estratègia intelligent de collocació d'arxius, afegida a una planificació de recursos d'acord a aquest coneixement; contribuirà a evitar els períodes d'inactivitat en els sistemes, causats pels temps d'espera d'arxius en els elements de processament. Amb la capacitat de còmput actual dels clústers, és possible que múltiples workflows puguin ser executats en parallel. A més, els clústers permeten que els multiworkflows, puguin compartir els arxius d'entrada i temporals en la jerarquia d'emmagatzematge. Proposem una jerarquia d'emmagatzematge composta pel sistema d'arxius distribuït, un RamDisk Local, Disc Local i Disc d'Estat Sòlid (SSD) Local. A fi de resoldre l'assignació d'aplicacions de multiworkflows als recursos del clúster, vam estendre l'heurística basada en llista per multiworkflows anomenada HEFT (Heterogeneuos Earliest Finish Time). Aquesta comprèn dues fases: primer es realitza una fase de priorització de tasques, per a posteriorment realitzar la selecció de processadors, que consisteix a assignar les aplicacions al node que minimitza el temps de finalització de cadascuna d'elles. El planificador conscient de l'emmagatzematge proposat, considera ubicar els arxius en la jerarquia d'emmagatzematge abans de començar l'execució. La pre-ubicació d'arxius en els nodes de còmput fa que les aplicacions que les utilitzen, puguin ser assignades al mateix node que els arxius, reduint el temps d'accés a disc. Per determinar la ubicació inicial dels arxius d'entrada i temporals, el planificador realitza la fusió de tots els workflows en un sol meta-workflow, a continuació, l'algoritme estableix segons les precedències d'aplicacions, mida dels arxius i grau de compartició de els mateixos; l'emmagatzematge adequat de cada arxiu dins de la jerarquia. L'objectiu del nostre treball és implementar una nova política de planificació conscient de l'emmagatzematge per multiworkflows que millori el temps de makespan d'aplicacions amb còmput intensiu de dades. Per avaluar l'escalabilitat de la política de planificació i a més poder comparar-la amb altres polítiques clàssiques de la literatura, hem utilitzat simuladors. Aquest és un mètode bastant comú per validar heurístiques de planificació i estalviar temps de còmput buscant la millor opció. Per a això, hem extès WorkflowSim i l'hem dotat d'un planificador conscient de la jerarquia d'emmagatzematge. El planificador resultant ha sigut validat en diversos escenaris, amb una càrrega composta per workflows sintètics de bioinformàtica, implementats a partir de la caracterització d'aplicacions bioinformàtiques reals, i workflows de referència àmpliament utilitzats, com Montage i Epigenomics, ja que són workflows que generen una gran quantitat d'arxius temporals. Per validar la nostra proposta hem utilitzat el planificador en dos escenaris: sistemes de clúster real de 128 nuclis i simulador de clúster en WorkflowSim fins a 1024 nuclis. L'escenari real, llanço millores de makespan de fins a 70%. A l'escenari simulat, la millora de makespan va ser del 69% amb errors entre 0,9% i 3%.


En el ámbito bioinformático, la experimentación se realiza a través de secuencias de ejecuciones de aplicaciones, cada aplicación utiliza como archivo de entrada el generado por la aplicación anterior. Este proceso de análisis formado por una lista de aplicaciones describiendo una cadena de dependencia se llama Workflow. Dos características relevantes de los workflows bioinformáticos, hacen referencia al manejo de grandes volúmenes de datos y a la complejidad de las dependencias de datos. Muchos de los gestores de recursos actuales, ignoran la ubicación de los archivos, esto implica un elevado costo si los elementos de procesamiento no están próximos a los archivos y hay que moverlos. El modelo de grafo dirigido acíclico (DAG), utilizado para representar el orden de ejecución de los trabajos del workflow, no ayuda a establecer la mejor ubicación de los archivos de entrada o temporales para una ejecución eficiente. La solución para este desafío, puede ser la planificación de recursos consciente del almacenamiento, donde una estrategia inteligente de colocación de archivos, añadida a una planificación de recursos acorde a este conocimiento; contribuirá a evitar los periodos de inactividad en los sistemas, causados por los tiempos de espera de archivos en los elementos de procesamiento. Con la capacidad de cómputo actual de los clústers, es posible que múltiples workflows puedan ser ejecutados en paralelo. Además, los clústers permiten que los multiworkflows, puedan compartir los archivos de entrada y temporales en la jerarquía de almacenamiento. Proponemos una jerarquía de almacenamiento compuesta por el sistema de archivos distribuido, una RamDisk Local, Disco Local y Disco de Estado Solido (SSD) Local. Con objeto de resolver la asignación de aplicaciones de multiworkflows a los recursos del clúster, extendimos la heurística basada en lista para multiworkflows llamada HEFT (Heterogeneuos Earliest Finish Time). Esta comprende dos fases: primero se realiza una fase de priorización de tareas, para posteriormente realizar la selección de procesadores, que consiste en asignar las aplicaciones al nodo que minimiza el tiempo de finalización de cada una de ellas. El planificador consciente del almacenamiento propuesto, considera ubicar los archivos en la jerarquía de almacenamiento antes de comenzar la ejecución. La pre-ubicación de archivos en los nodos de cómputo hace que las aplicaciones que las utilizan, puedan ser asignadas al mismo nodo que los archivos, reduciendo el tiempo de acceso a disco. Para determinar la ubicación inicial de los archivos de entrada y temporales, el planificador realiza la fusión de todos los workflows en un solo meta-workflow, a continuación, el algoritmo establece según las precedencias de aplicaciones, tamaño de los archivos y grado de compartición de los mismos; el almacenamiento adecuado de cada archivo dentro de la jerarquía. El objetivo del trabajo es implementar una política de planificación consciente del almacenamiento para multiworkflows que mejore el makespan de aplicaciones con cómputo intensivo de datos. Para evaluar la escalabilidad de la propuesta y compararla con otras políticas de la literatura, utilizamos simuladores. Este es un método común para validar heurísticas de planificación y ahorrar tiempo de cómputo buscando la mejor opción. Para ello, extendimos WorkflowSim dotándolo de un planificador consciente de la jerarquía de almacenamiento. El trabajo fue validado, con workflows sintéticos, implementados a partir de la caracterización de aplicaciones bioinformáticas reales, y workflows ampliamente utilizados como Montage y Epigenomics debido a que generan una gran cantidad de archivos temporales. La experimentación se realizó en dos escenarios: sistemas de clúster real de 128 núcleos y simulador de clúster en WorkflowSim hasta 1024 núcleos. El escenario real, arrojo mejoras de makespan de hasta 70%. En el escenario simulado, la mejora de makespan fue del 69% con errores entre 0,9% y 3%.


In the bioinformatic field, experimentation is performed through sequential execution of applications, each application uses as input file the one generated by the previous application. This analysis process consisting of a list of applications describing a dependency chain is called Workflow. Two relevant characteristics of bioinformatic workflows refer to the handling of large volumes of data and the complexity of data dependencies. Many of the current resource managers ignore the location of the files, this implies a high cost if the processing elements are not close to the files and have to be moved. The direct acyclic graph (DAG) model, used to represent the execution order of workflow jobs, does not help to establish the best location of input or temporary data files for efficient execution. The solution to this challenge may be the data-aware scheduling, where an intelligent file placement strategy, added to a resource scheduling according to this knowledge; Will help prevent system downtime caused by the waiting time of data file on processing elements. With the current computing power of clusters, it is possible that multiple workflows to be executed in parallel. In addition, clusters allow multiworkflows to share input and temporal data files in the storage hierarchy. We propose a storage hierarchy composed by the distributed file system, a Local RamDisk, Local Disk and Local Solid State Disk (SSD). In order to solve the assignment of multiworkflows applications to the cluster resources, we extended the multiworkflow heuristic called HEFT (Heterogeneous Earliest Finish Time). This comprises two phases: first a task prioritization phase is performed, and then the processors selection is performed, which consists of assigning the applications to the node that minimizes the execution time of each one of them. The data-aware scheduler considers placing the files in the storage hierarchy before starting the execution. The data files pre-fetching on the compute nodes makes the applications that use them, can be assigned to the same node as the data files, reducing the access time to disk. To determine the initial location of the input and temporal data files, the scheduler performs the merging of all workflows into a single meta-workflow, then the algorithm sets according to application precedence, file size and sharing degree; The proper storage of each file within the hierarchy. The goal of the research is to implement a multi-workflow data-aware scheduler policy that improves the makespan of data-intensive applications. To evaluate the scalability of the proposal and to compare it with other policies in the literature, we use simulators. This is a common method for validating scheduling heuristics and saving computation time by looking for the best option. To do this, we extend WorkflowSim by providing it with a data-aware scheduler with a storage hierarchy. Our work was validated, with synthetic workflows, implemented from the characterization of real bioinformatics applications, and workflows benchmark as Montage and Epigenomics because they generate a large amount of temporal files. The experimentation was performed in two scenarios: real cluster system of 128 cores and a simulated cluster in WorkflowSim with up to 1024 cores. In the real scenario, we achieve a makespan improvement of up to 70%. In the simulated scenario, the makespan improvement was 69% with errors between 0.9% and 3%.

Keywords

Planificador; Scheduler; Multiworkflows; Emmagatzematge; Almacenamiento; Storage

Subjects

004 - Computer science and technology. Computing. Data processing

Knowledge Area

Tecnologies

Documents

ceag1de1.pdf

6.293Mb

 

Rights

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/

This item appears in the following Collection(s)