Memory Bounds for the Distributed Execution of a Hierarchical Synchronous Data-Flow Graph

Karol Desnos 1, 2 Maxime Pelcat 1, 2 Jean François Nezan 1, 2 Slaheddine Aridhi 3
1 IETR - Institut d'Electronique et de Télécommunications de Rennes
2 UEB - Université européenne de Bretagne
3 CIV Texas Instruments
Abstract : This paper presents an application analysis technique to define the boundary of shared memory requirements of Multiprocessor System-on-Chip (MPSoC) in early stages of development. This technique is part of a rapid prototyping process and is based on the analysis of a hierarchical Synchronous Data-Flow (SDF) graph description of the system application. The analysis does not require any knowledge of the system architecture, the mapping or the scheduling of the system application tasks. The initial step of the method consists of applying a set of transformations to the SDF graph so as to reveal its memory characteristics. These transformations produce a weighted graph that represents the different memory objects of the application as well as the memory allocation constraints due to their relationships. The memory boundaries are then derived from this weighted graph using analogous graph theory problems, in particular the Maximum-Weight Clique (MWC) problem. Stateof-the-art algorithms to solve these problems are presented and a heuristic approach is proposed to provide a near-optimal solution of the MWC problem. A performance evaluation of the heuristic approach is presented, and is based on hierarchical SDF graphs of realistic applications. This evaluation shows the efficiency of proposed heuristic approach in finding near optimal solutions.
Keywords : Synchronous Data Flow Memory Bounds
Type de document :
Communication dans un congrès
12th International Conference on Embedded Computer Systems: Architecture, Modeling and Simulation (SAMOS XII), Jul 2012, Agios Konstantinos, Greece. pp.160, 2012
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
https://hal.archives-ouvertes.fr/hal-00721335
Contributeur : Karol Desnos <>
Soumis le : vendredi 27 juillet 2012 - 11:20:14
Dernière modification le : vendredi 16 novembre 2018 - 01:29:17
Document(s) archivé(s) le : dimanche 28 octobre 2012 - 03:30:16

Fichier

Samos12.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00721335, version 1

Collections

UNIV-NANTES | SUP_IETR | IETR-INSA | IETR | TDS-MACS | UR1-UFR-ISTIC | IETR-VAADER | UNIV-RENNES

Citation

Karol Desnos, Maxime Pelcat, Jean François Nezan, Slaheddine Aridhi. Memory Bounds for the Distributed Execution of a Hierarchical Synchronous Data-Flow Graph. 12th International Conference on Embedded Computer Systems: Architecture, Modeling and Simulation (SAMOS XII), Jul 2012, Agios Konstantinos, Greece. pp.160, 2012. 〈hal-00721335〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

652

Téléchargements de fichiers

326

Contact


archive-ouverte@inria.fr