| 1. |
- Afshar, Sara
(författare)
-
Lock-Based Resource Sharing for Real-Time Multiprocessors
- 2017
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems are widely used in the industry and are typically resource constrained, i.e., resources such as processors, I/O devices, shared buffers or shared memory might be limited in the system. Hence, techniques that can enable an efficient usage of processor bandwidths in such systems are of great importance. Locked-based resource sharing protocols are proposed as a solution to overcome resource limitation by allowing the available resources in the system to be safely shared. In recent years, due to a dramatic enhancement in the functionality of systems, a shift from single-core processors to multi-core processors has become inevitable from an industrial perspective to tackle the raised challenges due to increased system complexity. However, the resource sharing protocols are not fully mature for multi-core processors. The two classical multi-core processor resource sharing protocols, spin-based and suspension-based protocols, although providing mutually exclusive access to resources, can introduce long blocking delays to tasks, which may be unacceptable for many industrial applications. In this thesis we enhance the performance of resource sharing protocols for partitioned scheduling, which is the de-facto scheduling standard for industrial real-time multi-core processor systems such as in AUTOSAR, in terms of timing and memory requirements. A new scheduling approach uses a resource efficient hybrid approach combining both partitioned and global scheduling where the partitioned scheduling is used to schedule the major number of tasks in the system. In such a scheduling approach applications with critical task sets use partitioned scheduling to achieve higher level of predictability. Then the unused bandwidth on each core that is remained from partitioning is used to schedule less critical task sets using global scheduling to achieve higher system utilization. These scheduling schema however lacks a proper resource sharing protocol since the existing protocols designed for partitioned and global scheduling cannot be directly applied due to the complex hybrid structure of these scheduling frameworks. In this thesis we propose a resource sharing solution for such a complex structure. Further, we provide the blocking bounds incurred to tasks under the proposed protocols and enhance the schedulability analysis, which is an essential requirement for real-time systems, with the provided blocking bounds.
|
|
| 2. |
- Ashjaei, Mohammad, 1980-
(författare)
-
Real-Time Communication over Switched Ethernet with Resource Reservation
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Due to the need for advanced computer-controlled functionality in distributed embedded systems the requirements on network communication are becoming overly intricate. This dissertation targets the requirements that are concerned with real-time guarantees, run-time adaptation, resource utilization and flexibility during the development. The Flexible Time-Triggered Switched Ethernet (FTT-SE) and Hard Real-Time Ethernet Switching (HaRTES) network architectures have emerged as two promising solutions that can cater for these requirements. However, these architectures do not support multi-hop communication as they are originally developed for single-switch networks. This dissertation presents a fundamental contribution in multi-hop real-time communication over the FTT-SE and HaRTES architectures targeting the above mentioned requirements. It proposes and evaluates various solutions for scheduling and forwarding the traffic through multiple switches in these architectures. These solutions preserve the ability of dynamic adaptation without jeopardizing real-time properties of the architectures. Moreover, the dissertation presents schedulability analyses for the timeliness verification and evaluation of the proposed solutions as well as several protocols to support run-time adaptation in the multi-hop communication. Finally, the work led to an end-to-end resource reservation framework, based on the proposed multi-hop architectures, to support flexibility during the development of the systems. The efficiency of the proposed solutions is evaluated on various case studies that are inspired from industrial systems.
|
|
| 3. |
- Becker, Matthias, 1986-
(författare)
-
Consolidating Automotive Real-Time Applications on Many-Core Platforms
- 2017
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Automotive systems have transitioned from basic transportation utilities to sophisticated systems. The rapid increase in functionality comes along with a steep increase in software complexity. This manifests itself in a surge of the number of functionalities as well as the complexity of existing functions. To cope with this transition, current trends shift away from today’s distributed architectures towards integrated architectures, where previously distributed functionality is consolidated on fewer, more powerful, computers. This can ease the integration process, reduce the hardware complexity, and ultimately save costs.One promising hardware platform for these powerful embedded computers is the many-core processor. A many-core processor hosts a vast number of compute cores, that are partitioned on tiles which are connected by a Network-on-Chip. These natural partitions can provide exclusive execution spaces for different applications, since most resources are not shared among them. Hence, natural building blocks towards temporally and spatially separated execution spaces exist as a result of the hardware architecture.Additionally to the traditional task local deadlines, automotive applications are often subject to timing constraints on the data propagation through a chain of semantically related tasks. Such requirements pose challenges to the system designer as they are only able to verify them after the system synthesis (i.e. very late in the design process).In this thesis, we present methods that transform complex timing constraints on the data propagation delay to precedence constraints between individual jobs. An execution framework for the cluster of the many-core is proposed that allows access to cluster external memory while it avoids contention on shared resources by design. A partitioning and configuration of the Network-on-Chip provides isolation between the different applications and reduces the access time from the clusters to external memory. Moreover, methods that facilitate the verification of data propagation delays in each development step are provided.
|
|
| 4. |
- Behnam, Moris, 1973-
(författare)
-
Synchronization Protocols for a Compositional Real-Time Scheduling Framework
- 2010
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we propose techniques to simplify the integration of subsystems while minimizing the overall amount of CPU resources needed to guarantee the schedulability of real-time tasks. In addition, we provide solutions to the problem of allowing for the use of logical resources requiring mutual exclusion.The contribution of the thesis is presented in three parts. In the first part, we propose a synchronization protocol, called SIRAP, to facilitate sharing of logical resources in a hierarchical scheduling framework. In addition, we extend an existing synchronization protocol, called HSRP, such that each subsystem can be developed independently. The performance of the proposed protocols is evaluated by extensive simulations. In the second part, we present an efficient schedulability analysis that exploits the lower scheduling overhead introduced by each of the proposed protocols. Finally, in the third part, we propose new methods and algorithms that find the optimal system parameters (e.g., optimal resource ceiling), that minimize the amount of CPU resources required to ensure schedulability, when using the proposed synchronization protocols in a hierarchical scheduling framework.The motivation of this work comes from an emerging industrial trend in embedded software systems development to integrate multiple applications (subsystems) on a small number of processors. The purpose of this integration is to reduce the hardware related costs as well as the communication complexity between processors. In this setting a large number of industrial applications face the problem of preserving their real-time properties after their integration onto a single processor. In addition, temporal isolation between the applications during runtime may be required to prevent failure propagation between different applications.Specifically, we propose a hierarchical scheduling framework that allows for a simplified integration of subsystems. The framework preserves the essential temporal characteristics of the subsystems, both when running in isolation as well as when they are integrated with other subsystems. In this thesis, we assume a model where a system consists of a number of subsystems. The subsystems can interact with each other using shared logical resources. The framework ensures that the individual subsystem respects its allocated share of the processor. The difficulty lies in allowing two or more subsystems to share logical resources, which introduces an additional complexity in the schedulability analysis and also increases the system load.
|
|
| 5. |
- Faragardi, Hamid Reza, 1987-
(författare)
-
Optimizing Timing-Critical Cloud Resources in a Smart Factory
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis addresses the topic of resource efficiency in the context of timing critical components that are used in the realization of a Smart Factory.The concept of the smart factory is a recent paradigm to build future production systems in a way that is both smarter and more flexible. When it comes to realization of a smart factory, three principal elements play a significant role, namely Embedded Systems, Internet of Things (IoT) and Cloud Computing. In a smart factory, efficient use of computing and communication resources is a prerequisite not only to obtain a desirable performance for running industrial applications, but also to minimize the deployment cost of the system in terms of the size and number of resources that are required to run industrial applications with an acceptable level of performance. Most industrial applications that are involved in smart factories, e.g., automation and manufacturing applications, are subject to a set of strict timing constraints that must be met for the applications to operate properly. Such applications, including underlying hardware and software components that are used to run the application, constitute a real-time system. In real-time systems, the first and major concern of the system designer is to provide a solution where all timing constraints are met. To do so we need a time-predictable IoT/Cloud Computing framework to deal with the real-time constraints that are inherent in industrial applications running in a smart factory. Afterwards, with respect to the time predictable framework, the number of required computing and communication resources can and should be optimized such that the deployed system is cost efficient. In this thesis, to investigate and present solutions that provide and improve the resource efficiency of computing and communication resources in a smart factory, we conduct research following three themes: (i) multi-core embedded processors, which are the key element in terms of computing components embedded in the machinery of a smart factory, (ii) cloud computing data centers, as the supplier of a massive data storage and a large computational power, and(iii) IoT, for providing the interconnection of computing components embedded in the objects of a smart factory. Each of these themes are targeted separately to optimize resource efficiency. For each theme, we identify key challenges when it comes to achieving a resource-efficient design of the system. We then formulate the problem and propose solutions to optimize the resource efficiency of the system, while satisfying all timing constraints reflected in the model. We then propose a comprehensive resource allocation mechanism to optimize the resource efficiency in the whole system while considering the characteristics of each of these research themes. The experimental results indicate a clear improvement when it comes to timing-critical IoT / Cloud Computing resources in a smart factory. At the level of multi-core embedded devices, the total CPU usage of a quad-core processor is shown to be improved by 11.2%. At the level of Cloud Computing, the number of cloud servers that are required to execute a given set of real-time applications is shown to be reduced by 25.5%. In terms of network components that are used to collect sensor data, our proposed approach reduces the total deployment cost of thesystem by 24%. In summary these results all contribute towards the realization of a future smart factory.
|
|
| 6. |
- Khalilzad, Nima
(författare)
-
Adaptive and Flexible Scheduling Frameworks for Component-Based Real-Time Systems
- 2015
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Modern computer systems are often designed to play a multipurpose role. Therefore, they are capable of running a number of software components (software programs) simultaneously in parallel. These software components should share the system resources (e.g. processor and network) such that all of them run and finish their computations as expected. On the other hand, a number of software components have timing requirements meaning that they should not only access the resources, but this access should also be in a timely manner. Thus, there is a need to timely share the resources among different software components. The time-sharing is often realized by reserving a time-portion of resources for each component. Such a reservation should be adequate and resource-efficient. It should be sufficient to preserve the timing properties of the components. Also, the reservations should be resource-efficient to reduce the components' footprint on the resources which in turn allows integration of more software components on a given hardware resource. In this thesis, we mainly focus on the resource-efficiency of the reservations. We consider two cases. (I) Components which can tolerate occasional timing violations (soft real-time components): in this case we adjust the reservations during run-time to match the reservation sizes based on the instantaneous requirements of the components. (II) Components which cannot tolerate any timing violations (hard real-time components): in this case we use flexible approaches which allow us to improve the resource-efficiency at the design time.
|
|
| 7. |
- Liu, Meng
(författare)
-
Real-Time Communication over Wormhole-Switched On-Chip Networks
- 2017
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In a modern industrial system, the requirement on computational capacity has increased dramatically, in order to support a higher number of functionalities, to process a larger amount of data or to make faster and safer run-time decisions. Instead of using a traditional single-core processor where threads can only be executed sequentially, multi-core and many-core processors are gaining more and more attentions nowadays. In a multi-core processor, software programs can be executed in parallel, which can thus boost the computational performance. Many-core processors are specialized multi-core processors with a larger number of cores which are designed to achieve a higher degree of parallel processing. An on-chip communication bus is a central intersection used for data-exchange between cores, memory and I/O in most multi-core processors. As the number of cores increases, more contention can occur on the communication bus which raises a bottleneck of the overall performance. Therefore, in order to reduce contention incurred on the communication bus, a many-core processor typically employs a Network-on-Chip (NoC) to achieve data-exchange. Real-time embedded systems have been widely utilized for decades. In addition to the correctness of functionalities, timeliness is also an important factor in such systems. Violation of specific timing requirements can result in performance degradation or even fatal problems. While executing real-time applications on many-core processors, the timeliness of a NoC, as a communication subsystem, is essential as well. Unfortunately, many real-time system designs over-provision resources to guarantee the fulfillment of timing requirements, which can lead to significant resource waste. For example, analysis of a NoC design yields that the network is already saturated (i.e. accepting more traffic can incur requirement violation), however, in reality the network actually has the capacity to admit more traffic. In this thesis, we target such resource wasting problems related to design and analysis of NoCs that are used in real-time systems. We propose a number of solutions to improve the schedulability of real-time traffic over wormhole-switched NoCs in order to further improve the resource utilization of the whole system. The solutions focus mainly on two aspects: (1) providing more accurate and efficient time analyses; (2) proposing more cost-effective scheduling methods.
|
|
| 8. |
- Lu, Yue
(författare)
-
Pragmatic Approaches for Timing Analysis of Real-Time Embedded Systems
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Many industrial real-time embedded systems are very large, flexible and highly configurable software systems. Such systems are becoming ever more complex, and we are reaching the stage in which even if existing timing analysis was feasible from a cost and technical perspective, the analysis results are overly pessimistic, making them less useful to practitioners. When combined with the fact that most existing real-time embedded systems tend to be probabilistic in nature due to high complexity featured by advanced hardware and more flexible and/or adaptive software applications, this advocates moving toward pragmatic timing analysis, which is not specifically limited by constrains related to intricate task execution and temporal dependencies in systems. In this thesis, we address this challenge, and we present two pragmatic timing analysis techniques for real-time embedded systems.The first contribution is a simulation-based analysis using two simple yet novel search algorithms of meta-heuristic type, i.e., a form of genetic algorithms and hill-climbing with random restarts, yielding substantially better results, comparing traditional Monte Carlo simulation-based analysis methods.As the second contribution, we discuss one major issue when using simulation-based methods for timing analysis of real-time embedded systems, i.e., model validity, which determines whether a simulation model is an accurate representation of the target system at the certain level of satisfaction, from a task response time and execution time perspective.The third contribution is a statistical timing analysis, which, unlike the traditional timing analysis, does not require worst-case execution times of tasks as inputs, and computes a probabilistic task worst-case response time estimate pertaining to a configurable task reliability requirement.In addition, a number of tools have been implemented and used for the evaluation of our research results. Our evaluations, using different simulation models depicting fictive but representative industrial control applications, have shown a clear indication that our new timing analysis techniques have the potential to be both applicable and useful in practice, as well as being complementary to software testing focusing on timing properties of real-time embedded systems that are used in various domains of industrial automation, aerospace and defense, automotive telematics, etc.
|
|
| 9. |
- Nemati, Farhang
(författare)
-
Resource Sharing in Real-Time Systems on Multiprocessors
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In recent years multiprocessor architectures have become mainstream, and multi-core processors are found in products ranging from small portable cell phones to large computer servers. In parallel, research on real-time systems has mainly focused on traditional single-core processors. Hence, in order for real-time systems to fully leverage on the extra capacity offered by new multi-core processors, new design techniques, scheduling approaches, and real-time analysis methods have to be developed. In the multi-core and multiprocessor domain there are mainly two scheduling approaches, global and partitioned scheduling. Under global scheduling each task can execute on any processor at any time while under partitioned scheduling tasks are statically allocated to processors and migration of tasks among processors is not allowed. Besides simplicity and efficiency of partitioned scheduling protocols, existing scheduling and synchronization techniques developed for single-core processor platforms can more easily be extended to partitioned scheduling. This also simplifies migration of existing systems to multi-cores. An important issue related to partitioned scheduling is the distribution of tasks among the processors, which is a bin-packing problem. In this thesis we propose a blocking-aware partitioning heuristic algorithm to distribute tasks onto the processors of a multi-core architecture. The objective of the proposed algorithm is to decrease the blocking overhead of tasks, which reduces the total utilization and has the potential to reduce the number of required processors. In industrial embedded software systems, large and complex systems are usually divided into several components (applications) each of which is developed independently without knowledge of each other, and potentially in parallel. However, the applications may share mutually exclusive resources when they co-execute on a multi-core platform which introduce a challenge for the techniques needed to ensure predictability. In this thesis we have proposed a new synchronization protocol for handling mutually exclusive resources shared among real-time applications on a multi-core platform. The schedulability analysis of each application is performed in isolation and parallel and the requirements of each application with respect to the resources it may share are included in an interface. The protocol did not originally consider any priorities among the applications. We have proposed an additional version of the protocol which grants access to resources based on priorities assigned to the applications. We have also proposed an optimal priority assignment algorithm to assign unique priorities to the applications sharing resources. Our evaluations confirm that the protocol together with the priority assignment algorithm outperforms existing alternatives in most cases. In the proposed synchronization protocol each application is assumed to be allocated on one dedicated core. However, in this thesis we have further extended the synchronization protocol to be applicable for applications allocated on multiple dedicated cores of a multi-core platform. Furthermore, we have shown how to efficiently calculate the resource hold times of resources for applications. The resource hold time of a resource for an application is the maximum duration of time that the application may lock the resource whenever it requests the resource. Finally, the thesis discusses and proposes directions for future work.
|
|
| 10. |
- Nolte, Thomas, 1977-
(författare)
-
Share-Driven Scheduling of Embedded Networks
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Many products are built from more or less independently developed subsystems. For instance, a car consists of subsystems for transmission, braking, suspension, etc. These subsystems are frequently controlled by an embedded computer system. In the automotive industry, as well as in other application domains, there is currently a trend from an approach where subsystems have dedicated computer hardware and other resources (a federated approach) to an approach where subsystems share hardware and other resources (an integrated approach). This is motivated by a strong pressure to reduce product cost, at the same time as an increasing number of subsystems are being introduced.When integrating subsystems, it is desirable that guarantees valid before integration are also valid after integration, since this would eliminate the need for costly reverifications. The computer network is a resource that is typically shared among all subsystems. Hence, a central issue when integrating subsystems is to provide an efficient scheduling of message transmissions on the network. There are essentially three families of schedulers that can be used: priority-driven schedulers that assign priorities to messages, time-driven schedulers that assign specific time-slots for transmission of specific messages, and share-driven schedulers that assign shares of the available network capacity to groups of messages.This thesis presents a framework for share-driven scheduling, to be implemented and used in embedded networks, with the aim to facilitate subsystem integration by reducing the risk of interference between subsystems. The framework is applied in the automotive domain.The initial parts of the thesis give an overview of systems, subsystems and network technologies found and used in the automotive domain. Then, the share-driven scheduling framework is presented, analytically investigated and proven, as well as evaluated in a simulation study. Finally it is shown how the framework is to be configured and used in the context of subsystem integration. The results show that the framework allows for flexible and efficient scheduling of messages with real-time constraints, facilitating integration of subsystems from a network point of view.
|
|
