Michael Zolda
email: michaelz@vmars.tuwien.ac.at

Sven Bünte

Raimund Kirner
email: raimund@vmars.tuwien.ac.at

Towards Adaptable Control Flow Segmentation for Measurement-Based Execution Time Analysis *

During the design of embedded real-time systems, engineers have to consider the temporal behavior of software running on a particular hardware platform. Measurement-based timing analysis is a technique that combines elements from static code analysis with execution time measurements on real physical hardware. Because performing exhaustive measurement is generally not tractable, some kind of abstraction must be used to deal with the combinatoric complexity of real software. We propose an adaptable measurement-based analysis approach that uses the novel flexible abstraction of a segment graph to model control flow at varying levels of detail. We also present preliminary experimental results produced by a prototype implementation.

Introduction

In real-time systems the term correctness does not only refer to the functional behavior of calculations. Compliance with temporal requirements is an essential part in the design process. If transient violations of timing constraints are tolerated we speak of soft real-time systems. Think of a mobile phone for instance where short communication delays are acceptable. On the other hand, safetycritical hard real-time systems include at least one temporal requirement the violation of which would potentially lead to a catastrophe. An airbag not releasing in time or a non-reacting aircraft control unit for instance can lead to a fatal disaster.

Consequently, there is an inherent demand for verification techniques that focus on the temporal behavior of real-time systems. Usually, a design is composed out of tasks to handle complexity. A schedule ensures that functional as well as temporal dependencies are adhered to. Most of the common schedulability analysis techniques demand the knowledge of a safe upper bound of the worstcase execution time (WCET) for each single task. For hard real-time systems those deadlines are strict. However, soft real-time systems can tolerate violations to some degree.

A comprehensive overview of WCET analysis techniques is given in [START_REF] Wilhelm | The Worst-Case Execution-Time Problem -Overview of Methods and Survey of Tools[END_REF]. In summary, determining the WCET is hard due to the inherent complexity and the partly complementary requirements to the analysis:

• Safety is the property that the obtained WCET estimate may not underestimate the real WCET

• Precision is an indicator of the deviation between the obtained WCET estimate and the real WCET

• Performance of the WCET analysis denotes the amount of computational resources needed to perform the analysis

• Accessibility of the WCET analysis covers aspects like available granularity of WCET results, the backannotation of WCET results to the source code, and the necessary effort to perform the WCET analysis on a new target hardware There are three categories in which the various WCET analysis techniques can be classified. In end-to-end black box testing the program is simply executed on a set of input data. The advantage is that the test environment is easy to set up. However, there is no way to state anything about precision or safety. In contrast, static analysis examines a software/hardware model of the system under investigation without executing the program. This approach allows for deriving safe and sufficiently precise execution time bounds, which makes it suitable for verifying safetycritical real-time systems [START_REF] Heckmann | Worst-case execution time prediction by static program analysis[END_REF]. Still, modeling and analyzing the system adequately takes much effort. It can even be impossible if the system behavior is too complex or partly unknown (e.g. the documentation provided by the processor manufacturer may be incomplete w.r.t. temporal aspects). A third category encompasses measurementbased techniques, i.e. all approaches that combine execution time measurements and static program analysis. Measurement-based techniques is usually designed with the explicit goal to provide a trade-off between safety, precision on the one hand and performance, accessibility on the other hand.

This article illustrates the overall architecture and segmentation technique for a flexible and easily accessible measurement-based approach that is supposed to give a WCET estimate where the precision depends on how much effort the developer is willing to invest. The overall goal is to make it applicable in several development stages of the system under investigation. We focus on soft realtime systems because we cannot in general avoid underestimation of the actual WCET. However, the method is still appropriate for hard real-time systems in an early stage of development when preliminary results are needed.

The basic concepts of measurement-based timing analysis are discussed in Section 2, which is followed by a discussion of related work on measurement-based WCET analysis. Program segmentation, as described in Section 4, is the key strategy to provide an adjustable coverage metric for the systematic execution time measurements. The details of the algorithm for program segmentation are given in Section 5. In Section 6 we illustrate the setup of experiments on a prototype implementation of the Formal Timing Analysis Suite (FORTAS) 1 , which yields preliminary results regarding the applicability and consequences of adaptable program segmentation for WCET analysis.

Measurement-based Timing Analysis

Measurement-based Execution Time Analysis (MBTA) is a hybrid WCET analysis technique, i.e., it combines static program analysis techniques and execution time measurements. As shown in Figure 1, measurement-based timing analysis typically consists of the following three phases:

Analysis and Decomposition:

For WCET analysis, the maximal end-to-end execution time of the software is of interest. In general, to obtain a perfectly accurate timing model, we would have to consider the execution time of all possible operation sequences that can be performed by the computer while executing the given computer program. Measuring all these sequences is in general intractable, as there are simply too many of them. Therefore, reducing the number of execution time measurements is crucial for MBTA. One way to do this is to decompose the program behavior into subsets and to ensure coverage on each subset.

The control flow graph (CFG) is a common graphbased program representation in compiler construction, where nodes represent the operations of the software and where edges represent possible successive executions 2 . We have chosen to operate on the CFG as a good basis for MBTA, because the execution time depends largely on which specific instructions are executed.

We use the technique of segmentation to decompose the CFG of ANSI C programs into smaller subgraphs. Depending on how we decompose the program into segments, we can adjust the trade-off between safety, precision on the one hand, and performance, accessibility on the on the other hand.

Execution Time Measurement:

Once the program is decomposed, the execution time is determined for each segment.

We measure the execution time on the real hardware, allowing us to take hardware characteristics into account without modeling them in full detail.

Timing Composition:

Having performed systematic execution time measurements for each segment, the timing results from all segments have to be composed to obtain a WCET estimate.

As said above, due to hardware features like pipelines, caches, or out-of-order executions, without additional precautions our MBTA approach will not provide sufficient state coverage to guarantee safe WCET bounds. Accessibility: the derived timing information can be related to the source code. At least at the granularity of our segmentations it is directly possible to assign timing values to source code regions representing a segment. It is also possible to relate the timing of individual paths within a segment back to the source code. However, due to compiler optimizations, this can sometimes lead to timing distributions that may not be obvious at the source code level. Here the user would have to investigate the generated code to fully understand the timing results. Overall, our approach provides the software developer with a convenient representation of the timing information.

Analysis and Decomposition

Execution Time Measurement Timing Composition

WCET Estimate

Furthermore, since we do not make use of a hardware model, any systems can be analyzed as long as the target platform offers the necessary means for measurement.

Safety and Precision: the measurement-based timing analysis framework is generally used to provide WCET estimates of reasonable precision instead of safe WCET bounds. The WCET estimate can be potentially unsafe due to the following reasons:

• Compiler optimizations can introduce new control flow paths, which may not be covered by our test data generation based on the program source code. This is a given fact with today's compilers which can only be avoided by deactivating code optimizations. However, we are also working on a more intelligent approach where the goal is to let the compiler activate only those code optimizations that do not threaten the preservation of a selected code coverage [START_REF] Kirner | Towards preserving model coverage and structural code coverage[END_REF]. The advantage of this approach is that it will be relatively easy to integrate it into existing compilers.

• State coverage of hardware components is usually very hard to achieve by measurementbased timing analysis methods [START_REF] Kirner | Obstacles in worst-cases execution time analysis[END_REF]. Thus, on hardware where the instruction timing depends on the current state of the processor, the WCET estimate provided by our method may miss the worst-case initial hardware state for an execution-time measurement. A workaround to this problem would be the explicit enforcement of a predictable state at wellknown program points [START_REF] Wenzel | Measurement-Based Timing Analysis of Superscalar Processors[END_REF]. Measurementbased WCET analysis can potentially outperform static WCET analysis in precision. However, due to the statistical operation of measurement-based WCET analysis, this cannot be guaranteed.

The discussions so far leads to the following main requirement for our measurement-based WCET analysis:

The degree of precision and safety of the analysis has to be adaptable to the resources (e.g. analysis time) the developer is willing to invest. All involved means have to be conveniently accessible and capable of being integrated smoothly into a design process at multiple stages.

One way to achieve this goal is to make use of techniques where the level of abstraction is adaptable. We use program segmentation for splitting the CFG into overlapping subgraphs called segments. Each segment is small enough to be measured exhaustively w.r.t. path coverage (also referred to as predicate coverage [START_REF] Ntafos | A Comparison of Some Structural Testing Strategies[END_REF]).

The implicit premise of path coverage is that there is only a finite number of paths that need to be considered. Practically, this amounts to ruling out infinite loops and infinite recursion, which is a reasonable assumption for the kind software components we consider. Concretely we assume each task to be analyzed to be a so-called transformative system, i.e., a subsystem that takes its input data and transforms them into output data [START_REF] Berkenkötter | Model-based Testing of Reactive Systems[END_REF].

