The requirements for real-time systems in safety-critical applications typically contain strict timing constraints. The design of such a system must be subject to extensive validation to guarantee that critical timing constraints will never be violated while the system operates. A mathematically rigorous technique to do so is to perform a schedulability analysis for formally verifying models of the computational workload. Different workload models allow to describe task activations at different levels of expressiveness, ranging from traditional periodic models to sophisticated graph-based ones. An inherent conflict arises between the expressiveness and analysis efficiency of task models. The more expressive a task model is, the more accurately it can describe a system design, reducing over-approximations and thus minimizing wasteful over-provisioning of system resources. However, more expressiveness implies higher computational complexity of corresponding analysis methods. Consequently, an ideal model provides the highest possible expressiveness for which efficient exact analysis methods exist. This thesis investigates the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced, which generalizes all previously proposed models that can be analyzed in pseudo-polynomial time without using any analysis-specific over-approximations. We develop methods allowing to efficiently analyze variants of the model despite their strictly increased expressiveness. A key contribution is the notion of path abstraction which enables efficient graph traversal algorithms. We demonstrate tractability borderlines for different classes of schedulers, namely static priority and earliest-deadline first schedulers, by establishing hardness results. These hardness proofs provide insights about the inherent complexity of developing efficient analysis methods and indicate fundamental difficulties of the considered schedulability problems. Finally, we develop a novel abstraction refinement scheme to cope with combinatorial explosion and apply it to schedulability and response-time analysis problems. All methods presented in this thesis are extensively evaluated, demonstrating practical applicability.

With the increasing demand of computation capabilities, many-core processors are gain-ing more and more attention. As a communication subsystem many-core processors, Network-on-Chip (NoC) draws a lot of attention in the related research fields. A NoC is used to deliver messages among different cores. For many applications, timeliness is of great importance, especially when the application has hard real-time requirements. Thus, the worst-case end-to-end delays of all the messages passing through a NoC should be concerned. Unfortunately, there is no existing analysis tool that can support multiple NoC architectures as well as provide a user-friendly interface.This thesis focuses on a wormhole switched NoC using different arbitration policies which are Fixed Priority (FP) and Round Robin (RR) respectively. FP based arbitration policy includes distinct and shared priority based arbitration policies. We have developed a timing analysis tool targeting the above NoC designs. The Graphical User Interface (GUI) in the tool can simplify the operation of users. The tool takes characteristics of flow sets as input, and returns results regarding the worst-case end-to-end delay of each flow. These results can be used to assist the design of real-time applications on the corre-sponding platform.A number of experiments have been generated to compare different arbitration mecha-nisms using the developed tool. The evaluation focuses on the effect of different param-eters including the number of flows and the number of virtual-channels in a NoC, and the number of hops of each flow. In the first set of experiment, we focus on the schedulabil-ity ratio achieved by different arbitration policies regarding the number of flows. The sec-ond set of experiments focus on the comparison between NoCs with different number of virtual-channels. In the last set of experiments, we compare different arbitration mecha-nisms with respect to the worst-case end-to-end latencies.

L’objectif que nous nous sommes fixés dans ce travail est la conception d’algorithmes d’ordonnancement temps réel en-ligne faisables optimisant l’utilisation de la plate-forme d’exécution et/ou des critères applicatifs de qualité de service propres à l’application. Nous avons en particulier étudié l’ordonnancement d’activités sur une ressource unique. Deux cas ont été analysés : le cas de tâches indépendantes périodiques s’exécutant sur un processeur et le cas de flux de messages indépendants périodiques sur un réseau de terrain avec accès au médium priorisé. Nos contributions reposent sur le “modèle classique” de l’ordonnancement temps réel où le système est représenté par un ensemble d’activités périodiques indépendantes et deux problématiques ont été abordées : • optimisation de l’utilisation de la plate-forme d’exécution : utiliser au mieux le potentiel de la plate-forme d’exécution tout en garantissant le respect des contraintes temporelles imposées au système ; ceci optimise le nombre de configurations faisables, • optimisation des critères applicatifs de qualité de service propres à l’application (i.e., pris en compte des performances de l’application autre que la faisabilité) : garantir les contraintes de temps tout en optimisant les performances de l’application. Nous avons donc proposé : • des méthodes de configurations permettant d’optimiser l’utilisation de la plate-forme d’exécution (i.e., maximiser faisabilité) en fixant les paramètres des politiques ou des systèmes considérés d’une manière appropriée. Deux études ont été conduites dans ce cadre : • allocation des “offsets” dans les systèmes “offset free”, • allocation de priorités, de politiques et de quantum dans les systèmes conformes au standard Posix 1003.1b, • une nouvelle classe de politiques d’ordonnancement permettant d’optimiser des critères de performances propres à l’application. De plus, une analyse d’ordonnancement générique pour cette classe a été proposée / Our goal is to come up with feasible (i.e., all required time constraints are met) on-line real-time scheduling algorithms. These algorithms have to optimise 1) the utilisation of the execution platform (i.e., meet time constraints and use platform at its fullest potential) and/or 2) optimise the application dependent performance criteria. We study two cases : the case of independent periodic tasks scheduled on a processor and the case of periodic traffic streams scheduled on a priority bus. To deal with these two problems, we propose : • Configuration methods to allow to optmlise the utilisation rate of the execution platform by setting the parameters of the policies or of the activities of the considered system. We perform two studies : the allocation of offsets in "Offset free" systems (I.E., offsets can be chosen off-line) and the priorities, policies and quantum allocations in systems compliant to the standard Posix 1003.1B, • A new class of scheduling policies to allow optimising application performance dependent criteria

With multiprocessors and multicore processors becoming ubiquitous, focus has shifted from research on uniprocessors to that on multiprocessors. Results derived for the uniprocessor case unfortunately do not always directly extend to the multiprocessor case in a straightforward manner. This necessitates a paradigm shift in the approach used to design and analyse the behaviour of such processors. In the case of Real-time systems, that is, systems characterised by explicit timing constraints, analysis and performance guarantees are more important, as failure is unacceptable. Scheduling algorithms used in Real-time systems have to be carefully designed as the performance of the system depends critically on them. Efficient tests for determining if a set of tasks can be feasibly scheduled on such a computing system using a particular scheduling algorithm thus assumes importance. Traditionally, the ‘task utilization’ parameter has been used for devising such tests. Utilization based tests for Earliest Deadline First(EDF) and Rate Monotonic(RM) scheduling algorithms are known and are well understood for uniprocessor systems. In our work, we derive limits on similar bounds for the multiprocessor case. Our work diners from previous literature in that we explore the case when the individual processors constituting the multiprocessor need not be identical. Each processor in such a system is characterised by a capacity, or speed, and the time taken by a task to execute on a processor is inversely proportional to its speed. Such instances may arise during system upgradation, when faster processors may be added to the system, making it a non-identical multiprocessor, or during processor design, when the different cores on the chip may have different processing power to handle dynamic workloads. We derive results for the partitioned paradigm of multiprocessor scheduling, that is, when tasks are partitioned among the processors, and interprocessor migration after a part of execution is completed is not allowed. Results are derived for both fixed priority algorithms(RM)and dynamic priority algorithms (EDF) used on individual processors. A maximum and minimum limit on the bounds for a ‘greedy’ class of algorithms are established, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm whose bound is close to the upper limit in both cases. We find that an expression for the utilization bound can be obtained when EDF is used as the uniprocessor scheduling algorithm, but when RM is the uniprocessor scheduling algorithm,an O(mn) algorithm is required to find the utilization bound, where m is the number of tasks in the system and n is the number of processors. Knowledge of such bounds allows us to carry out very fast schedulability tests, although we have the limitation that the tests are sufficient but not necessary to ensure schedulability. We also compare the value of the bounds with those achievable in ‘equivalent’ identical multiprocessor systems and find that the performance guarantees provided by the non-identical multiprocessor system are far higher than those offered by the equivalent identical system.

Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design. On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework. On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem. On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.

For the past several decades, we have experienced the tremendous growth, in both scale and scope, of real-time embedded systems, thanks largely to the advances in IC technology. However, the traditional approach to get performance boost by increasing CPU frequency has been a way of past. Researchers from both industry and academia are turning their focus to multi-core architectures for continuous improvement of computing performance. In our research, we seek to develop efficient scheduling algorithms and analysis methods in the design of real-time embedded systems on multi-core platforms. Real-time systems are the ones with the response time as critical as the logical correctness of computational results. In addition, a variety of stringent constraints such as power/energy consumption, peak temperature and reliability are also imposed to these systems. Therefore, real-time scheduling plays a critical role in design of such computing systems at the system level. We started our research by addressing timing constraints for real-time applications on multi-core platforms, and developed both partitioned and semi-partitioned scheduling algorithms to schedule fixed priority, periodic, and hard real-time tasks on multi-core platforms. Then we extended our research by taking temperature constraints into consideration. We developed a closed-form solution to capture temperature dynamics for a given periodic voltage schedule on multi-core platforms, and also developed three methods to check the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research by incorporating the power/energy constraint with thermal awareness into our research problem. We investigated the energy estimation problem on multi-core platforms, and developed a computation efficient method to calculate the energy consumption for a given voltage schedule on a multi-core platform. In this dissertation, we present our research in details and demonstrate the effectiveness and efficiency of our approaches with extensive experimental results.