Optimization techniques for distributed task-based programming models

Abstract

(English) In HPC, task-based models have gained prominence via the adoption of tasks in OpenMP, as an asynchronous and platform-agnostic high-performance and productive model by annotating existing code, transforming it into a parallel version. A program is expressed as a Directed Acyclic Graph (DAG), whose vertices are units of code called tasks. Edges between tasks represent dependencies between them, and tasks with no logical relationship can be executed concurrently. The task graph is independent of the targeted platform architecture, making these models suitable for concurrent execution on a broad spectrum of platforms such as multi-core SMPs or offloaded to GPUs, FPGAs, or accelerators. Several initiatives explore distributed-tasking approaches, which use the task model to decompose the application across multiple nodes with distributed memory. The advantage is that the application is expressed in a simple and clean manner that reflects only the computations and dependencies. Unfortunately, the distributed tasking approaches suffer from poor efficiency and scalability, which hinder their adoption by the HPC community. This is mainly due to the overhead of task creation and dependency graph construction, which are usually sequential. This thesis proposes two techniques to address this problem. Our first approach relates to task nesting, which mitigates the sequential bottleneck by building the full dependency graph in parallel using multiple concurrently executing parent tasks. A key limitation of task nesting is that a task cannot be created until all its accesses and its descendants’ accesses are known. Current approaches to work around this limitation either halt task creation and execution using an explicit taskwait barrier or substitute dependencies with artificial accesses known as sentinels. We introduce the auto clause, which indicates that the task may create subtasks that access unspecified memory regions, or it may allocate and return memory at addresses that are not yet known. Contrary to taskwait, our approach does not prevent the concurrent creation and execution of tasks, maintaining parallelism and allowing the scheduler to optimize load balance and data locality. In addition, all tasks can be given a precise specification of their own data accesses, unlike sentinels, resulting in a unified mechanism governing task ordering, program data transfers on distributed memory, and optimizing data locality, e.g. on NUMA systems. The auto clause, therefore, provides an incremental path to develop programs with nested tasks by removing the need for every parent task to have a complete specification of the accesses of its descendent tasks while reducing redundant information that can be time-consuming and error-prone to describe. Our second approach takes advantage of the iterative behaviour of many HPC applications, such as those that employ iterative methods or multi-step simulations. Most models construct the full unrolled task graph sequentially despite the fact that these applications create the same directed acyclic graph of tasks on each timestep. We define the programming model based on the taskiter clause, a recently introduced construct in the literature for iterative applications on SMP. We also describe the full runtime implementation to exploit this information to eliminate the sequential bottleneck and control messages while retaining the simplicity and productivity of the existing approach. We integrate both techniques into OmpSs-2@Cluster, the distributed tasking variant of OmpSs-2, and evaluate the performance on the MareNostrum 4 supercomputer.

(Català) En HPC, els models basats en tasques han guanyat prominència adoptant OpenMP com a model d'alt rendiment, productiu, asincrònic i agnòstic respecte a la plataforma dins del node. Un programa s'expressa com un Graf Acíclic Dirigit (DAG), els vèrtexs del qual són unitats de codi anomenades tasques. Les arestes entre les tasques representen dependències entre elles, i les tasques sense relacions lògiques poden executar-se concurrentment. El graf de tasques és independent de l'arquitectura de la plataforma objectiu, fent aquests models adequats per a l'execució concurrent en una àmplia gamma de plataformes, incloent multiprocessadors y acceleradors.

Diverses iniciatives estan explorant enfocaments de tasques distribuïdes, que utilitzen el model de tasca per descompondre l’aplicació en diversos nodes amb memòria distribuïda. L'avantatge d'aquest enfocament és que permet expressar l'aplicació de manera simple i clara, reflectint únicament els càlculs i les dependències. Malauradament, les implementacions actuals de tasques distribuïdes pateixen de baixa eficiència i escalabilitat, fet que dificulta la seva adopció per part de la comunitat de HPC. Això es deu principalment a l'alt cost de creació de tasques i a la construcció del graf de dependències, que generalment són seqüencials. Aquesta tesi proposa dues tècniques per solucionar aquest problema.

La nostra primera proposta es centra en la nidificació de tasques, que atenua el coll d'ampolla seqüencial mitjançant la construcció paral·lela del graf complet de dependències usant múltiples tasques mestres que s'executen concurrentment. Una limitació clau de la nidificació de tasques és que no es pot crear una tasca fins que no se'n coneguin tots els accessos i els dels seus descendents. Els enfocaments actuals per a resoldre aquesta limitació detenen la creació i execució de tasques fent servir una barrera explícita (taskwait) o substituint les dependències amb accessos artificials anomenats sentinelles. Proposem la clàusula auto, que indica que la tasca pot crear subtasques que accedeixin a regions de memòria no especificades, o pot assignar i retornar memòria en adreces encara desconegudes. A diferència de una barrera explicita (taskwait), el nostre enfocament no impedeix la creació i execució concurrent de tasques, mantenint el paral·lelisme i permetent al programador optimitzar el balanç de càrrega i la localització de dades. A més, totes les tasques poden tenir una especificació precisa dels seus propis accessos a dades, a diferència dels sentinelles, resulta en un mecanisme unificat que governa l’ordre de les tasques, les transferències de dades del programa en memòria distribuïda i l’optimització de la localització de dades, per exemple en sistemes NUMA. Així, la clàusula auto proporciona un camí incremental per al desenvolupament de programes de tasques niades, eliminant la necessitat que cada tasca pare tingui una especificació completa dels accessos de les seves tasques descendents, tot reduint la informació redundant que pot ser tediosa i propensa a errors.

