Behavioral Intervals in Embedded Software

by Wolf, Fabian

• ISBN13: 9781402071355
• ISBN10: 1402071353
• Format: Hardcover
• Copyright: 2002-08-01
• Publisher: Kluwer Academic Pub

Summary

Behavioral Intervals in Embedded Software introduces a comprehensive approach to timing, power, and communication analysis of embedded software processes. Embedded software timing, power and communication are typically not unique but occur in intervals which result from data dependent behavior, environment timing and target system properties. In system design, these intervals are used in many ways. In some cases, only the worst case is of interest, e.g. for single processor schedulability analysis, in another context both best and worst cases are relevant, such as for multiprocessor scheduling. In all these cases, these behavioral intervals of the individual software processes are fundamental data needed to analyze system behavior. With growing importance of embedded software, formal analysis of behavioral intervals has met increasing interest. Major contributions were the introduction of implicit path enumeration and the inclusion of cache analysis. While all approaches are conservative, i.e. all possible timing behavior (or communication, power consumption) is included in the resulting intervals, the main differences are in the architecture features that are covered by the hardware model and the width of the conservative interval. The closer this interval to the real timing bounds, the higher is the practical use of formal analysis. The current analysis techniques leverage on previous work in compiler technology by using basic blocks as elementary units for architecture modeling and path analysis. The work presented here opens a new direction moving from basic block based analysis to an analysis based on larger program segments with a single execution path. Such program segments frequently extend over many basic blocks, in particular in embedded system applications. The approach combines the generality and accuracy of formal analysis with the modeling precision of cycle true simulation without compromising formal completeness. The results show that with this combination of tracing and formal analysis both higher precision than previous approaches leading to tighter and more realistic intervals can be obtained and easier adaptation due to the use of standard off-the-shelf cache simulators, cycle-true processor models or evaluation boards is possible. Behavioral Intervals in Embedded Software will be a useful reference for academics as well as research scientists who are active in the field of Design Automation and Embedded Systems.

Table of Contents

