C Jeffrey

R Cutajar

S Prosser

M Lickess

A D Richardson

S Riches

& S Riches

The Integration of On

HAL is

Introduction

Today's motor vehicles contain an increasing number of microcontrollers (20 to 50), providing electronic control of a range of systems, including engine management, braking, steering and airbag safety systems. The demands of both the automotive market and physical environment puts pressure upon electronics design to ensure low cost, robust, high quality and high volume products. Quality targets of typically 10 parts per million are currently set by vehicle manufacturers. The trend to X-by-wire systems (e.g. braking and steering) and the proposed future electrical architectures are forcing the migration of the electronic control units to more harsh environments (e.g. brake caliper, engine, exhaust). Locating intelligence directly at the transducer interface is also becoming extremely desirable, as sub-system performance increases as signal noise is reduced, auto/intelligent calibration can be realised, connector count can be reduced and manufacturing costs optimised. It is also vital that both design and architectures meet the appropriate level of safety integrity and reliability. There is no doubt that future systems will be heavily dependent upon highintegrity, high-reliability embedded electronic modules. The implications of these trends are a paradigm shift in automotive electronic design from board based to fully integrated systems. Table 1 provides some typical environmental specifications associated with the range of automotive applications.

Recently in [START_REF] Dilger | Fault Tolerant Mechatronics[END_REF] fault tolerant sensors and actuators for Xby-wire systems have been addressed. This paper highlights the technical difficulties associated with fault tolerant mechatronic systems but does not address the underlying electronics. To address this, the work presented in this paper has led to the integration of test support hardware into an automotive ECU through an innovative application of IEEE1149.4 boundary scan [START_REF]Standard for a Mixed Signal Test Bus[END_REF] and IDR to address production test costs and test quality requirements, with further functionality including condition monitoring required to meet safety critical sub-system specifications. The paper is organised as follows. In section 2, the integration technologies required to realise low cost, safety critical ECU's are discussed. In section 3, the methods used to achieve auto health monitoring and fault avoidance are described. Section 4 describes the demonstrator and innovation in the application of the methods described in section 3. Section 5 draws conclusions.

Existing Strategies to Achieve Fault Avoidance

In the event of a potential failure, some kind of backup has to be provided to ensure certain reduced system functionality without complete system breakdown. In the majority of cases this may be achieved through circuit reconfiguration.

In many safety critical applications redundancy is used, in the form of both hardware and software, to ensure that the system will not fail [START_REF] Yen | Winner take all experts network for sensor validation[END_REF][START_REF] Camargo | Quantitative analysis methodology in safetycritical microprocessor applications[END_REF]. The subsystem would consist of duplicate devices that would run simultaneously; if one device becomes faulty the other device's output would be used instead. This technique is costly, as the entire functionality of the subsystem has to be duplicated. These systems are not economical for the automotive market place as it is impractical to implement an entire redundant subsystem. Automotive systems need to be produced cheaply and achieve high reliability. In failsafe systems additional circuitry will be required, the extent of which will depend on the architecture of the system and knowledge of the failure effects.

Having less than an entire redundant system available to achieve fault avoidance means that one will not be able to tolerate every possible fault. Instead, fault avoidance would be optimised to cope with faults that have significant impact on the functionality of the system. These faults need to be identified and ranked and this can be achieved through detailed Failure Mode and Effect Analysis (FMEA) and a Physics Of Failure (POF) approach. It is even possible to predict the type of failures that may occur in a newly designed system [START_REF]Guide to failure modes, effects and criticality analysis (FMEA and FMECA)[END_REF][START_REF] Upadhyayula | Physics-of-Failure Guidelines for Accelerated Qualification of Electronic Systems[END_REF]. Novel On-Line Monitoring (OLM) techniques have to be developed which detect these identified failure modes and also verify subsystem performance.

ECU Failure Analysis

Automotive electronics already exhibit a high degree of reliability within existing systems. This is currently achieved by using a combination of historical data, field returns and formal techniques (FMEA, failure rate analysis and fault tree analysis) to predict the areas of concern within the system. This is also supported by specific validating testing (temperature cycling, vibration etc) to focus upon items identified within the FMEA/failure analysis. Electronic component suppliers are required to submit specific validation tests results. On reviewing detailed FMEA analysis of automotive Electric Control Unit's (ECU), we find that one of the most common failures are interconnect related on both discrete and IC devices. It is therefore imperative that:

The number and density of interconnects are greatly reduced.

There is a facility for interconnect testing at startup.

There is a facility for on-line signal verification. The lack of hardware related integrated on-line monitoring techniques for automotive systems means that there are few indications of the health and quality of a system in operation. When using components supplied from 3 rd parties, test access to internal sensitive nodes of the device is not possible. It is therefore desirable to have a nonintrusive method to verify that system blocks are working correctly.

Health Monitoring and Reconfiguration

Techniques Selected

System Monitoring

