Traditional design methods could not cope with the recent development of multiprocessorsystems-on-chip (MPSoC). Especially, hard real-time systems that requiretime-predictability are cumbersome to develop. What is needed, is an efficient, automaticprocess that abstracts away all the implementation details. ForSyDe, a designmethodology developed at KTH, allows this on the system modelling side. The NoCSystem Generator, another project at KTH, has the ability to create automaticallycomplex systems-on-chip based on a network-on-chip on an FPGA. Both of themsupport the synchronous model of computation to ensure time-predictability. Inthis thesis, these two projects are analysed and modelled. Considering the characteristicsof the projects and exploiting the properties of the synchronous model ofcomputation, a mapping process to map processes to the processors at the differentnetwork nodes of the generated system-on-chip was developed. The mapping processis split into three steps: (1) Binding processes to processors, (2) Placement of theprocessors on net network nodes, and (3) scheduling of the processes on the nodes.An implementation of the mapping process is described and some synthetic exampleswere mapped to show the feasibility of algorithms.

Due to the ever increasing complexity of safety-critical applications, handwritten code is being replaced by automatically generated code derived from a high level specification. Code generation from high level specification requires a model of computation with an underlying formalism and correctness-preserving refinement steps to generate the lower level application code. Such software synthesis techniques are said to be 'correct-by-construction'. Synchronous programming languages such as Esterel, LUSTRE, which are based on a synchronous model of computation are used for sequential code generation. They work on a synchrony assumption (zero time intraprocess computation and zero time inter process communication) at the specification level. Early versions of synchronous languages followed an execution pattern where an iteration of software was mapped to an interval between ticks of an external reference clock. Since this external reference tick was unrelated to variables (or signals) within the software, redundant operations such as reading of ports, computation of guards were performed for each tick. In this dissertation, we highlight some of these performance issues and missed optimization opportunities. Also we show how a multi-clock (or polychronous) formalism, where each variable has an independent rate of execution associated with it, can avoid these problems. An existing polychronous language named SIGNAL, creates a hierarchy of clocks based on the rate of execution of individual variables, to form a root clock which acts a reference tick. We seek to replace the clock analysis with a technique to form a unique order of events without a reference time line. For this purpose, we present a new polychronous formalism termed Multi-rate Instantaneous Channel connected Data Flow (MRICDF). Our new synthesis technique inspects the specification to identify a master trigger at a Boolean equation level to act as the reference tick. Furthermore, we attempt to make polychronous specification based software synthesis more accessible to practicing engineers, by constructing a software tool EmCodeSyn, with a visual environment for specification and a more intuitive analysis technique. Our Boolean approach to sequential synthesis of embedded software has multiple implementations, each of which utilizes existing academic software tools. Optimizations are proposed to minimize synthesis time by simplifying the input to these external tools. Weaknesses in causal loop analysis techniques applied by existing synthesis tools are highlighted and solutions for performing time efficient loop analysis are integrated into EmCodeSyn. We have also determined that a part of the non-synthesizable polychronous specifications can be used to generate correct multi-threaded code. Additionally, we investigate composition of polychronous modules and propose properties that are necessary to guarantee agreement on shared signals. / Ph. D.

L’importance des systèmes temps-réels embarqués dans les sociétés industrialisées modernes en font un terrain d’application privilégié pour les méthodes formelles. La prépondérance des contraintes temporelles dans les spécifications de ces systèmes motive la mise au point de solutions spécifiques. Cette thèse s’intéresse à une classe de systèmes temps-réels incluant ceux développés avec la chaîne d’outils OASIS, développée au CEA LIST. Nos travaux portent sur la notion de délai de bout-en-bout, que nous proposons de modéliser comme une contrainte temporelle concernant l’influence du flot d’informations des entrées sur celui des sorties. Afin de répondre à la complexité croissante des systèmes temps-réels, nous étudions l’applicabilité de cette notion nouvelle au développement incrémental par raffinement et par composition. Le raffinement est abordé sous l’angle de la conservation de propriétés garantes de la correction du système au cours du processus de développement. Nous délimitons les conditions nécessaires et suffisantes à la conservation du délai de bout-en-bout lors d’un tel processus. De même, nous donnons des conditions suffisantes pour permettre le calcul du délai de bout-en-bout de manière compositionnelle. Combinés, ces résultats permettent d’établir un formalisme permettant la preuve du délai de bout-en-bout lors d’une démarche de développement incrémentale. / Real-time embedded systems are at the core of modern industrialized societies. They are a privileged target for the application of formal methods. The importance of real-time constraints in the specification of these systems requires the design of ad-hoc solutions. This work considers a class of real-time systems including those developed using OASIS, a tool-chain targeting hard real-time embedded systems developed at CEA LIST. We study the notion of end-to-end delay, which we propose to model as a constraint bearing directly on the influence of the input information flow over the output information flow . In order to cope with the growing complexity of real-time embedded systems, we study the possibility to apply this new notion of delay to the incremental development of such systems, by using both stepwise refinement and composition operators. We define the necessary and sufficient conditions to the preservation of the end-to-end delay by stepwise refinement. Similarly, we give sufficient conditions to compute the end-to-end delay in a compositional fashion. Together, these results permit to establish a formalism allowing to prove end-to-end delay properties in stepwise development methodologies.

Les systèmes intégrés sont aujourd’hui de plus en plus fréquemment confrontés à des contraintes de faible consommation ou d’efficacité énergétique. Ces problématiques se doivent d’être intégrées le plus en amont possible dans le flot de conception afin de réduire les temps de design et d’éviter de nombreuses itérations dans le flot. Dans ce contexte, le projet collaboratif HiCool, partenariat entre les laboratoires LIRMM et TIMA, les sociétés Defacto, Docea et ST Microelectronics, a mis en place une stratégie et un flot de conception pour concevoir des systèmes intégrés faible consommation tout en facilitant la réutilisation de blocks matériels (IPs) existants. L’approche proposée dans cette thèse s’intègre dans cette stratégie en apportant une petite dose d’asynchronisme dans des systèmes complètement synchrones. En effet, la réduction de la consommation est basée sur le constat que l’activation permanente de la totalité du circuit est inutile dans bien des cas. Néanmoins, contrôler l’activité avec des techniques de « clock gating » ou de « power gating » nécessitent usuellement d’effectuer un re-design du système et d’ajouter un organe de commande pour contrôler l’activation des zones effectuant un traitement. Le travail présenté dans ce manuscrit définit une stratégie basée sur des contrôleurs d’horloge et de domaine d’alimentation, asynchrones, distribués et facilement insérables dans un circuit avec un coût de re-design des plus réduit. / Today integrated systems are increasingly faced with the constraints of low consumption or energy efficiency. These issues need to be integrated as far upstream as possible in the design flow to reduce design time and avoid much iteration in the flow. In this context, the collaborative project HiCool, between LIRMM and TIMA laboratories, Defacto, Docea and ST Microelectronics companies, has set up a strategy and design flow to design integrated low power systems while facilitating the reuse of existing hardware blocks (IPs). The approach proposed in this thesis fits into this strategy by bringing a small dose of asynchrony in completely synchronous systems. Indeed, the reduction in consumption is based on the observation that permanent activation of the entire circuit is unnecessary in many cases. However, controlling the activity with techniques of "clock gating" or "power gating" usually need to perform a re-design of the system and to add a control device for controlling activation of areas effecting treatment. The work presented in this manuscript provides a strategy based clock controllers and power domain, asynchronous, distributed and easily insertable into a circuit with a low cost design.