Real-time scheduling of embedded applications on multi-core platforms

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.

Leakage Temperature Dependency Aware Real-Time Scheduling for Power and Thermal Optimization

Catering to society’s demand for high performance computing, billions of transistors are now integrated on IC chips to deliver unprecedented performances. With increasing transistor density, the power consumption/density is growing exponentially. The increasing power consumption directly translates to the high chip temperature, which not only raises the packaging/cooling costs, but also degrades the performance/reliability and life span of the computing systems. Moreover, high chip temperature also greatly increases the leakage power consumption, which is becoming more and more significant with the continuous scaling of the transistor size. As the semiconductor industry continues to evolve, power and thermal challenges have become the most critical challenges in the design of new generations of computing systems. In this dissertation, we addressed the power/thermal issues from the system-level perspective. Specifically, we sought to employ real-time scheduling methods to optimize the power/thermal efficiency of the real-time computing systems, with leakage/ temperature dependency taken into consideration. In our research, we first explored the fundamental principles on how to employ dynamic voltage scaling (DVS) techniques to reduce the peak operating temperature when running a real-time application on a single core platform. We further proposed a novel real-time scheduling method, “M-Oscillations” to reduce the peak temperature when scheduling a hard real-time periodic task set. We also developed three checking methods to guarantee the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research from single core platform to multi-core platform. We investigated the energy estimation problem on the multi-core platforms and developed a light weight and accurate method to calculate the energy consumption for a given voltage schedule on a multi-core platform. Finally, we concluded the dissertation with elaborated discussions of future extensions of our research.

Optimum-Path Forest Applied for Breast Masses Classification

In Computer-Aided Diagnosis-based schemes in mammography analysis each module is interconnected, which directly affects the system operation as a whole. The identification of mammograms with and without masses is highly needed to reduce the false positive rates regarding the automatic selection of regions of interest for further image segmentation. This study aims to evaluate the performance of three techniques in classifying regions of interest as containing masses or without masses (without clinical findings), as well as the main contribution of this work is to introduce the Optimum-Path Forest (OPF) classifier in this context, which has never been done so far. Thus, we have compared OPF against with two sorts of neural networks in a private dataset composed by 120 images: Radial Basis Function and Multilayer Perceptron (MLP). Texture features have been used for such purpose, and the experiments have demonstrated that MLP networks have been slightly better than OPF, but the former is much faster, which can be a suitable tool for real-time recognition systems.

Towards a real-time 3D object recognition pipeline on mobile GPGPU computing platforms using low-cost RGB-D sensors

In this project, we propose the implementation of a 3D object recognition system which will be optimized to operate under demanding time constraints. The system must be robust so that objects can be recognized properly in poor light conditions and cluttered scenes with significant levels of occlusion. An important requirement must be met: the system must exhibit a reasonable performance running on a low power consumption mobile GPU computing platform (NVIDIA Jetson TK1) so that it can be integrated in mobile robotics systems, ambient intelligence or ambient assisted living applications. The acquisition system is based on the use of color and depth (RGB-D) data streams provided by low-cost 3D sensors like Microsoft Kinect or PrimeSense Carmine. The range of algorithms and applications to be implemented and integrated will be quite broad, ranging from the acquisition, outlier removal or filtering of the input data and the segmentation or characterization of regions of interest in the scene to the very object recognition and pose estimation. Furthermore, in order to validate the proposed system, we will create a 3D object dataset. It will be composed by a set of 3D models, reconstructed from common household objects, as well as a handful of test scenes in which those objects appear. The scenes will be characterized by different levels of occlusion, diverse distances from the elements to the sensor and variations on the pose of the target objects. The creation of this dataset implies the additional development of 3D data acquisition and 3D object reconstruction applications. The resulting system has many possible applications, ranging from mobile robot navigation and semantic scene labeling to human-computer interaction (HCI) systems based on visual information.

Low-cost real-time gesture recognition

A major impediment to developing real-time computer vision systems has been the computational power and level of skill required to process video streams in real-time. This has meant that many researchers have either analysed video streams off-line or used expensive dedicated hardware acceleration techniques. Recent software and hardware developments have greatly eased the development burden of realtime image analysis leading to the development of portable systems using cheap PC hardware and software exploiting the Multimedia Extension (MMX) instruction set of the Intel Pentium chip. This paper describes the implementation of a computationally efficient computer vision system for recognizing hand gestures using efficient coding and MMX-acceleration to achieve real-time performance on low cost hardware.

Cooperative framework for open real-time systems

