Performance Improvement Methodology based on Divisible Load Theory for Data Intensive Applications

Abstract

L'augment de la quantitat de dades que necessiten ser processades actualment, representa un dels majors reptes a l' ambit de la computaci o. Aix o ha perm es el creixement d'aplicacions amb requeriments especials conegudes com aplicacions intensives en dades. En general, per afavorir l'execuci o en paral lel de aquest tipus d'aplicacions, les dades d'entrada son partits en trossos m es petits que poden ser processats individualment. No obstant aix o, en molts casos, aquestes aplicacions mostren problemes graus de rendiment, deguts principalment a desequilibris de c arrega, l' us ine cient dels recursos de c omput disponibles, i inadequades pol tiques de partici o i distribuci o de les dades. A m es, l'impacte d'aquests problemes de rendiment es pot veure acrescut pel comportament din amic de l'aplicaci o. Aquest treball proposa una metodologia per a millorar, din amicament, el rendiment d'aplicacions intensives en dades, basat en: (i) l'adaptaci o de la grand aria i nombre de les particions de dades amb la nalitat de reduir el temp d'execuci o total; i (ii) l'adaptaci o del nombre de nodes de c omput per aconseguir una execuci o e cient. Proposem observar el comportament de l'aplicaci o per cada iteraci o (o consulta) i utilitzar les dades recollides per a ajustar din amicament el seu rendiment. La metodologia assumeix que cada execuci o inclou m ultiples consultes relacionades sobre una unica c arrega de treball partida. L'ajust del factor de partici o de la c arrega de treball es fa mitjan cant la de nici o de la grand aria inicial dels trossos de dades; la modi caci o de la pol tica de plani caci o (per a enviar primerament els trossos amb major temps d'execuci o); la divisi o dels trossos amb major temps d'execuci o; i el agrupament de trossos de dades amb temps de c omput massa curts. Els criteris per a decidir si el trossos es divideixen o es agrupen estan basats en els temps d'execuci o associats a cada tros (com el temps mitj a i la desviaci o est andard) aix com tamb e en el nombre de nodes de c omputs que s'estan utilitzant. A m es a m es, el referent a l' us de recursos de c omput es va abordar mitjan cant l'avaluaci o din amica del rendiment de l'aplicaci o, juntament amb l'estimaci o i modi caci o del nombre de nodes de processament que es puguin utilitzar e cientment. Hem avaluat la nostra proposta usant aplicacions intensives en dades reals i sint etiques. Aix com tamb e hem analitzat les expressions anal tiques propostes mitjan cant simulaci o. Despr es d'aplicar la nostra metodologia, hem obtingut resultats prometedors en la reducci o del temps total d'execuci o i l' us e cient dels recursos. Paraules claus: balanceig de c arrega; an alisi i sintonitzaci o din amic del rendiment; aplicacions intensives en dades; c arrega arbitr ariament divisible.

La gran cantidad de datos que recientemente necesitan ser procesados, representa uno de los mayores retos en el campo de la computaci on. Esto ha conllevado al crecimiento de aplicaciones con requerimientos especiales conocidas como aplicaciones intensivas en datos. En general, para facilitar la ejecuci on en paralelo de aplicaciones intensivas en datos, los datos de entrada son divididos en trozos m as peque~nos que pueden ser procesados individualmente. Sin embargo, en muchos casos, estas aplicaciones muestran graves problemas de rendimiento debidos principalmente a desbalances de carga, uso ine ciente de los recursos de c omputo disponibles, e inapropiadas pol ticas de partici on y distribuci on de los datos. Adem as, el impacto de dichos problemas de rendimiento puede depender del comportamiento din amico de la aplicaci on. Este trabajo propone una metodolog a para mejorar, din amicamente, el rendimiento de aplicaciones intensivas en datos, en base a: (i) adaptar el tama~no y el n umero de las particiones de datos con el n de reducir el tiempo de ejecuci on total; y (ii) adaptar el n umero de nodos de c omputo para conseguir una ejecuci on e ciente. Proponemos monitorizar el comportamiento de la aplicaci on para cada iteraci on (o consulta) y usar los datos recogidos para ajustar din amicamente el rendimiento de la aplicaci on. La metodolog a asume que una sola ejecuci on incluye m ultiples consultas relacionadas sobre una misma carga de trabajo particionada. El ajuste del factor de partici on de la carga de trabajo es llevado a cabo a trav es de la de nici on del tama~no inicial de los trozos de datos; la modi caci on de la pol tica de plani caci on, para enviar primero los trozos de datos con los tiempos de procesamiento m as largos; la divisi on de dichos trozos de datos; y el agrupamiento de trozos de datos con tiempos de c omputo muy cortos. Los criterios para decidir dividir o agrupar trozos est an basados en los tiempos de ejecuci on asociados a cada pieza (tiempo medio y desviaci on est andar) y en el n umero de elementos de c omputo que est an siendo utilizados. Adicionalmente, lo inherente al uso de los recursos se abord o mediante la evaluaci on din amica del rendimiento de la aplicaci on, junto con la estimaci on y consiguiente modi caci on del n umero de nodos de procesamiento que pueden ser utilizados e cientemente. Hemos evaluado nuestra propuesta usando aplicaciones intensivas en datos reales y sint eticas. As como tambi en hemos analizado las expresiones anal ticas propuestas a trav es de simulaci on. Luego de aplicar nuestra metodolog a, hemos obtenido resultados prometedores en la reducci on del tiempo total de ejecuci on y el uso e ciente de los recursos. Palabras clave: balanceo de carga; an alisis y sintonizaci on din amico del rendimiento; aplicaciones intensivas en datos; carga arbitrariamente divisible.

The recent large amount of data needing to be processed represents one of the major challenges in the computational eld. This fact led to the growth of specially designed applications known as data-intensive applications. In general, to ease the parallel execution of data-intensive applications input data is divided into smaller data chunks that can be processed separately. However, in many cases, these applications show severe performance problems mainly due to load imbalance, ine cient use of available resources, and improper data partition policies. In addition, the impact of these performance problems can depend on the dynamic behavior of the application. This work proposes a methodology to dynamically improve the performance of data-intensive applications based on: (i) adapting the size and the number of data partitions to reduce overall execution time; and (ii) adapting the number of processing nodes to achieve an e cient execution. We propose to monitor the application behavior for each iteration (query) and use gathered data to dynamically tune the performance of the application. The methodology assumes that a single execution includes multiple related queries on the same partitioned workload. The adaptation of the workload partition factor is addressed through the de nition of the initial size for the data chunks; the modi cation of the scheduling policy to send rst data chunks with large processing times; dividing of the data chunks with the biggest associated computation times; and joining of data chunks with small computation times. The criteria for dividing or gathering chunks are based on the chunks' associated execution time (average and standard deviation) and the number of processing elements being used. Additionally, the resources utilization is addressed through the dynamic evaluation of the application performance and the estimation and modi cation of the number of processing nodes that can be e ciently used. We have evaluated our strategy using a real and a synthetic data-intensive application. Analytical expressions have been analyzed through simulation. Applying our methodology, we have obtained encouraging results reducing total execution times and e cient use of resources. Keywords: load balancing; dynamic performance analysis and tuning; Data-intensive applications; arbitrarily divisible load.