Following common practice, we assume the availability of iteration bounds for all cycles in the CFG. In many cases, such bounds can be derived automatically via static analysis techniques [START_REF] Ermedahl | Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis[END_REF][START_REF] De Michiel | Static Loop Bound Analysis of C Programs Based on Flow Analysis and Abstract Interpretation[END_REF]. Otherwise they must be provided by a human expert.

The input data for the measurements is produced by FSHELL [START_REF] Holzer | FShell: Systematic Test Case Generation for Dynamic Analysis and Measurement[END_REF][START_REF] Holzer | Query-Driven Program Testing[END_REF], a database engine dispatching queries about a C program to program analysis tools. The version at hand utilizes the bounded model checker CBMC [START_REF] Clarke | A Tool for Checking ANSI-C Programs[END_REF], which supports full ANSI-C, including function-pointers, bit-operations, and floating-point arithmetic. As a result, FSHELL is able to cope with full ANSI-C, but-due to the nature of bounded model checking-requires loop bounds to be given for all loops or recursive calls with non-constant bounds.

For deriving a global WCET estimate we use the Implicit Path Enumeration Technique (IPET) [START_REF] Puschner | Computing Maximum Task Execution Times -A Graph-BasedApproach[END_REF][START_REF] Li | Performance Analysis of Embedded Software Using Implicit Path Enumeration[END_REF], for which the segment graph forms the input, i.e., the linear equations model the flow between segments and the cost for a segment is the worst case observed execution time thereof.

As we will show, the segment size inherently affects analysis complexity and precision and must therefore be adaptable to satisfy our main requirement of having the precision and safety adaptable. Moreover, we will see that segments can be formed out of any graph-like structure such that hardware effects can potentially be incorporated. This enables our measurement-based WCET analysis to increase the level of precision and safety.

Related Work

A means for control flow segmentation is discussed in [START_REF] Johnson | The Program Structure Tree: Computing Control Regions in Linear Time[END_REF] where the program is decomposed into a hierarchical tree of Regions. Each region has a single entry and a single exit (SESE) like our segments. We do not make use of any hierarchical structure, though. Furthermore, the presented algorithm to form the regions does not specifically target the reduction of possible control flow paths.

Bernat et al. paths, both the structures and the segmentation algorithms differ from ours.

Our work is largely motivated by Wenzel et al. [START_REF] Wenzel | Automatic Timing Model Generation by CFG Partitioning and Model Checking[END_REF]. The idea of CFG partitioning to reduce the amount of local paths for exhaustive measurements and the successive compositions of timing information for WCET calculation is first discussed in their work. We extend the segmentation to deal with loops and unstructured code. Furthermore, our approach is more flexible in the sense that we extend the degree of freedom for decomposition.

The idea for an adaptable abstraction by using segments is discussed in [START_REF] Ballabriga | Improving the WCET Computation Time by IPET Using Control Flow Graph Partitioning[END_REF]. However, while we decompose the CFG, their segmentation splits the IPET equation system for reducing complexity.

Segmentation

To obtain a perfectly accurate timing model, we generally have to consider the execution time of all possible operation sequences that can be performed by the computer while executing the given computer program.

In compiler construction, the traditional program representation that makes all statically possible operation sequences explicit is the control flow graph (CFG), a graph where nodes represent the operations of the software, and where edges represent possible successive execution.

There are richer graph-like system representations for the set of possible operation sequences, like, e.g., the kripke structures used in formal methods, which can encode detailed information on the system state (the CFG merely distinguishes different code locations). Also, it is possible to enrich a CFG with additional state information, e.g., by using preconditions. In this paper we will only consider plain CFGs, but it should be noted that the concepts presented here can be adapted to other graph-like representations on different levels of abstraction.

A CFG does not include information about the dynamics of the software. It therefore overapproximates the (dynamically) feasible operation sequences, a subset of all statically possible operation sequences.

More precisely, each path through the CFG (from a distinguished start node to a distinguished end node) represents a (statically) possible operation sequence. By considering all these paths, we can conclude about the timing behavior of the complete program, from the timing behavior of the individual paths. For example, if we know the Worst Case Execution Time (WCET) of each path, we could, in principle, derive the WCET of the complete program.

Consider the C source code in Listing 1. We can see that the false branch of the second conditional statement cannot be taken, if the false branch of the first conditional statement has been taken before. As a consequence, only three of the four statically possible paths through the corresponding CFG (Figure 2) are feasible.

The infeasible path e 7 , e 6 , e 3 , e 2 does not contribute to the timing behavior of the program, because it can never be executed. It should therefore be excluded from timing analysis.

The CFG alone cannot represent this information. What we would like to have is a representation that is expressive enough to represent individual paths. However, considering the prohibitively large number of paths in most real software, the representation must also be capable of representing collections of paths concisely. Lastly, our representation should be similar to a CFG, so that timing analysis methods like IPET, which operate on a CFG, can be used with minimal adaption. For any inter edge s, t , we require that exit(s), entry(t) ∈ E.

Definition 1 (Segment

Graph) A segment graph Σ of a CFG G is a tuple G,
An intra edge in a segment s is an edge v, w with v, w ∈ edges(s).

Each node and each intra edge must be in at least one segment, i.e., s∈S nodes(s) = N and s∈S edges(s) = E.

Furthermore, entry and exit nodes must be in their corresponding segments, i.e., {entry(s), exit(s)} ⊆ nodes(s).

Moreover, the source and target nodes of all intra edges must also be in the corresponding segment, i.e., v, w ∈ edges(s) ⇒ v ∈ nodes(s) ∧ w ∈ nodes(s).

An initial segment is a segment s with init ∈ nodes(s). Likewise, a final segment is a segment s with f inal ∈ nodes(s).

A segment path π(s) through a segment s is a sequence

π(s) = v 1 , v 2 v 2 , v 3 . . . v n-2 , v n-1 v n-1 , v n
of intra edges v i , v i+1 that are all in the segment s, i.e., v i , v i+1 ∈ edges(s), for some s ∈ S. Moreover, the path must start in the segment's entry node and end in the segment's exit node, i.e., v 1 = entry(s) and v n = exit(s).

Figure 3 visualizes a segmentation of the CFG from Figure 2 with three segments. We can seen that segments s 1 and s 3 are initial segments, because they contain the CFG's initial node, whereas segments s 2 and s 3 are final segments, because they contain the CFG's final node. Entry and exit of each segment indicated by dashed or dotted borders, respectively. We see that nodes and intra edges can be shared between segments. Although not shown in this figure, it is also possible that an inter edge can at the same time be an intra edge for some segments.

Semantically, a segment graph of a CFG G is a description of a subset of the paths in G. A segment graph can therefore be seen as a restriction of a CFG to a certain set of paths.

Definition 2 (Paths in a Segment Graph) Let Σ be a segment graph G, S, nodes, edges, entry, exit .

The set of paths in Σ is the set of all CFG paths

π = π 1 (s 1 )e 1 π 2 (s 2 )e 2 . . . e n-1 π n (s n ),
where the π i s i are segment paths that constitute dynamically feasible subpaths in G, and where e i = exit(s i ), entry(s i+1 ) , i.e., the segment paths are connected via inter edges.

It can be shown that the set of paths in a segment graph of a CFG G is a subset of the paths in G.

There are two interesting special cases of segment graphs: minseg: The minseg segment graph is the segment graph where each node is contained in its own segment, and where no segment contains any edge, i. Applying the semantic definitions on the segment graph visualized in Figure 3, we obtain the following segment paths: s1 :{e 5 } s2 :{e 1 e 0 , e 3 e 2 } s3 :{e 7 e 6 e 1 e 0 , e 7 e 6 e 3 e 2 }.

Because the path e 7 e 6 e 3 e 2 is a dynamically infeasible path, the set of paths in the segment graph is {e 5 e 1 e 0 , e 5 e 3 e 2 , e 7 e 6 e 1 e 0 }. Figure 3: A segment graph that was obtain from the one in Figure 2 by splitting at edge e 4 . In this example the segment split into three smaller segments. Segment s 1 now holds all paths that went from the original entry node of the prevision segment to the source node of the split edge, without passing the split edge itself. Segment s 2 contains all paths that went from the target node of the split edge to the exit node, without passing the split edge itself. Segment s 3 contains all paths that went from the entry node to the exit node, without passing the split edge. Edge e 4 has become an inter edge.

The segment graph framework as presented here does not include any special construct for handling function In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 calls. However, function calls are easily supported via inlining the body of called functions at their respective call sites. This approach allows for unrestricted segments across calling borders. On the other hand, function calls that have not been inlined are handled transparently, as atomic operations. This black-box view can be particularly useful in the case of closed-source third-party code.

