logo EDITE Mohamed BENAZOUZ
Identité
Mohamed BENAZOUZ
État académique
Thèse soutenue le 2012-04-13
Sujet: Dimensionnement des Mémoires pour les Applications de Traitement de Flux de Données
Direction de thèse:
Laboratoire:
Voisinage
Ellipse bleue: doctorant, ellipse jaune: docteur, rectangle vert: permanent, rectangle jaune: HDR. Trait vert: encadrant de thèse, trait bleu: directeur de thèse, pointillé: jury d'évaluation à mi-parcours ou jury de thèse.
Productions scientifiques
oai:hal.archives-ouvertes.fr:hal-00368648
A new Approach for Minimizing Buffer Capacities with Throughput Constraint for Embedded System Design.
The design of streaming (e.g. multimedia or network packet processing) applications must consider several optimizations such as the mimimization of the whole surface of the memory needed on a Chip. The minimum throughput of the output is usually fixed. In this paper, we present an original methodology to solve this problem. The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and the places model buffers for data transfers. It is assumed that transitions are periodically fired with a fixed throughput. The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to the capacity. A first polynomial simple algorithm computing the minimum surface for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. We prove in this case that the capacities of every buffer may be optimized independently. For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.
preprint 2009-01-27
oai:hal.archives-ouvertes.fr:hal-00610751
Cyclo-Static DataFlow Phases Scheduling Optimization for the Throughput Constrained Buffer Sizes Minimization Problem
Cyclo-Static DataFlow (CSDF) is a powerful model for the specification of DSP applications. However, as in any asynchronous model, the synchronization of the different communicating tasks (processes) is made through buffers that have to be sized such that timing constraints are met. In this paper, we want to determine buffer sizes such that the throughput constraint is satisfied. This problem has been proved to be of exponential complexity. Exact techniques to solve this problem are too time and/or space consuming because of the self-timed schedule needed to evaluate the maximum throughput. Therefore, a periodic schedule is used. Each CSDF actor is associated with a period that satisfies the throughput constraint and sufficient buffer sizes are derived in polynomial time. However, within a period, an actor phases can be scheduled in different manners which impacts the evaluation of sufficient buffer sizes. This paper presents a Min-Max Linear Program that derives an optimized periodic phases scheduling per CSDF actor in order to minimize buffer sizes. It is shown through an MP3 Playback and an H.263 Encoder that this Min-Max Linear Program allows to obtain close to optimal values while running in polynomial time. The impact of phases scheduling on periodic schedulability of applications with critical cycles is also highlighted on a Channel Equalizer.
preprint 2011-07-24
ftp://asim.lip6.fr/pub/reports/2009/ar.benaz.cie.1.2009.pdf
A polynomial algorithm for the computation of buffer capacities with throughput constraint for embedded system design.
CIE IEEE International Conference on Computers & Industrial Engineering , Troyes, FRANCE 2009
oai:hal.archives-ouvertes.fr:hal-00461647
A New Method for Minimizing Buffer Sizes for Cyclo-Static Dataflow Graphs.
Several optimizations must be considered for the design of streaming applications (e.g. multimedia or network packet processing). These applications can be modelled as a set of processes that communicate using buffers. Cyclo-Static Dataflow graphs, which are an extension of Synchronous Dataflow graphs, allow to consider a large class of industrial applications. This paper presents an original methodology to minimize the global surface of the buffers for a Cyclo-Static Dataflow graph under a given throughput constraint. It is proved that, if the processes are periodic, each buffer introduces a linear constraint described analytically. The optimization problem is then modelled by an Integer Linear Program. A polynomial algorithm based on its relaxation provides a quasi-optimal solution for real life problems. The resolution of the optimization problem for a Reed-Solomon Decoder application is then detailed.
preprint 2010-02-16
edite:1332792428470
A New Approach for Minimizing Buffer Capacities with Throughput Constraint for Embedded System Design
AICCSA IEEE/ACS International Conference on Computer Systems and Applications, Hammamet, Tunisie 2010
edite:1332792428472
A New Method for Minimizing Buffer Sizes for Cyclo-Static Dataflow Graphs
ESTIMedia IEEE International Workshop on Embedded Systems for Real-Time Multimedia, Scottsdale, Arizona, USA 2010
Soutenance
Thèse: Dimensionnement des mémoires pour les applications de traitement de flux de données
Soutenance: 2012-04-13
Rapporteurs: Dritan NACE    Sid TOUATI