DF‐DTM: Dynamic Task Memoization and reuse in dataflow

Citations Over TimeTop 18% of 2018 papers

Abstract

Summary Instruction Reuse is a technique adopted in Von Neumann architectures that improves performance by avoiding redundant execution of instructions when the result to be produced can be obtained by searching an input/output memoization table for such instruction. Trace reuse can be applied to traces of instructions in a similar fashion. However, those techniques are yet to be studied in the context of the Dataflow 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), a technique that allows the reuse of both nodes and subgraphs in dataflow, which are analogous to instructions and traces, respectively. The potential of DF‐DTM is evaluated by a series of experiments that analyze the behavior of redundant tasks in five relevant benchmarks, where up to 99.70 % of the instantiated tasks could be reused. Moreover, this paper evaluates how reuse rates can be affected by limiting subgraph size, memoization table size, task granularity, and problem size, showing that DF‐DTM can yield good reuse rates in more realistic environments.

Related Papers

• → The LSTS toolchain for networked vehicle systems(2013)138 cited
• → Software Numerical Instability Detection and Diagnosis by Combining Stochastic and Infinite-Precision Testing(2016)11 cited
• → Stream machine learning on vehicle data(2018)2 cited
• → SKilLed communication for toolchains(2015)
• → Finite Element Method Based Toolchain for Simulation of Proximity Estimation Using Electronic Skin(2023)