Actualmente, os sistemas embebidos estão presentes em toda a parte. Embora grande parte da população que os utiliza não tenha a noção da sua presença, na realidade, se repentinamente estes sistemas deixassem de existir, a sociedade iria sentir a sua falta. A sua utilização massiva deve-se ao facto de estarem practicamente incorporados em quase os todos dispositivos electrónicos de consumo, telecomunicações, automação industrial e automóvel. Influenciada por este crescimento, a comunidade científica foi confrontada com novos problemas distribuídos por vários domínios científicos, dos quais são destacados a gestão da qualidade de serviço e gestão de recursos - domínio encarregue de resolver problemas relacionados com a alocação óptima de recursos físicos, tais como rede, memória e CPU. Existe na literatura um vasto conjunto de modelos que propõem soluções para vários problemas apresentados no contexto destes domínios científicos. No entanto, não é possível encontrar modelos que lidem com a gestão de recursos em ambientes de execução cooperativos e abertos com restrições temporais utilizando coligações entre diferentes nós, de forma a satisfazer os requisitos não funcionais das aplicações. Devido ao facto de estes sistemas serem dinâmicos por natureza, apresentam a característica de não ser possível conhecer, a priori, a quantidade de recursos necessários que uma aplicação irá requerer do sistema no qual irá ser executada. Este conhecimento só é adquirido aquando da execução da aplicação. De modo a garantir uma gestão eficiente dos recursos disponíveis, em sistemas que apresentam um grande dinamismo na execução de tarefas com e sem restrições temporais, é necessário garantir dois aspectos fundamentais. O primeiro está relacionado com a obtenção de garantias na execução de tarefas de tempo-real. Estas devem sempre ser executadas dentro da janela temporal requirida. O segundo aspecto refere a necessidade de garantir que todos os recursos necessários à execução das tarefas são fornecidos, com o objectivo de manter os níveis de performance quer das aplicações, quer do próprio sistema. Tendo em conta os dois aspectos acima mencionados, o projecto CooperatES foi especificado com o objectivo de permitir a dispositivos com poucos recursos uma execução colectiva de serviços com os seus vizinhos, de modo a cumprir com as complexas restrições de qualidade de serviço impostas pelos utilizadores ou pelas aplicações. Decorrendo no contexto do projecto CooperatES, o trabalho resultante desta tese tem como principal objectivo avaliar a practicabilidade dos conceitos principais propostos no âmbito do projecto. O trabalho em causa implicou a escolha e análise de uma plataforma, a análise de requisitos, a implementação e avaliação de uma framework que permite a execução cooperativa de aplicações e serviços que apresentem requisitos de qualidade de serviço. Do trabalho desenvolvido resultaram as seguintes contribuições: Análise das plataformas de código aberto que possam ser utilizadas na implementação dos conceitos relacionados com o projecto CooperatES; Critérios que influenciaram a escolha da plataforma Android e um estudo focado na análise da plataforma sob uma perspectiva de sistemas de tempo-real; Experiências na implementação dos conceitos do projecto na plataforma Android; Avaliação da practicabilidade dos conceitos propostos no projecto CooperatES; Proposta de extensões que permitam incorporar características de sistemas de tempo real abertos na plataforma Android.

Capacity sharing and stealing in serverbased real-time systems

A dynamic scheduler that supports the coexistence of guaranteed and non-guaranteed bandwidth servers is proposed. Overloads are handled by an efficient reclaiming of residual capacities originated by early completions as well as by allowing reserved capacity stealing of non-guaranteed bandwidth servers. The proposed dynamic budget accounting mechanism ensures that at a particular time the currently executing server is using a residual capacity, its own capacity or is stealing some reserved capacity, eliminating the need of additional server states or unbounded queues. The server to which the budget accounting is going to be performed is dynamically determined at the time instant when a capacity is needed. This paper describes and evaluates the proposed scheduling algorithm, showing that it can efficiently reduce the mean tardiness of periodic jobs. The achieved results become even more significant when tasks’ computation times have a large variance.

Mechanisms for reflection-based monitoring of real- time systems

Monitoring is a very important aspect to consider when developing real-time systems. However, it is also important to consider the impact of the monitoring mechanisms in the actual application. The use of Reflection can provide a clear separation between the real-time application and the implemented monitoring mechanisms, which can be introduced (reflected) into the underlying system without changing the actual application part of the code. Nevertheless, controlling the monitoring system itself is still a topic of research. The monitoring mechanisms must contain knowledge about “how to get the information out”. Therefore, this paper presents the ongoing work to define a suitable strategy for monitoring real-time systems through the use of Reflection.

CIDER - envisaging a COTS communication infrastructure for evolutionary dependable real-time systems

