Scheduling Strategies for Dataflow Guided Execution Environments

A Sucuri é uma biblioteca em Python que provê programação dataflow através de uma sintaxe razoavelmente simples. Ela permite uma execução transparente em clusters explorando de forma natural o paralelismo. Na Sucuri, o programador instancia o grafo dataflow, onde cada nó está associado a uma função e as arestas representam as dependências de dados entre os nós. A implementação original da Sucuri, utiliza um escalonador centralizado, que gera altos custos de comunicação, principalmente em clusters com um elevado número de máquinas. Neste trabalho nós modificamos a Sucuri de modo que cada máquina no cluster tenha seu próprio escalonador. Antes da execução, o Grafo dataflow é particionado e os nós são distribuídos entre as máquinas do cluster. Em tempo de execução os trabalhadores livres de cada máquina recebem tarefas da fila de prontos de seu escalonador local. Quando uma máquina termina de executar sua lista de nós, ela irá solicitar às outras máquinas, que estejam sobrecarregadas, parte das tarefas que estejam nas suas filas de prontos. Os resultados experimentais confirmam que a solução pode reduzir o tempo gasto com comunicação e aumentar o desempenho em grandes clustersSucuri is a minimalistic Python library that provides dataflow programming through a reasonably simple syntax. It allows transparent execution on computer clusters and natural exploitation of parallelism. In Sucuri, programmers instantiate a dataflow graph, where each node is assigned to a function and edges represent data dependencies between nodes. The original implementation of Sucuri adopts a centralized scheduler, which incurs high communication overheads, specially in clusters with a large number of machines. In this paper we modify Sucuri so that each machine in a cluster will have its own scheduler. Before execution, the dataflow graph is partitioned, so that nodes can be distributed among the machines of the cluster. In runtime, idle workers will grab tasks from a ready queue in their local scheduler. When a machine finishes running their list of nodes, it will request the other machines, which are overloaded, the tasks of their ready queue. Experimental results confirm that the solution can reduce communication overheads, improving performance in larger cluster