| 1. |
- Altmeyer, Sebastian, et al.
(författare)
-
Parametric timing analysis for complex architectures
- 2008
-
Ingår i: Proceedings - 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008. - 9780769533490 ; , s. 367-376
-
Konferensbidrag (refereegranskat)abstract
- Hard real-time systems have stringent timing constraints expressed in units of time. To ensure that a task finishes within its time-frame, the designer of such a system must be able to derive upper bounds on the task's worst-case execution time (WCET). To compute such upper bounds, timing analyses are used. These analyses require that information such as bounds on the maximum numbers of loop iterations are known statically, i.e. during design time. Parametric timing analysis softens these requirements: it yields symbolic formulas instead of single numeric values representing the upper bound on the task's execution time.In this paper, we present a new parametric timing analysis that is able to derive safe and precise results. Our method determines what the parameters of the program are, constructs parametric loop bounds, takes processor behaviour into account and attains a formula automatically. In the end, we present tests to show that the precision and runtime of our analysis are very close to those of numeric timing analysis.
|
|
| 2. |
- Barkah, Dani, et al.
(författare)
-
Evaluation of Automatic Flow Analysis for WCET Calculation on Industrial Real-Time System Code
- 2008
-
Ingår i: Proceedings - Euromicro Conference on Real-Time Systems, 2008. - 9780769532981 ; , s. 331-340
-
Konferensbidrag (refereegranskat)abstract
- A static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such analysts requires information about the possible program flows. The current practice is to provide this information manually, which can be laborious and error-prone. An alternative is to derive this information through an automated flow analysis. In this article, we present a case study where an automatic flowanalysis method was tested on industrial real-time system code. The same code was the subject of an earlier WCET case study, where it was analysed using manual annotations for the flow information. The purpose of the current study was to see to which extent the same flow information could be found automatically. The results show that for the most part this is indeed possible, and we could derive comparable WCET estimates using the automatically generated flow information. In addition, valuable insights were gained on what is needed to make flow analysis methods work on real production code.
|
|
| 3. |
- Bohlin, Markus, 1976-
(författare)
-
A Study of Combinatorial Optimization Problems in Industrial Computer Systems
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- A combinatorial optimization problem is an optimization problem where the number of possible solutions are finite and grow combinatorially with the problem size. Combinatorial problems exist everywhere in industrial systems. This thesis focuses on solving three such problems which arise within two different areas where industrial computer systems are often used. Within embedded systems and real-time systems, we investigate the problems of allocating stack memory for an system where a shared stacks may be used, and of estimating the highest response time of a task in a system of industrial complexity. We propose a number of different algorithms to compute safe upper bounds on run-time stack usage whenever the system supports stack sharing. The algorithms have in common that they can exploit commonly-available information regarding timing behaviour of the tasks in the system. Given upper bounds on the individual stack usage of the tasks, it is possible to estimate the worst-case stack behaviour by analysing the possible and impossible preemption patterns. Using relations on offset and precedences, we form a preemption graph, which is further analysed to find safe upper-bounds on the maximal preemptions chain in the system. For the special case where all tasks exist in a single static schedule and share a single stack, we propose a polynomial algorithm to solve the problem. For generalizations of this problem, we propose an exact branch-and-bound algorithm for smaller problems and a polynomial heuristic algorithm for cases where the branch-and-bound algorithm fails to find a solution in reasonable time. All algorithms are evaluated in comprehensive experimental studies. The polynomial algorithm is implemented and shipped in the developer tool set for a commercial real-time operating system, Rubus OS. The second problem we study in the thesis is how to estimate the highest response time of a specified task in a complex industrial real-time system. The response-time analysis is done using a best-effort approach, where a detailed model of the system is simulated on input constructed using a local search procedure. In an evaluation on three different systems we can see that the new algorithm were able to produce higher response times much faster than what has previously been possible. Since the analysis is based on simulation and measurement, the results are not safe in the sense that they are always higher or equal to the true response time of the system. The value of the method lies instead in that it makes it possible to analyse complex industrial systems which cannot be analysed accurately using existing safe approaches. The third problem is in the area of maintenance planning, and focus on how to dynamically plan maintenance for industrial systems. Within this area we have focused on industrial gas turbines and rail vehicles. We have developed algorithms and a planning tool which can be used to plan maintenance for gas turbines and other stationary machinery. In such problems, it is often the case that performing several maintenance actions at the same time is beneficial, since many of these jobs can be done in parallel, which reduces the total downtime of the unit. The core of the problem is therefore how to (or how not to) group maintenance activities so that a composite cost due to spare parts, labor and loss of production due to downtime is minimized. We allow each machine to have individual schedules for each component in the system. For rail vehicles, we have evaluated the effect of replanning maintenance in the case where the component maintenance deadline is set to reflect a maximum risk of breakdown in a Gaussian failure distribution. In such a model, we show by simulation that replanning of maintenance can reduce the number of maintenance stops when the variance and expected value of the distribution are increased. For the gas turbine maintenance planning problem, we have evaluated the planning software on a real-world scenario from the oil and gas industry and compared it to the solutions obtained from a commercial integer programming solver. It is estimated that the availability increase from using our planning software is between 0.5 to 1.0 %, which is substantial considering that availability is currently already at 97-98 %.
|
|
| 4. |
- Bygde, Stefan, et al.
(författare)
-
An Efficient Algorithm for Parametric WCET Calculation
- 2009
-
Ingår i: 2009 15TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS. - LOS ALAMITOS : IEEE COMPUTER SOC. - 9780769537870 ; , s. 13-21
-
Konferensbidrag (refereegranskat)abstract
- Static WCET analysis is a process dedicated to derive a safe upper bound of the worst-case execution time of a program. In many real-time systems, however, a constant global WCET estimate is not always so useful since a program may behave very differently depending on its configuration or mode. A parametric WCET analysis derives the upper bound as formula rather than a constant. This paper presents a new efficient algorithm that can obtain a safe parametric estimate of the WCET of a program. This algorithm is evaluated on a large set of benchmarks and compared to a previous approach to parametric WCET calculation. The evaluation shows that the new algorithm, to the cost of some imprecision, scales much better and can handle more realistic programs than the previous approach.
|
|
| 5. |
- Bygde, Stefan, et al.
(författare)
-
Towards an automatic parametric WCET analysis
- 2008
-
Ingår i: OpenAccess Ser. Informatics. - 9783939897101 ; , s. 9-17
-
Konferensbidrag (refereegranskat)abstract
- Static WCET analysis obtains a safe estimation of the WCET of a program. The timing behaviour of a program depends in many cases on input, and an analysis could take advantage of this information to produce a formula in input variables as estimation of the WCET, rather than a constant. A method to do this was suggested in [12]. We have implemented a working prototype of the method to evaluate its feasibility in practice. We show how to reduce complexity of the method and how to simplify parts of it to make it practical for implementation. The prototype implementation indicates that the method presented in [12] successfully can be implemented for a simple imperative language, mostly by using existing libraries.
|
|
| 6. |
- Carlson, Jan, 1976-
(författare)
-
Event Pattern Detection for Embedded Systems
- 2007
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Events play an important role in many computer systems, from small reactive embedded applications to large distributed systems. Many applications react to events generated by a graphical user interface or by external sensors that monitor the system environment, and other systems use events for communication and synchronisation between independent subsystems. In some applications, however, individual event occurrences are not the main point of concern. Instead, the system should respond to certain event patterns, such as "the start button being pushed, followed by a temperature alarm within two seconds". One way to specify such event patterns is by means of an event algebra with operators for combining the simple events of a system into specifications of complex patterns.This thesis presents an event algebra with two important characteristics. First, it complies with a number of algebraic laws, which shows that the algebra operators behave as expected. Second, any pattern represented by an expression in this algebra can be efficiently detected with bounded resources in terms of memory and time, which is particularly important when event pattern detection is used in embedded systems, where resource efficiency and predictability are crucial.In addition to the formal algebra semantics and an efficient detection algorithm, the thesis describes how event pattern detection can be used in real-time systems without support from the underlying operating system, and presents schedulability theory for such systems. It also describes how the event algebra can be combined with a component model for embedded system, to support high level design of systems that react to event patterns.
|
|
| 7. |
- Curuklu, Baran, 1969-
(författare)
-
A Canonical Model of the Primary Visual Cortex
- 2005
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Ny datormodell visar hur hjärnan behandlar informationBaran Çürüklüs forskning handlar om att förstå hur syncentret i hjärnan fungerar. Detta är viktigt för forskningen inom neurovetenskap och artificiell intelligens.Under de senaste decennierna har hjärnforskningen visat att olika centra av hjärnbarken hos en och samma art har liknande struktur och att det finns stora likheter mellan olika arters hjärnbark. Dessa resultat tyder också på att nerv cellerna använder ett universellt språk när de kommunicerar med varandra. Dessutom verkar det finns generella regler som kan förklara hur hjärnan utvecklas och får sin slutliga form. En direkt konsekvens av dessa hypoteser är att Baran Çürüklüs forskning på syncentret kan ha stor inverkan på forskning på andra delar av hjärnan.Syncentret är den del av hjärnbarken som tar emot de inkommande signaler från ögat. Syncentret är en mycket viktig del av hjärnan och innehåller uppskattningsvis 40 % av hjärnbarkens nerv celler. Baran Çürüklü har i detalj kartlagt svarsegenskaperna hos nerv cellerna i den primära visuella hjärnbarken under hjärnans utvecklingsförlopp. Detta arbete bygger på upptäckten av Hubel och Wiesel om att nerv cellerna i den primära visuella hjärnbarken reagerar på kontrastkanter. Deras forskning har resulterat i feedforward modellen som är en viktig del av arbetet som har gett dem Nobelpriset i fysiologi/medicin (1981).Trots att denna modell har varit den mest refererade modellen i litteraturen så återstår fortfarande mycket forskning för att förstå nerv cellernas svarsegenskaper. Baran Çürüklüs modell kompletterar feedforward-modellen genom att bl.a. förklara hur hjärnan kan känna igen former under olika kontrastförhållanden. Modellen visar också hur omgivningen inverkar på syncentrets utvecklingsförlopp.
|
|
| 8. |
- Dodig-Crnkovic, Gordana, 1955-
(författare)
-
Investigations into Information Semantics and Ethics of Computing
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The recent development of the research field of Computing and Philosophy has triggered investigations into the theoretical foundations of computing and information.This thesis consists of two parts which are the result of studies in two areas of Philosophy of Computing (PC) and Philosophy of Information (PI) regarding the production of meaning (semantics) and the value system with applications (ethics).The first part develops a unified dual-aspect theory of information and computation, in which information is characterized as structure, and computation is the information dynamics. This enables naturalization of epistemology, based on interactive information representation and communication. In the study of systems modeling, meaning, truth and agency are discussed within the framework of the PI/PC unification.The second part of the thesis addresses the necessity of ethical judgment in rational agency illustrated by the problem of information privacy and surveillance in the networked society. The value grounds and socio-technological solutions for securing trustworthiness of computing are analyzed. Privacy issues clearly show the need for computing professionals to contribute to understanding of the technological mechanisms of Information and Communication Technology.The main original contribution of this thesis is the unified dual-aspect theory of computation/information. Semantics of information is seen as a part of the data-information-knowledge structuring, in which complex structures are self-organized by the computational processing of information. Within the unified model, complexity is a result of computational processes on informational structures. The thesis argues for the necessity of computing beyond the Turing-Church limit, motivated by natural computation, and wider by pancomputationalism and paninformationalism, seen as two complementary views of the same physical reality. Moreover, it follows that pancomputationalism does not depend on the assumption that the physical world on some basic level is digital. Contrary to many believes it is entirely compatible with dual (analogue/digital) quantum-mechanical computing.
|
|
| 9. |
- Ermedahl, Andreas, et al.
(författare)
-
Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis
- 2007
-
Ingår i: OpenAccess Series in Informatics, Volume 6, 2007. - 9783939897057
-
Konferensbidrag (refereegranskat)abstract
- Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for static derivation of precise WCET estimates is upper bounds on the number of times different loops can be iterated. In this paper we present an approach for deriving upper loop bounds based on a combination of standard program analysis techniques. The idea is to bound the number of different states in the loop which can influence the exit conditions. Given that the loop terminates, this number provides an upper loop bound. An algorithm based on the approach has been implemented in our WCET analysis tool SWEET. We evaluate the algorithm on a number of standard WCET benchmarks, giving evidence that it is capable to derive valid bounds for many types of loops.
|
|
| 10. |
- Faxén, Karl-Filip, et al.
(författare)
-
Multicore computing--the state of the art
- 2009
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This document presents the current state of the art in multicore computing, in hardware and software, as well as ongoing activities, especially in Sweden. To a large extent, it draws on the presentations given at the Multicore Days 2008 organized by SICS, Swedish Multicore Initiative and Ericsson Software Research but the published literature and the experience of the authors has been equally important sources. It is clear that multicore processors will be with us for the foreseeable future; there seems to be no alternative way to provide substantial increases of microprocessor performance in the coming years. While processors with a few (2–8) cores are common today, this number is projected to grow as we enter the era of manycore computing. The road ahead for multicore and manycore hardware seems relatively clear, although some issues like the organization of the on-chip memory hierarchy remain to be settled. Multicore software is however much less mature, with fundamental questions of programming models, languages, tools and methodologies still outstanding.
|
|
| 11. |
- Gustafsson, Jan, et al.
(författare)
-
ALF - A Language for WCET Flow Analysis
- 2009
-
Ingår i: OpenAccess Series in Informatics Volume 10, 2009. - 9783939897149
-
Konferensbidrag (refereegranskat)abstract
- Static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is the flow analysis, which derives bounds on the number of times different code entities can be executed. Examples of flow information derived by a flow analysis are loop bounds and infeasible paths. Flow analysis can be performed on source code, intermediate code, or binary code: for the latter, there is a proliferation of instruction sets. Thus, flow analysis must deal with many code formats. However, the basic flow analysis techniques are more or less the same regardless of the code format. Thus, an interesting option is to define a common code format for flow analysis, which also allows for easy translation from the other formats. Flow analyses for this common format will then be portable, in principle supporting all types of code formats which can be translated to this format. Further, a common format simplifies the development of flow analyses, since only one specific code format needs to be targeted. This paper presents such a common code format, the ALF language (ARTIST2 Language for WCET Flow Analysis).
|
|
| 12. |
- Gustafsson, Jan, et al.
(författare)
-
ALF (ARTIST2 Language for Flow Analysis) Specification
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- ALF (ARTIST2 Language for Flow Analysis) is a language intended to be used for flow analysis in conjunction with WCET(Worst Case Execution Time) analysis. ALF is designed to be possible to generate from a rich set of sources: linked binaries,source code, compiler intermediate formats, and possibly more.
|
|
| 13. |
- Gustafsson, Jan, et al.
(författare)
-
Algorithms for Infeasible Path Calculation
- 2006
-
Ingår i: OpenAccess Series in InformaticsVolume 4, 2006. - 9783939897033
-
Konferensbidrag (refereegranskat)abstract
- Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is to derive flow information, such as loop bounds and infeasible paths. Such flow information can be provided as either as annotations by the user, can be automatically calculated by a flow analysis, or by a combination of both. To make the analysis as simple, automatic and safe as possible, this flow information should be calculated automatically with no or very limited user interaction. In this paper we present three novel algorithms to calculate infeasible paths. The algorithms are all designed to be simple and efficient, both in terms of generated flow facts and in analysis running time. The algorithms have been implemented and tested for a set of WCET benchmarks programs.
|
|
| 14. |
- Gustafsson, Jan, et al.
(författare)
-
ALL-TIMES - a European Project on Integrating Timing Technology
- 2008
-
Ingår i: Communications in Computer and Information Science, Volume 17. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540884781 ; , s. 445-459
-
Konferensbidrag (refereegranskat)abstract
- ALL-TIMES is a research project within the EC 7th Framework Programme. The project concerns embedded systems that are subject to safety, availability, reliability, and performance requirements. Increasingly, these requirements relate to correct timing. Consequently, the need for appropriate timing analysis methods and tools is growing rapidly. An increasing number of sophisticated and technically mature timing analysis tools and methods are becoming available commercially and in academia. However, tools and methods have historically been developed in isolation, and the potential users are missing a process-related and continuous tool- and methodology-support. Due to this fragmentation, the timing analysis tool landscape does not yet fully exploit its potential.The ALL-TIMES project aims at: combining independent research results into a consistent methodology, integrating available timing tools into a single framework, and developing new timing analysis methods and tools where appropriate.ALL-TIMES will enable interoperability of the various tools from leading commercial vendors and universities alike, and develop integrated tool chains using as well as creating open tool frameworks and interfaces. In order to evaluate the tool integrations, a number of industrial case studies will be performed.This paper describes the aims of the ALL-TIMES project, the partners, and the planned work.
|
|
| 15. |
- Gustafsson, Jan, et al.
(författare)
-
Approximate Worst-Case Execution Time Analysis for Early Stage Embedded Systems Development
- 2009
-
Ingår i: SOFTWARE TECHNOLOGIES FOR EMBEDDED AND UBIQUITOUS SYSTEMS, PROCEEDINGS. - Berlin, Heidelberg : Springer. - 9783642102646 ; , s. 308-319
-
Bokkapitel (refereegranskat)abstract
- A Worst-Case Execution Time (WCET) analysis finds upper bounds for the execution time of programs. Reliable WCET estimates are essential in the development of safety-critical embedded systems, where failures to meet timing deadlines can have catastrophic consequences. Traditionally, WCET analysis is applied only in the late stages of embedded system software development. This is problematic, since WCET estimates are often needed already in early stages of system development, for example as inputs to various kinds of high-level embedded system engineering tools such as modelling and component frameworks, scheduling analyses, timed automata, etc. Early WCET estimates are also useful for selecting a suitable processor configuration (CPU, memory, peripherals, etc.) for the embedded system. If early WCET estimates are missing, many of these early design decisions have to be made using experience and ``gut feeling''. If the final executable violates the timing bounds assumed in earlier system development stages, it may result in costly system re-design. This paper presents a novel method to derive approximate WCET estimates at early stages of the software development process. The method is currently being implemented and evaluated. The method should be applicable to a large variety of software engineering tools and hardware platforms used in embedded system development, leading to shorter development times and more reliable embedded software.
|
|
| 16. |
- Gustafsson, Jan, et al.
(författare)
-
Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis using Abstract Execution
- 2006
-
Ingår i: Proceedings - Real-Time Systems Symposium. - 0769527612 ; , s. 57-66
-
Konferensbidrag (refereegranskat)abstract
- Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for statically deriving safe and tight WCET bounds is information on the possible program flow through the program. Such flow information can be provided manually by user annotations, or automatically by a flow analysis. To make WCET analysis as simple and safe as possible, it should preferably be automatically derived, with no or very limited user interaction. In this paper we present a method for deriving such flow information called abstract execution. This method can automatically calculate loop bounds, bounds for including nested loops, as well as many types of infeasible paths. Our evaluations show that it can calculate WCET estimates automatically, without any user annotations, for a range of benchmark programs, and that our techniques for nested loops and infeasible paths sometimes can give substantially better WCET estimates than using loop bounds analysis only.
|
|
| 17. |
- Gustafsson, Jan, et al.
(författare)
-
Code Analysis for Temporal Predictability
- 2006
-
Ingår i: Real-time systems. - : Springer Science and Business Media LLC. - 0922-6443 .- 1573-1383. ; 32:3, s. 253-277
-
Tidskriftsartikel (refereegranskat)abstract
- The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements. These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided for hard real-time code development.
|
|
| 18. |
- Larsson, Thomas, 1968-
(författare)
-
Adaptive Bounding Volume Hierarchies for Efficient Collision Queries
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The need for efficient interference detection frequently arises in computer graphics, robotics, virtual prototyping, surgery simulation, computer games, and visualization. To prevent bodies passing directly through each other, the simulation system must be able to track touching or intersecting geometric primitives. In interactive simulations, in which millions of geometric primitives may be involved, highly efficient collision detection algorithms are necessary. For these reasons, new adaptive collision detection algorithms for rigid and different types of deformable polygon meshes are proposed in this thesis. The solutions are based on adaptive bounding volume hierarchies. For deformable body simulation, different refit and reconstruction schemes to efficiently update the hierarchies as the models deform are presented. These methods permit the models to change their entire shape at every time step of the simulation. The types of deformable models considered are (i) polygon meshes that are deformed by arbitrary vertex repositioning, but with the mesh topology preserved, (ii) models deformed by linear morphing of a fixed number of reference meshes, and (iii) models undergoing completely unstructured relative motion among the geometric primitives. For rigid body simulation, a novel type of bounding volume, the slab cut ball, is introduced, which improves the culling efficiency of the data structure significantly at a low storage cost. Furthermore, a solution for even tighter fitting heterogeneous hierarchies is outlined, including novel intersection tests between spheres and boxes as well as ellipsoids and boxes. The results from the practical experiments indicate that significant speedups can be achieved by using these new methods for collision queries as well as for ray shooting in complex deforming scenes.
|
|
| 19. |
- Lindhult, Johan
(författare)
-
Operational Semantics for PLEX : A Basis for Safe Parallelization
- 2008
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The emerge of multi-core computers implies a major challenge for existing software. Due to simpler cores, the applications will face decreased performance if not executed in parallel. The problem is that much of the software is sequential.Central parts of the AXE telephone exchange system from Ericsson is programmed in the language PLEX. The current software is executed on a single-processor architecture, and assumes non-preemptive execution.This thesis presents two versions of an operational semantics for PLEX; one that models execution on the current, single-processor, architecture, and one that models execution on an assumed shared-memory architecture. A formal semantics of the language is a necessity for ensuring correctness of program analysis, and program transformations.We also report on a case study of the potential memory conflicts that may arise when the existing code is allowed to be executed in parallel. We show that simple static methods are sufficient to resolve many of the potential conflicts, thereby reducing the amount of manual work that probably still needs to be performed in order to adapt the code for parallel processing.
|
|
| 20. |
- Lindhult, Johan, et al.
(författare)
-
Sequential PLEX, and its Potential for Parallel Execution
- 2007
-
Konferensbidrag (refereegranskat)abstract
- Some computer systems have been designed under the assumption that activities in the system are executed non-preemptively. Exclusive access to any shared data in such a system is automatically guaranteed as long as the system is executed on a single-processor architecture. However, if the activities are executed on a multiprocessor, exclusive access to the data must be guaranteed when memory con- flicts are possible. An analysis of the potential memory conflicts can be used to estimate the possibility for parallel execution. Central parts of the AXE telephone exchange system from Ericsson is programmed in the language PLEX. The current software is executed on a single-processor architecture, and assumes non-preemptive execution. In this paper, we investigate some existing PLEX code with respect to the number of possible shared-memory conflicts that could arise if the existing code, without modifications, would be executed on a parallel architecture. Our initial results are promising; only by examining the data that actually can be shared, we manage to reduce the number of conflicts from the assumed 100% to figures between 25-75% for the observed programs. Simple optimizations decrease the numbers even further.
|
|
| 21. |
- Lisper, Björn, et al.
(författare)
-
Model Identification for WCET Analysis
- 2009
-
Ingår i: Proc. 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2009). - 9780769536361 ; , s. 55-64
-
Konferensbidrag (refereegranskat)abstract
- Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. Static WCET analysis derives safe upper bounds. For complex hardware architectures the hardware modelling is still a challenge, leading to long analysis times and a risk of large WCET overestimation. Therefore, hybrid WCET analysis methods have appeared, where measurements are used to augment or replace the detailed low-level static WCET analysis. These methods do not in general yield a safe WCET estimate, but can still be appropriate in soft real-time systems where such WCET estimates are not crucial. In this paper we make two contributions. First, we develop a hybrid WCET analysis method, which uses regression to identify parameters in the common linear Implicit Path Enumeration Technique (IPET) model for WCET calculation. The method can use timing measurements of different granularity, including end-to-end measurements, which reduces the need for fine-grained timing measurement instrumentation. It uses a novel kind of regression, which guarantees that the identified model does not underestimate any observed execution times. Second, we initiate the development of an IPET-based theory for hybrid WCET analysis test coverage, and we formulate and prove a coverage criterion for the tests needed to identify a safe model.
|
|
| 22. |
- Lisper, Björn
(författare)
-
Trends in Timing Analysis
- 2006
-
Ingår i: From Model-Driven Design to Resource Management for Distributed Embedded Systems. - Boston, MA : Springer US. - 9780387393612 ; , s. 85-94
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Static Worst-Case Execution Time (WCET) analysis aims to find safe upper bounds to the execution time of a program. We give a brief status report on the field of static WCET analysis, and we then present a personal perspective on the current and anticipated forthcoming trends in the area.
|
|
| 23. |
- Lüders, Frank, 1971-
(författare)
-
An Evolutionary Approach to Software Components in Embedded Real-Time Systems
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Component-based software engineering denotes the practice of building software from pre-existing smaller products, in particular when this is done using standardized software component models. The main expected benefits of this practice over traditional software engineering approaches are increased productivity and timeliness of development projects. While the use of software component models has become common for desktop and server-side software, this is not the case in the domain of embedded real-time systems, presumably due to the special requirements such systems have to meet with respect to predictable timing and limited use of resources. Much research exists that aims to define new component models for this domain, typically focusing on source code components, static system configuration, and relatively narrow application domains.This dissertation explores the alternative approach of using components based on binary code, allowing dynamic configuration, and targeting a broader domain. A study of a general purpose component model shows that the model is compatible with real-time requirements, although putting some restrictions on its use may be necessary to ensure predictability. A case study demonstrates how the model has been used with advantage in an industrial control system. The dissertation furthermore proposes an approach for extending the component model with run-time services for embedded real-time systems. It presents a prototype tool for supporting such services, along with two empirical studies to evaluate the approach and the tool as well as the component model itself. One study shows that both the component model and the services provided by the tool result in very modest and predictable run-time overheads. The other study, evaluating the effects on productivity and quality of using the approach in a software development project, did not produce quantitative evidence, but concludes that the approach is promising and identifies possible adjustments to it and opportunities for further studies.
|
|
| 24. |
- Sandberg, Christer, et al.
(författare)
-
Faster WCET Flow Analysis by Program Slicing
- 2006
-
Ingår i: ACM SIGPLAN Notices, Volume 41, Issue 7, July 2006. - : Association for Computing Machinery (ACM). - 159593362X ; , s. 103-112
-
Konferensbidrag (refereegranskat)abstract
- Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. WCET analysis needs a program flow analysis to derive constraints on the possible execution paths of the analysed program, like iteration bounds for loops and dependences between conditionals.Current WCET analysis tools typically obtain flow information through manual annotations. Better support for automatic flow analysis would eliminate much of the need for this laborious work. However, to automatically derive high-quality flow information is hard, and solution techniques with large time and space complexity are often required.In this paper we describe how to use program slicing to reduce the computational need of flow analysis methods. The slicing identifes statements and variables which are guaranteed not to influence the program flow. When these are removed, the calculation time of our different flow analyses decreases, in some cases considerably.We also show how program slicing can be used to identify the input variables and globals that control the outcome of a particular loop or conditional. This should be valuable aid when performing WCET analysis and systematic testing of large and complex real-time programs.
|
|
| 25. |
- Sandell, Daniel, et al.
(författare)
-
Static Timing Analysis of Real-Time Operating System Code
- 2006
-
Ingår i: Leveraging Applications of Formal Methods. - Berlin, Heidelberg : Springer. - 9783540489283 ; , s. 146-160
-
Bokkapitel (refereegranskat)abstract
- Methods for Worst-Case Execution Time (WCET) analysis have been known for some time, and recently commercial tools have emerged. However, the technique has so far not been much used to analyse real production codes. Here, we present a case study where static WCET analysis was used to find upper time bounds for time-critical regions in a commercial real-time operating system. The purpose was not primarily to test the accuracy of the estimates, but rather to investigate the practical difficulties that arise when applying the current WCET analysis methods to this particular kind of code. In particular, we were interested in how labor-intense the analysis becomes, measured by the number of annotations to explicitly constrain the program flow which is necessary to perform the analysis. We also make some qualitative observations regarding what a WCET analysis method would need in order to perform a both convenient and tight analysis of typical operating systems code. In a second set of experiments, we analyzed some standard WCET benchmark codes compiled with different levels of optimization. The purpose of this study was to see how the different compiler optimizations affected the precision of the analysis, and again whether it affected the level of user intervention necessary to obtain an accurate WCET estimate.
|
|
| 26. |
- Santos, Marcelo, et al.
(författare)
-
Evaluation of an Additive WCET Model for Software Components
- 2008
-
Konferensbidrag (refereegranskat)abstract
- The use of component technology in embedded systems brings new challenges to this domain. One important issue is how to derive properties of the system when we know the properties of the system’s components. When the system is real-time, it is useful to find out how component composition will affect the execution time of tasks made out of components. In this work, we use a statistical design to examine and rank different hardware features with respect to their impact on the execution time at component composition. Our results indicate, for example, that main memory latency and the block size of the L2 cache have the greatest effect, while memory bandwidth has the least effect.
|
|
| 27. |
- Sehlberg, Daniel, et al.
(författare)
-
Static WCET Analysis of Real-Time Task-Oriented Code in Vehicle Control Systems
- 2006
-
Ingår i: Proceedings - ISoLA 2006: 2nd International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. - 0769530710 ; , s. 212-219
-
Konferensbidrag (refereegranskat)abstract
- Methods for Worst-Case Execution Time (WCET) analysis have been known for some time, and recently commercial tools have emerged. This technique is gradually being entered into industry to analyse real production codes. This article presents a case study where the aiT WCET analysis tool was used to find upper time bounds for task-oriented vehicular control code. The main purpose was to investigate the practical difficulties that arise when applying the current WCET analysis methods to this particular kind of code. In particular, we were interested in how labor-intense the analysis becomes, measured by the number of manual annotations necessary for calculating a WCET estimate. We were also interested how much tighter WCET estimates will become by manually adding extra annotations, and how much additional work that is needed to give these annotations. We also made some systematic comparisons between calculated and measured WCET estimates for the analysed system.
|
|
| 28. |
- Vera, Xavier, et al.
(författare)
-
Data cache locking for tight timing calculations
- 2008
-
Ingår i: ACM Transactions on Embedded Computing Systems. - : Association for Computing Machinery (ACM). - 1539-9087 .- 1558-3465. ; 7:1
-
Tidskriftsartikel (refereegranskat)abstract
- Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. In addition, caches are a source of unpredictability, resulting in programs sometimes behaving in a different way than expected. Detailed information about the number of cache misses and their causes allows us to predict cache behavior and to detect bottlenecks. Small modifications in the source code may change memory patterns, thereby altering the cache behavior. Code transformations, which take the cache behavior into account, might result in a high cache performance improvement. However, cache memory behavior is very hard to predict, thus making the task of optimizing and timing cache behavior very difficult. This article proposes and evaluates a new compiler framework that times cache behavior for multitasking systems. Our method explores the use of cache partitioning and dynamic cache locking to provide worst-case performance estimates in a safe and tight way for multitasking systems. We use cache partitioning, which divides the cache among tasks to eliminate intertask cache interferences. We combine static cache analysis and cache-locking mechanisms to ensure that all intratask conflicts, and consequently, memory access times, are exactly predictable. The results of our experiments demonstrate the capability of our framework to describe cache behavior at compile time. We compare our timing approach with a system equipped with a nonpartitioned, but statically, locked data cache. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, demonstrating that our fully predictable scheme does not compromise the performance of the transformed programs.
|
|
