Embedded systems are prevalent in today’s society and promise to be even more pervasive in the future. Applications vary from airplane jet or car controllers, communication devices like cellular phones to consumer electronics like set-top boxes. The steadily increasing number of functional requirements lead to a complex embedded hardware and software architecture. Often, applications not only have to compute correct results but have to achieve this within a given time period. Timing behavior is an important requirement if the application has to react to signals from the environment. To safely and tightly verify timing behavior is very challenging for today’s complex embedded designs. Caches are small memories close to the processor and they are needed to increase the processor performance but their influence on execution time is difficult to predict because of their complex behavior. Preemptive scheduling is popular in real-time systems to guarantee short response times and a high processor utilization. An additional cache-related preemption delay has to be considered when several tasks share the same cache and when preemptive task scheduling is used. Cache improvements can be strongly degraded by frequent replacements of cache blocks. There are several approaches to make caches more predictable and efficient. Cache partitioning and cache locking strategies are used to make cache behavior partly orthogonal. These approaches require larger caches and main memories to become effective. However, caches are usually small in embedded systems because of their high cost. While these approaches are certainly a very useful add-on to improve cache predictability and efficiency, they do not solve the problem of cache behavior prediction if all tasks shared the cache. This thesis makes several contributions to instruction and data cache timing behavior. First, we propose a novel schedulability analysis for fixed priority preemptive scheduling to consider timing effects for associative instruction caches at a context switch. The preemption delays are calculated by considering the preempted as well as the preempting task. The proposed schedulability analysis bounds the number of preemptions more tightly by excluding infeasible cache interferences. The analysis is conservative, e.g. determines a safe upper bound of the preemption delay, and has a low time complexity. As a refinement, the cache interference by multiple task preemptions is analyzed. While previous approaches calculate the worst-case preemption point and assume that each preemption takes place at this preemption point, we consider the preemption history in the calculation of the total cost for multiple task preemptions. The advantage is that the bound of the total preemption delay for multiple task preemptions can consider the preemption history. Execution time verification is often used on different levels of the system design. Less precise estimates are acceptable in early design stages while highly accurate ones are necessary for verification of hard real time constraints. Two approaches to bound the preemption delay have been proposed which both use data flow techniques but differ significantly in respect to time-complexity and analysis precision. In this thesis we combine these two approaches in a single scalable precision cache analysis to scale the analysis precision and the time-complexity. In an automotive case study we found out that control intensive applications designed with ASCET-SD and Matlab/Simulink models contain only sequential code without loops. Caches cannot increase the performance for such applications because linear code significantly limits the spacial and temporal locality of memory accesses for which a cache is optimized. Existing timing analyses focus on a single task execution. However, embedded applications are activated very frequently if not regularly. Cache lines from a previous task activation might still be available in the cache and need not be loaded during a subsequent task execution. This effect of multiple task execution can result in a significantly reduced number of cache misses. In this thesis we estimate a conservative bound of the cache contents at the beginning of task activation and consider the effect in instruction cache timing behavior. While previous analysis techniques focus on instruction caches, we also provide a novel timing analysis for data caches. Data cache behavior is more difficult to predict because it depends on control flow of the application but also on the input data. While instruction addresses are fixed, a single instruction can access different data memory addresses, for example operations on an array. In this thesis we propose a static timing analysis for data caches which considers input data dependency of memory accesses. Finally, we integrate instruction and data cache timing analysis in a measurement-based WCET-analysis tool, which has been developed in previous work. Measuring the execution time requires insertion of instrumentation points which disturbs the temporal behavior of an application. In this thesis we present a novel instrumentation methodology that reduces the number of instrumentation points. In summary, this thesis provides a sophisticated framework to analyze instruction and data cache effects for fixed priority preemptive real-time systems.

This volume contains the proceedings of the ACM SIGPLAN Workshop on L- guages, Compilers, and Tools for Embedded Systems (LCTES 2000), held June 18, 2000, in Vancouver, Canada. Embedded systems have developed consid- ably in the past decade and we expect this technology to become even more important in computer science and engineering in the new millennium. Interest in the workshop has been con rmed by the submission of papers from all over the world. There were 43 submissions representing more than 14 countries. Each submitted paper was reviewed by at least three members of the program committee. The expert opinions of many outside reviewers were in- luable in making the selections and ensuring the high quality of the program, for which, we express our sincere gratitude. The nal program features one invited talk, twelve presentations, and ve poster presentations, which re?ect recent - vances in formal systems, compilers, tools, and hardware for embedded systems. We owe a great deal of thanks to the authors, reviewers, and the members of the program committee for making the workshop a success. Special thanks to Jim Larus, the General Chair of PLDI 2000 and Julie Goetz of ACM for all their help and support. Thanks should also be given to Sung-Soo Lim at Seoul National University for his help in coordinating the paper submission and review process. We also thank Professor Gaetano Borriello of the University of Washington for his invited talk on Chinook, a hardware-software co-synthesis CAD tool for embedded systems.