List of Figures	xi
List of Tables	xv
Foreword	xvii
Preface	xix
Abstract	xxi
Introduction	1	(8)
Embedded Real-Time Systems	1	(2)
Software Performance Estimation	3	(3)
Application Domains	6	(1)
Codesign of Embedded Real-Time Systems	6	(1)
Global System Representation	6	(1)
System Design	6	(1)
Summary and Problem Identification	7	(1)
Proposed Solution	7	(2)
Software Running Time Analysis	9	(22)
General Requirements and Background	9	(3)
Process Model	9	(1)
Influences on Process Running Time	10	(1)
Input Data and Parameters	11	(1)
Input Data Dependent Control Flow	11	(1)
Input Data Dependent Instruction Execution	12	(1)
Program Simulation and Test Patterns	12	(1)
Static Program Analysis	12	(3)
Path Identification	13	(1)
Annotations Using a Timing Analysis Language	13	(1)
Source Level Timing Scheme	14	(1)
Path Annotation Using Regular Expressions	15	(1)
Implicit Path Enumeration and Cost Model	15	(3)
Functional Constraints	15	(1)
Structural Constraints and Solution	16	(1)
Overlapping Basic Block Execution	17	(1)
Limitations and Possible Extensions	18	(1)
Other Previous Work	18	(5)
Branching Probabilities	18	(1)
Test Patterns Generation	19	(1)
Test Flow Frameworks	20	(1)
Abstract Interpretation	20	(1)
Automatic Loop Bounding	21	(1)
Symbolic Extension to Simulators	21	(1)
Source Level Timing Annotations	22	(1)
Real Time Euclid	22	(1)
Spark Proof and Timing System	23	(1)
The SYMTA Approach to Path Analysis	23	(8)
Hybrid Analysis	23	(1)
Local Cost Model	24	(1)
Informal Path Classification	25	(1)
SFP Identification and Path Clustering	26	(3)
Calculation of Global Cost	29	(1)
Limitations	29	(2)
A Formal Approach to SYMTA	31	(20)
Syntax Graph	31	(1)
Classification of Program Segments	32	(3)
Program Segment Cost	35	(1)
Validation of the Approach	36	(4)
Proof of Conservativity	36	(2)
Transition Cost	38	(1)
Functional and Structural Constraints	39	(1)
Function Calls	39	(1)
Exploitation	40	(1)
Example: Bubble Sort	40	(3)
Path Analysis	41	(1)
Global Cost Calculation	42	(1)
Limitations	43	(1)
Hierarchical Control Flow Graph	43	(1)
Context Dependent Execution	44	(7)
ATM Switch Component	46	(1)
Context Dependent Execution Cost	46	(2)
Context Dependency in Array Elements	48	(1)
Example: Integration of Context Dependent Paths	48	(2)
Conclusion	50	(1)
Formal Cache Analysis in SYMTA	51	(32)
Motivation and Background	51	(1)
Cache Properties	51	(3)
Cache and Memory Architecture	52	(1)
Instruction and Data Cache	52	(1)
Set Associativity	53	(1)
Previous Work on Cache Analysis	54	(11)
Trace Based Cache Simulation	54	(1)
First Hit/Miss Scenario	55	(1)
Cache State Transition Graph	55	(5)
Clustering in the Cache Conflict Graph	60	(1)
Use-/Define Chains for Data Access Addresses	61	(1)
Static Categorization of Cache Accesses	61	(2)
Pipeline and Cache States	63	(1)
Abstract Interpretation	63	(2)
Straight-Line Code Programs	65	(1)
Local Program Segment Simulation	65	(3)
Program Properties Found by SYMTA	65	(1)
Access Addresses and Data Caches	66	(1)
Local Simulation	66	(1)
Program Segment Cache Evaluation	67	(1)
Data Flow Analysis for Cache Sets	68	(6)
Cache Set Content Prediction	69	(1)
Hybrid Prediction Approach	70	(1)
Evaluation of Flow Analysis Results	71	(1)
Process-Level Cost Calculation	72	(1)
Cache Modeling and Representation	73	(1)
Application of Cache Constraints	73	(1)
Impact on Execution Cost	74	(1)
Process Preemptions	75	(1)
Examples for Cache Analysis	76	(6)
Direct Mapped Cache Analysis	76	(2)
Set Associative Cache Analysis	78	(4)
Conclusion	82	(1)
Program Segment Cost Analysis	83	(20)
Processor Simulators	83	(6)
Previous Work in Processor Simulation	83	(1)
Instruction Cost Addition ICA	84	(1)
Extensions to ICA	85	(1)
Program Segment Simulation PSS	85	(2)
Implemented Simulators	87	(1)
Simulator Interfaces	88	(1)
Segment-Wise Simulation Methodology	89	(3)
Simulation of the Complete Program Code	89	(1)
Simulation of Isolated Program Segments	89	(1)
Open Interface to Code Instrumentation	90	(2)
Modeling Shared Resources	92	(3)
Context Switch	92	(1)
Scheduling Strategies	93	(1)
Behavioral Intervals for Process Sequences	94	(1)
Interrupts	94	(1)
Execution Cost Measurement	95	(8)
Motivation and Problem Identification	96	(1)
Previous Work on Measurement	96	(2)
Segment-Wise Timing and Power Measurement	98	(1)
Compact Timed Trace Acquisition	99	(1)
SPARClite Timing and Power Measurement	100	(2)
Conclusion	102	(1)
Experiments and Results	103	(26)
Single Feasible Path Analysis	103	(1)
Context Dependent Path Analysis	104	(1)
Architecture Modeling by Simulation	105	(1)
Impact of Trigger Point Insertion	105	(2)
Local Cache Analysis	107	(1)
Improvements to Basic Block Based Analysis	108	(10)
SFP Analysis Without Functional Constraints	108	(4)
Cache Parameters	112	(1)
SFP Analysis With Functional Constraints	112	(1)
ILP Problem Size	113	(1)
Exploitation of Context Dependency	114	(2)
Comparing Architectures	116	(1)
OAM Component	117	(1)
Case Study: Filter on Packet Data	118	(4)
Detailed Power Analysis	122	(7)
Instruction Energy Consumption Intervals	123	(1)
Measurement of Instruction Sequences	124	(2)
Instruction Cost Addition Evaluation	126	(1)
Process-Level Energy Intervals	126	(1)
Conclusion	127	(2)
Summary and Conclusion	129	(2)
Summary	129	(1)
Conclusion	130	(1)
Appendices	131	(44)
System Implementation	131	(1)
A.1 Overview	131	(1)
A.2 Tool Flow	132	(1)
A.3 SYMTA Designer Interface	133	(1)
A.4 Path Analysis Software	134	(1)
A.4.1 Symbolic Execution	134	(1)
A.4.2 Process Mode Annotation	134	(1)
A.4.3 Path Identification	134	(1)
A.4.4 ILP Solution	134	(1)
A.5 Cache Analysis Software	135	(2)
A.5.1 Local Simulation	135	(1)
A.5.2 Set Definition Propagation	135	(1)
A.5.3 Future Work	136	(1)
A.6 Architecture Modeling	137	(3)
A.6.1 PSS: Strong ARM Simulator	137	(1)
A.6.2 Hardware Interfaces	138	(1)
A.6.3 Communication Components	138	(1)
A.6.4 Bus Controller	138	(2)
A.6.5 Cache Simulation	140	(1)
A.6.6 ICA: Data Book Implementation	140	(1)
A.7 Software Power Analysis	140	(8)
A.7.1 Power Measurement	140	(2)
A.7.2 Instruction-Wise Power Analysis	142	(1)
A.7.3 Example: SPARClite Power Measurement	142	(1)
A.7.4 Further Implementation Details	143	(5)
A.7.5 ICA for SPARClite Power Consumption	148	(1)
A.8 Design Flow Integration in MEDIA	148	(3)
A.8.1 System Property Intervals	149	(2)
Generation of Experimental Results	151	(1)
B.1 Path Analysis	151	(1)
B.1.1 Symbolic Simulation	151	(1)
B.1.2 ILP Solving	151	(1)
B.2 Architecture Modeling	151	(7)
B.2.1 Strong ARM Simulation	151	(2)
B.2.2 Strong ARM Simulation Case Studies	153	(1)
B.2.3 Measurement	154	(3)
B.2.4 Measurement Case Study: Image Processing	157	(1)
B.3 Intermediate Formats: Bubble Sort	158	(3)
B.3.1 Source Code	158	(1)
B.3.2 Symbolic Expressions	159	(1)
B.3.3 Control Flow Graph	159	(2)
B.3.4 ILP solver input	161	(1)
B.4 Analysis Improvements in Previous Work	161	(2)
B.5 Graphical Behavioral Interval Representation	163	(6)
Abbreviations	169	(2)
Biography	171	(2)
Publications	173	(2)
Bibliography	175	(12)
Index	187