logo EDITE Bruno Loic Alexandre BODIN
Bruno Loic Alexandre BODIN
État académique
Thèse soutenue le 2013-12-20
Sujet: Optimisation pour exécuter une application sur une architecture MPSOC
Direction de thèse:
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
K-Periodic schedules for evaluating the maximum throughput of a Synchronous Dataflow graph
Synchronous Dataflow graphs, introduced by Lee and Messerschmitt in 1987, are a well-known formalism commonly used to model data-exchanges between parallel processes. This model was extensively studied in the last two decades because of the importance of its applications. However, the determination of a maximal throughput is a difficult question, for which no polynomial time algorithm exists to date. In this context, several authors proved that a K-Periodic schedule, where K is a vector of no polynomially bounded values, reaches the maximum throughput. On the other hand, a 1-Periodic schedule may be built polynomially, but without any guarantee on the throughput achieved. Therefore, the investigated problem is the trade-off between the schedule size induced by the vector K (called the periodicity vector) and its corresponding throughput. Necessary and sufficient conditions for the existence of K-Periodic schedules are first shown for any fixed value in the vector K; the computation of the maximum throughput of a K-Periodic schedule is deduced. A set of dominant values of K is exhibited, and a relationship between the optimal throughput of these values is proved. Some real-life experiments measure the variation of the throughput according to K.
Proceedings 2012 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS) 2012 International Conference on Embedded Computer Systems (SAMOS)conference proceeding 2012-07
Liveness evaluation of a cyclo-static DataFlow graph
Cyclo-Static DataFlow Graphs (CSDFG in short) is a formalism commonly used to model parallel applications composed by actors communicating through buffers. The liveness of a CSDFG ensures that all actors can be executed infinitely often. This property is clearly fundamental for the design of embedded applications. This paper aims to present first an original sufficient condition of liveness for a CSDFG. Two algorithms of polynomial-time for checking the liveness are then derived and compared to a symbolic execution of the graph. An original method to compute close-to-optimal buffer capacities ensuring liveness is also presented and experimentaly tested. The performance of our methods are comparable to those existing in the literature for industrial applications. However, they are far more effective on randomly generated instances, ensuring their scalability for future more complex applications and their possible implementation in a compiler.
Proceedings of the 50th Annual Design Automation Conference DAC 2013conference proceeding 2013-04
Extended Cyclostatic Dataflow Program Compilation and Execution for an Integrated Manycore Processor
The ever-growing number of cores in embedded chips emphasizes more than ever the complexity inherent to parallel programming. To solve these programmability issues, there is a renewed interest in the dataflow paradigm. In this context, we present a compilation toolchain for the Sigma-C language, which allows the hierarchical construction of stream applications and automatic mapping of this application to an embedded manycore target. As a demonstration of this toolchain, we present an implementation of a H.264 encoder and evaluate its performance on Kalray's embedded manycore MPPA chip.
Alchemy 2013 - Architecture, Languages, Compilation and Hardware support for Emerging ManYcore systemsconference proceeding 2013-06-05
Periodic Schedules for Cyclo-Static Dataflow
Cyclo-Static Dataflow Graphs (CSDFGs in short) is a static model commonly used to describe communications between processes. It is increasingly considered for modeling applications executed by many-core architectures; their static analysis becomes thus essential for developing efficient compile- time optimization. This paper aims to develop efficient algorithms to approxi- mately solve two main difficult problems: the determination of the maximum throughput of a CSDFG and the optimization of the buffer sizes with a minimum required throughput. They are both based on a new characterization of feasible periodic schedules. A polynomial-time algorithm is deduced to evaluate the maximum throughput of a periodic schedule, providing a lower bound of the maximum throughput of the CSDFG. A new model for the optimization of the buffer sizes with a minimum required throughput based on integer linear pro- gramming is also developed, leading to a new algorithm to solve it approximately. Our algorithms are successfully compared with other academic solutions through representative benchmarks.
Proceedings of the 11th IEEE Symposium on Embedded Systems For Real-time Multimedia Symposium on Embedded Systems For Real-time Multimedia (ESTIMedia '13)conference proceeding 2013-10
Thèse: Analyse d'Applications à Flot de Données pour la Compilation Multiprocesseur
Soutenance: 2013-12-20
Rapporteurs: Dritan NACE    Jean-François NEZAN