This book constitutes the joint refereed proceedings of seven international workshops held as part of OTM 2004 in Agia Napa, Cyprus in October 2004. The 73 revised papers presented together with 31 abstracts of posters from the OTM main conferences were carefully reviewed and selected from more than 150 submissions. In accordance with the 7 workshops, the papers are organized in topical sections on grid computing and its applications to data analysis; Java technologies for real-time and embedded systems; modeling inter-organizational systems; regulatory ontologies; ontologies, semantics and e-learning; PhD symposium; and interoperability.

A special mention for 2004 is in order for the new Doctoral Symposium Workshop where three young postdoc researchers organized an original setup and formula to bring PhD students together and allow them to submit their research proposals for selection. A limited number of the submissions and their approaches were independently evaluated by a panel of senior experts at the conference, and presented by the students in front of a wider audience. These students also got free access to all other parts of the OTM program, and only paid a heavily discounted fee for the Doctoral Symposium itself. (In fact their attendance was largely sponsored by the other participants!) If evaluated as successful, it is the intention of the General Chairs to expand this model in future editions of the OTM conferences and so draw in an audience of young researchers to the OnTheMove forum. All three main conferences and the associated workshops share the d- tributed aspects of modern computing systems, and the resulting applicati- pull created by the Internet and the so-called Semantic Web. For DOA 2004, the primary emphasis stayed on the distributed object infrastructure; for ODBASE 2004, it was the knowledge bases and methods required for enabling the use of formalsemantics;andforCoopIS2004themaintopicwastheinteractionofsuch technologies and methods with management issues, such as occurs in networked organizations. These subject areas naturally overlap and many submissions in factalsotreatenvisagedmutualimpactsamongthem.

Today’s embedded devices and sensor networks are becoming more and more sophisticated, requiring more efficient and highly flexible compilers. Engineers are discovering that many of the compilers in use today are ill-suited to meet the demands of more advanced computer architectures. Updated to include the latest techniques, The Compiler Design Handbook, Second Edition offers a unique opportunity for designers and researchers to update their knowledge, refine their skills, and prepare for emerging innovations. The completely revised handbook includes 14 new chapters addressing topics such as worst case execution time estimation, garbage collection, and energy aware compilation. The editors take special care to consider the growing proliferation of embedded devices, as well as the need for efficient techniques to debug faulty code. New contributors provide additional insight to chapters on register allocation, software pipelining, instruction scheduling, and type systems. Written by top researchers and designers from around the world, The Compiler Design Handbook, Second Edition gives designers the opportunity to incorporate and develop innovative techniques for optimization and code generation.

Design and Analysis of Distributed Embedded Systems is organized similar to the conference. Chapters 1 and 2 deal with specification methods and their analysis while Chapter 6 concentrates on timing and performance analysis. Chapter 3 describes approaches to system verification at different levels of abstraction. Chapter 4 deals with fault tolerance and detection. Middleware and software reuse aspects are treated in Chapter 5. Chapters 7 and 8 concentrate on the distribution related topics such as partitioning, scheduling and communication. The book closes with a chapter on design methods and frameworks.

This book constitutes the strictly refereed post-workshop proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, LCTES '98, held in Montreal, Canada, in June 1998. The 19 revised papers presented were carefully reviewed and selected from a total of 54 submissions for inclusion in the book; also included are one full paper and an abstract of an invited contribution. The papers address all current aspects of research and development in the rapidly growing area of embedded systems and real-time computing.

This book constitutes the refereed proceedings of the Second International Conference, TPNC 2013, held in Cáceres, Spain, in December 2013. The 19 revised full papers presented together with one invited talk were carefully reviewed and selected from 47 submissions. The papers are organized in topical sections on nature-inspired models of computation; synthesizing nature by means of computation; nature-inspired materials and information processing in nature.

Encompassing both computer-science and engineering aspects of real-time systems the 31 papers cover scheduling, experimental systems and applications, formal methods, synchronization, models and tools, communications, databases, timing analysis, resource allocation, and system implementation. Among the specific topics are optimizing interprocess communications for embedded systems, analyzing cache-related pre-emption delay in fixed-priority preemptive scheduling, exploiting data semantics to schedule transactions with temporal constraints, queuing theory, message transmission with timing constraints in ring networks, and approximate reachability analysis of times automata. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR.