DF-DTM :explorando redundância de tarefas em dataflow

Instruction reuse is an optimization technique that can be used in Von Neumann architectures. This technique improves performance by avoiding the execution of redundant instructions, when the result to be produced by them can be obtained by searching a historical input/output table. Trace reuse can be applied to traces of instructions in a similar fashion. However, these techniques still need to be studied in the context of the Dataflow [1–4] model, which has been gaining traction in the high-performance computing community, due to its inherent parallelism. Dataflow programs are represented by directed graphs where nodes are instructions or tasks and edges denote data dependencies between tasks. This work presents Dataflow Dynamic Task Memoization (DF-DTM) technique, which is inspired by the Von Neumann architecture reuse technique known as DTM [5] (Dynamic Trace Memoization). DF-DTM allows the reuse of nodes and subgraphs in Dataflow models, which are analogous to instructions and traces in traditional models, respectively. We modified the Python version of the Dataflow library, Sucuri[6], to implement the DF-DTM technique. The potential of the DF-DTM is evaluated by a series of experiments that analyze the behavior of redundant tasks in five relevant benchmarks: Conway’s game of life (GoL), longest common sub-sequence (LCS), a cryptography application using the Triple DES standard (3-DES), a word counting application that follows a MapReduce (MR) model and the unbounded knapsack problem (KS). Our results shows a remarkable potential redundancy rate of approximate 98.83%, 54.73%, 72.35%, 99.73% for the benchmarks applications LCS, MR, 3-DES and GoL, respectively.Reutilização de instruções é uma técnica de otimização que pode ser utilizada em arquiteturas de Von Neumann. Esta técnica gera ganho de desempenho ao evitar que instruções redundantes executem, quando os resultados a serem produzidos por elas podem ser obtidos pesquisando uma tabela histórica de entrada/saída. A reutilização de traços pode ser aplicada aos traços de instruções de forma semelhante. No entanto, essas técnicas ainda precisam ser estudadas no contexto do modelo Dataflow[1–4], que vem ganhando notoriedade na comunidade de computação de alto desempenho devido ao seu paralelismo inerente. Os programas Dataflow são representados por grafos direcionados, onde os nós são instruções (tarefas dataflow) e as arestas denotam dependências de dados entre estas tarefas. Este trabalho apresenta a técnica Dataflow Dynamic Task Memoization (DF-DTM), a qual é inspirada na técnica de reúso de instruções em arquiteturas Von Neumann, conhecida como DTM[5] (Dynamic Trace Memoization). DF-DTM permite a reutilização de nós e subgrafos em modelos Dataflow, que são análogos às instruções e traços em modelos tradicionais, respectivamente. Modificamos a versão Python da biblioteca Dataflow, Sucuri[6], para implementar a técnica DF-DTM. O potencial da DF-DTM é avaliado por uma série de experimentos que analisam o comportamento de tarefas redundantes em cinco benchmarks relevantes: Conway’s Game of Life (GoL), longest common sub-sequence (LCS), uma aplicação de criptografia utilizando o padrão Triple DES (3-DES), uma aplicação de contagem de palavras que segue um modelo MapReduce (MR) e o problema da mochila sem limites (KS). Nossos resultados mostram uma notável taxa de redundância potencial de aproximadamente 98, 83%, 54, 73%, 72, 35%, 99, 73% para as aplicações benchmarks LCS, MR, 3-DES e GoL, respectivamente