One of the key challenges in circuit fault avoidance is the variety of potential subsystem failure modes with varying failure intensity. Novel reconfiguration techniques may be dedicated to particular failure effects aiming at fault elimination though altering circuit topology. The results of an FMEA carried out on the subsystem will provide designers with failure modes that could occur in its operational lifetime. It is the faults arising from these failure modes that the subsystem needs to be configured around to ensure that the required level of operation is attained. In application, BIST methods could be used to check if failures are present on start up. If a failure is detected on a critical path, then the system would refuse to start as safety could be compromised. If the failure was on a non-critical path, then diagnostic data could be sent to a circuit topology manager, which would alter the circuit topology to provide its best performance at a required safety level.

Input

In this work, a circuit topology manager has been implemented and integrated into a novel system architecture as illustrated in (Figure 1). Once the system is operational, OLM techniques continuously check the subsystem for faults and notify the circuit topology manager as soon as a fault is detected.

Using IEEE1149.4 for on-line signal monitoring

IEEE 1149.1 Boundary Scan is a digital architecture that enables accessibility and observablity to circuit nodes and interconnect through a Test Access Port (TAP). The IEEE 1149.4 standard for a mixed-signal test bus [START_REF]Standard for a Mixed Signal Test Bus[END_REF] extends the test access structure for analogue stimulus injection and response evaluation via two buses connected to pins AT1 and AT2 respectively. Recent research in 1149.4 [START_REF] Sunter | A general Purpose 1149.4 IC with HF Analogue Test Capabilities[END_REF][START_REF] Kac | Experimental test infrastructure supporting IEEE 1149.4 standard[END_REF] and its implementation and application [START_REF] Ducoucdray -Acevedo | Innovative Built-In Self-Test Schemes for On-Chip Diagnosis, Compliant with IEEE 1149.4 Mixed Signal Test Bus Standard[END_REF][START_REF] Mcdemid | Limited Access Testing: IEEE 1149.4[END_REF][START_REF] Kac | Alternative Test Methods Using IEEE 1149.4[END_REF] have shown that measurements for current, voltage level, frequency and phase are supported. However, measurement accuracy is limited due to capacitive and resistive characteristics of the Analogue Boundary Modules (ABM) that also cause degradation of the observed signal. Limitations in passive component measurements (resistance and capacitance) facilitating 1149.4 have been identified [START_REF] Duzevik | Preliminary Results of Passive Component Measurement Methods Using and IEEE 1149.4 Compliant Device[END_REF]. Building on previous review work [START_REF] Jeffrey | Reconfigurable Circuits for Fault Tolerant Systems: Factors to Consider[END_REF] that suggested IEEE1149.4 could be used for on-line test, a circuit topology manager described in section 3.1 has been presented to control an 1149.4 standard architecture to implement both on-line monitoring and a circuit reconfiguration capability. (See Figure 2) The aim is to enable successive monitoring of circuit nodes with minimum area overhead, while avoiding an increase in pin count.

Circuit Topology Manger

Pre

Figure 2 Circuit Topology Manager

To facilitate the IEEE1149.4 as an on-line monitoring technique an architecture is proposed for the Circuit Topology Manager in Figure 2. Test Master This stores information required to execute a test. The test type and test data is passed to the Test Measurement circuit for simple tests e.g. DC voltage level (requires reference levels from Test Master) the test is evaluated directly and the results fed back to the Test Master. Once the Test Measurement circuitry is configured the vector information is passed to the Test Access Engine to connect AT1 and AT2 to the relevant circuit nodes. Test Access Engine Converts the vectors containing boundary scan data from the Test Master and applies them to the ECU. When the system is correctly configured the engine informs the Test Master so the measurement can be performed. Test Measurement This circuit is an analogue interface that conditions the signals on the analogue buses for processing/evaluation. This architecture is based on sequential tests hence the timing data for each test node is also stored in the Test Master.

IDR

A sensing system designed using the IDR method [START_REF] Richardson | Fault Tolerant & Self Testable Architectures for Zero Failure Electronics[END_REF] exploits existing multiple on-chip sensing that are switchable through electronic reconfiguration, reducing the need for redundant sensors used purely for test. A constraint to this technique is that the components within the system under test must exhibit a degree of replication to allow the connectivity of embedded functions to be changed. This takes advantage of the fact that many sensors exhibit some degree of component replication to remove cross-sensitivities and unwanted modes. During normal operation, these elements are dynamically rearranged though the overall circuit function remains the same. When a fault occurs, one or more components cease to be equivalent to the others in the same group. When this component is interchanged with another, the overall circuit function changes. It has been shown that in the majority of cases, even minor parametric faults in analogue paths are easily observed at the system level, thus giving early fault detection. The profile of the changes is also observed, allowing the faulty component to be identified and therefore excluded. The circuit is then operational, but with reduced functionality in terms of signal or bandwidth [START_REF] Sharif | An Integrated Diagnostic Reconfiguration (IDR) Technique for Fault Tolerant Mixed Signal Microsystems[END_REF]. The frequency at which the circuit reconfigures must be sufficiently different to the normal operational frequency to prevent IDR from interfering with the response time and efficiency. In this work IDR has been applied to a network of identical components providing visual and audible warnings to achieve tolerance to failure. This is further described in section 4.5.

