| 1. |
- Andersson, Björn, et al.
(författare)
-
Exact admission-control for integrated aperiodic and periodic tasks
- 2007
-
Ingår i: Journal of Computer and System Sciences. - : Elsevier BV. - 1090-2724 .- 0022-0000. ; 73:2, s. 225-241
-
Tidskriftsartikel (refereegranskat)abstract
- Admission-controllers are used to prevent overload in systems with dynamically arriving tasks. Typically, these admission-controllers are based on sufficient (but not necessary) capacity bounds in order to maintain a low computational complexity. In this paper we present how exact admission-control for aperiodic tasks can be efficiently obtained. Our first result is an admission-controller for purely aperiodic task sets where the test has the same runtime complexity as utilization-based tests. Our second result is an extension of the previous controller for a baseload of periodic tasks. The runtime complexity of this test is lower than for any known exact admission-controller. In addition to presenting our main algorithm and evaluating its performance, we also discuss some general issues concerning admission-controllers and their implementation. (C) 2006 Elsevier Inc. All rights reserved.
|
|
| 2. |
- Claesson, Vilgot, 1968, et al.
(författare)
-
The Event-Triggered and Time-Triggered Medium-Access Methods
- 2003
-
Ingår i: Proceedings - 6th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, Hakodate, Japan, 14-16 May 2003. - 0769519288 ; , s. 131-134
-
Konferensbidrag (refereegranskat)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.
|
|
| 3. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
A Lower-Bound Algorithm for Load Balancing in Real-Time Systems
- 2004
-
Ingår i: 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
-
Konferensbidrag (refereegranskat)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.
|
|
| 4. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
A Lower-Bound Algorithm for Minimizing Network Communication in Real-Time Systems
- 2002
-
Ingår i: International Conference on Parallel Processing, 2002. Proceedings.. - 0190-3918. - 0769516777
-
Konferensbidrag (refereegranskat)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.
|
|
| 5. |
- Ekelin, Cecilia, 1973
(författare)
-
An Optimization Framework for Scheduling of Embedded Real-Time Systems
- 2004
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)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.
|
|
| 6. |
|
|
| 7. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
Evaluation of Search Heuristics for Embedded System Scheduling Problems
- 2001
-
Ingår i: 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
-
Konferensbidrag (refereegranskat)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.
|
|
| 8. |
|
|
| 9. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
The Performance of Constraint Programming for Off-line-Scheduling of Distributed Real-Time Systems
- 2002
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 10. |
- Parthasarathy, Dhasarathy, 1986, et al.
(författare)
-
Measuring design compliance using neural language models: An automotive case study
- 2022
-
Ingår i: PROMISE 2022 - Proceedings of the 18th International Conference on Predictive Models and Data Analytics in Software Engineering, co-located with ESEC/FSE 2022. - New York, NY, USA : ACM. ; , s. 12-21
-
Konferensbidrag (refereegranskat)abstract
- As the modern vehicle becomes more software-defined, it is beginning to take significant effort to avoid serious regression in software design. This is because automotive software architects rely largely upon manual review of code to spot deviations from specified design principles. Such an approach is both inefficient and prone to error. In recent days, neural language models pre-trained on source code are beginning to be used for automating a variety of programming tasks. In this work, we extend the application of such a Programming Language Model (PLM) to automate the assessment of design compliance. Using a PLM, we construct a system that assesses whether a set of query programs comply with Controller-Handler, a design pattern specified to ensure hardware abstraction in automotive control software. The assessment is based upon measuring whether the geometrical arrangement of query program embeddings, extracted from the PLM, aligns with that of a set of known implementations of the pattern. The level of alignment is then transformed into an interpretable measure of compliance. Using a controlled experiment, we demonstrate that our technique determines compliance with a precision of 92%. Also, using expert review to calibrate the automated assessment, we introduce a protocol to determine the nature of the violation, helping eventual refactoring. Results from this work indicate that neural language models can provide valuable assistance to human architects in assessing and fixing violations in automotive software design.
|
|