Segmentation Algorithm

For a given CFG, many different segment graphs are possible, so which one should we choose for our purpose of measurement-based timing analysis? The two corner cases are minseg and maxseg. The minseg segment graph is only interesting for comparison purposes, as it describes the same set of paths as the plain CFG. On the other hand, performing an analysis on a maxseg segment graph would mean that all statically possible paths have to be checked for feasibility and, in case they are found feasible, be subject to measuring and analysis.

In this paper, we consider a segmentation algorithm that is based on the following idea: in order to exclude from the analysis as many infeasible paths as possible, we would like to have segments that are as large as possible in terms of the total number of segment paths. However, the total number of segment paths must not become too large, because we can only check, measure, and analyze a limited number of paths.

Our algorithm starts out with a maxseg segment graph and iteratively splits segments into smaller segments until the number of segment paths3 is small enough in each segment.

Because we have ruled out infinite loops, the number of paths in a segment is always finite and can be calculated as exact or approximate solution of a combinatorial problem that incorporates the given iteration bounds.

Segments are always split at some intra edge and are thereby reduced to up to four smaller segments-details follow below. The new segments are put into a priority queue that is ordered by the number of segment paths. Multiple copies of the same segment are merged into a single segment, as soon as they occur. The algorithm keeps on splitting the largest segment (unless it is already small enough) until the queue is empty. As split edge, the algorithm chooses an edge with a maximal edge betweenness centrality measure.

Edge betweenness is a centrality measure for graphs that indicates the relative importance of an edge as a passageway for shortest paths. It is defined as

Σ v,w∈N σ v,w (e) σ v,w , (1)
where σ v,w designates the number of different shortest paths 4 from node v to node w, and where σ v,w (e) desig-nates the number of shortest paths from node v to node w that pass through edge e.

The rationale for choosing an edge with maximal edge betweenness for splitting is that cutting such an edge will produce new segments of considerably smaller size than the original segment, i.e., the algorithm will converge to a solution quickly. Moreover, the solution will feature relatively few, but large segments, which can be advantageous during further analysis, e.g., to keep the constraint system in an IPET analysis small.

Edge betweenness can be computed very efficiently. Brandes [START_REF] Brandes | A Faster Algorithm for Betweenness Centrality[END_REF] presents a method for computing betweenness and related shortest-path based centrality measures. The algorithm has an asymptotic worst-case time complexity of O(n•m), and an asymptotic worst-case space complexity of O(n + m), where n and m are the number of nodes and edges in the graph, respectively. Our current implementation of segmentation makes use of the BGL [START_REF] Siek | The Boost Graph Library: User Guide and Reference Manual (C++ In-Depth Series)[END_REF][START_REF] Siek | The Boost Graph Library[END_REF] implementation of Brandes' algorithm.

Algorithm 1 illustrates our implementation.

Algorithm 1 Pseudo code of the maximum betweenness segmentation algorithm. 1: procedure SEGMENTATE MAXBET(cf g, limit)

2:

g ← maxseg segment graph of cf g 3:

s ← the segment of g 4:

insert s into priority queue q 5: while q is not empty do 6:

pop segmentation s from q

7:
if number of paths in s > limit then

8:

e ← intra edge of s w/max. betweenness loop segment: A segment capturing all paths in the previous segment s from node w to node v that do not pass through edge (v, w).

Figure 4 shows how these segments are connected by inter edges. Figures 5 and6 show a concrete example of splitting at a back edge.

Complexity Considerations

In the course of repeated splitting, it may happen that some of the produced segments are very similar. In particular, our experimental evaluation showed that the plain Figure 6: A segment graph that was obtained from the one in Figure 5 by splitting at the back edge e 8 . Because the previous segment contained a loop, loop segment s 3 was produced. This segment can be reached directly from the tosplit segment, and directly reaches the fromsplit segment, as well as itself, via a self loop. maximum betweenness segmentation algorithm, as presented above, can produce a large number of identical segments. Mostly, this happens when overlapping segments with a common entry or exit node are found to have their maximum betweenness in a shared edge. Our implementation of the maximum betweenness segmentation algorithm can optionally be configured to merge identical segments after each splitting step, which can reduce the size of the intermediate and final segment graphs significantly.

During our experimental evaluation, our optimized segmentation algorithm was seen to work fine in practice. For a formal worst case complexity analysis of the algorithm, one would have to consider the combination of two diametrically opposed tendencies. On the one hand, each splitting step will replace a segment with up to four smaller segments. Even though many of these segments are immediately collapsed by the subsequent merging step, this can lead to exponential space complexity in the number of splitting steps. On the other hand, however, the bypass segment yielded by splitting is linearly smaller (in terms of paths) than the original segment. Moreover, the size of the to split, from split, and loop segments yielded by splitting at the edge with maximum betweenness is typically a fractional power of the size of the original segment. We have not performed a formal analysis of the overall space and time complexity of our algorithm.

Experiments

To highlight the adaptable character of the segmentation techniques we will compare two segmentations of the same input program. They represent two extreme cases where the first includes segments as large as possible (at most 100 paths per segment, i.e. test case generation is barely feasible for the number of contained paths) and the second one forms a single segment for each CFG node (i.e. one path per segment), respectively. This way we illustrate the dependency between analysis complexity and the WCET estimate's precision.

We utilize the FORTAS framework to perform our experiments by which means we have access to all basic functions we need. Figure 7 illustrates the FORTAS architecture that combines a collection of modules/plugins. The core manages the communication between these plug-ins by distributing XML-RPC protocol messages. It potentially allows for running plug-ins on different hosts for instance to parallelize the measurement and the test case generation processes. The presented algorithm is implemented in the segmentor. It gets the CFG from C modeler, an extension of LLVM and the Clang frontend. The derived segment graphs are added to the repository plug-in which provides a consistent and persistent way to access both intermediate and final analysis results. For each segment, we automatically derive a query for FSHELL [START_REF] Holzer | FShell: Systematic Test Case Generation for Dynamic Analysis and Measurement[END_REF][START_REF] Holzer | Query-Driven Program Testing[END_REF] which in turn generates a test data set yielding path coverage for the according segment. A query to FSHELL is formed by a sequence of program locations such that the generated input data result in an execution sequence including those locations. The input language also includes negations to exclude code locations for a test case and commands to target coverage metrics. By these means, each path in a segment can be expressed by the sequence of its CFG nodes. Query generation is therefore straightforward and convenient.

Once all test data are generated, the consecutive measurement process takes the input data set and performs execution time measurements on the target platform. In a next step the longest observed execution time for each segment is filtered out from all measurements. The IPET plug-in assembles those values and the segment graph to apply the implicit path enumeration technique, yielding a global WCET estimate. The so far unmentioned controller implements the demonstrated work flow as well as means of logging, monitoring and verification. All plugins and the core run on a 2.66 GHz Intel Core2 Quad host with 8 GB of RAM.

Target Platform and Measurement

We perform measurements on an Infineon TriCore TC1796 microcontroller. It includes an instruction cache and a processor pipeline which leads to potential underestimations of the global WCET since we do not incorporate execution histories at segment entries on the one hand. We also cannot capture all data-dependent execution time jitter on the other hand, as the CFG is a too coarse abstraction. However, for less complex hardware, e.g. the HCS12 microcontroller, the introduced timing analysis produces a safe WCET bound. We have chosen the TriCore for our measurements, because we plan to tackle the shortcomings of the approach w.r.t. complex hardware in the near future. Furthermore, the TC1796 includes On-Chip Debug Support (OCDS) level 2, providing means for cycleaccurate execution tracing. We utilize the Lauterbach LA-7690 Powertrace device to document both timing and flow of control, rendering code instrumentation obsolete: not only measurements have a higher resolution, also the source code can remain unchanged. A measurement starts with test data injection right before the call of the main function where all relevant registers (e.g. function arguments) and global variables are set. Note, that the hardware state (cache, pipeline, etc.) is unknown at this point. However, due to a previous initialization script this state is identical for every measurement. The measured execution (or trace) then includes not only the execution of main but also of all its children in the function call graph. In a postprocessing phase the resulting trace is related to the source code, its CFG and segments by the Measurement plug-in using debug information from the binary. OCDS Level 2 provides traces of temporally high resolution, i.e. every executed machine instruction gets a time stamp. Consequently, the duration of a measured segment path can be derived precisely as the machine instructions can be related to all CFG nodes in the corresponding segment. If measurements are too coarse, not every CFG node of a path through a segment will get a time stamp. This happens for instance when software instrumentation is used to raise hardware signals at certain program points to externally assign timestamps. In this case we choose the splitting edges during segmentation such that they are near to CFG nodes that can be mapped to a time stamp. Consequently, the level of freedom in choosing segment borders is an important feature for guaranteeing portability of our approach. One problem that comes along with OCDS is that the trace buffer might overflow if too many control flow changing instructions follow in succession. A lack of timing information in the trace influences measurement precision if it occurs at segment borders in which case the first/last available time stamp after/before the gap is taken as a reference for calculating the duration of a segment path. Although this potentially introduces a source of pessimism, we did not observe any trace gaps so far for any benchmark.

