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

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