Application to an X-By-Wire Control Unit

The specific objectives of this work are to establish a route to the realisation of the "zero failure" concept for automotive electronic systems by developing on-chip monitoring and self-test functions to detect in-field and production failures, and develop associated diagnostic algorithms to control system reconfiguration. An Electronic Control Unit (ECU) was selected as the demonstrator for this work. This system combines a variety of power, signal and sensing components, all of which have to operate in a harsh environment. This type of ECU is designed to be mounted directly in the sensor environment, for example on engine or the brake calliper of the vehicle. The electronics can be subjected to a combination of temperature extremes, vibration, and a whole range of contaminants such as hydraulic oil, brake dust, and salts. Due to the nature of the ECU demonstrator, a substrate technology which can withstand the harsh environment, dissipate heat efficiently and is compatible with hybrid assembly techniques had to be selected. The decision was made to use Insulated Metal Substrate (IMS) technology combined with bare die for the majority of the components and high temperature-resistant packaged components for the remaining devices. A two-layer IMS module was designed and manufactured on a copper base layer, with high temperature dielectric insulation between the metal layers. In order to avoid bumping the bare die components, standard die attach followed by aluminium wire bonding was carried out. Gold bonding was avoided to eliminate the formation of intermetallics at high temperatures. A nickel/gold surface finish was applied to the substrate, allowing Aluminium wire bonding and SMT component assembly. A high temperature resistant epoxy-based glob

Add-On Board

In order to facilitate the circuit topology manager from Figure 2 a separate Add-On board was developed to emulate the automotive system to which the ECU was attached. Its primary functions are:

Pass sensor data to the ECU. Allow the user to invoke test routines and induce faults.

Act as the on-line test and reconfiguration engine. Convey information and regarding the ECU configured state.

Integrating Boundary Scan

The ECU was redesigned to use IEEE1149.1 compliant devices where possible, if an equivalent device was not found with boundary scan, then it was emulated via the placement of compliant devices in the signal path or in software. IEEE1149.4 compliance was implemented for the analogue nodes and the critical signal path. This enabled on-line probing of the critical signals in the system and in the event of a failure allows signals to be extracted, processed, bypassed and injected into the system. Since 1149.4 is not fitted to devices as standard, the STA400 dual multiplexers from National Semiconductors were used as an add-on block to emulate compliance. Interfacing to the IC signal pins through hardwired STA400 devices, as illustrated in Figure 4.

On-line Interconnect Monitoring

In order to monitor the integrity of an interconnect on-line, each side of a connection is linked to AT1 and the other side is connected to AT2. The two buses are then fed into a differential amplifier to check to see if there is a difference in the signals. The output of the amplifier is then fed into a comparator circuit and is triggered to a logic high when there is a noticeable difference. See Figure 5. This test principle works on the basis that there is a signal present on the interconnect that one wishes to monitor. Since ABMs are fitted into the critical signal path, even for the digital interconnects, it is possible to pass low amplitude signals ~ 0.5V to facilitate the detection of a connection for when the signals are at a logic low without placing an incorrect logic value in the circuit.

Motor Drive Circuitry

The existing H-Bridge circuitry was replaced with smart 'high side' BTS6510 and 'low side' BTS133 power drivers from Infineon and had an STA400 act as a transparent interface to emulate the drivers compliance to the standard. The advantages of using these devices are:

The interconnect count would be greatly reduced. Would no longer require external test circuitry, as there are integrated voltage monitors and current monitoring circuits. An output pin on the high side driver provides diagnostic feedback to the microprocessor.

Lamps and Indicator Circuitry

The ECU had 3 lamps and a buzzer that were used as indicators for the operator. Even though their operation is not essential in the ECU's function, they are ranked as critical in the FMEA and failure as the status of the system cannot be conveyed to the user. This could result in incorrect operation of the vehicle e.g. a fault lamp cannot relay that extra caution is required from the user when a xby-wire system is functioning incorrectly. Since the indicator circuits are 4 identical circuits, it is possible to use the IDR technique to interchange them at a frequency above 85Hz. If there were faulty circuit/interconnect it would sequentially change what indicator it affected at a speed that was unnoticeable to the human eye. See Figure 6. When measuring DC values noise present in the system limited measurement accuracy to +/-10mV.

On-Line Monitoring of Circuit Nodes

Signal Analysis

Results obtained on the limitations of the signal properties that can be measured are: DC Response : Results from passing a low frequency sinusoid through an ABM to identify maximum and minimum voltages to propagate through without clipping indicates that the maximum voltage that can be observed through the ABM is 3.92V. The minimum voltage observed was -640mV with an accuracy of +/-10mV. AC Response : The 3dB cut-off frequency of the ABM has been determined through measurements:

o 50kHz stimulus frequency, no signal degradation in phase and magnitude can be observed. o 200kHz a phase difference becomes observable.