Benchmark

The input program on which we carried out the analysis is an engine control unit implemented in ANSI C. The reason for choosing the benchmark is manifold: (a) it rep-resents a practical application from the automotive industry (provided by Magna Steyer Fahrzeugtechnik), (b) the code is generated by Matlab/Simulink and demonstrates that the analysis can potentially be integrated into a modern design process, (c) with 2952 source code lines and a size of 201430 bytes, it is considerably large and (d) it involves a complex control flow structure (1632 CFG nodes, 2164 transitions) with more than 10 45 statically possible paths. The target function has one subfunction which is called at most three times per execution. The benchmark includes 230 integer variables that potentially affect control flow. Unfortunately, we cannot make the benchmark publicly available due to a non-disclosure agreement.

Preliminary Results

The relation between maximal number of paths per segment, analysis complexity and precision is illustrated in Table 1. We see the results for two segmentations with a maximum of 1 and 100 paths per segment, respectively. The most important effects of these parameters, i.e. analysis complexity and precision are emphasized in rows 10 and 14: the more time is spent the less pessimistic the WCET estimate gets. Here, pessimism is defined as the difference between WCET estimate and the worst-case observed execution time (WCOET), divided by the WCET estimate. There were no manual efforts to maximize the WCOET, i.e. the WCOET is the execution time of maximal observed length. Note, that this metric is only an approximation for this target hardware. However, comparing WCOET and WCET estimate is the best metric available.

The overall analysis time comprises applying the segmentation algorithm [START_REF] De Michiel | Static Loop Bound Analysis of C Programs Based on Flow Analysis and Abstract Interpretation[END_REF], test case generation via FSHELL [START_REF] Ermedahl | Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis[END_REF], measuring the feasible segment paths [START_REF] Ernst | Embedded Program Timing Analysis Based on Path Clustering and Architecture Classification[END_REF] and timing composition via IPET [START_REF] Heckmann | Worst-case execution time prediction by static program analysis[END_REF] to get a WCET estimate. Test case generation uses up most of the analysis time: it has to generate input data or prove infeasibility for each statically possible segment path in each segment.

The difference in analysis time per path is due to an optimization technique. In the experiment with one path per segment, we instructed FSHELL to generate input data yielding basic block coverage for the whole program which implies path coverage for each segment in this special case. This also causes the reduced set of 387 out of 1287 paths that had to be analyzed and measured. In contrast, using a path bound of 100, all 2139 statically feasible paths have to be analyzed individually.

A critical point that we observe is the too pessimistic estimate for a path bound of 1. Our major concern is now to find better segmentation parameters and to improve the overall performance such that useful results can be derived over night.

Potential for Optimization

So far, measurement and test case generation are processed sequentially although they can be pipelined. Table 1 shows that measurements are too time consuming. This is due to a bottleneck in our prototypical measurements device and will be improved in the future.

All measurements are performed end-to-end such that a program execution causes the control flow to pass multiple segments sequentially. However, we do not test whether there is already a measurement in the repository for the segment path that we want to cover. We expect a drastic performance enhancement for this optimization technique.

Another option which is not accounted for so far is to initially apply heuristic test case generation prior to model checking. This technique proved to boost performance considerably in [START_REF] Wenzel | Automatic Timing Model Generation by CFG Partitioning and Model Checking[END_REF].

Conclusion and Outlook

In this paper we presented a measurement-based timing analysis approach that incorporates an abstraction technique to express a real-time system's temporal behavior a varying levels of detail. This enables the analysis to be adaptable in terms of complexity, precision and safety.

We have introduced the segment graph as a novel, flexible control flow abstraction that can be used to exclude dynamically infeasible paths from further analysis. As a basic operation on a segment graph, we have presented the splitting of individual segments at a given intra edge. This operation forms the foundation of the maximum betweenness segmentation algorithm, which tries to heuristically find a good segmentation.

Although we have only considered CFG-like program representations in this paper, the concept of a segmentation graph is not restricted to this representation. Segmentation graphs can be constructed over other graph-based representations, like, e.g., kripke structures.

Lastly, we have presented preliminary results of experiments that were performed using a prototype implementation of our approach.

Immediate next steps are the further improvement of our prototype implementation which is still in an early stage of development, and performing further experiments. Our more ambitious plans include the develop-ment of an adaptive analysis approach that employs an incremental refinement strategy to improve the analysis results.

Figure 1 :

 1 Figure 1: Measurement-based Timing Analysis. Our design choice of decomposing C programs based on their CFG and learning a hardware model closely related to the CFG has two major ramifications:

  [START_REF] Bernat | WCET Analysis of Probabilistic Hard Real-Time Systems[END_REF] and Ernst et al.[START_REF] Ernst | Embedded Program Timing Analysis Based on Path Clustering and Architecture Classification[END_REF] use program segmentation explicitly to target WCET analysis. Because they do not address the problem of systematic generation of input data and the implicit goal of reducing control flow In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

Figure 2 :

 2 Figure 2: Maxseg segment graph induced by the program in Listing 1, an equivalent of the programs CFG. There are four statically possible paths. Assuming that edges 5 and 2 correspond to a successful test of the conditions x != 0 and x % 2 == 0, respectively, the path e 7 , e 6 , e 3 , e 2 is dynamically infeasible. i f ( x ! = 0 ) f l a g s = 1 ; e l s e f l a g s = 0 ; i f ( x % 2 == 0 ) f l a g s = f l a g s | 2 ; e l s e f l a g s = f l a g s | 4 ; Listing 1: Source code of a program with two consecutive tests, where the second test can only fail after the first test has succeeded.

  S, I, nodes, edges, entry, exit , where G = N, E, init, f inal is a CFG with nodes N , edges E ⊆ N × N , an unique initial node init ∈ N , and an unique final node f inal ∈ N . Moreover, S is a set of segment names, I ⊆ S × S is a set of inter edges (edges between segments), nodes : S → P(N ) is a function designating the nodes in each segment, edges : S → P(E) is a function designating the edges in each segment, entry : S → N is function designating the entry node of each segment, and exit : S → N is a function designating the exit node of each segment.

  e., nodes(s v ) = {v}, for any v ∈ N , edges(s v ) = ∅, entry(s v ) = v, and exit(s v ) = v. The paths in a minseg segment graph of a CFG G are the statically possible paths described by G. maxseg: There is a single segment s, which contains all nodes and edges of the CFG, i.e., nodes(s) = N , edges(s) = E, entry(s) = init, and exit(s) = f inal. The paths in a maxseg segment graph of a CFG G are the dynamically feasible paths of G.

Figure 4 :

 4 Figure 4: Connection scheme of new segments after splitting. The left hand side shows segment s together with two predecessor segments, s 1 and s 2 , and two successor segments, s 3 and s 4 . On the right hand side s has been replaced by the new segments tosplit, f romsplit, bypass, and loop. These segments have been connected among each other as well as to their environment.

Figure 5 :

 5 Figure 5: A maxseg segment graph of a CFG that contains a loop.

Figure 7 :

 7 Figure 7: The FORTAS architecture.

  at an intra edge (v, w) means removing (v, w) from s and turning it into one or more inter edges e 1 , . . . , e n that connect the segments in the segment graph in such a way that, semantically, no dynamically feasible path is lost.In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 bypass segment: A segment capturing all paths in the previous segment s from node entry(s) to node exit(s) that do not pass through edge (v, w).

	11:	insert new segments into q
	12:	merge equivalent segments in q
	13:	end if
	14:	end while
	15:	return g
	16: end procedure
	Splitting
		Splitting a segment s When the split edge is removed, the previous segment
	breaks into up to four new segments:
	tosplit segment: A segment capturing all paths in the
		previous segment s from node entry(s) to node v

9:

new segments ← split s at edge e 10: replace s with new segments in g that do not pass through edge (v, w). fromsplit segment: A segment capturing all paths in the previous segment s from node w to node exit(s) that do not pass through edge (v, w).

Table 1 :

 1 Summarized results.

	1	Paths per Segment	1	≤ 100
	2	Number of segments	1287	73
	3	Sum of statically possible segment paths	1287	2139
	4	Sum of feasible segment paths	1201	1403
	5	Analyzed and/or measured paths	387	2139
	6	Segmentation time [s]	166	81
	7	Test case generation time [s]	6025	177464
	8	Measurement [s]	4447	10706
	9	IPET time [s]	1423	0.005
	10	Overall analysis time [s]	12061	188251
	11	Analysis time / path [s]	20	83
	12	WCET estimate [µs]	20789	1975
	13	WCOET [µs]	728	728
	14	Pessimism [%]	2756	171

