cfaed Publications

mAPN: Modeling, Analysis, and Exploration of Algorithmic and Parallelism Adaptivity


Hasna Bouraoui, Chadlia Jerad, Omar Romdhani, Jeronimo Castrillon, "mAPN: Modeling, Analysis, and Exploration of Algorithmic and Parallelism Adaptivity", arXiv, Jul 2022. [doi]


author = {Bouraoui, Hasna and Jerad, Chadlia and Romdhani, Omar and Castrillon, Jeronimo},
title = {mAPN: Modeling, Analysis, and Exploration of Algorithmic and Parallelism Adaptivity},
doi = {10.48550/ARXIV.2207.07591},
url = {},
copyright = {Creative Commons Attribution 4.0 International},
month = jul,
publisher = {arXiv},
year = {2022},
abstract = {Using parallel embedded systems these days is increasing. They are getting more complex due to integrating multiple functionalities in one application or running numerous ones concurrently. This concerns a wide range of applications, including streaming applications, commonly used in embedded systems. These applications must implement adaptable and reliable algorithms to deliver the required performance under varying circumstances (e.g., running applications on the platform, input data, platform variety, etc.).
Given the complexity of streaming applications, target systems, and adaptivity requirements, designing such systems with traditional programming models is daunting. This is why model-based strategies with appropriate Model of Computation (MoC) have long been studied for embedded system design. Dataflow models, in particular, are a good fit for streaming applications that execute in parallel on embedded devices. Most of today’s models, however, are based on static dataflow models with adaptivity extensions to describe data parallelism. Some dynamic dataflows capture dynamic behavior but offer only limited support for algorithmic adaptivity. This work provides algorithmic adaptivity on top of parallelism for dynamic dataflow to express larger sets of variants and trade-offs. We present a multi-Alternative Process Network (mAPN), a high-level abstract representation in which several variants of the same application coexist in the same graph expressing different implementations. We introduce multi-Alternative Process Network (mAPN) properties and its formalism to describe various local implementation alternatives. Furthermore, mAPNs are enriched with metadata to provide the alternatives with quantitative annotations in terms of a specific metric. To help the user analyze the rich space of variants, we propose a methodology to extract feasible variants under user and hardware constraints. At the core of the methodology is an algorithm for computing global metrics of an execution (e.g., execution time) of different alternatives from a compact mAPN specification. We validate our approach by exploring several possible variants created for the Automatic Subtitling Application (ASA) on two hardware platforms and analyzing the trade-off space. A comparison to the well-known analysis tool SDF3 is also performed, where we showed that we are more than 500 times faster for a large number of variants.}


2207_Bouraoui_Arxvi [PDF]


Go back to publications list