责任导师 : Claire HANEN

Cyclic RCPSP study

The constant evolution of high performance processors architectures, to hold the challenging requirements of embedded applications, gives an increasing importance to a more efficient programming, mainly in compilation level, in these systems. Our study is particularly motivated by the optimization of scheduling when compiling instructions in VLIW processors (Very Large Instruction Word), and its resolution by using the RCPSP (Resource Constrained Project Scheduling Problem) cyclic. In such model, there is usually a small number of independent functional units that can execute multiple task simultaneously if the data dependencies are met and if necessary resources are available. Today, theoretical studies in the field of cyclic scheduling aims to characterize the scheduling algorithms (worst-case analysis, optimality result, etc.) for real applications in embedded systems as well as in mass production systems. In this thesis, we worked on identifying suitable models, able to take into account the new characteristics of these systems (the nature of dependencies, the heterogeneity of resources, etc..). Several approximation algorithms with performance guarantees have been proposed, and an experimental study to analyze their performance in practice has been established.

2008-2013 刊物