http://www.fortastic.net

The traditional definition of a CFG does not allow for linear sequences of operations, i.e., the nodes must constitute so-called basic blocks. We relax this requirement and allow for general graphs, as the restriction the basic blocks is neither strictly necessary, nor particularly useful in our context. In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

An alternative measure is the total number of paths over all segments.

[START_REF] Brandes | A Faster Algorithm for Betweenness Centrality[END_REF] I.e., shortest statically possible CFG paths, in our case.

Acknowledgments. We are grateful to Michael Tautschnig and Andreas Holzer for providing FSHELL and the C Modeler. We also thank them for discussions on the topic of this paper.

The research leading to these results has received funding from the Austrian Science Fund (Fonds zur Förderung der wissenschaftlichen Forschung) within the research project Formal Timing Analysis Suite of Real-Time Systems (FORTASRT) under contract P19230-N13 and the research project 'Sustaining Entire Code-Coverage on Code Optimization (SECCO) under contract P20944-N13.


Zheng Shi

Alan Burns
email: burns@cs.york.ac.uk

Improvement of Schedulability Analysis with a Priority Share Policy in On-Chip Networks

Priority-based wormhole switching with a priority share policy has been proposed as a possible solution for real-time on-chip communication. However, the blocking introduced by priority share complicates the analysis process. In this paper, we propose a new "per-priority" basis analysis scheme which computes the total time window at each priority level instead of each traffic-flow. By checking the release instance of each flow at the corresponding priority window, we can determine schedulability efficiently.

Introduction

On-chip networks (NoCs) [START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF][START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF], have emerged as a new design paradigm to overcome the limitation of current busbased communication infrastructure [START_REF] Furber | Future trends in SoC interconnect[END_REF], and are increasingly importance in today's System-on-Chip (SoC) designs. The typical architecture of on-chip networks consists of multiple intellectual property (IP) modules connected through an interconnection network. This architecture offers a general and fixed communication platform which can be reused for a large number of SoC designs.

Multiple IP-cores based design using NoC allows multiple applications to run at the same time. These applications execute data processing and exchange information through the underlying communication infrastructure. Some applications have very stringent communication service requirements, the correctness relies on not only the communication result but also the completion time bound. A data packet received by a destination too late could be useless. These critical communications are called real-time communications. For a packet transmitted over the network, the communication duration is denoted by the packet network latency. The maximum acceptable duration is defined to be the deadline of the packet. A traffic-flow is a packet stream which traverses the same route from the source to the destination and requires the same grade of service along the path. For hard real-time traffic-flows, it is necessary that all the packets generated by the traffic-flow must be delivered before their deadlines even under worst case scenarios.

The on-chip network is a significant solution for complex communication of SoCs and outperforms the traditional busses or a point-to-point approach in many ways [START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF]. But it also introduces unpredictable network delay since the expensive hardware resources ( e.g. link bandwidth and buffer space) are usually shared by a number of applications. When more than one packet tries to access the shared resource at the same time, contention occurs. The contention problem, which leads to packet delays and even missing deadlines, has become the major influence factor of network predictability. So how to solve contention problem is a key issue in implementing guaranteed performance service in NoC design.

Contention avoidance and contention acceptance are two basic approaches to address the contention problem. First approach considers that contention is avoidable by trying to pre-arrange and allocate resources before the start of the communication, so that two packets never access the same resource at the same time. Time division multiplexing (TDM) and circuit switching are two common contention avoidance schemes. In AEtheral [START_REF] Goossens | Aethereal network on chip: Concepts, architectures, and implementations[END_REF] and Nostrum [START_REF] Millberg | Guaranteed bandwidth using looped containers in temporally disjoint networks within the Nostrum network on chip[END_REF], the whole link transmission capacity is partitioned into fixed time-slots, each of which represents a unit of time when a single application can occupy this physical link exclusively for data transmission. But this scheme requires a global notion of time in the network. Besides that, the latency is coupled to bandwidth, preventing low latency from being provided to low rate requirement without over-allocating. A circuit-switching technique is used in [START_REF] Wolkotte | An energy-efficient reconfigurable circuitswitched network-on-chip[END_REF][START_REF] Wiklund | Socbus: Switched network on chip for hard real time embedded systems[END_REF]. A dedicated connection is constructed between source and destination nodes by reserving a sequence of wiring resources. The major problem of this scheme is that the resources that have been reserved for a flow can not be used by any other flow which results in the under-utilized links. The contention avoidance policy requires the network resource to be configured before the communication which lacks flexibility and wastes the links transmission capacity.

A contention acceptance policy normally utilizes an arbiter at running time. QNoC [START_REF] Bolotin | QNoC: QoS architecture and design process for network on chip[END_REF] divides network services into four levels and utilizes a priority arbiter to implement the differentiated services. But this scheme only offers the coarse-granularity service and does not seem to be suitable for hard real time application. Kavaldjiev et al [START_REF] Kavaldjiev | A virtual channel network-on-chip for GT and BE traffic[END_REF] presented a simple round-robin arbiter to cater for the real time services. In Mango NoC project [START_REF] Bjerregaard | A scheduling discipline for latency and bandwidth guarantees in asynchronous network-on-chip[END_REF], a new arbiter is designed which combine round-robin and priority to bound latency and bandwidth. But both of them suffer the same problem as TDM that the latency is coupled with bandwidth. As a new solution, a priority based wormhole switching technique [START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF] is introduced to provide communication service guarantees. The hard timing bound is delivered by this approach with the support of a priority based router infrastructure which allocates each traffic-flow with a distinct priority and virtual channel independently. This scheme successfully overcomes the problem of latency coupled with bandwidth and thus supports a wide range of traffic types. Latency analysis and validation have been discussed in a number of papers [START_REF] Balakrishnan | A priority-driven flow control mechanism for real-time traffic in multiprocessor networks[END_REF][START_REF] Hary | Feasibility test for real-time communication using wormhole routing[END_REF][START_REF] Kim | A realtime communication method for wormhole switching networks[END_REF][START_REF] Lu | Feasibility analysis of messages for on-chip networks using wormhole routing[END_REF][START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF]. But the drawback of the prioritybased wormhole switching approach is precisely that the distinct priority per traffic-flow implementation policy results in higher area and energy overhead and hence limits its employment and development in on-chip networks. To solve this problem, Shi and Burns [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF] proposed a priority share policy to reduce the resource overhead while still achieving hard real-time communication guarantees. The priority share policy permits multiple traffic-flows to contend for a single virtual channel and share the same priority level. In that paper [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF], the authors also presented a composite model analysis scheme. But this approach requires that all the traffic-flows must meet the constrain that network latency is no more than period. This is a strong restriction. The more complex the system, with long communication delays over several hops, the greater the global delays will become.

In this paper, we propose a new analysis approach which can efficiently handle wormhole switching with a priority share policy. The new analysis is based on "per-priority basis", that is, it computes the total time window at each priority level instead of each traffic-flow. By checking the packet release instance of each traffic-flow at the corresponding priority window, we can verify the timing semantics of real time traffic-flow with a simple yet efficient mechanism. The deadline no more than period constraint is successfully removed by this approach with a low computational complexity. In addition, we also find that the previous result proposed in [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF] is just a special case covered by this new analysis.

The rest of this paper is organized as follows: Section 2 introduces wormhole switching networks with a priority share policy. Section 3 describes the real-time communication model and notations used in this paper. A novel schedu-lability analysis technique and related example are presented in sections 4 and 5. Finally, section 6 concludes the paper.

2 Wormhole switching with priority share 2.1 Wormhole switching structure Wormhole switching [START_REF] Ni | A survey of wormhole routing techniques in direct networks[END_REF] is an increasingly common interconnect scheme for NoC as it minimizes communication latencies, requires small buffer and is simple to implement. Each packet in a wormhole network is divided into a number of fixed size flits [START_REF] Ni | A survey of wormhole routing techniques in direct networks[END_REF]. The header flit takes the routing information and governs the route. As the header advances along the specified path, the remaining flits follow in a pipeline way. If the header flit encounters a link already in use, it is blocked until the link becomes available. In this situation, all the flits of the packet will remain in the routers along the path and only a small flits buffer is required in each router.

Figure 1. Output Arbitration with Priority Share