Hence one has to account for that difference in phase dependant measurements. o 1MHz signals put through the ABM at this frequency show a 3dB cut-off.

Fault Avoidance

Once an interconnect failure is detected, the AT1 and AT2 buses are linked together to bypass the failure. This is possible on any nodes that are 1149.4 compliant; but once a fault is being compensated via AT1 and AT2, no further monitoring can take place as the test system has its resources utilised. It is therefore important to segment the analogue bus lines into multiple functional groups so that multiple configurations can take place.

The IDR method works on the basis that the system configures the lamp and buzzer network constantly regardless of fault manifestation.

To verify that the ECU could function without the microprocessor, the power supply bond wires were removed. The Add-On board then monitored the switch circuitry until a transition of state was applied. Once this was detected, the Add-On board then accessed the circuit nodes that enabled the actuation of the motor drives. The correct signal was injected to operate the motor while the sensor status was monitored to know when to turn the motors off. Thus remote operation of the system was achieved. In addition, it has been verified that when an interconnect failure is injected into the system, fault free operation was observed. The technique is however, limited to coping with faults inside the reconfiguration matrix and should ideally be integrated into the silicon.

Limitations

The main challenge associated with the circuit topology manager is the detection and correction of a fault is not instantaneous. Therefore, careful analysis of what and when key parameters should be measured is required. The total time for conducting a test without repair is:

Test con total T T T
Where T con is the time it takes to connect to the specific node. The worst case scenario would be to fully reconfigure each device in the scan chain between each test. The best case scenario it that the only 1 initial configuration is required to monitor all the relevant circuit nodes. This is shown in Figure 7. The Term T Test is the time it takes to perform the measurement of the parameter. The 16 bit HCS12 processor used for implementation of the test master has an ADC capture time of 7µs which is very small in comparison to the configuration times above. However, computing a Fourier analysis of a sampled signal can be very time consuming to verify especially for very low frequency signals (~10Hz) and would result in an analysis time in the excess of 100ms. Using the above configuration and measurement times applied to a system where 10 circuit nodes are monitored and a test master with a 16MHz clock speed is used. The upper and lower bounds of the system performance are: 0.949Hz< T total < 153Hz With regard to fault tolerance the solution presented is limited to bypass a number of signals equal to half the number of analogue test buses that are implemented in the system. Once a fault is detected and compensated for, by using the reconfiguration technique presented, then subsequent testing will not be able to take place as the test resources are already in use. If there are 2 sets of buses then 1 bus set (AT1 and AT2) can monitor sensors while the other bus set can perform actuations. This means that each circuit segment will still have only 1 bus set allocated to it so in the event of reconfiguration online test cannot continue in each segment. The amount of buses could be increased to create more circuit test segments but this will start to increase the complexity of the circuits and increase the potential for noise and crosstalk in the system.

Conclusion

The environments in which automotive systems are being placed are becoming increasingly harsh and the applications which they serve more safety critical. To achieve a high degree of reliability new packaging technologies need to be applied. In this paper an innovative application of 1149.4 modules has been used to achieve a degree of fault avoidance in an automotive ECU that targets an X-by-wire application. The IDR concept has also been applied to manage the monitoring and reconfiguration strategies implemented in the system and proven in hardware. Results have verified that it is feasible to test, manage and reconfigure a fully integrated heterogeneous electronic systems on-line to achieve fault avoidance to key failure modes identified through an FMEA process.

Figure 1 :

 1 Figure 1: Subsystem test and configuration flow

Figure 3 IMS

 3 Figure 3 IMS Electronic Control Unit

Figure 4

 4 Figure 4 Using STA400 devices as an emulation of 1149.4 compliant devices

Figure 5

 5 Figure 5 On-line interconnect monitoring

Figure 6

 6 Figure 6 Using IDR on Indicator Circuits 5 Results

Figure 7

 7 Figure 7 Number of clock cycles Vs scan chain length

Table 1 Electronic environmental conditions in automotive applications

 1

	Location		Typical	Vibration	Fluid Exposure
			Continuous	Level
			Max
			Temperature
	On Engine		140°C	Up to 15g	Harsh
	On
	Transmission
	At Engine		125°C	Up to 10g	Harsh
	(Intake
	Manifold)
	Under Hood	120°C	3 -5g	Harsh
	(Near Engine)
	Under	Hood	105°C	3 -5g	Harsh
	(Remote
	Location)
	Exterior		70°C	3 -5g	Harsh
	Passenger		70 -80°C	3 -5g	Benign
	Compartment

Table 2 Types of signal lines and their detectability

 2

	When monitoring digital signals, a bias of 0.5V was
	injected into the signal line in order to detect the
	connection when there was logic low. At high frequency
	of operation, propagation delays became apparent so a
	high frequency filter was added on the output of the
	differential amplifier to remove any peaks.
	When monitoring analogue nodes a high impedance buffer
	is required as sensitive circuit nodes can easily be affected
	by this test method. It is also possible to measure signal
	characteristics through the 1149.4 architecture. The
	demonstrator uses Pulse Width Modulation (PWM) signals
	to control the speed of a motor. The frequency of the
	signal was 1kHz with a duty cycle of 60%. The Add-On
	board could detect changes of 0.001% in the duty cycle.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgement

This work has been supported by EPSRC grant number GR/N36271/01 under the DREAM project.

The authors would like to thank National Semiconductor for access to their technology and prototype devices.


Jan Staschulat
email: staschulat|ernst@ida.ing.tu-bs.de

Rolf Ernst

Andreas Schulze

Fabian Wolf

Context Sensitive Performance Analysis of Automotive Applications

Accurate timing analysis is key to efficient embedded system synthesis and integration. While industrial control software systems are developed using graphical models, such as Matlab/Simulink or ASCET/SD, exhaustive simulation is not suitable for verifying functional and timing behavior. Formal performance analysis is an alternative but can lead to wide timing intervals because of input data dependency and complex target architectures. Hence a designer might want to restrict the formal performance analysis to parts of the software system, called context or process modes.

In this paper, we describe how to define and characterize such context information from graphical models. Further, we extend the formal performance analysis to consider contexts. Results from an automotive application demonstrate the applicability of our approach.

Introduction and Motivation

Accurate timing analysis is key to efficient embedded system synthesis and integration. In general, imprecise estimation of software execution costs increases design risks or leads to inefficient designs [START_REF] Wolf | Integrationsverfahren fuer Softwaresysteme im Antriebsstrang[END_REF].

Increasing functionality and software complexity in automotive systems requires concepts for distributed development between car manufacturers and control unit suppliers. These concepts need well-defined and established development processes as well as safe and certifiable software integration approaches [START_REF] Jerraya | Embedded Software for SoC, chapter Formal Methods for Integration of Automotive Software[END_REF] [START_REF] Jersak | Formal methods for integration of automotive software[END_REF]. Functional and timing behavior is often specified in graphical environments, such as Matlab/Simulink or ASCET/SD. For timing validation the stateof-the-art in industry is still simulation or profiling. Since the automatically generated code from such models heav-ily depends on input data a great many test cases would be required for a full path coverage. The exponential number of input data makes exhaustive simulation impracticable for performance validations of industrial applications. To make testing feasible, system complexity should be broken down to the software module. Input dependency is restricted to this module and function calls and hence input data dependency to other modules can be ignored.

As a consequence, software simulation in general can only partially test a software system and only a lower bound of the worst case execution time (WCET) can be found. As an alternative to simulation, many approaches to static timing analysis [START_REF] Malik | Performance Analysis of Real-Time Embedded Software[END_REF] [START_REF] Ye | Embedded program timing analysis based on path clustering and architecture classificaton[END_REF] [6] [START_REF] Bernat | Wcet analysis of probabilistic hard real-time systems[END_REF] have been proposed during the last decade. Formal analysis provides reliable upper and lower bounds of the execution time. Despite the theoretic advances in academic research there has been hardly any impact on the industrial practice of timing analysis [START_REF] Kirner | Discussion of misconceptions about wcet analysis[END_REF].

None of the existing formal approaches can be applied to software modules because input data dependencies cannot be defined systematically. Context dependent analysis can be used to improve the analysis precision [START_REF] Wolf | Execution cost interval refinement in static software analysis[END_REF]. For example, a context for a cruise control software might be keeping the speed while driving uphill or stepping on the brake to disable speed control. Context information are also used in [START_REF] Jersak | Context-aware performance analysis for efficient embedded system design[END_REF] for scheduling analysis to obtain tighter analysis results. However, for complex embedded applications it is often difficult to find these contexts.

This paper describes how to define and characterize contexts using graphical modeling environments. Here we propose a generic XML format to specify contexts which is useful for timing analysis approaches. Then we extend our static timing analysis to consider context dependency.

This paper is structured as follows. Related work is reviewed in Section 2. In Section 3 we describe our static timing analysis Symta/P. The context sensitive analysis is presented in Section 4, and in Section 5 we show the applicability of our approach in several experiments before we conclude in Section 6.

Related Work

During the last decade many research approaches have been proposed for static performance analysis. In [START_REF] Malik | Performance Analysis of Real-Time Embedded Software[END_REF] implicit path enumeration was introduced. Here, the user provides linear equations to define feasible and false paths. To evaluate these equations, Li and Malik map the upper and lower bound identification to two optimization problems. The work in [START_REF] Ferdinand | Efficient and precise cache behavior prediction for real-time systems[END_REF] is based on this kind of interaction while abstract interpretation is used for the static prediction of execution time including cache and pipeline behavior.

