Dynamic load balancing for hybrid applications

It is well known that load imbalance is a major source of efficiency loss in HPC (High Performance Computing) environments. The load imbalance problem has very different sources, from static ones related to the data distribution to very dynamic ones, for example, the noise of the system. In this thesis, we present DLB: Dynamic Load Balancing library. DLB is a framework to improve the efficient use of the computational resources of a computational node. With DLB we offer a dynamic solution to load imbalance problems. DLB is applied at runtime and does not need previous information to solve load imbalance problems, for this reason, it can deal with load imbalances coming from any source. The DLB framework includes a novel load balancing algorithm: LeWI (Lend When Idle). The main idea of LeWI is to use the computational resources assigned to a process or thread when it is idle, to speed up another process running on the same node that it is still doing computation. We will see how this idea although being quite simple it is powerful and flexible to obtain an efficient use of resources close to the ideal one. En aquesta tesi presentem DLB (Dynamic Load Balancing), una llibreria que ajuda a fer un us eficient dels recursos d'un node de càlcul. Dins de DLB hem implementat un algoritme de balanceig original: LeWI (Lend When Idle). LeWI està basat en la idea que quan un procés MPI està esperant en una crida MPI bloquejant els recursos de càlcul que té assignats no estan ocupats. Per tant, aquests recursos els poden fer servir altres processos que s'estiguin executant al mateix node per acabar el seu càlcul més ràpid. DLB intercepta les crides MPI i canvia el nombre de threads OpenMP com calgui. Quan un procés arriba a una crida MPI bloquejant cedirà les seves CPUs a un altre procés que s'estigui executant al mateix node. Quan el primer procés MPI acabi la crida MPI bloquejant recuperarà les seves CPUs. Hem implementat LeWI a DLB i avaluat el seu rendiment, amb aquesta avaluació hem vist que DLB i LeWI poden millorar el rendiment d'aplicacions híbrides. LeWI pot balancejar aplicacions amb patrons regulars o irregular de desbalanceig sense modificar l'aplicació. Hem observat que la mal·leabilitat del model de programació i de l'aplicació pot afectar el rendiment que s'obté amb l'algoritme de balanceig. Tot i que OpenMP és mal·leable té una limitació, el nombre de threads només es pot canviar fora d'una regió paral·lela. El model de programació OmpSs és més mal·leable, ja que el nombre de threads es pot canviar en qualsevol punt. L'avaluació ens va demostrar que la mal·leabilitat del model de programació que es fa servir te un impacte substancial en el rendiment que obté l'algoritme de balanceig. Per defecte els diferents processos MPI es distribueixen de manera consecutiva entre els nodes de càlcul, però hem observat que en les aplicacions científiques la tendència és que els processos més carregats siguin consecutius. Per aquest motiu fer una distribució cíclica (Round Robin) dels processos MPI entre els nodes permet a l'algoritme de balanceig obtenir un millor rendiment. També hem observat que lligar els threads a CPUs o no fer-ho afecta al rendiment de les aplicacions i en especial quan es fa servir l'algoritme de balanceig. Per a permetre que LeWI pugui gestionar CPUs concretes hem modificat la llibreria perquè utilitzi mascares de CPUs. Amb l'avaluació hem vist que lligar els threads a CPUs té un impacte important en el rendiment que s'obté. Però també que l'impacte depèn de la mida del node (nombre de CPUs per node) i l'estructura de la memòria. Hem integrat DLB amb un runtime parallel, Nanos++. Aquesta integració ens ha mostrat el potencial d'aquest tipus de col·laboracions entre runtimes. Ens ha permès identificar els punts clau de coordinació necessaris i ens ha demostrat que DLB està preparat per a ser integrat amb altres runtimes paralels. L'avaluació ha mostrat el potencial d'aquest tipus d'integracions i col·laboracions. Finalment, hem fet una avaluació exhaustiva de l'entorn i l'algoritme amb una aplicació en producció: Alya. Hem vist que podem reduir fins a un 40% el temps d'execució per a situacions amb un alt desbalanceig. I en el cas de situacions sense desbalanceig l'ús de DLB no penalitza el rendiment de l'aplicació. També hem vist que el rendiment de la paral·lelització OpenMP de l'aplicació té un alt impacte en el rendiment de DLB i LeWI. Hem pogut provar que DLB i LeWI estan llestos per a ser utilitzats en execucions reals. I en executar proves d'escalabilitat fins a 16.000 cores hem vist que no només LeWI pot escalar fins a milers de cores sinó que l'algoritme de balanceig que només s'aplica dins del node de càlcul pot millorar el rendiment d'execucions en milers de nodes de càlcul.