In order to ensure hard real-time service guarantees with limited resources, a priority share based flit-level arbitration structure is introduced [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF], Figure 1 shows such a structure. There are a number of prioritized virtual channels [START_REF] Dally | Virtual-channel flow control[END_REF] available at each router output port. The virtual channels (VCs) area resource allocation technique which provides multiple independent buffers for each physical link. Each of these buffers is considered as a virtual channel and can hold one or more flits of a packet. The credit-based flow control provides each virtual channel of each router with some credit, which is equal to the buffer size of that virtual channel of the subsequent router. The credit is decremented upon transmitting a flit and incremented upon receiving a buffer-free notification from the next router. A priority based arbitrator controls the access to the shared physical link for all the virtual channels. Since VCs are not mutually dependent on each other, the transmitting packet can bypass a blocked one through the different VCs. This strategy efficiently utilizes the network resource (link bandwidth) and improves the per-formance with a very small buffer overhead [START_REF] Bjerregaard | A survey of research and practices of network-on-chip[END_REF].

Differing from previous works [START_REF] Hary | Feasibility test for real-time communication using wormhole routing[END_REF][START_REF] Kim | A realtime communication method for wormhole switching networks[END_REF][START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF], the distinctive characteristic of the priority share scheme is that multiple traffic-flows per virtual channel are supported. These trafficflows sharing the same virtual channel will be mapped to the same priority. Each packet generated by the traffic-flow inherits this priority. A packet with priority G i can only request the virtual channels associated with priority G i . At any time, a flit of a given packet will be sent out through its respective output port if it has the highest priority and it has credit(s). In addition, a higher priority packet can also preempt a lower priority packet during its transmission. As a hybrid solution, best-effort traffic-flows also can be multiplexed on the same links with lowest priority (any real time flow has higher priority than best-effort flows). In the case where no real time flow is available, best-effort flows make use of spare bandwidth.

The problem of blocking

By sharing priority, the hardware resource overhead can be reduced dramatically compared with the traditional distinct priority per traffic-flow scheme [START_REF] Hary | Feasibility test for real-time communication using wormhole routing[END_REF][START_REF] Kim | A realtime communication method for wormhole switching networks[END_REF][START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF]. But on the other side, it may lead to significantly blocking and unpredictable network latency. Consider the fact that traffic-flows within the same virtual channel are served in first-in-first-out (FIFO) order because the priority preemption is only available between the different virtual channels. When a packet has to wait for the transmission of another packet (this packet can be released from the same flow or other flow) in the same buffer due to priority share, blocking occurs. Therefore, a packet can be blocked by every packet with the same priority which arrives just before it. Once a packet is blocked by another packet with the same priority which holds a virtual channel for a prolonged duration, it can block other packets, which can in turn block other packets, and so on.

Figure 2. A Case of Traffic-flows with Priority Share

As a simple example to motivate the blocking problem, consider Figure 2, which illustrates a number of traffic-flows loaded on a NoC platform. Flows τ 1 , τ 2 and τ 3 share the same priority G 1 , τ 4 and τ 5 share the same priority G 2 and G 1 is higher a priority than G 2 . We assume that a packet from τ 5 is released, because of priority share, τ 5 can be blocked by τ 4 if it arrives just after τ 4 . During τ 4 's transmission, it can be preempted by the packet releases from higher priority flows τ 2 and τ 3 . Note that when τ 2 or τ 3 is active, τ 4 's packet service will be suspended but will still occupy link resources. In this situation, only after τ 4 's completion, can the packet from τ 5 resume its transmission service. So the interference suffered by τ 4 actually extends the possible completion time of τ 5 . Besides that, flow τ 1 in this case also can introduce some interference (see [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF]) which delays the network latency of τ 5 further. Eventhough flows τ 1 , τ 2 and τ 3 never share any physical link with τ 5 , they still can play a major role in determining τ 5 's transmission latency. This phenomenon only exists when the network supports priority share. The latency analysis in this situation is very hard due to the complicated blocking inter-relationship between the flows.

To simplify the blocking problem, the analysis in [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF] imposes a deadline no more than period restriction so that one traffic-flow can not be blocked by another flow with the same priority more than once; this is termed single blocking. With this property, all the flows sharing the same priority are transformed into a single scheduling unit and the maximum network latency is addressed by this new model. However, without this enforced constraint, we find two additional blocking phenomena may appear which also need to be considered. Multiple blocking : A set of traffic-flows sharing the same priority; one could block another more than once. Figure 3(A) shows such a situation. The solid up arrow indicates the packet release instance. The packet's latency is depicted as horizontal arrow line. τ a shares the same priority as τ i , if the transmission latency of τ i is bigger than the period of τ a , τ i could be blocked by τ a more than once. shows such a situation. In this example, the second packet released from τ i is blocked by the first one until its completion. Similarly, the third packet is also blocked by the second one, etc.

3 System model and definition

τ i = (G i , C i , T i , D i , J R i , J I i ).
We assume that all the traffic-flows which require timely delivery are periodic or sporadic. The lower bound interval on the time between releases of successive packets is called the period T i for the traffic-flow τ i . The maximum basic network latency C i is the maximum duration of transmission latency when no traffic-flow contention exists [START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF]. Each real-time traffic-flow has relative deadline D which is the upper bound restriction of network latency. There is no restriction on the relationship between deadline D i and period T i . Any flow's deadline can be less than, equal to or greater than its period. J R i is the release jitter [1] and denotes the maximum deviation of successive packet releases from its period. If a packet from τ i is generated at time a, then it will be released for transmission by time a + J R i and have an absolute deadline of a + D i . J I i is interference jitter [START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF] which denotes the maximum deviation of successive packets start transmission time. Besides these, each trafficflow has a priority G i . The value 1 denotes the highest priority and larger integers denote lower priorities. We assume the traffic-flow is prioritized by any possible priority assignment policy, e.g. a greedy priority allocation algorithm has been proposed in [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF]. All the traffic-flows competing for the same virtual channel will be allocated to the same priority. Therefore, each priority level G i can be regarded as a flow set denoted by S(i). The priority should be assigned off-line and remain constant at run-time. We also define a functions G(τ i ) to obtain the corresponding priority for a traffic-flow τ i . It follows that τ i ∈ S(G(τ i )).

Inter-relationships between traffic-flows

To capture the relations between traffic-flows and the physical links of the network, we formalize the mesh network topology defined as a directed graph G : V × E. V is a set, whose elements are called nodes, each node v i denotes one router in the mesh network. E is a set of ordered pairs of vertices, called edges. An edge e x,y = {v x → v y } is considered to be a real physical link from router v x to router v y ; v x is called the source and v y is called the destination.

We define a mapping space from the traffic-flow set to the physical links Γ → E. Given a set of n traffic-flows Γ, we can map them to the target network. The routing i of each traffic-flows τ i is denoted by the ordered pairs of edges, i = {e 1,2 , e 2,3 , . . . , e n-1,n }. If a traffic-flow τ i shares at least one link with τ j , the intersection set between them is i ∩ j . If i ∩ j = ∅, τ i and τ j are disjoint. Based on whether they share the same physical links, we introduce two different relationships between the trafficflows: direct competing relationship, and indirect competing relationship. The direct competing relationship means a traffic-flow has at least one physical link in common with the observed traffic-flow. For any two traffic-flows τ i and τ j , if direct competing relationship exists between them, then i ∩ j = ∅. In the indirect competing relationship, on the contrary, the two traffic-flows do not share any physical link but there is (are) intervening traffic-flow(s) between the given two traffic-flows. For example, if there are three flows τ i , τ j , τ k meeting the following situation, k ∩ i = ∅, k ∩ j = ∅ and i ∩ j = ∅; τ j is the intervening flow in this case, then there is an indirect competing relationship between τ i and τ k . Notice that indirect competing has transitivity. If more than one intermediate flow exists, the indirect competing relationship still holds. Following the above case, if there is a new flow τ a which has an indirect competing relationship with τ j (τ k is intermediate flow between τ a and τ j ), and τ a does not share any physical link with τ i , then there is an indirect competing relationship between τ a and τ i (both τ k and τ j are intermediate flows). Figure 4 shows the situation.

Figure 4. Transitivity in indirect competing relationship

Assuming that the priorities have been assigned to each traffic-flow, if a packet is released, the possible delays it suffered before completion consist of all the interferences from higher priority traffic-flows and the blocking from the trafficflows with the same priority. Based on different priority levels and the competing relationships, we categorize the delays into four different types:

• Direct interference from traffic-flow with higher priority When two traffic-flows τ i and τ j have a direct compet- ing relationship and meet the condition G(τ j ) > G(τ i ), τ j will force a direct interference with the observed traffic-flow τ i . For flow τ i , we define a direct interference set S D i which includes all the traffic-flows meeting the above conditions, S D i = {τ j | j ∩ i = ∅ and G(τ j ) > G(τ i ) for all τ j ∈ Γ}.

