Sistemas embarcados baseados em processadores têm sido largamente aplicados em áreas críticas no que diz respeito à segurança de seres humanos e do meio ambiente. Em tais aplicações, que compreendem desde o controle de freio de carros a missões espaciais, pode ser necessária a execução confiável de todas as funcionalidades do sistema durante longos períodos e em ambientes desconhecidos, hostis ou instáveis. Mesmo em aplicações não críticas, nas quais a confiabilidade do sistema não é um requisito primordial, o usuário final deseja que seu produto apresente comportamento estável e livre de erros. Daí vem a importância de se considerar o auto-teste on-line no projeto dos sistemas embarcados atuais. Entretanto, a crescente complexidade de tais sistemas somada às fortes restrições a que eles estão sujeitos torna o projeto do auto-teste um problema cada vez mais desafiador. Em aplicações de tempo-real a dificuldade é ainda maior, uma vez que, além dos cuidados com as restrições do sistema alvo, deve-se levar em conta o atendimento dos requisitos temporais da aplicação. Entre as técnicas de auto-teste on-line atualmente pesquisadas, uma tem se destacado pela eficácia obtida a um baixo custo de projeto e sem grande impacto no atendimento dos requisitos e restrições do sistema: o auto-teste baseado em software (SBST – Software-Based Self-Test). Neste trabalho, é proposta uma metodologia para o projeto e aplicação de auto-teste on-line para processadores embarcados, considerando-se também aplicações de temporeal. Tal metodologia, denominada STEP (Self-Test for Embedded Processors), tem como base a técnica SBST e prevê o planejamento, a geração e a seleção de rotinas de teste para o processador alvo. O método proposto garante a execução periódica do autoteste, com o menor período permitido pela aplicação de tempo-real, e assegura o atendimento de todas as restrições do sistema embarcado. Além disso, a solução fornecida pelo método alcança uma boa qualidade de teste enquanto auxilia a redução de custos do sistema final. Como estudo de caso, a metodologia proposta é aplicada a diferentes arquiteturas de processadores Java e os resultados obtidos comprovam a eficiência da mesma. Por fim, é apresentada uma ferramenta que implementa a metodologia STEP, automatizando, assim, o projeto e a aplicação de auto-teste on-line para os processadores estudados. / Processor-based embedded systems have been widely used in safety-critical applications. In such applications, which include from cars break control to spatial missions, the whole system operation must be reliable during long periods even within unknown, hostile and unstable environments. In non-critical applications, system reliability is not a prime requirement, but the final user requires an error free product, with stable behavior. Hence, one can realize the importance of on-line self-testing in current embedded systems. Self-testing is becoming an important challenge due to the increasing complexity of the systems allied to their strong constraints. In real-time applications this problem becomes even more complex, since, besides meeting systems constraints, one must take into consideration the application timing requirements. Among all on-line self-testing techniques studied, Software-Based Self-Test (SBST) has been distinguished by its effectiveness, low-cost and small impact on system constraints and requirements. This work proposes a methodology for the design and implementation of on-line self-test in embedded processors, considering real-time applications. Such a methodology, called STEP (Self-Test for Embedded Processors), is based on SBST technique and encloses planning, generation and selection of test routines for the target processor. The proposed method guarantees periodical self-test execution, at the smallest period allowed by the real-time application, and ensures that all embedded system constraints are met. Furthermore, provided solution achieves high test quality while helping in the optimization of the costs of the final system. The proposed methodology is applied to different architectures of Java processors to demonstrate its efficiency. Finally, this work presents a tool that automates the design and implementation of on-line self-test in the studied processors by implementing the STEP methodology.

Les systèmes d'aide à la décision (SAD) doivent permettre aux utilisateurs (décideurs) de prendre les meilleures décisions dans les meilleurs délais. Dans cette thèse, nous nous sommes intéressés aux systèmes qui reposent sur une architecture multi-agents. En effet, les systèmes multi-agents (SMA) permettent de construire des systèmes informatiques ayant recours à l'interrogation multi-critères, souvent utilisée dans les SAD. De façon plus générale, les SMA permettent de concevoir des systèmes qui sont de nature complexe. Cependant, ils n'intègrent pas la notion de contraintes temporelles qui sont souvent très fortes dans les SAD. De plus, dans ces systèmes, des résultats même partiels ou incomplets obtenus dans les temps sont souvent préférés car plus utiles pour la prise de décision que des résultats complets et précis obtenus en retard. Pour cela, les techniques ``anytime'' (raisonnement progressif) semblent une excellente solution. Dans cette thèse, nous présentons une méthode de conception d'un système multi-agent temps réel basé sur l'exploitation des techniques ``anytime''. De plus, nous prenons en compte dans notre modèle l'aspect souvent distribué des SAD.