In [START_REF] Bernat | Wcet analysis of probabilistic hard real-time systems[END_REF] the notion of probabilistic hard real time system is introduced, as a system which has to meet all deadlines but for which a probabilistical guarantee is sufficient. The work in [START_REF] Engblom | A worst case execution time analysis tool prototype for embedded real time systems[END_REF] presents a WCET framework with several low-level timing analysis techniques, while restricting input programs to a subset of the language C and requiring the user to specify all input data. In [START_REF] Lisper | Fully automatic, parametric worst-case execution time analysis[END_REF] a parametric WCET analysis is proposed, where parameters may represent values of input parameters, or maximal iteration counts for loops. No results from experiments have been reported. In [START_REF] Kirner | Measurement-based worst-case execution time analysis using automatic test-data generation[END_REF] a hybrid framework using runtime measurements together with static program analysis is presented. Traditional WCET analysis is extended by automatic generation of test data using model checking and constraint-based analysis.

Despite the theoretic advances in academic research in WCET and the commercial availability of analysis tools, such as [1] [3] [4], there has been hardly any impact on the industrial practice of timing analysis [START_REF] Kirner | Discussion of misconceptions about wcet analysis[END_REF]. One reason is that performing pure runtime measurements with exhaustive search over the value space of the input data is in general not feasible. In approaches with abstract interpretation a new abstract model has to be written for every new processor which is time consuming and makes it difficult to re-target the analysis.

Input data generation becomes feasible for programs with few input-data dependent control flows [START_REF] Kirner | Discussion of misconceptions about wcet analysis[END_REF]. In previous work [START_REF] Wolf | Execution cost interval refinement in static software analysis[END_REF] we have shown that contexts lead to a reduced number of input data and more precise execution time intervals. However, for complex embedded applications, it is often difficult to find these contexts. Therefore, we describe in Section 4 how to define and characterize contexts in a general and flexible framework and extend our static timing analysis to context dependency in Section 3.

Symta/P -a Static Timing Analysis Tool

Symta/P is a tool for static timing analysis of embedded applications [14] [START_REF] Wolf | Behavioral Intervals in Embedded Software[END_REF]. Best case and worst case execution time bounds of C programs for complex target architectures are computed. Path analysis based on an abstract syntax tree identifies input data independent program segments while the execution time of program segments can be estimated by a cycle accurate off-the-shelf processor simulator or by direct measurement. For the determination of execution times of program segments no interrupts are allowed. A cache analysis determines the number of cache hits and misses for best and worst case.

Program Path Analysis

For path analysis techniques [START_REF] Malik | Performance Analysis of Real-Time Embedded Software[END_REF], a program is typically divided into basic blocks. Then, the program structure is represented as a directed program flow graph with basic blocks as nodes. For each basic block the execution time is determined. The longest and shortest path analysis on the program flow graph is used to identify a global execution time interval. This procedure does not provide sufficient accuracy. For acceptable analysis precision feasible paths of a program have to be identified. A feasible program path is a path in this flow graph corresponding to a possible sequence of basic blocks when the program is executed. A program segment is a sequence of nodes in a program flow graph.

Program properties can be exploited to simplify path analysis for the determination of the execution time through basic block sequences [START_REF] Ye | Embedded program timing analysis based on path clustering and architecture classificaton[END_REF]. Large parts of typical embedded system programs have a single program path only. An FIR filter is a simple and a Fast Fourier Transform is a more complex one. There is only one path executed for any input pattern, even though this path may wrap around many loops, conditional statements and even function calls. A program segment has a single feasible path (SFP) when paths through this segment are not depending on input data. Most practical systems also contain non-SFP parts. These parts have multiple feasible paths (MFP).

For the identification of SFP and MFP segments, the input program is mapped to its syntax graph. A depth first search algorithm on the syntax graph can be used to determine input data dependencies of conditions while storing the data in a symbol table. Every control structure which does not contain an input data dependent condition is a SFP. If conditions depend on input data, the syntax tree nodes are classified as MFP.

Execution Time Model

The execution time model in [START_REF] Malik | Performance Analysis of Real-Time Embedded Software[END_REF] is established as a standard model for static approaches which is called sum-ofbasic-blocks model. In previous work [START_REF] Ye | Embedded program timing analysis based on path clustering and architecture classificaton[END_REF] we have extended this concept to program segments. Let a program consist of N program segments with x i the execution count of program segment s i and c i the execution time. Then the program execution time is determined by: C = N i c i • x i . For the execution counts x i , the designer provides functional constraints, such as loop bounds or implicit description of possible paths by means of linear equations. Structural constraints define another set of equations: The execution count inflow of a segment equals its execution count outflow. These equations for the upper and lower execution bound are mapped to two integer linear optimization problems (ILP).

Architecture Modeling

The execution time of a program segment can be determined by instruction time addition or program segment simulation [START_REF] Ye | Embedded program timing analysis based on path clustering and architecture classificaton[END_REF]. Instruction time addition adds up the execution time for each instruction. Host tracing is used while execution times are taken from a table. This approach only works for simple architectures without pipelines and caches where instruction execution is independent. A second approach is program segment simulation. Program segments are simulated on a cycle accurate processor simulator using known input data or the segments are executed directly on the target architecture.

Context Sensitive Analysis

