Embedded Software Timing: Methodology, Analysis and Practical Tips with a Focus on Automotive

Description

Without correct timing, there is no safe and reliable embedded software. This book shows how to consider timing early in the development process for embedded systems, how to solve acute timing problems, how to perform timing optimization, and how to address the aspect of timing verification. The book is organized in twelve chapters. The first three cover various basics of microprocessor technologies and the operating systems used therein. The next four chapters cover timing problems both in theory and practice, covering also various timing analysis techniques as well as special issues like multi- and many-core timing. Chapter 8 deals with aspects of timing optimization, followed by chapter 9 that highlights various methodological issues of the actual development process. Chapter 10 presents timing analysis in AUTOSAR in detail, while chapter 11 focuses on safety aspects and timing verification. Finally, chapter 12 provides an outlook on upcoming and future developments in software timing. The number of embedded systems that we encounter in everyday life is growing steadily. At the same time, the complexity of the software is constantly increasing. This book is mainly written for software developers and project leaders in industry. It is enriched by many practical examples mostly from the automotive domain, yet the vast majority of the book is relevant for any embedded software project. This way it is also well-suited as a textbook for academic courses with a strong practical emphasis, e.g. at applied sciences universities. Features and Benefits * Shows how to consider timing in the development process for embedded systems, how to solve timing problems, and how to address timing verification * Enriched by many practical examples mostly from the automotive domain * Mainly written for software developers and project leaders in industry Preface Acknowledgments Contents 1 General Basics 1.1 Real-Time 1.2 Phase Driven Process Model: The V-Model 1.2.1 The V-Model in Connection with Timing 1.3 Build Process: From the Model to the Executable 1.3.1 Model-Based Software Development and Code Generation 1.3.2 C Preprocessor 1.3.3 C Compiler 1.3.4 Code Optimization by the Compiler 1.3.5 Assembler 1.3.6 Linker 1.3.7 Locator 1.3.8 Linker Script 1.4 Summary 2 Microprocessor Technology Basics 2.1 Microprocessor Design 2.1.1 CISC vs. RISC 2.1.2 Register 2.2 Code Execution 2.3 Memory Addressing and Addressing Modes 2.3.1 The Most Important Addressing Modes for Data Accesses 2.3.2 Addressing Modes for Jumps and Calls 2.3.3 Selecting Addressing Modes 2.3.3.1 Explicit Usage of Sections 2.3.3.2 Automatic Assignment to Near Section Based Upon Size 2.4 Wait States and Burst Accesses 2.5 Cache 2.5.1 Cache Structure and Cache Rows 2.5.2 Associative Caches and Cache Eviction 2.5.3 Cache Consistency and Cache Coherency 2.6 Pipeline 2.6.1 Branch Prediction Unit 2.7 Interrupts 2.8 Traps/Exceptions 2.9 Data Consistency 2.10 Comparison of Desktop Processors Versus Embedded Processors 2.11 Summary 3 Operating Systems 3.1 No OS: Endless-Loop Plus Interrupts 3.1.1 Example Implementation with Periodic Interrupt 3.1.2 Polling: Implementation Without Interrupts 3.1.3 Scalability 3.2 OSEK/VDX 3.2.1 Tasks 3.2.2 Interrupts 3.2.3 ErrorHook 3.2.4 Basic Scheduling Strategy 3.2.4.1 Multiple Task Activation 3.2.4.2 Resource Protection and Priority Ceiling Protocol 3.2.4.3 Scheduling Strategy: Preemptive, Non-preemptive, and Mixed 3.3 Cooperative and Preemptive Multitasking 3.3.1 Illustration with Two Traces (Example 1) 3.3.2 Stack Consumption (Example 2) 3.3.3 Ensuring Data Consistency 3.3.4 Limitations of Cooperative Multitasking 3.3.5 Possible Optimization for Fewer OS Schedule() Calls 3.3.6 Summary Advantages of the Cooperative Multitasking Approach Advantages of the Preemptive Multitasking Approach 3.4 POSIX PSE51: Minimal Realtime System Profile PSE52: Realtime Controller System Profile PSE53: Dedicated Realtime System Profile PSE54: Multi-Purpose Realtime System Profile 3.4.1 Process 3.4.2 Thread 3.4.3 State Diagram of POSIX Threads 3.4.4 Scheduling Strategy 3.5 Summary 4 Timing Theory 4.1 Timing Parameters 4.1.1 RTOS Scheduling (OSEK, AUTOSAR CP, etc.) Timing Parameters 4.1.2 Timing Parameters Related to POSIX 4.2 Statistical Aspects 4.2.1 Minimum and Maximum 4.2.2 Average 4.2.3 Histograms 4.2.4 Occurrence Patterns of Irregular Events 4.3 CPU Load 4.3.1 Definitions 4.3.2 Selecting an Observation Frame 4.3.3 Scaled CPU Load 4.3.4 CPU Load When Using a Background Task 4.4 Bus Load 4.5 Logical Execution Time (LET) 4.6 Summary 5 Timing Analysis Techniques 5.1 Overview, Layered View 5.1.1 Communication Level 5.1.2 Scheduling Level (Also RTOS Level) 5.1.3 Code Level 5.2 Definitions of Terms 5.2.1 Tracing 5.2.2 Profiling, Timing Measurement, and Tracing (Again) 5.3 Static Code Analysis 5.3.1 Fundamental Functionality and Workflow 5.3.2 Use Cases 5.3.3 Limits of Static Code Analysis 5.3.3.1 Indirect Function Calls 5.3.3.2 Recursion 5.3.3.3 Upper Loop Bounds 5.3.3.4 Annotation 5.3.3.5 Modes of Operation and Mutually Exclusive Code 5.3.3.6 Over-Estimation 5.3.3.7 Interrupts, Multi-Core, and Transient Errors 5.3.4 Interview with an Expert of Static Code Analysis 5.4 Code Simulation 5.4.1 Functionality and Workflow 5.4.2 Use Cases 5.4.3 Limits of Static Code Simulation 5.4.4 Interview with an Expert in the Area of Code Simulation 5.5 Timing Measurement 5.5.1 Basic Functionality and Workflow 5.5.1.1 Measuring Without Port-Pins 5.5.1.2 Measuring the Net Runtime CET 5.5.1.3 OSEK PreTaskHook/PostTaskHook 5.5.1.4 Measuring the CPU Load Using an Idle Loop Counter 5.5.1.5 Measurements Using `Performance Counters' 5.5.1.6 Measurement Using `Ping' 5.5.2 Use Cases 5.5.3 Limits of Timing Measurement 5.5.4 Interview with an Expert of Timing Measurement 5.6 Hardware-Based Tracing 5.6.1 Basic Functionality and Workflow 5.6.1.1 Instruction Tracing for Program-Flow Analysis 5.6.1.2 Data Trace 5.6.2 Use Cases 5.6.3 Limits of Hardware-Based Tracing 5.6.4 Interview with Experts for Hardware-Based Tracing 5.7 Instrumentation-Based Tracing 5.7.1 Basic Functionality and Workflow 5.7.1.1 Software-Based Tracing with External Trace Buffer 5.7.1.2 Pure Software-Based Tracing 5.7.1.3 The Instrumentation of the Software 5.7.1.4 Instrumentation at Runtime 5.7.1.5 Synchronization of Traces from Different Sources 5.7.2 Use Cases 5.7.2.1 Timing Analysis at the Code Level 5.7.2.2 Timing Analysis at the Scheduling Level 5.7.2.3 Analysis of Data-Flow, Communication, and Synchronization 5.7.3 Limits of Instrumentation-Based Tracing 5.7.3.1 Incomplete Test Vectors 5.7.3.2 Overhead with Respect to Additional Runtime 5.7.3.3 Overhead with Respect to Memory Consumption 5.7.3.4 Interface of the Tracing Tool to the Outside World 5.7.4 Interview with an Instrumentation-Based Tracing Expert 5.8 Scheduling Simulation 5.8.1 Basic Functionality and Workflow 5.8.1.1 Import of Data from Other Tools 5.8.2 Use Cases 5.8.3 Limits of Scheduling Simulation 5.8.4 Interview with a Scheduling Simulation Expert 5.9 Static Scheduling Analysis 5.9.1 Basic Functionality and Workflow 5.9.2 Use Cases 5.9.2.1 Tool Example: chronVAL by INCHRON 5.9.3 Limits of Static Scheduling Analysis 5.9.4 Interview with a Static Scheduling Analysis Expert 5.10 Optimization Using Evolutionary Algorithms 5.11 Timing Analysis Techniques in the V-Model 6 Practical Examples of Timing Problems 6.1 Where Do All the Interrupts Come From? 6.2 OSEK ECC: Rarely the Best Choice 6.3 Rare Crashes 17 min After Reset 6.4 Missing or Duplicated Sensor Data 6.5 In a Race with the Handbrake On 6.6 Measurement Delivers WCET Results Greater Than Those from Static Code Analysis 6.7 Network Management Messages Appear too Soon 6.8 Seamless Timing Process in a Mass-Production Project 6.9 Timing Analysis Saves OEM e12m 6.10 Summary 7 Multi-Core, Many-Core, and Multi-ECU Timing 7.1 Multi-Core Basics 7.1.1 Amdahl vs. Gustafson: Who Is Right? 7.1.2 CPU Cores: Homogeneous, Heterogeneous, or Lock-Step? 7.1.3 Lock-Step Multi-Core 7.1.4 Infineon AURIX: Homogenous, Heterogeneous, and Lock-Step 7.2 Different Types of Parallel Execution 7.2.1 Application Parallelism 7.2.2 Function Parallelism 7.2.2.1 Switching from Single-Core to Multi-Core: Example `Bubblesort' 7.2.2.2 Duplicate Parallelism vs. Pipeline Parallelism Advantages of Parallelization Through Multiplication Advantages of Parallelization Through Sequencing 7.2.3 Instruction Parallelism 7.3 Data Consistency, Spinlocks 7.3.1 The Ideal Solution for Ensuring Data Consistency 7.3.2 The Costs of Ensuring Data Consistency 7.4 Cloning of Memory Addresses 7.5 Summary 8 Timing Optimization 8.1 Timing Optimization at the Scheduling Level 8.1.1 Prevention of Cross-Core Communication 8.1.2 Separation of Computationally Intensive Code and Interrupts 8.1.3 Avoiding the Use of ECC Tasks 8.1.4 Sensible Use of Heterogeneous Multi-Core Processors 8.1.5 Avoiding the Necessity for Mechanisms That Ensure Data Consistency 8.1.6 Load Balancing with Optimized Offsets for Periodical Tasks 8.1.7 Splitting of Tasks 8.1.8 Moving Functionality to Less Frequently Executed Tasks 8.2 Timing Optimization of Memory Usage 8.2.1 Optimal Use of Fast Memory 8.2.2 Alignment of Data 8.2.3 Alignment of Code and Cache Optimization 8.3 Timing Optimization at Code Level 8.3.1 Optimization of Small, Frequently-Called Functions 8.3.2 Optimization of the Function sqrt 8.3.3 Linear Core IDs for the AURIX 8.3.4 Calculating to Saturation 8.3.5 Processor-Specific Instructions in General 8.3.6 Compiler Optimizations 8.3.7 Code Optimization Using the Example memcpy 8.4 Summary and Guidelines for Timing Optimization 9 Methodology During the Development Process 9.1 Requirements Related to Timing 9.1.1 Timing Requirements 9.1.1.1 Identification of Timing Requirements Through Interviews 9.1.1.2 Formats for Timing Requirements 9.1.2 Requirements Regarding Methodology and Tools 9.1.3 Generic Requirement Templates 9.2 Collaboration During the Development 9.3 Timing Concept, Scheduling Layout, and OS Configuration 9.4 Timing Debugging 9.5 Timing Optimization 9.6 Timing Verification 9.6.1 Test Phase ``Profiling'' 9.6.2 Test Phase `POI (Point of Interest) Tracing' 9.6.3 Test Phase `Corner Cases' 9.6.4 Test Phase `Empirical Determination of Headroom' 9.7 Early Consideration for Future Functionality 9.8 Timing Supervision in the Final Product 9.9 Positive Example: CoReMa by Vitesco Technologies 9.10 Summary 10 AUTOSAR 10.1 AUTOSAR Classical Platform (CP) 10.1.1 Functional Architecture 10.1.2 Software Architecture, SW-C Definition and VFB 10.1.3 RTE 10.1.4 Implementation, System Configuration, and Runnables 10.2 AUTOSAR Adaptive Platform (AP) 10.2.1 Functional Architecture 10.2.2 Software Architecture AA 10.2.3 Implementation and System Configuration 10.2.4 Deployment 10.2.5 Execution Management and Execution Client 10.2.6 Deterministic Execution and Deterministic Client 10.2.6.1 Redundant Execution 10.2.6.2 Periodical Execution 10.2.7 POSIX Scheduling 10.2.8 Timing in AUTOSAR AP 10.2.8.1 The Timing Parameters of the Deterministic Client 10.3 TIMEX (AUTOSAR Timing Extensions) 10.3.1 Goals 10.3.2 Events and Event Chains 10.3.3 TIMEX Requirement Types 10.3.4 AUTOSAR/TIMEX Views 10.4 ARTI (AUTOSAR/ASAM Run-Time Interface) 10.4.1 AUTOSAR ARTI 10.4.2 ASAM ARTI 10.5 Technical Report ``Timing Analysis'' 10.6 Summary 11 Safety and ISO 26262 11.1 Basics 11.1.1 Risk 11.1.2 SIL: Safety Integrity Level 11.1.3 Out of Context, in Context, and Proven-in-use 11.2 Safety Standards, Timing, and Timing Verification 11.3 Tools for Timing Verification 11.4 Legal Aspects 11.5 Summary 12 Outlook References Index