<p>Safety-critical applications have to function correctly even in presence of faults. This thesis deals with techniques for tolerating effects of transient and intermittent faults. Reexecution, software replication, and rollback recovery with checkpointing are used to provide the required level of fault tolerance. These techniques are considered in the context of distributed real-time systems with non-preemptive static cyclic scheduling.</p><p>Safety-critical applications have strict time and cost constrains, which means that not only faults have to be tolerated but also the constraints should be satisfied. Hence, efficient system design approaches with consideration of fault tolerance are required.</p><p>The thesis proposes several design optimization strategies and scheduling techniques that take fault tolerance into account. The design optimization tasks addressed include, among others, process mapping, fault tolerance policy assignment, and checkpoint distribution.</p><p>Dedicated scheduling techniques and mapping optimization strategies are also proposed to handle customized transparency requirements associated with processes and messages. By providing fault containment, transparency can, potentially, improve testability and debugability of fault-tolerant applications.</p><p>The efficiency of the proposed scheduling techniques and design optimization strategies is evaluated with extensive experiments conducted on a number of synthetic applications and a real-life example. The experimental results show that considering fault tolerance during system-level design optimization is essential when designing cost-effective fault-tolerant embedded systems.</p>

Embedded systems have become indispensable in our life: household appliances, cars, airplanes, power plant control systems, medical equipment, telecommunication systems, space technology, they all contain digital computing systems with dedicated functionality. Most of them, if not all, are real-time systems, i.e. their responses to stimuli have timeliness constraints. The timeliness requirement has to be met despite some unpredictable, stochastic behaviour of the system. In this thesis, we address two causes of such stochastic behaviour: the application and platform-dependent stochastic task execution times, and the platform-dependent occurrence of transient faults on network links in networks-on-chip. We present three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation. Our contribution is manifold in the area of buffer and time constrained communication along unreliable on-chip links. First, we introduce the concept of communication supports, an intelligent combination between spatially and temporally redundant communication. We provide a method for constructing a sufficiently varied pool of alternative communication supports for each message. Second, we propose a heuristic for exploring the space of communication support candidates such that the task response times are minimised. The resulting time slack can be exploited by means of voltage and/or frequency scaling for communication energy reduction. Third, we introduce an algorithm for the worst-case analysis of the buffer space demand of applications implemented on networks-on-chip. Last, we propose an algorithm for communication mapping and packet timing for buffer space demand minimisation. All our contributions are supported by sets of experimental results obtained from both synthetic and real-world applications of industrial size.

The proper composition of independently developed components of an embedded real- time system is complicated due to the fact that besides the functional behavior also the non-functional properties and in particular the timing have to be compatible. Nowadays related compatibility problems have to be addressed in a cumbersome integration and configuration phase at the end of the development process, that in the worst case may fail. Therefore, a number of formal approaches have been developed, which try to guide the upfront decomposition of the embedded real-time system into components such that integration problems related to timing properties can be excluded and that suitable configurations can be found. However, the proposed solutions require a number of strong assumptions that can be hardly fulfilled or the required analysis does not scale well. In this paper, we present an approach based on timed automata that can provide the required guarantees for the later integration without strong assumptions, which are difficult to match in practice. The approach provides a modular reasoning scheme that permits to establish the required guarantees for the integration employing only local checks, which therefore also scales. It is also possible to determine potential configuration settings by means of timed game synthesis. / Die korrekte Komposition individuell entwickelter Komponenten von eingebetteten Realzeitsystemen ist eine Herausforderung, da neben funktionalen Eigenschaften auch nicht funktionale Eigenschaften berücksichtigt werden müssen. Ein Beispiel hierfür ist die Kompatibilität von Realzeiteigenschaften, welche eine entscheidende Rolle in eingebetteten Systemen spielen. Heutzutage wird die Kompatibilität derartiger Eigenschaften in einer aufwändigen Integrations- und Konfigurationstests am Ende des Entwicklungsprozesses geprüft, wobei diese Tests im schlechtesten Fall fehlschlagen. Aus diesem Grund wurde eine Zahl an formalen Verfahren Entwickelt, welche eine frühzeitige Analyse von Realzeiteigenschaften von Komponenten erlauben, sodass Inkompatibilitäten von Realzeiteigenschaften in späteren Phasen ausgeschlossen werden können. Existierenden Verfahren verlangen jedoch, dass eine Reihe von Bedingungen erfüllt sein muss, welche von realen Systemen nur schwer zu erfüllen sind, oder aber, die verwendeten Analyseverfahren skalieren nicht für größere Systeme. In dieser Arbeit wird ein Ansatz vorgestellt, welcher auf dem formalen Modell des Timed Automaton basiert und der keine Bedingungen verlangt, die von einem realen System nur schwer erfüllt werden können. Der in dieser Arbeit vorgestellte Ansatz enthält ein Framework, welches eine modulare Analyse erlaubt, bei der ausschließlich miteinender kommunizierende Komponenten paarweise überprüft werden müssen. Somit wird eine skalierbare Analyse von Realzeiteigenschaften ermöglicht, die keine Bedingungen verlangt, welche nur bedingt von realen Systemen erfüllt werden können.

Ethernet Switches are widely used in real-time distributed systems as a solution to guarantee the real-time behavior in communication. In this solution there are still some limitations which are the important obstacles obtaining timeliness in the network. These limitations are the limited number of priority levels as well as the possibility of memory overruns with consequent messages. The mentioned limitations can be eliminated using a master/slave technique along with FTT paradigm. The FTT-SE protocol which is a technique based on the master/slave and FTT methods was proposed to overcome the mentioned limitations. However, the FTT-SE protocol has been investigated for a small network architecture with a single switch and master node. Extension of this solution to larger networks is still an open issue. Three different architectures were suggested to scale the FTT-SE to large scale network. In this thesis we propose a solution that extends the FTT-SEprotocol while keeping the real-time behavior of the network. In this solution, we divided the network into a set of sub-networks, each contains one switch, set of slave nodes and one master node that connected to the associated switch in the network. Moreover, the switches are connected together directly without gateways and form a tree topology network. The solution includes both synchronous and asynchronous traffic in the network. We also show that the timeliness of the traffic can still be enforced. Moreover, to validate the solution we have designed and implemented a simulator based on the Matlab/Simulink which is a tool to evaluate different network architecture using Simulink blocks. All transmission can be visualized by the ordinary Scope block in the Simulink. Moreover, the end-to-end delay for all messages is calculated after the simulation running to show the response time of the network. Furthermore, the response time analysis is done for both synchronous and asynchronous messages in this thesis according to the proposed solution. The results from simulation and the analysis are compared together to validate the investigations.

In this thesis, we propose an approach to estimate the Worst Case Response Time (WCRT) of each task in a preemptive multi-tasking single-processor real-time system utilizing an L1 cache. The approach combines inter-task cache eviction analysis and intra-task cache access analysis to estimate the Cache Related Preemption Delay (CRPD). CRPD caused by preempting task(s) is then incorporated into WCRT analysis. We also propose a prioritized cache to reduce CRPD by exploiting cache partitioning technique. Our WCRT analysis approach is then applied to analyze the behavior of a prioritized cache. Four sets of applications with up to six concurrent tasks running are used to test our WCRT analysis approach and the prioritized cache. The experimental results show that our WCRT analysis approach can tighten the WCRT estimate by up to 32% (1.4X) over prior state-of-the-art. By using a prioritized cache, we can reduce the WCRT estimate of tasks by up to 26%, as compared to a conventional set associative cache.

In this thesis, the problem of optimal resource allocation in real-time systems is studied. A recently proposed resource allocation approach called Q-RAM (Quality of Service based Resource Allocation Model) is investigated in detail. The goal of the Q-RAM based approaches is to minimize the execution speed in real-time systems while meeting resource constraints and maximizing total utility. Phased array radar system is an example of a system in which multiple tasks contend for multiple resources in order to satisfy their requirements. In this system, multiple targets are tracked (each a separate task) by the radar system simultaneously requiring processor and energy resources of the radar system. Phased array radar system is considered as an illustrative application area in order to comparatively evaluate the resource allocation approaches. For the problem of optimal resource allocation with single resource type, the Q-RAM algorithm appears incompletely specified, namely it does not have a termination criteria set that can terminate the algorithm in all possible cases. In the present study, first, the Q-RAM solution approach to the radar resource allocation problem with single resource type is extended to give a global optimal solution in all possible termination cases. For the case of multiple resource types, the Q-RAM approach can only generate near-optimal results. In this thesis, for the formulated radar resource allocation problem with multiple resource types, the Methods of Feasible Directions are considered as an alternative solution approach. For the multiple resource type case, the performances of both the Q-RAM approach and the Methods of Feasible Directions are investigated in terms of optimality and convergence speed with the help of Monte-Carlo simulations. It is observed from the results of the simulation experiments that the Gradient Projection Method produce results outperforming the Q-RAM approach in closeness to optimality with comparable execution times.

No description available.

Performance analysis is an objective method of gathering the data of performance, and generally transforms these observations into numerical data. Performance indicators, as well as a selection or elements of sucessful outcome, have often been used in order to feedback augmented information in performance analysis systems, but they have rarely been considered within the classification of performance analysis systems based on timing of analysis and feedback. The main aim of this study is to investigate performance indicators used within real-time and lapsed time systems so that the definitions of the performance indicators, the effectiveness of the performance indicators, their reliability and validity within real time analysis systems can be analyzed.