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

Abstract

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.