• Indirect interference from traffic-flow with higher priority When two traffic-flows τ i and τ k have an indirect competing relationship and meet the condition G(τ k ) ≥ G(τ j ) > G(τ i ), τ j is the intervening flow, τ i may suffer an indirect interference from τ k even when they do not share any physical link, see [START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF] for detailed description. For flow τ i , we define an indirect interference set S I i which includes all the traffic-flows meeting the above conditions, S I i = {τ k |τ k has indirect competing relationship with τ i and G(τ k ) ≥ G(τ j ) > G(τ i ) for all τ k ∈ Γ, where τ j is any intermediate flow}.

• Direct blocking from traffic-flow with same priority

When two traffic-flows τ i and τ j have the direct competing relationship and meet the condition G(τ j ) = G(τ i ), if the packet from τ j is release just before τ i , τ j will force a blocking with τ i . For flow τ i , we define a direct blocking set S SD i which includes all the traffic-flows meeting the above conditions,

S SD i = {τ j | j ∩ i = ∅ and G(τ j ) = G(τ i ) for all τ j ∈ Γ}.
• Indirect blocking from traffic-flow with same priority When two traffic-flows τ i and τ k have an indirect competing relationship and meet the conditions G(τ k ) = G(τ j ) = G(τ i ), τ j is the intervening flow, τ i may suffer an indirect blocking from τ k even they do not share any physical link. An indirect blocking example has been shown in Figure 2 where τ 1 blocks τ 3 and further blocks τ 2 . For flow τ i , we define an indirect blocking set S SI i which includes all the traffic-flows meeting the above conditions, S SI i = {τ k |τ k has indirect competing relationship with τ i and G(τ k ) = G(τ j ) = G(τ i ) for all τ k ∈ Γ, where τ j is any intermediate flow}.

Note that the affect of the direct and indirect interferences has been presented in [START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF]. The priority share policy introduces the new direct and indirect blockings. Especially without constraint of D ≤ T, there are three different blocking relationships which severely complicate the analysis progress. So in this paper, we propose a new scheme which changes the analysis view from per flow to per priority. The detailed issues will be discussed in the next section.

Return to the example in Figure 2. Five traffic-flows τ 1 , τ 2 , τ 3 , τ 4 and τ 5 are mapped into two sets, the set with priority G 1 includes τ 1 , τ 2 and τ 3 , S(1) = {τ 1 , τ 2 , τ 3 }, the set with priority G 2 includes τ 4 and τ 5 , S(2) = {τ 4 , τ 5 }; G 1 > G 2 in this case. Traffic-flows τ 1 , τ 2 and τ 3 have no shared links with any higher priority flow so no direct or direct interference. Due to sharing the same priority, the direct and indirect blocking set for τ 1 , τ 2 and τ 3 are S SD 4 Network latency upper bound analysis

Priority window model

The correctness of the design and development of practical real-time applications in priority-based wormhole switching relies on efficient schedulability analysis. The schedulability test in this paper is based on the computation of the worst case network latency for each traffic-flow. If the worst case network latency, R, of a flow is no more than its deadline, R ≤ D, then the traffic-flow is schedulable. If all the trafficflows loaded on a network are schedulable, then the trafficflow set is called schedulable.

The term priority level-G i shared resource is introduced which denotes all the link resources required by the flows with the same priority G i . This shared resource is modeled as a single competing unit. A priority window W (i) is used to define a contiguous time interval during which this priority level-G i shared resource keeps the network busy and serves all the traffic-flows of priority higher than or equal to the priority G i . The priority window will continue until the time when the shared resource becomes idle, ready for the next transmission and yet there is no service requirement from priority level G i or higher waiting to be transmitted. As shown in Figure 2, for the priority level G 2 shared resource, the links between router 3 and 6, the corresponding priority window is the contiguous time duration where the shared resource keeps serving all the queueing packets with priority G 2 or higher (G 1 in this case). Figure 5 illustrates a priority level-G 2 window. The bold circle denotes the time the packet is received completely at the destination node. In this example, the total window W (2) at priority level-G 2 shared resource is the time span from the first release of τ 2 to the completion time of the second instance of τ 5 .

For a set of traffic-flow S(i) with the same system priority level G i , next, we show how to compute the corresponding priority window W (i).

Lemma 1. The priority level-G i window W (i) upper bound can be calculated by the following relation:

W (i) = E(i) + I(i) (1)
In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 where E(i) denotes the summation of service requirements generated by all the traffic-flows with the priority G i and I(i) accounts all the interferences from the higher priority traffic-flows which contend the level-G i share link resource during this window.

Proof. According to the definition of priority window, all the arrival packets of priority G i or higher before the end of the priority window must be transmitted during the window. Besides that, any packet with priority lower than G i is unable to delay current window. Therefore, the width of the priority window is equal to the time interval taken to serve the transmission requirements, E(i), made by all the trafficflows with the priority G i and all the interferences, I(i), from the higher priority traffic-flows which contend the level-G i share link resource during this window.

The value E(i) and I(i) determine the priority window for the level-G i shared resource. So if we can find an upper bound of E(i) and I(i), the maximum priority window W (i) is then trivially computed. Note that, when we explain how to calculate the priority window for G i priority level, we assume that analysis for all the higher priority G 1 , G 2 , . . . , G i-1 has been completed. Theorem 1. The maximum priority window W (i) for priority level G i share resource can be found by:

W (i) = ∀τn∈S(i) W (i) + J R n T n C n + ∀τj ∈hp(i) W (i) + J R j + R j -C j T j C j (2)
where hp(i) is the higher priority set, all the flows in S D i , τ i ∈ S(i), are the members of the set hp(i),

hp(i) = ∀τi∈S(i) S D i (3)
where is the union operation of the flow sets.

Proof. Supposing that we can find an upper bound of the total priority window W (i), the maximum number of instances of a flow τ n with priority G i that can delay this window is computed as follows:

W (i) + J R n T n (4)
assuming the worst case release scenario of τ n : the first packet release starts J R n later than the first arrival, and the subsequent releases are maximum packet size with the maximum release rate of 1/T n . Consequently, the service requirement summation from all the flows in S(i) is thus:

E(i) = ∀τn∈S(i) W (i) + J R n T n C n (5)
On the other hand, the interferences produced by all the higher priority flows which compete the level-G i shared resource also delay the corresponding priority window. The maximum interference analysis has been discussed in [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF]. During any time interval, an upper bound of interference produced by any higher priority traffic-flow τ j when interference jitter exists is:

W (i) + J R j + R j -C j T j C j (6)
where R j -C j is the maximal possible jitter upper bound and R j is the worst case latency of τ j . Theorems 2 and 3 below will show that the network latency of τ j can be found by calculating the corresponding priority window. The interference jitter phenomenon only happens when indirect higher priority flow exists. The paper [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF] has discussed two possible conditions, S D j ∩ S I i = ∅ or S SD j ∩ S I i = ∅, where τ i ∈ S(i) and τ j ∈ S D i , either of which can result in the interference jitter. Any packet release from the higher priority flows which compete the priority level-G i shared resource will finally extend the corresponding priority window W (i). For convenience, we define a higher priority set hp(i), all the flows in S D i , τ i ∈ S(i) are inserted into set hp(i). The maximum interferences produced by these higher priority flows can be computed as follows:

I(i) = τj ∈hp(i) W (i) + J R j + R j -C j T j C j (7)
Combining Eq.( 1), Eq.( 5) and Eq.( 7) , an upper bound of priority level-G i window in case of interference jitter and release jitter is given by:

W (i) = ∀τn∈S(i) W (i) + J R n T n C n + ∀τj ∈hp(i) W (i) + J R j + R j -C j T j C j (8)
The result of W (i) can be solved using the iterative technique [1]. The iteration starts with W (i) 0 = ∀τn∈S(i) C n and terminates when W (i) n no longer increases, it has converged. By this iterative technique, the maximum priority window can be calculated (W

(i) = W (i) n+1 = W (i) n ).

Maximum network latency

Based on the maximum priority window of G i , the next step is how to find the maximum network latency for each flow in S(i). For any observed flow τ i , τ i ∈ S(i), the maximum delay occurs when it is released with all the higher priority flows simultaneously and all the other flows sharing the same priority as τ i start their services just before τ i , this will produce the maximum service requirements on the share resource. So the earliest starting time of τ i is the same as the priority level G i window beginning. To calculate the worst case network latency, we need to find the latest completion time. Due to the multiple blocking and self-blocking problems, if more than one packet instance is released from the same flow during a priority level G i window, then it is necessary to check these instances in order to find the overall worst case network latency of traffic-flow.

Motivated by the observation of the relation between priority window and period, we check the priority window at three different situations:

W (i) ≤ min(T n -J R n ), min(T n - J R n ) < W (i) ≤ T i -J R i and W (i) > T i -J R i
, (τ n is any flow in S(i)) as showed in Figure 6.

Figure 6. Three possible relations between priority window and period