La segona proposta nostra aprofita el comportament iteratiu de moltes aplicacions HPC, com ara aquelles que utilitzen mètodes iteratius o simulacions en múltiples etapes. Malgrat que aquestes aplicacions generen el mateix graf acíclic dirigit de tasques en cada pas temporal, la majoria de models construeixen el graf complet de tasques de manera seqüencial. Definim el model de programació basat en la clàusula taskiter, una proposta recentment introduït a la literatura per a aplicacions iteratives en plataformes SMP. També descrivim la implementació completa en temps d'execució per aprofitar aquesta informació per eliminar el coll d'ampolla seqüencial i els missatges de control, preservant la simplicitat i productivitat de l'aproximació existent. Integrem ambdues tècniques a OmpSs-2@Cluster, la variant de tasques distribuïdes de OmpSs-2, i avaluem el rendiment al superordinador MareNostrum 4.

(Español) En HPC, los modelos basados en tareas han ganado prominencia adoptando OpenMP como un modelo de alto rendimiento, productivo, asincrónico y agnóstico respecto a la plataforma dentro del nodo. Un programa se expresa como un Grafo Acíclico Dirigido (DAG), cuyos vértices son unidades de código llamadas tareas. Los arcos entre las tareas representan dependencias entre ellas, y las tareas sin relaciones lógicas pueden ejecutarse concurrentemente. El grafo de tareas es independiente de la arquitectura de la plataforma objetivo, haciendo estos modelos adecuados para la ejecución concurrente en una amplia gama de plataformas, incluyendo multiprocesadores y aceleradores.

Diversas iniciativas están explorando enfoques de tareas distribuidas, que utilizan el modelo de tarea para descomponer la aplicación en varios nodos con memoria distribuida. La ventaja de este enfoque es que permite expresar la aplicación de manera simple y clara, reflejando únicamente los cálculos y las dependencias. Desafortunadamente, las implementaciones actuales de tareas distribuidas sufren de baja eficiencia y escalabilidad, lo que dificulta su adopción por parte de la comunidad de HPC. Esto se debe principalmente al alto costo de creación de tareas y a la construcción del grafo de dependencias, que generalmente son secuenciales. Esta tesis propone dos técnicas para solucionar este problema.

Nuestra primera propuesta se centra en la anidación de tareas, que atenúa el cuello de botella secuencial mediante la construcción paralela del grafo completo de dependencias usando múltiples tareas maestras que se ejecutan concurrentemente. Una limitación clave de la anidación de tareas es que no se puede crear una tarea hasta que se conozcan todos los accesos de memoria de la misma y de sus descendientes. Los enfoques actuales para resolver esta limitación detienen la creación y ejecución de tareas utilizando una barrera explícita (taskwait) o sustituyendo las dependencias con accesos artificiales llamados centinelas. Proponemos la cláusula auto, que indica que la tarea puede crear subtareas que accedan a regiones de memoria no especificadas, o puede asignar y devolver memoria en direcciones aún desconocidas. A diferencia de una barrera explícita (taskwait), nuestro enfoque no impide la creación y ejecución concurrente de tareas, manteniendo el paralelismo y permitiendo al programador optimizar el balance de carga y la localización de datos. Además, todas las tareas pueden tener una especificación precisa de sus propios accesos a datos, a diferencia de los centinelas, resultando en un mecanismo unificado que gobierna el orden de las tareas, las transferencias de datos del programa en memoria distribuida y la optimización de la localización de datos, por ejemplo en sistemas NUMA. Así, la cláusula auto proporciona un camino incremental para el desarrollo de programas de tareas anidadas, eliminando la necesidad de que cada tarea padre tenga una especificación completa de los accesos de sus tareas descendientes, reduciendo a su vez la información redundante que puede ser tediosa y propensa a errores.

Nuestra segunda propuesta aprovecha el comportamiento iterativo de muchas aplicaciones HPC, como aquellas que utilizan métodos iterativos o simulaciones en múltiples etapas. A pesar de que estas aplicaciones generan el mismo grafo acíclico dirigido de tareas en cada paso temporal, la mayoría de los modelos construyen el grafo completo de tareas de manera secuencial. Definimos el modelo de programación basado en la cláusula taskiter, una propuesta recientemente introducida en la literatura para aplicaciones iterativas en plataformas SMP. También describimos la implementación completa en tiempo de ejecución para aprovechar esta información y eliminar el cuello de botella secuencial y los mensajes de control, preservando la simplicidad y productividad del enfoque existente. Integramos ambas técnicas en OmpSs-2@Cluster, y evaluamos el rendimiento en el superordenador MareNostrum.