Often the designer is interested in a context dependent process behavior. Here, context is defined to be a subset of input data and/or a subset of possible process states, often called process modes.

In each context, only a subset of paths through a program segment can be executed. This potentially means reduced time bounds which could be exploited for analysis. Global process representation models [START_REF] Ziegenbein | Combining multiple models of computation for scheduling and allocation[END_REF] can support process modes, such that the distinguishable contexts are considered in scheduling analysis [START_REF] Jersak | Context-aware performance analysis for efficient embedded system design[END_REF].

The next subsection describes how to define context information and Section 4.2 describes how to specify them in a generic way to be useful for a static timing analysis. In Section 4.3 we describe the extensions of Symta/P to analyze context information, and give an overview of the general tool flow in Section 4.4.

Context Definition

Automotive control systems are typically designed in graphical models, such as the development environment ASCET/SD or Matlab/Simulink. The source code for the software is automatically generated from hierarchical block diagrams and state machines. Simulation is state-of-the-art to test functional behavior. A complete path coverage is not possible for complex software because of the exponential number of test data. Therefore testing is prioritized by functional importance: for critical paths more intensive testing is required than for less critical ones. The application is analyzed on each hierarchical level. Consider a software module m l on level l which calls several functions on higher hierarchy and is called from lower levels. The top level function level is 1 and the level increases by one for every hierarchy top down. Then a functional software test requires input data to reach module m l through all hierarchical levels smaller than l. For a function call to a higher level, not every path is tested, instead only one arbitrary path is chosen. This functional testing strategy can be adapted for static timing analysis and the test pattern can be used for a context definition.

A context C is defined as a subset of all input data variables I which have predefined values. Variables of the set C are called context variables and all other variables I \ C are called free variables. The static timing analysis is simplified because several paths are excluded, and consequently, the total number of input data is reduced.

Fig. 1 shows an example control flow graph with three if-conditions where a, X, Y are (unknown) input variables. Suppose the designer wants to test the left branch of the first if-condition. Then a is a context variable and X, Y are free variables.

To define contexts from graphical models, variables of some hierarchy level l are useful for context definition. In this paper we assume that one context corresponds to one hierarchical level l as a first approach. All variables on higher and lower levels i = l are classified as context variables and all variables of module m l are free variables. If a context spans over several hierarchies the input variables from different levels have to be considered also. Note, that different contexts can share code segments.

The next subsection describes how to specify a context from an abstract specification model and how to provide context information as an interface to a static timing analysis, such as Symta/P.

Context Specification

From the graphical specification environment AS-CET/SD a logical context is defined on the functional level. For a cruise control a context might be keeping the speed while driving uphill or accelerating to a given speed. This is translated into a table of input data variables with the corresponding values for every context. To specify context and free variables in a flexible way the language XML is used. Further on, the precise input data values for the measurement need to be specified.

In Table 1 the contents of the XML structure is given with context variable a and free variables X and Y . Two combinations of test patterns for the free variables are sufficient to execute all feasible branches of the program of Fig. 1

Extentions of Symta/P to Contexts

Current approaches for static timing analysis assume that input data is unknown and additional information has to be specified by the user, such as loop bounds [13] [6]. Context information, as described in Section 4.2, are specified by the predefined variables. The path analysis is extended by classifying context variables as input data independent. This is done by extracting the names of the context variables from the XML structure. In the initialization step, a symbol table is filled with these variables and classified as input data independent. Whenever a context variable is used in other expressions the input data classification is simply propagated. As a result, the program is structured into larger segments according to the context specification. No changes are necessary for architecture modeling and ILP formulation because context dependent control flow is independent of the target architecture.

Overall Tool Flow

Fig. 2 shows the tool flow for the context sensitive performance analysis. Rectangular shapes denote tools or user actions and circular shapes denote input, intermediate or output files. The analysis starts with the c file and the context specification in the upper left corner. From the abstract model context definitions are extracted and specified in Context using the XML interface, as described in Section 4.2. Together with the source file f.c the path analysis identifies input data dependent control flows, classifies the source code into segments f.seg and outputs the control flow graph f.cfg. According to architecture specific measurement instructions Syntax and the segment classification the source code is instrumented for measurement f.path.c and for f.instrum.c branch identification. The instrumentation syntax contains instructions specific for target architectures to measure the execution time or other properties like power consumption of a program segment. The syntax of the instrumentation depends on the measurement strategy. When processor simulators are used an instrumentation consists of debugging commands, such as stopping the execution and reading the system timer. For direct measurement on target architecture of automotive software, an instrumentation might be a CAN message.

For input dependent control structures the branch identification is used to determine which branch is taken during the execution of a given set of input data. This is also necessary for back annotation of the execution time. The instrumentation for branch identification also depends on the architecture modeling strategy. For example, the line numbers of the executed branch could be recorded in a local variable or written out by a CAN message.

