DROPS

Document

DOI: 10.4230/OASIcs.NG-RES.2023.6

Throughput and Memory Optimization for Parallel Implementations of Dataflow Networks Using Multi-Reader Buffers

Authors: Martin Letras, Joachim Falk, and Jürgen Teich

Published in: OASIcs, Volume 108, Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)

Abstract

In this paper, we introduce the concept of Multi-Reader Buffers (MRBs) for high throughput and memory-efficient implementation of dataflow applications. Our work is motivated by the huge amount of data that needs to be processed and typically accessed in a FIFO manner, particularly in image and video processing applications. Here, multi-cast, fork, and merge operator implementations known today produce huge memory overheads by storing and communicating copies of the same data. As a remedy, we first introduce MRBs as buffers preserving FIFO semantics for a finite number of readers of the same data while storing each data item only once. Second, we present an approach for memory minimization of data flow networks by replacing all multi-cast actors and connected FIFOs with MRBs. Third, we present a Design Space Exploration approach to selectively replace multi-cast actors with MRBs in order to explore memory, throughput, and processor resource allocation tradeoffs. Our results show that the explored Pareto fronts of our approach improve the solution quality over a reference by 78% in average for six benchmark applications in terms of a hypervolume indicator.

Cite as

Martin Letras, Joachim Falk, and Jürgen Teich. Throughput and Memory Optimization for Parallel Implementations of Dataflow Networks Using Multi-Reader Buffers. In Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023). Open Access Series in Informatics (OASIcs), Volume 108, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{letras_et_al:OASIcs.NG-RES.2023.6,
  author =	{Letras, Martin and Falk, Joachim and Teich, J\"{u}rgen},
  title =	{{Throughput and Memory Optimization for Parallel Implementations of Dataflow Networks Using Multi-Reader Buffers}},
  booktitle =	{Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)},
  pages =	{6:1--6:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-268-6},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{108},
  editor =	{Terraneo, Federico and Cattaneo, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2023.6},
  URN =		{urn:nbn:de:0030-drops-177374},
  doi =		{10.4230/OASIcs.NG-RES.2023.6},
  annote =	{Keywords: Dataflow, Memory Optimization, MPSoCs, Design Space Exploration}
}

Document

DOI: 10.4230/OASIcs.NG-RES.2020.2

Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice

Authors: Bertrand Simon, Joachim Falk, Nicole Megow, and Jürgen Teich

Published in: OASIcs, Volume 77, Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020)

Abstract

Static (offline) techniques for mapping applications given by task graphs to MPSoC systems often deliver overly pessimistic and thus suboptimal results w.r.t. exploiting time slack in order to minimize the energy consumption. This holds true in particular in case computation times of tasks may be workload-dependent and becoming known only at runtime or in case of conditionally executed tasks or scenarios. This paper studies and quantitatively evaluates different classes of algorithms for scheduling periodic applications given by task graphs (i.e., DAGs) with precedence constraints and a global deadline on homogeneous MPSoCs purely at runtime on a per-instance base. We present and analyze algorithms providing provably optimal results as well as approximation algorithms with proven guarantees on the achieved energy savings. For problem instances taken from realistic embedded system benchmarks as well as synthetic scalable problems, we provide results on the computation time and quality of each algorithm to perform a) scheduling and b) voltage/speed assignments for each task at runtime. In our portfolio, we distinguish as well continuous and discrete speed (e.g., DVFS-related) assignment problems. In summary, the presented ties between theory (algorithmic complexity and optimality) and execution time analysis deliver important insights on the practical usability of the presented algorithms for runtime optimization of task scheduling and speed assignment on MPSoCs.

Cite as

Bertrand Simon, Joachim Falk, Nicole Megow, and Jürgen Teich. Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice. In Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020). Open Access Series in Informatics (OASIcs), Volume 77, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{simon_et_al:OASIcs.NG-RES.2020.2,
  author =	{Simon, Bertrand and Falk, Joachim and Megow, Nicole and Teich, J\"{u}rgen},
  title =	{{Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice}},
  booktitle =	{Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020)},
  pages =	{2:1--2:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-136-8},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{77},
  editor =	{Bertogna, Marko and Terraneo, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2020.2},
  URN =		{urn:nbn:de:0030-drops-117781},
  doi =		{10.4230/OASIcs.NG-RES.2020.2},
  annote =	{Keywords: energy minimization, speed scaling, precedence graphs, scheduling, critical path, MPSoC}
}

Search Results

Documents authored by Falk, Joachim

Throughput and Memory Optimization for Parallel Implementations of Dataflow Networks Using Multi-Reader Buffers

Abstract

Cite as

Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice

Abstract

Cite as

Thanks for your feedback!

Could not send message