Theorem 2. The maximum network latency R i for τ i is given by:

R i = W (i) + J R i (9) when W (i) ≤ T i -J R i Proof. The interval [0, T i -J R i ] is divided into two subin- tervals [0, min(T n -J R n )] and (min(T n -J R n ), T i -J R i ]. If condition W (i) ≤ min(T n -J R n )
for ∀τ n ∈ S(i) is true, then the priority window ends at or before any repeated release from flow with priority G i . This means that no trafficflow can be blocked by any other flow sharing the same priority more than once. The multiple blocking and self blocking discussed in section 2.2 do not occur. In the worst case, τ i will be the last flow getting transmission opportunity in this priority window. So the ending of the priority window is the completion time of τ i 's packet instance. The maximum network latency R i for τ i is hence given by:

R i = W (i) + J R i (10)
We also find that for ∀τ n ∈ S(i), the relation

W (i)+J R n Tn
= 1 is always true. Eq.( 5) in this situation is simplified as ∀τn∈S(i) C n and the priority window analysis scheme is degraded to the composite analysis presented in [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF]. Actually, the composite model analysis is only a specific case in the priority window analysis when

W (i) ≤ min(T n -J R n ). If min(T n -J R n ) < W (i) ≤ T i -J R
i is true, this implies that only the first packet instance of τ i is served during this window and no self-blocking occurs. But multiple packet instances from any other flow in S(i) may fall into the current window because of ∃τ n ∈ S(i),

W (i)+J R n Tn > 1.
These multiple blockings will delay the completion time of the current packet, but the worst case latency still can be found by checking the priority window. In this case, only one packet instance is released by τ i , hence the existing relation showed by Eq.( 10) is still valid and hence provides the maximum network latency.

From the above discussion, the maximum network latency is calculated by Eq. [START_REF] Goossens | Aethereal network on chip: Concepts, architectures, and implementations[END_REF] when

W (i) ≤ T i -J R i .
If W (i) > T i -J R i , then more than one packet instance of τ i is generated during a priority level-G i window. Some successive generated packets from τ i might be blocked by previous ones. In this situation, the delay from self-blocking also needs to be taken into account.

Theorem 3. The maximum network latency R i for τ i is given by: R i = max q=1,...,

W (i)+J R i T i (w q (i) -(q -1)T i + J R i ) ( 11
)
where q is the index of packet instance, and w i (q) is given

w q (i) = qC i + ∀τn∈S(i),τn =τi w q (i) + J R n T n C n + ∀τj ∈hp(i) w q (i) + R j -C j + J R j T j C j (12)
when

W (i) > T i -J R i .
Proof. The number of packets that could be released from τ i before the end of the priority window is given by:

W (i) + J R i T i (13)
To determine the worst case network latency, we must check all the packet instances during the priority window. The maximum of these values gives the worst case network latency.

Figure 7. Priority Level-G i window with Selfblocking

Figure 7 shows self-blocking during a priority level-G i window. We use the index variable q to denote a packet instance of τ i . The first packet in the window corresponds to q = 1 and the final one is q = W (i)+J R i Ti . Therefore, the time from the first release of τ i until achieving the q th transmission is given as a collection of service requirements from all the flows which compete the priority-G i shared resource. We assume a new time phase w q (i) which denotes the time interval from the beginning of the priority window until the completion of the q th packet transmission. The time phase for the 1 st , the 2 nd and the 3 rd packet in the window are shown in Figure 7 as w 1 (i), w 2 (i) and w 3 (i) respectively. The time phase w q (i) is given by:

w q (i) = qC i + ∀τn∈S(i),τn =τi w q (i) + J R n T n C n + ∀τj ∈hp(i) w q (i) + R j -C j + J R j T j C j (14)
The variable qC i accounts for the transmission service time of the first q packet instances of τ i during the priority window. The final part of the right hand side of this equation includes all the service requirements from priority level G i or higher flows which fall in this time windows w q (i). The value of w q (i) can be found by the similar iteration policy while starting with w q (i) 0 = C i + qT i and ending when w q (i) n+1 = w q (i) n . The generation time of the q th packet happens at instant (q -1)T i relative to the start of priority window so the network latency of the q th instance is given by: R i (q) = w q (i)

-(q -1)T i + J R i ( 15
)
The maximum network latency can occur at any one of these packet releases during the priority window. We will consecutively analyze each release until τ i stops blocking itself; which means the packet transmission service finishes within the same period as it is released, W (i) ≤ qT i -J R i . Thus maximum network latency is given by: R i = max q=1,...,

W (i)+J R i T i (w q (i) -(q -1)T i + J R i ) (16)
Finally, flow τ i is schedulable, if and only if R i ≤ D i .

A case example

Revisiting the example given in Figure 2. The interrelations between these traffic-flows have been examined in section 3.2. The attributes of the traffic-flows are showed in Table 1. The time units are not necessary in this analysis as long as all the traffic-flows use the same base. The recurrence stops at W (1) = 8 which is less than min(T n -J R n ) for ∀τ n ∈ S(1). So R 1 =R 2 =R 3 = W (1) =8 less than D.

Flows τ 4 and τ 5 share the priority level G 2 . The maximum window for G 2 not only considers the blocking but also the interference from higher priority flow. In this case, τ 2 and τ 3 contend for the priority level G 2 shared resources and hence contribute direct interference. Besides that, the activity of indirect higher priority flow τ 1 also can introduce some extra interference which is treated as interference jitter. So the window for G 2 is given by:

W (2) = W (2) T2 C 2 + W (2)+R3-C3 T3 C 3 + W (2) T4 C 4 + W (2) T5 C 5
which iteratively results in W (2) = 22.

For τ 5 , W (2) < T 5 , so only one instance is released during this window. According to Theorem 2, R 5 = W (2) = 22.

For τ 4 , since W (2) T4 = 3, there are three packet instances released during the priority window. We need check all these instances to determine the worst case network latency. Utilizing Theorem 3, the window phases for the first packet, first two packets and the first three packets are w 1 (2), w 2 (2) and w 3 (2) respectively. Using Eq.( 14) and Eq.( 15), we get: The maximum network latency is thus max(R 4 (1), R 4 (2), R 4 (3)) = 11. All the flows meet their deadlines and the set is schedulable.

Conclusion

The new on-chip communication architectures need to provide different levels of service for various components on the same network. Wormhole switching with fixed priority preemption has been proposed as a possible solution for realtime on-chip communication. Utilizing a priority share policy, the resource overhead can be reduced effectively. However, in order to simplify the analysis process, an existing technique imposes a deadline no more than period restriction which will bring inflexibility to network exploration and design. In this paper, we relax this constraint and present a novel analysis approach to cover all possible situations. Utilizing this new analysis scheme, we can flexibly evaluate at design time the schedulability of traffic-flow sets with different QoS requirements in a real-time communication platform.

Figure 3 .

 3 Figure 3. The Blocking Problem

3. 1

 1 Traffic-flow model A wormhole switching real-time network Γ comprises n real-time traffic-flows Γ ={τ 1 , τ 2 , . . . τ n }. Each trafficflow τ i has a set of properties and timing requirements which are characterized by six-tuple attributes

1 = 1 = {τ 2 }, S SD 2 = {τ 3 }, S SI 2 = {τ 1 }, S SD 3 =SI 3 = 4 = 5 =

 11223213345 {τ 3 }, S SI {τ 1 , τ 2 } and S ∅. Flow τ 4 directly competes with higher priority flows τ 2 and τ 3 and indirect suffers interference from τ 1 , S D 4 = {τ 2 , τ 3 }, S I 4 = {τ 1 }. Flow τ 5 does not have any higher priority flow, so S D 5 =, S I 5 = ∅. Besides that, τ 4 and τ 5 share the same priority level, thus S SD {τ 5 }, S SI 4 = ∅, S SD {τ 4 } and S SI 5 = ∅.

Figure 5 .

 5 Figure 5. Priority Level-G 2 Window

  In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 inria-00441970, version 1 -17 Dec 2009

RealFlows τ 1 , 3

 13 τ 2 and τ 3 share the same priority G 1 . Utilizing priority window analysis, first we calculate the W (1) according to Eq.(2):Utilizing the iterative technique,W (1) 0 = 2 + 2 + 4 = 8 W (1)1 = 8 8 2 + 8 11 2 + 8 13 4 = 2 + 2 + 4 = 8 In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 inria-00441970, version 1 -17 Dec 2009

w 1 ( 2 )

 12 = 10 and R 4 (1) = 10 -0 = 10 w 2 (2) = 19 and R 4 (2) = 19 -8 = 11 w 3 (2) = 22 and R 4 (3) = 22 -8 * 2 = 6

  In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

  In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

inria-00441970, version 1 -17 Dec 2009

by: