| 1. |
- Claesson, Vilgot, 1968, et al.
(author)
-
The Event-Triggered and Time-Triggered Medium-Access Methods
- 2003
-
In: Proceedings - 6th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, Hakodate, Japan, 14-16 May 2003. - 0769519288 ; , s. 131-134
-
Conference paper (peer-reviewed)abstract
- The processes of accessing a shared communication media have been extensively researched in the dependability and real-time area. For embedded systems, the primary approaches have revolved around the event-triggered and the time-triggered paradigms. In this paper, our goal is to objectively and quantitatively outline the capabilities and limitations of each of these paradigms. The event-triggered approach is commonly perceived as providing high flexibility, while the time-triggered approach is expected to provide for a higher degree of predictable communication access to the media. We have quantified the spread of their differences, and provide a summary discussion about suggested best usage for each approach. The focus of our work is on the response times of the communication system, and also on the schedulability of the communication system in collaboration with tasks in the nodes.
|
|
| 2. |
- Ekelin, Cecilia, 1973, et al.
(author)
-
A Lower-Bound Algorithm for Load Balancing in Real-Time Systems
- 2004
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 3540226672 ; 3144, s. 146-158
-
Conference paper (peer-reviewed)abstract
- We study the problem of finding a safe and tight lower-bound on the load-balancing objective often found in real-time systems. Our approach involves the formulation of the Multiple Bounded Change-Making Problem which we efficiently solve by using a new symmetry-breaking algorithm. An experimental evaluation shows that the computed lower-bound is optimal in more than 70% of the cases and is able to find more than four times as many decidedly optimal solutions.
|
|
| 3. |
- Ekelin, Cecilia, 1973, et al.
(author)
-
A Lower-Bound Algorithm for Minimizing Network Communication in Real-Time Systems
- 2002
-
In: International Conference on Parallel Processing, 2002. Proceedings.. - 0190-3918. - 0769516777
-
Conference paper (peer-reviewed)abstract
- In this paper, we propose a pseudo-polynomial-time lower-bound algorithm for the problem of assigning and scheduling real-time tasks in a distributed system such that the network communication is minimized The key feature of our algorithm is translating the task assignment problem into the so called k-cut problem of a graph, which is known to be solvable in polynomial time for fixed k. Experiments show that the lower bound computed by our algorithm in fact is optimal in up to 89% of the cases and increases the speed of an overall optimization algorithm by a factor of two on average.
|
|
| 4. |
- Ekelin, Cecilia, 1973
(author)
-
An Optimization Framework for Scheduling of Embedded Real-Time Systems
- 2004
-
Doctoral thesis (other academic/artistic)abstract
- Embedded real-time systems - appearing in products such as cars and mobile phones - are nowadays common in our everyday lives. Despite this fact, the design process of such systems is still cumbersome due to the large variety of design constraints that must be considered to ensure a safe operation of the system. In particular, present scheduling techniques - that analyze the timing behavior of the system - typically assume a too limited model to truly represent the system. In addition, to make the system cost-effective its design should be optimized regarding performance measures such as resource utilization, energy consumption and robustness. Unfortunately, optimization in general is very time-consuming process, often without guarantee that the best solution will be found. This thesis addresses these problems by proposing a scheduling framework that not only enables arbitrary design constraints to be modelled but also allows for design optimization. The framework is based on constraint programming, and this thesis presents how the problem of scheduling embedded real-time systems can be modeled and solved using this technique. In addition, a number of novel techniques for reducing the runtime of the optimization algorithm are presented. This includes the identification and exclusion of symmetries in the solution space as well as fast and tight estimates of how good a solution may get. Finally, this thesis contains a performance comparison between the proposed framework and other state-of-the-art scheduling algorithms. The evaluation shows that both the quality of the solutions and the optimization time is improved over previous approaches - in many cases the order of the solution time is reduced from minutes to seconds.
|
|
| 5. |
|
|
| 6. |
- Ekelin, Cecilia, 1973, et al.
(author)
-
Evaluation of Search Heuristics for Embedded System Scheduling Problems
- 2001
-
In: Proceedings of the 7th IEEE Int’l Conference on Principles and Practice of Constraint Programming, Paphos, Cyprus, November 26 – December 1, 2001. ; , s. 640-654
-
Conference paper (peer-reviewed)abstract
- In this paper we consider the problem of optimal task allocation and scheduling in embedded real-time systems. This problem is far from trivial due to the wide range of complex constraints that typically appear in this type of systems. We therefore address this problem using constraint programming due to its expressive, yet powerful features. Our work includes an evaluation of different search heuristics, such as variable-value orderings and symmetry exclusion, for this particular problem domain. It is shown that by using search configurations appropriate for the problem, the average search complexity can be reduced by as much as an order of magnitude.
|
|
| 7. |
|
|
| 8. |
- Ekelin, Cecilia, 1973, et al.
(author)
-
The Performance of Constraint Programming for Off-line-Scheduling of Distributed Real-Time Systems
- 2002
-
Reports (other academic/artistic)abstract
- Many real-time systems are distributed in the sense that they consist of tasks that execute on dierent nodes. As a consequence of the distribution, additional task constraints concerning communication and resource sharing are imposed to the traditional timing constraints. Unfortunately, these constraints increase the computational complexity involved in finding a feasible distributed schedule for the tasks, making an off-line approach to the scheduling problem the only viable alternative. Off-line analysis is also required if the constraints must be guaranteed to always hold and if the distributed schedule should be optimal regarding some objective. State-of-the-art scheduling algorithms for these kind of systems include the application of techniques such as branch-and-bound and simulated annealing. In this paper, we present a scheduling algorithm based on constraint programming which is a technique that originates from the area of artificial intelligence. To demonstrate its usefulness for the scheduling of distributed real-time systems, we compare the performance of our algorithm with previously proposed algorithms through a number of experiments. The results from our evaluation show that the constraint programming approach not only results in faster average runtimes but also produces more and better solutions in terms of optimality.
|
|