Given the Context specification and the instrumented source code, the execution time is measured either by cycle accurate processor simulator or by direct measurement on an evaluation board. Using the branch identification the times for every segment are back annotated. The Context file in the upper left and lower right corner have the same content and are shown twice for notational convenience.

Finally the ILP problem is formulated using the control flow graph f.cfg the segment classification f.seg and the execution time file f.costs and solved by an ILP solver. The solutions for the WCET and the BCET are now available for the software if all program segments have been reached. If not, the user has to supply additional test cases for this context in the Context XML file and the analysis continues.

Experiments

The context sensitive analysis described in Section 4 has been applied to modules of a cruise control software for a TriCore architecture with 75 MHz clock frequency.

Experimental Setup

The cruise control consists of several moduls and was designed with ASCET/SD's graphical environment and the source code was generated automatically from it. Then, Symta/P has been used to analyze the source code and to extract the control flow graph (CFG). From the ASCET/SD model and from the CFG the contexts have been defined by specifying the free and context variables as XML format. Table 2 shows the size of the software modules in C lines without considering the size of sub-functions and the number of free and context variables. The real names of the modules had to be removed because of non disclosure agreements.

Context. #cLines #freeVar

Table 2. Context Specification

The testing-environment is a Triboard, equipped with a variety of peripherals for connecting the environment and a TriCore microcontroller. The TriCore is a 32-bit microcontroller-DSP architecture for real-time embedded systems. Binaries are created with GNU Cross-Compiler toolchain for TriCore. Hard real-time debugging requires close interaction with the processor. JTAG OCDS (On-Chip Debug Support) offers direct access to microcontrollers with an OCDS module. It provides a direct serial interface to the controller-internal functional units (registers, busses, control unit etc.) to make accurate measurements of execution time and path identification feasible in real time. The JTAG OCDS is connected via flat ribbon with the UAD (Universal Access Device). UAD is a high-speed communication hardware for interconnection between microcontroller-boards and desktop PCs. On PC-side the UDE (Universal Debug Engine), a debuggingsoftware for microcontrollers, is used. For reproductional purposes and to achieve the best cycle performance using the TriCore non-cached memory, both the program code and data are allocated in the internal scratch pad memory. When the instrumented program segment starts and stops, the cycle information of the actual timestamp and the c-line number is saved in an array. This array is allocated in the non-cached internal memory. Start time is the time stamp when the segment starts and stop time is the time stamp when the segment ends. Thus, the difference between these two time stamps represents the time taken by the run of the program segment.

Results

Several test cases were specified for a complete branch coverage for every context. Table 3 shows the number of test cases for each context. The number of test cases ranged from 14 for small modules to 47 for larger ones.

Then for these modules the execution time was determined by high level simulation using the existing functional testing equipment. In this experiment the complete module was tested by inserting an instrumentation point only at the beginning and at the end of the module. Table 3 For simulation, software modules were chosen which could easily be tested. As a second experiment, more complex software modules were statically analyzed by considering context information. Table 4 shows the execution time for the worst and best case. Each context corresponds to a module that contains several function calls. For example, context G consists of 14 function calls to other modules and has a total of 161 lines of code.

Figure 1 .

 1 Figure 1. Example control flow graph

Figure 2 .

 2 Figure 2. Overall Tool Flow of Symta/P

Table 1 . Example of XML Specification

 1 for this context.

	Field	Value
	contextVar a
	freeVar	X Y
	testCase 1 a=1; X=1; Y=12;
	testCase 2 a=1; X=6; Y= 1;

Table 3 . Context sensitive analysis using sim- ulation time

 3 summarizes the best case and worst case execution times. The execution interval without considering context is between 156 and 1152 cycles, a range of 996 cycles, whereas the largest range is 312 cycles for context A and the smallest is 12 cycles for context B.

	Context #test BCET WCET range
		cases	[clk]	[clk]	[clk]
	A	47	840	1152	312
	B	20	324	336	12
	C	18	342	450	108
	D	14	126	156	30
	E	14	102	156	54
	no cont.	113	156	1152	996

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

In almost all cases the best case execution time is 72 cycles because the software module consists of a sequence of if-then-else structures and in the then branch there is a return statement. In the best case the function executes only the first if condition and exits. The range without context information is 1824 cycles that is the same range as for context H. However, the ranges for context F, G and K are much smaller (248 -722). In context J no input dependent flow leads to the same execution time for best and worst case.

Summary and Conclusion

This paper has proposed a methodology to define and characterize context information to give a basis for a performance validation of software modules. Our formal analysis approach has been extended by context specification and a general tool flow with context sensitive analysis has been described.

The approach was applied to an industrial automotive control application. The experiments show that our approach is easy to use and flexible enough for complex applications. Timing bounds by simulation and by applying the static timing analysis lead to tighter timing intervals for each software module.

To conclude, context sensitive analysis makes formal performance analysis approaches feasible for software modules. Input data dependent control flow can systematically be restricted to software modules reducing the number of necessary input patterns. Further work will involve automatic generation of context information from functional specification documents and ASCET/SD models and the automation of the context sensitive timing analysis.