It is foreseen that future dependable real-time systems will also have to meet flexibility, adaptability and reconfigurability requirements. Considering the distributed nature of these computing systems, a communication infrastructure that permits to fulfil all those requirements is thus of major importance. Although Ethernet has been used primarily as an information network, there is a strong belief that some very recent technological advances will enable its use in dependable applications with real-time requirements. Indeed, several recently standardised mechanisms associated with Switched-Ethernet seem to be promising to enable communication infrastructures to support hard real-time, reliability and flexible distributed applications. This paper describes the motivation and the work being developed within the CIDER (Communication Infrastructure for Dependable Evolvable Real-Time Systems) project, which envisages the use of COTS Ethernet as an enabling technology for future dependable real-time systems. It is foreseen that the CIDER approach will constitute a relevant stream of research since it will bring together cutting edge research in the field of real-time and dependable distributed systems and the industrial eagerness to expand Ethernet responsabilities to support dependable real-time applications.

Designing real-time systems based on mono-master Profibus-DP networks

Profibus networks are widely used as the communication infrastructure for supporting distributed computer-controlled applications. Most of the times, these applications impose strict real-time requirements. Profibus-DP has gradually become the preferred Profibus application profile. It is usually implemented as a mono-master Profibus network, and is optimised for speed and efficiency. The aim of this paper is to analyse the real-time behaviour of this class of Profibus networks. Importantly, we develop a new methodology for evaluating the worst-case message response time in systems where high-priority and cyclic low-priority Profibus traffic coexist. The proposed analysis constitutes a powerful tool to guarantee prior to runtime the real-time behaviour of a distributed computer-controlled system based on a Profibus network, where the realtime traffic is supported either by high-priority or by cyclic poll Profibus messages.

To Ada or not To Ada: Adaing vs. Javaing in real-time systems

Ada is really an unfortunate Lady. After years fighting against C/C++ villains, her major lift-up (Ada 95) had brought up a promise of fortune. However, a new strong villain (Java) has appeared trying to end her struggle for survival. Ada has now to fight with her own weapons. She will only prosper by her own merits. But two questions emerge. Do they exist? Are they better than Java’s? Our opinion is that they do exist, and are not matched by any other programming language

Replication management in reliable real-time systems

Building reliable real-time applications on top of commercial off-the-shelf (COTS) components is not a straightforward task. Thus, it is essential to provide a simple and transparent programming model, in order to abstract programmers from the low-level implementation details of distribution and replication. However, the recent trend for incorporating pre-emptive multitasking applications in reliable real-time systems inherently increases its complexity. It is therefore important to provide a transparent programming model, enabling pre-emptive multitasking applications to be implemented without resorting to simultaneously dealing with both system requirements and distribution and replication issues. The distributed embedded architecture using COTS components (DEAR-COTS) architecture has been previously proposed as an architecture to support real-time and reliable distributed computer-controlled systems (DCCS) using COTS components. Within the DEAR-COTS architecture, the hard real-time subsystem provides a framework for the development of reliable real-time applications, which are the core of DCCS applications. This paper presents the proposed framework, and demonstrates how it can be used to support the transparent replication of software components.

Supporting real-time distributed computer-controlled systems with multi-hop P-NET networks

Fieldbus communication networks aim to interconnect sensors, actuators and controllers within process control applications. Therefore, they constitute the foundation upon which real-time distributed computer-controlled systems can be implemented. P-NET is a fieldbus communication standard, which uses a virtual token-passing medium-access-control mechanism. In this paper pre-run-time schedulability conditions for supporting real-time traffic with P-NET networks are established. Essentially, formulae to evaluate the upper bound of the end-to-end communication delay in P-NET messages are provided. Using this upper bound, a feasibility test is then provided to check the timing requirements for accessing remote process variables. This paper also shows how P-NET network segmentation can significantly reduce the end-to-end communication delays for messages with stringent timing requirements.

Multi-μ: an Ada 95 based architecture for fault tolerance support of real-time systems

This paper presents an architecture (Multi-μ) being implemented to study and develop software based fault tolerant mechanisms for Real-Time Systems, using the Ada language (Ada 95) and Commercial Off-The-Shelf (COTS) components. Several issues regarding fault tolerance are presented and mechanisms to achieve fault tolerance by software active replication in Ada 95 are discussed. The Multi-μ architecture, based on a specifically proposed Fault Tolerance Manager (FTManager), is then described. Finally, some considerations are made about the work being done and essential future developments.

A communication support for real-time distributed computer controlled systems

In this paper, we analyse the ability of P-NET [1] fieldbus to cope with the timing requirements of a Distributed Computer Control System (DCCS), where messages associated to discrete events should be made available within a maximum bound time. The main objective of this work is to analyse how the network access and queueing delays, imposed by P-NET’s virtual token Medium Access Control (MAC) mechanism, affect the realtime behaviour of the supported DCCS.