B Cheon

E Lee

L.-T Wang

X Wen

P Hsu

J Cho

J Park

H Chao

S Wu

At-Speed Logic BIST for IP Cores

This paper describes a logic BIST scheme that features high fault coverage achieved by fault-simulation guided test point insertion, real at-speed test capability for multi-clock designs without clock frequency manipulation, and easy physical implementation due to the use of a low-speed SE signal. Application results

of this scheme to two widely used IP cores are also reported.

Introduction

Built-In Self-Test for logic circuits or logic BIST implements most of ATE functions on chip, and is especially beneficial for IP cores. Making an IP core a BISTed IP core has the following advantages: Simple Test Interface: Pure logic BIST only needs a start signal to start self-test, a finish signal to indicate its end, and a status signal to show its result. Other test control data is usually small enough to be provided through Boundary-Scan. This completely solves the test access problem when testing an with many embedded cores. Better Test Quality: Logic BIST can easily apply a large number of test patterns. As a result, more defects, either modeled or un-modeled, can be detected. N-detection is also naturally done. In addition, logic BIST makes it easy to conduct at-speed testing for timing-related defects. Lower Test Cost: Logic BIST has most of ATE in a chip, so test costs are reduced by less test time, less tester memory requirement, or cheaper tester investment. Higher Reliability: A BISTed IP core can be tested easily after being integrated into a system. Periodic core testing, even with test of relatively low fault coverage, can greatly improve the reliability of the whole system.

Most of logic BIST schemes are based on the STUMPS structure, which applies random patterns generated by a PWG to a fbll-scan circuit in parallel and compresses the responses into a signature with a MISR. Despite the conceptual simplicity, most of previous logic BIST schemes suffer the following problems: (1) Test Frequency Manipulation: Some logic BIST schemes require all test frequencies satisfy a strict test-oriented relation, which is totally different functional mode. Not only such a test clocking system is physically to implement but also it fails to realize real at-speed testing; (2) Performance Concern:Control points inserted for improving fault coverage add delay to functional paths, thus adversely affecting core performance; (3) Implementation Some logic BIST schemes require some test signals, especially the scan enable (SE) signal, to be implemented as high-speed signals that require clock tree synthesis for strict skew management. All these problems limit the use of previous logic BIST scheme in core testing.

Proposed Logic BIST Scheme

General Structure

This paper addresses the above problems with a flexible logic BIST scheme as shown in Fig. 1. It has a TPG block for test pattern generation, an input selector for providing random patterns or top-up ATPG patterns for the under-test, a BIST-ready core, an ODC block for output data compression, a clock gating block for generating test clocks from original clocks, and a controller for managing the whole BIST operation [13. Self-test is started by Start, its end is indicated by Finish, and its result is shown by Result. There is also a standard Boundary-Scan interface, which can be used for loading initial test data or for downloading internal states for fault diagnosis. The BIST-ready core is a fbll-scan circuit with unknown value sources properly blocked. In order to directly improve final fault coverage, some observation points are inserted based on the results of fault simulation, instead of observability calculation commonly used in previous logic BIST schemes. In addition, no control point is used in order to meet strict performance requirements for IP cores.

Note that the BIST-ready core has two inter-related clock domains, whose clock skews are usually not aggressively managed. In order to avoid additional design efforts for clock skew management in logic BIST, we use two MISR pairs, one for each clock domain, even though they may have the same frequency. In addition, PSI and are phase shifters for breaking inter-dependency in raw 1 data streams from PRPGs. Furthermore, space expanders, and and space compactors, and are used to reduce the lengths of PRPGs and MISRs.

At-Speed Test Timing Control

This paper proposes a new at-speed test timing control method based on the double-capture scheme. An example is shown in Fig. 2, where test clocks and are generated by the clock gating block shown in Fig. 1.

Shift Window

Capture Window Shift Window Fig.

At-speed test timing control.

In a capture window, two capture pulses are generated for each clock The last shift pulse and the first capture pulse are used to create transitions at the outputs of some scan and the responses to the transitions are caught by the second capturepulse, where and are set based on functional clock frequencies. Thus, real at-speed testing is guaranteed since no test clock frequency manipulation is conducted. In addition, and can be as long as desired, making it possible to use a single and slow scan enable signal for all clock domains. This significantly eases physical design for logic BIST.

Physical Implementation

In addition to a single and slow SE signal, other techniques are also used to ease physical implementation. This is illustrated in Fig. 3, which only shows two scan chains in Clock Domain and Clock Domain #2. In a shift window, a PRPG, a scan chain, and a MISR should operate properly as one shift register. Since the PRPG and the MISR are in a clock domain that is different from the one for the scan chain, timing violations may occur between the PRPG and the scan chain as well as between the scan chain and the MISR. To facilitate physical design, we propose a technique that always makes the clock driving the PRPG and the MISR to be ahead of the clock driving the scan chain in phase. This way, only hold-time violations may occur from the PRPG to the scan chain, while only setup-time violations may occur from the scan chain to the MISR. In this case, the hold-time violations can be corrected with re-timing while the setup-time violations can be avoided by reducing logic levels from the scan chain to the MISR. This will significantly ease physical design.

In a capture window, as shown in Fig. 2, can be easily adjusted to be larger than the maximal clock skew between the two clock domains. This way, the capture operation can be correctly conducted without adding any holding that increase delay on functional paths.

Experimental Results

The flexible logic BIST scheme has been applied to two commercial CPU IP cores. The results are shown in Table 1. The following techniaues were also used in the applications:

One pair was used for each clock domain since there may be cross-clock-domain logic between any two clock domains. (2) Scan cells were inserted for all and to increase delay fault coverage. (3) No space compactor was used between scan outputs and a MISR in order to avoid setup-time violations. This is why there were long MISRs, 99-bit for Core X and 80-bit for Core Y. Such a MISR is generally related to the main and large clock domain which has a larger number of scan chains.

Conclusions

This paper has described a flexible and pure logic BIST scheme, in which real at-speed testing is realized with easy physical implementation. application of this scheme to two popular IP cores has also been reported.

  Fig.General LBIST structure.

  Fig.Clock skew issues.

  -Capture DFT System for Detecting or Locating Crossing Clock-Domain Faults During Self-Test or Scan-Test," US Patent Application,

Table Experimental Results Gate Count of of Scan Chains Max. Chain Length of Clock Domains Frequency of PRPGs PRPG Length of MISR Length of Test Points of Random Patterns Fault Coverage 1 CPU Time Overhead of Top-Up Patterns Fault Coverage 2

 Experimental

	core x	core Y
		345
	2	8
	2	8
	19	19
	2	8
		7: 19 1: 80
	20K	20K
	93.82%	93.22%
	4.4%	3.2%
	135	528
	97.12%	97.58%

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


Viacheslav Izosimov

Paul Pop

Petru Eles

Zebo Peng

In this paper we present an approach to the design optimization of faulttolerant embedded systems for safety-critical applications. Processes are statically scheduled and communications are performed using the timetriggered protocol. We use process re-execution and replication for tolerating transient faults. Our design optimization approach decides the mapping of processes to processors and the assignment of fault-tolerant policies to processes such that transient faults are tolerated and the timing constraints of the application are satisfied. We present several heuristics which are able to find fault-tolerant implementations given a limited amount of resources. The developed algorithms are evaluated using extensive experiments, including a real-life example.

Introduction

Safety-critical applications have to function correctly and meet their timing constraints even in the presence of faults. Such faults can be permanent (i.e., damaged microcontrollers or communication links), transient (e.g., caused by electromagnetic interference), or intermittent (appear and disappear repeatedly). The transient faults are the most common, and their number is continuously increasing due to the continuously raising level of integration in semiconductors.

Researchers have proposed several hardware architecture solutions, such as MARS [START_REF] Kopetz | Distributed Fault-Tolerant Real-Time Systems: The Mars Approach[END_REF], TTA [START_REF] Kopetz | The Time-Triggered Architecture[END_REF] and XBW [START_REF] Claeson | The XBW Model for Dependable Real-Time Systems[END_REF], that rely on hardware replication to tolerate a single permanent fault in any of the components of a fault-tolerant unit. Such approaches, can be used for tolerating transient faults as well, but they incur very large hardware cost. An alternative to such purely hardware-based solutions are approaches such as re-execution, replication, checkpointing.

Pre-emptive on-line scheduling environments are flexible enough to handle such fault-tolerance policies. Several researchers have shown how the schedulability of an application can be guaranteed at the same time with appropriate levels of fault-tolerance [START_REF] Bertossi | Scheduling Algorithms for Fault-Tolerance in Hard-Real Time Systems[END_REF][START_REF] Burns | Feasibility Analysis for Fault-Tolerant Real-Time Task Sets[END_REF][START_REF] Han | A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults[END_REF][START_REF] Zhang | Energy-Aware Adaptive Checkpointing in Embedded Real-Time Systems[END_REF]. However, such approaches lack the predictability required in many safety-critical applications, where static off-line scheduling is the only option for ensuring both the predictability of worst-case behavior, and high resource utilization [START_REF] Kopetz | Real-Time Systems-Design Principles for Distributed Embedded Applications[END_REF].

The disadvantage of static scheduling approaches, however, is their lack of flexibility, which makes it difficult to integrate tolerance towards unpredictable fault occurrences. Thus, researchers have proposed approaches for integrating fault-tolerance into the framework of static scheduling. A simple heuristic for combining together several static schedules in order to mask fault-patterns through replication is proposed in [START_REF] Dima | Off-line Real-Time Fault-Tolerant Scheduling[END_REF], without considering the timing constraints of the application. This approach is used as the basis for cost and fault-tolerance trade-offs within the Metropolis environment [START_REF] Pinello | Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications[END_REF]. Graph transformations are used in [START_REF] Chevochot | Scheduling Fault-Tolerant Distributed Hard-Real Time Tasks Independently of the Replication Strategies[END_REF] in order to introduce replication mechanisms into an application. Such a graph transformation approach, however, does not work for re-execution, which has to be considered during the construction of the static schedules.

Fohler [START_REF] Fohler | Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems[END_REF] proposes a method for joint handling of aperiodic and periodic processes by inserting slack for aperiodic processes in the static schedule, such that the timing constraints of the periodic processes are guaranteed. In [START_REF] Fohler | Adaptive Fault-Tolerance with Statically Scheduled Real-Time Systems[END_REF] he equates the aperiodic processes with fault-tolerance techniques that have to be invoked on-line in the schedule table slack to handle faults. Overheads due to several fault-tolerance techniques, including replication, re-execution and recovery blocks, are evaluated.

When re-execution is used in a distributed system, Kandasamy [START_REF] Kandasamy | Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems[END_REF] proposes a list-scheduling technique for building a static schedule that can mask the occurrence of faults, thus making the re-execution transparent. Slacks are inserted into the schedule in order to allow the re-execution of processes in case of faults. The faulty process is re-executed, and the processor switches to a contingency schedule that delays the processes on the corresponding processor, making use of the slack introduced. The authors propose an algorithm for reducing the necessary slack for re-execution. This algorithm has later been applied to the fault-tolerant transmission of messages on a time-division multiple-access bus (TDMA) [START_REF] Kandasamy | Dependable Communication Synthesis for Distributed Embedded Systems[END_REF].

Applying such fault-tolerance techniques introduces overheads in the schedule and thus can lead to unschedulable systems. Very few researchers [START_REF] Kandasamy | Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems[END_REF][START_REF] Pinello | Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications[END_REF] consider the optimization of implementations to reduce the overheads due to fault-tolerance and, even if optimization is considered, it is very limited and does not include the concurrent usage of several fault-tolerance techniques. Moreover, the application of fault-tolerance techniques is considered in isolation, and thus is not reflected at all levels of the design process, including mapping, scheduling and bus access optimization. In addition, the communication aspects are not considered or very much simplified.

In this paper, we consider hard real-time safety-critical applications mapped on distributed embedded systems. Both the processes and the messages are scheduled using static cyclic scheduling. The communication is performed using a communication environment based on the time-triggered protocol [START_REF] Kopetz | Distributed Fault-Tolerant Real-Time Systems: The Mars Approach[END_REF]. We consider two distinct fault-tolerance techniques: re-execution of processes, which provides time-redundancy, and active replication, which provides space-redundancy. We show how re-execution and active replication can be combined in an optimized implementation that leads to a schedulable fault-tolerant application without increasing the amount of employed resources. We propose several optimization algorithms for the mapping of processes to processors and the assignment of fault-tolerance techniques to processes such that the application is schedulable and no additional hardware resources are necessary.

The next two sections present the system architecture and the application model, respectively. Section 4 introduces the design optimization problems tackled, and Section 5 proposes a tabu-search based algorithm for solving these problems. The evaluation of the proposed approaches, including a reallife example consisting of a cruise controller are presented in Section 6. The last section presents our conclusions.

System Architecture

Hardware Architecture and Fault Model

We consider architectures composed of a set N nodes which share a broadcast communication channel. Every node N i ∈ N consists, among others, of a communication controller and a CPU. Figure 1a depicts an architecture consisting of four nodes. The communication controllers implement the protocol services and run independently of the node's CPU. We consider the time-triggered protocol (TTP) [START_REF] Kopetz | Distributed Fault-Tolerant Real-Time Systems: The Mars Approach[END_REF] as the communication infrastructure for a distributed real-time system. However, the research presented is also valid for any other TDMA-based bus protocol that schedules the messages statically based on a schedule table like, for example, the SAFEbus [START_REF] Hoyme | SAFEbus[END_REF] protocol used in the avionics industry.

The TTP has a replicated bus that integrates all the services necessary for fault-tolerant real-time systems. According to the TTP, each node N i can transmit only during a predetermined time interval, the so called TDMA slot S i , see Figure 1b. In such a slot, a node can send several messages packed in a frame. A sequence of slots corresponding to all the nodes in the TTC is called a TDMA round. A node can have only one slot in a TDMA round. Several TDMA rounds can be combined together in a cycle that is repeated periodically. The TDMA access scheme is imposed by a message descriptor list (MEDL) that is located in every TTP controller. The MEDL serves as a schedule table for the TTP controller which has to know when to send/receive a frame to/from the communication channel.

In this paper we are interested in fault-tolerance techniques for tolerating transient faults, which are the most common faults in today's embedded systems. We have generalized the fault-model from [START_REF] Kandasamy | Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems[END_REF] that assumes that one single transient fault may occur on any of the nodes in the system during the application execution. In our model, we consider that at most k transient faults 1 may occur anywhere in the system during one operation cycle of the application. Thus, not only several transient faults may occur simultaneously on several processors, but also several faults may occur on the same processor. We consider that the transient faults can have a worstcase duration of µ, from the moment the fault is detected until the system is back to its normal operation, and that a fault is confined to a single process and does not affect other processes.

Software Architecture and Fault-Tolerance Techniques

We have designed a software architecture which runs on the CPU in each node, and which has a real-time kernel as its main component. The processes are activated based on the local schedule tables, and messages are transmitted according to the MEDL. For more details about the software architecture and the message passing mechanism the reader is referred to [START_REF] Eles | Scheduling with Bus Access Optimization for Distributed Embedded Systems[END_REF].

The error detection and fault-tolerance mechanisms are part of the software architecture. We assume a combination of hardware-based (e.g., watchdogs, signature checking) and software-based error detection methods, systematically applicable without any knowledge of the application (i.e., no reasonableness and range checks) [START_REF] Claeson | The XBW Model for Dependable Real-Time Systems[END_REF]. We also assume that all faults can be found using such detection methods, i.e., no byzantine faults which need voting on the output of replicas for detection. The software architecture, including the real-time kernel, error detection and fault-tolerance mechanisms are themselves fault-tolerant.

We use two mechanisms for tolerating faults: re-execution and active replication. Let us consider the example in Figure 2, where we have process P 1 and a fault-scenario consisting of k = 2 faults with a duration µ = 10 ms that can happen during one cycle of operation. In Figure 2a we have the worstcase fault scenario for re-execution, when the first fault happens at the end of the process P 1 's execution. The fault is detected and, after an interval µ, P 1 can be re-executed. Its second execution is labeled with P 1/2 , which, in the worst-case could also experience a fault at the end. Finally, the third re-execution of P 1 , namely P 1/3 , will execute without error. In the case of active rep-lication, depicted in Figure 2b, each replica is executed on a different processor. Three replicas are needed to tolerate the two possible faults and, in the worst-case scenario depicted in Figure 2b, only the execution of P 1/3 is successful. In addition, we consider a third case, presented in Figure 2c, which combines re-execution and replication for tolerating faults in a process. In this case, for tolerating the two faults we use two replicas and one reexecution: the process P 1/1 , which has P 1/2 as a replica, is re-executed.

With active replication, the input has to be distributed to all the replicas. Since we do not consider the type of faults that need replica agreement, our execution model assumes that the descendants of replicas can start as soon as they have received the first valid message from a replica. Replica determinism is achieved as a by-product of the underlying TTP architecture [START_REF] Poldena | Fault Tolerant Systems-The Problem of Replica Determinism[END_REF].

Application Model

We model an application A as a set of directed, acyclic, polar graphs G(V, E) ∈ A. Each node P i ∈ V represents one process. An edge e ij ∈ E from P i to P j indicates that the output of P i is the input of P j . A process can be activated after all its inputs have arrived and it issues its outputs when it terminates. The communication time between processes mapped on the same processor is considered to be part of the process worst-case execution time and is not modeled explicitly. Communication between processes mapped to different processors is performed by message passing over the bus. Such message passing is modeled as a communication process inserted on the arc connecting the sender and the receiver process.

The combination of fault-tolerance policies to be applied to each process is given by two functions. F R : V → V R determines which processes are replicated. When active replication is used for a process P i , we introduce several replicas into the process graph G, and connect them to the predecessors and successors of P i .. The second function F X : V ∪ V R → V X applies re-execution to the processes in the application, including to the replicas in V R , if necessary, see Figure 2c. Let us denote the tuple <F R , F X > with F .

The mapping of a process graph G is given by a function M: V ∪ V R → N, where N is the set of nodes in the architecture. For a process P i ∈ V ∪ V R , M(P i ) is the node to which P i is assigned for execution. Each process P i can potentially be mapped on several nodes. Let N P i ⊆ N be the set of nodes to which P i can potentially be mapped. We consider that for each N k ∈ N P i , we know the worst-case execution time C P i N k of process P i , when executed on N k . We also consider that the size of the messages is given.

All processes and messages belonging to a process graph G i have the same period T i = T G i which is the period of the process graph. A deadline D G i ≤ T G i is imposed on each process graph G i . In addition, processes can have associated individual release times and deadlines. If communicating processes are of different periods, they are combined into a hyper-graph capturing all process activations for the hyper-period (LCM of all periods).

Design Optimization Problems

In this paper, by policy assignment we denote the decision whether a certain process should be re-executed or replicated. Mapping a process means placing it on a particular node in the architecture.

1. The number of faults k can be larger than the number of processors in the system. There could be cases where the policy assignment decision is taken based on the experience and preferences of the designer, considering aspects like the functionality implemented by the process, the required level of reliability, hardness of the constraints, legacy constraints, etc. We denote with P R the subset of processes which the designer has assigned replication, while P X contains processes which are to be re-executed.

P 1/3 P 1/1 P 1/2 P 1/3 P 1/1 P 1/2 P 1/3 a) Re-execution b) Replication k = 2 µ= 10 ms C 1 = 30 ms P 1 N 1 N 1 N 2 N 3 P 1/1 P 1/2 c) Re-executed replicas N 1 N 2
Most processes, however, do not exhibit certain particular features or requirements which obviously lead to re-execution or replication. Let P be the set of processes in the application A. The subset P + = P \ (P X ∪ P R ) of processes could use any of the two techniques for tolerating faults. Decisions concerning the policy assignment to this set of processes can lead to various trade-offs concerning, for example, the schedulability properties of the system, the amount of communication exchanged, the size of the schedule tables, etc.

For part of the processes in the application, the designer might have already decided their mapping. For example, certain processes, due to constraints like having to be close to sensors/actuators, have to be physically located in a particular hardware unit. They represent the set P M of already mapped processes. Consequently, we denote with P * = P \ P M the processes for which the mapping has not yet been decided.

Our problem formulation is as follows: • As an input we have an application A given as a set of process graphs (Section 3) and a system with a set of nodes N connected using the TTP. • The fault model is given by the parameters k and µ, which denote the total number of transient faults that can appear in the system during one cycle of execution and their duration, respectively. • As introduced previously, P X and P R are the sets of processes for which the fault-tolerance policy has already been decided. Also, P M denotes the set of already mapped processes. We are interested to find a system configuration ψ such that the k transient faults are tolerated and the imposed deadlines are guaranteed to be satisfied, within the constraints of the given architecture N.

Determining a system configuration ψ = <F, M, S> means: 1. finding a combination of fault-tolerance policies F for each processes in P + = P \ (P R ∪ P X ); 2. deciding on a mapping M for each processes in P * = P \ P M ; 3. deriving the set S of tables for each processor and the MEDL for TTP.

Fault-Tolerance Policy Assignment

Let us illustrate some of the issues related to policy assignment. In the example presented in Figure 3 we have the application A 1 with three processes, P 1 to P 3 , and an architecture with two nodes, N 1 and N 2 . The worst-case execution times on each node are given in a table to the right of the architecture. Note that N 1 is faster than N 2 . The fault model assumes a single fault, thus k = 1, with a duration µ = 10 ms. The application A 1 has a deadline of 160 ms depicted with a thick vertical line. We have to decide which fault-tolerance technique to use. In Figure 3 we depict the schedules 1 for each node, and for the TTP bus. Node N 1 is allowed to transmit in slot S 1 , while node N 2 can use slot S 2 . A TDMA round is formed of slot S 1 followed by slot S 2 , each of 10 ms length. Comparing the schedules in Figure 3a 1 and 3b 1 , we can observe that using (a 1 ) active replication the deadline is missed. In order to guarantee that time constraints are satisfied in the presence of faults, re-execution slacks have to finish before the deadline. However, using (b 1 ) re-execution we are able to meet the deadline. However, if we consider application A 2 with process P 3 data dependent on P 2 , the deadline is missed in Figure 3b 2 if re-execution is used, and it is met when replication is used as in Figure 3a 2 .

Note that in Figure 3b 1 processes P 1 and P 2 can use the same slack for re-execution. Similarly, in Figure 3b 2 , one single slack of size C 3 + µ is enough to tolerate one fault in any of the processes. In general, re-execution slacks can be shared as long as they allow a re-execution of processes to tolerate faults.

This example shows that the particular technique to use, has to be carefully adapted to the characteristics of the application. Moreover, the best result is most likely to be obtained when both techniques are used together, some processes being re-executed, while others replicated. Let us consider the example in Figure 4, where we have an application with four processes mapped on an architecture of two nodes. In Figure 4a all processes are reexecuted, and the depicted schedule is optimal for re-execution.

We use a particular type of re-execution, called transparent re-execution [START_REF] Kandasamy | Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems[END_REF], that hides fault occurrences on a processor from other processors. On a processor N i where a fault occurs, the scheduler has to switch to a contingency schedule that delays descendants of the faulty process. However, a fault happening on another processor, is not visible on N i , even if the descendants of the faulty process are mapped on N i . For example, in order to isolate node N 1 from the occurrence of a fault in P 1 on node N 2 , message m 2 from P 1 to P 3 cannot be transmitted at the end of P 1 's execution. Message m 2 has to arrive at the destination even in the case of a fault occurring in P 1 , so that P 3 can be activated on node N 2 at a fixed start time, regardless of what happens on node N 1 , i.e., transparently. Consequently, m 2 can only be transmitted after a time C 1 + µ passes, at the end of the potential re-execution of P 1 , depicted in grey. Message m 2 is delivered in the slot S 2 of the TDMA round corresponding to node N 2 . With this setting, using re-execution will miss the deadline. Once a fault happens, the scheduler in N 2 will have to switch to a contingency schedule, depicted with thick-border rectangles.

However, combining re-execution with replication, as in Figure 4b where process P 1 is replicated, will meet the deadline. In this case, message m 2 does not have to be delayed to mask the failure of process P 1 . Instead, P 2 and P 3 will have to receive m 1 and m 2 , respectively, from both replicas of P 1 , which will introduce a delay due to the inter-processor communication on the bus.

Mapping and Bus Access Optimization

For a distributed system, the communication infrastructure has an important impact on the mapping decisions [START_REF] Pop | Design Optimization of Multi-Cluster Embedded Systems for Real-Time Applications[END_REF]. Not only is the mapping influenced by the protocol setup, but the fault-tolerance policy assignment cannot be done separately from the mapping design task. Consider the example in Figure 5. Let us suppose that we have applied a mapping algorithm without considering the fault-tolerance aspects, and we have obtained the best possible mapping, depicted in Figure 5a. If we apply on top of this mapping a fault-tolerance technique, for example, re-execution as in Figure 5b, we miss the deadline. The re-execution has to be considered during the mapping process, and then the best mapping will be the one in Figure 5c which clusters all processes on the same processor in order to reduce the re-execution slack and the delays due to the masking of faults.

In this paper, we will consider the assignment of fault-tolerance policies at the same time with the mapping of processes to processors. However, to simplify the presentation we will not discuss the optimization of the communication channel. Such an optimization can be performed with the techniques we have proposed in [START_REF] Pop | Schedulability Analysis and Optimization for the Synthesis of Multi-Cluster Distributed Embedded Systems[END_REF] for non fault-tolerant systems.

Design Optimization Strategy

The design problem formulated in the previous section is NP complete. Our strategy is outlined in Figure 6 and has three steps: 1. In the first step (lines 1-3) we decide very quickly on an initial bus access configuration B 0 , and an initial fault-tolerance policy assignment F 0 and mapping M 0 . The initial bus access configuration (line 1) is determined by assigning nodes to the slots (S i = N i ) and fixing the slot length to the minimal allowed value, which is equal to the length of the largest message in the application. The initial mapping and faulttolerance policy assignment algorithm (InitialMPA line 2 in Figure 6) assigns a re-execution policy to each process in P + and produces a mapping for the processes in P * that tries to balance the utilization among nodes and buses. The application is then scheduled using the ListScheduling algorithm outlined in Section 5.1. If the application is schedulable the optimization strategy stops. 2. The second step consists of a greedy heuristic GreedyMPA (line 4), discussed in Section 5.2, that aims to improve the fault-tolerance policy assignment and mapping obtained in the first step. 3. If the application is still not schedulable, we use, in the third step, a tabu search-based algorithm TabuSearchMPA presented in Section 5.2. Finally, the bus access optimization is performed.

If after these three steps the application is unschedulable, we conclude that no satisfactory implementation could be found with the available amount of resources.

List Scheduling

Once a fault-tolerance policy and a mapping are decided, as well as a communication configuration is fixed, the processes and messages have to be scheduled. We use a list scheduling algorithm for building the schedule tables for the processes and deriving the MEDL for messages.

Before applying list scheduling, we merge the application graphs into one single merged graph Γ, as detailed in [START_REF] Pop | Analysis and Synthesis of Communication-Intensive Heterogeneous Real-Time Systems[END_REF], with a period equal to the LCM of all constituent graphs. List scheduling heuristics are based on priority lists from which processes are extracted in order to be scheduled at certain moments. A process P i is placed in the ready list L if all its predecessors have been already scheduled. All ready processes from the list L are investigated, and that process P i is selected for placement in the schedule which has the highest priority. We use the modified partial critical path priority function presented in [START_REF] Eles | Scheduling with Bus Access Optimization for Distributed Embedded Systems[END_REF]. At the same time with placing processes in the schedule, the messages are also scheduled using the ScheduleMessage function from [START_REF] Eles | Scheduling with Bus Access Optimization for Distributed Embedded Systems[END_REF]. The ListScheduling loops until the ready list L is empty.

During scheduling, re-execution slack is introduced in the schedule for the re-executed processes. The introduction of re-execution slack is discussed in [START_REF] Kandasamy | Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems[END_REF] where the total amount of slack is reduced through slacksharing, as depicted in Figure 3b 2 , where processes P 1 to P 3 can share the same slack for re-execution in the case of a fault.

However, the notion of "ready process" in [START_REF] Kandasamy | Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems[END_REF] is different for us in the case of processes waiting inputs from replicas. In that case, a process can be placed in the schedule as soon as we are certain that at least one valid message has arrived from a replica. Let us consider the example in Figure 7, where P 2 is replicated. In the worst-case fault-scenario, P 2 on processor N 1 can fail, and thus P 3 has to receive message m 2 from the P 2 replica on processor N 2 . Thus, P 3 has to be placed in the schedule as in Figure 7a. However, our scheduling algorithm will place P 3 as in Figure 7b instead, immediately following P 2 on N 1 . In addition, it will create a contingency schedule for P 3 on processor N 1 , as depicted in Figure 7b using a rectangle with a thicker margin. The scheduler on N 1 will switch to this schedule only in the case of an error occurring in P 2 on processor N 1 . This contingency schedule has two properties. First, P 3 starts such that the arrival of m 2 from the P 2 's replica on N 2 is guaranteed. Up to this point, it looks similar to the case in Figure 7a, where P 3 has been started at this time from the beginning. However, the contingency schedule has another important property: although P 3 's failure is handled through re-execution, the contingency schedule will not contain any re-execution slack for P 3 . That is because, according to the fault model, no more errors can happen. Thus, the deadline is met, even if any of the processes will experience a fault.

Mapping and Fault-Policy Assignment

For deciding the mapping and fault-policy assignment we use two steps, see Figure 6. One is based on a greedy heuristic, GreedyMPA. If this step fails, we use in the next step a tabu search approach, TabuSearchMPA. Both approaches investigate in each iteration all the processes on the critical path of the merged application graph Γ, and use design transformations (moves) to change a design such that the critical path is reduced. Let us consider the example in Figure 8, where we have an application of four processes that has to tolerate one fault, mapped on an architecture of two nodes. Let us assume that the current solution is the one depicted in Figure 8a. In order to generate neighboring solutions, we perform design transformations that change the mapping of a process, and/or its fault-tolerance policy. Thus, the neighbor solutions generated starting from Figure 8a, are the solutions presented in Figure 8b-8e. Out of these, the solution is Figure 8c is the best in terms of schedule length.

The greedy approach selects in each iteration the best move found and applies it to modify the design. The disadvantage of the greedy approach is that it can "get stuck" into a local optima. To avoid this, we have implemented a tabu search algorithm, presented in Figure 9.

The tabu search takes as an input the merged application graph Γ, the architecture N and the current implementation ψ, and produces a schedulable and fault-tolerant implementation x best . The tabu search is based on a neighborhood search technique, and thus in each iteration it generates the set of moves N now that can be reached from the current solution x now (line 7 in Figure 9). In our implementation, we only consider changing the mapping or fault-tolerance policy of the processes on the critical path, denoted with CP in Figure 9. We define the critical path as the path through the merged graph Γ which corresponds to the longest delay in the schedule table. For example, in Figure 8a, the critical path is formed from P 1 , m 2 and P 3 . Step 1:

B 0 = InitialBusAccess(A, N) 2 ψ 0 = InitialMPA(A, N, B 0 ) 3 if S 0 is schedulable then stop end if 4
Step 2: ψ= GreedyMPA(A, N, ψ 0 ) 5 if S is schedulable then stop end if 6

Step 3: ψ = TabuSearchMPA(A, N, ψ) 7 return ψ end OptimizationStrategy

P 2 S 1 S 2 S 2 m 1 S 1 m 2 a) Deadline Missed Met N 1 N 2 N 1 N 2
The key feature of a tabu search is that the neighborhood solutions are modified based on a selective history of the states encountered during the search. The selective history is implemented in our case through the use of two tables, Tabu and Wait. Each process has an entry in this tables. If Tabu(P i ) is non-zero, it means that the process is "tabu", i.e., should not be selected for generating moves, while if Wait(P i ) is greater than the number of processes in the graph, |Γ|, the process has waited a long time and should be selected for diversification. Thus, lines 9 and 10 of the algorithm, a move will be removed from the neighborhood solutions if it is tabu. However, tabu moves are also accepted if they are better than the best-so-far solution (line 10). In line 12 the search is diversified with moves which have waited a long time without being selected.

In lines 14-20 we select the best one out of these solutions. We prefer a solution that is better than the best-so-far x best (line 17). If such a solution does not exist, then we choose to diversify. If there are no diversification moves, we simply choose the best solution found in this iteration, even if it is not better than x best . Finally, the algorithm updates the best-so-far solution, and the selective history tables Tabu and Wait. The algorithm ends when a schedulable solutions has been found, or an imposed time-limit has been reached.

Figure 8 illustrates how the algorithm works. Let us consider that the current solution x now is the one presented in Figure 8a, with the corresponding selective history presented to its right, and the best-so-far solution x best is the one in Figure 4a. The generated solutions are presented in Figure 8b-8e. The solution (b) is removed from the set of considered solutions because it is tabu, and it is not better than x best . Thus, solutions (c)-(e) are evaluated in the current iteration. Out of these, the solution in Figure 8c is selected, because although it is tabu, it is better than x best . The table is updated as depicted to the right of Figure 8c in bold, and the iterations continue with solution (c) as the current solution.

Experimental Results

For the evaluation of our algorithms we used applications of 20, 40, 60, 80, and 100 processes (all unmapped and with no fault-tolerance policy assigned) implemented on architectures consisting of 2, 3, 4, 5, and 6 nodes, respectively. We have varied the number of faults depending on the architecture size, considering 3, 4, 5, 6, and 7 faults for each architecture dimension, respectively. The duration µ of a fault has been set to 5 ms. Fifteen examples were randomly generated for each application dimension, thus a total of 75 applications were used for experimental evaluation. We generated both graphs with random structure and graphs based on more regular structures like trees and groups of chains. Execution times and message lengths were assigned randomly using both uniform and exponential distribution within the 10 to 100 ms, and 1 to 4 bytes ranges, respectively. The experiments were done on Sun Fire V250 computers.

We were first interested to evaluate the proposed optimization strategy in terms of overheads introduced due to fault-tolerance. Hence, we have implemented each application, on its corresponding architecture, using the Optimi- zationStrategy (MXR) strategy from Figure 6. In order to evaluate MXR, we have derived a reference non-fault tolerant implementation, NFT. The NFT approach is an optimized implementation similar to MXR, but we have removed the moves that decide the fault-tolerance policy assignment. To the NFT implementation thus obtained, we would like to add fault-tolerance with as little as possible overhead, and without adding any extra hardware resources. For these experiments, we have derived the shortest schedule within an imposed time limit: 10 minutes for 20 processes, 20 for 40, 1 hour for 60, 2 hours and 20 min. for 80 and 5 hours and 30 min. for 100 processes.

The first results are presented in Table 1a, where we have four columns: the third column presents the average overheads introduced by MXR compared to NFT, while the second and fourth columns present the maximum and minimum overhead, respectively. Let δ MXR and δ NFT be the schedule lengths obtained using MXR and NFT, respectively. The overhead is defined as 100 × (δ MXR -δ NFT ) / δ NFT . We can see that the overheads due to fault-tolerance grow with the application size. MXR approach can offer fault-tolerance within the constraints of the architecture at an average overhead of approximately 100%. However, even for applications of 60 processes, there are cases where the overhead is as low as 52%.

We were also interested to evaluate our MXR approach in the case the number of faults and their length varies. We have considered applications with 60 processes mapped on four processors, and we have varied the number k of faults from 2, 4, 6, 8, to 10, using a constant µ = 5 ms. Table 1b shows that the overheads increase substantially as the number of faults that have to be tolerated increase. This is to be expected, since we need N now = N non-tabu ∪ N waiting 14 --Select a solution based on aspiration criteria 15

x now = SelectBest(N now ); 16

x waiting = SelectBest(N waiting ); x non-tabu = SelectBest(N more replicas and/or re-executions if there are more faults. Similarly, we have kept the number of faults constant to 3, and varied µ: 1, 5, 10 15 and 20 ms, for 20 processes and two processors. We can observe in Table 1c that the overhead also increases with the increase in fault duration. However, the increase due to the fault duration is significantly lower compared to the increase due to the number of faults.

As a second set of experiments, we were interested to evaluate the quality of our MXR optimization approach. Thus, together with the MXR approach we have also evaluated two extreme approaches: MX that considers only re-execution, and MR which relies only on replication for tolerating faults. MX and MR use the same optimization approach as MRX, but besides the mapping moves, they consider assigning only reexecution or replication, respectively. In Figure 10 we present the average percentage deviations of the MX and MR from MXR in terms of overhead. We can see that by optimizing the combination of re-execution and replication, MXR performs much better compared to MX and MR. On average, MXR is 77% and 17.6% better than MR and MX, respectively. There are also situations, for graphs with 60 processes, for example, where MXR is able to reduce the overhead with up to 40% compared to MX and 90% compared to MR. This shows that considering re-execution at the same time with replication can lead to significant improvements.

In Figure 10 we have also presented a straightforward strategy SFX, which first derives a mapping without fault-tolerance considerations (using MXR without fault-tolerance moves) and then applies re-execution. This is a solution that can be obtained by a designer without the help with our fault-tolerance optimization tools. We can see that the overheads thus obtained are very large compared to MXR, up to 77% more on average. This shows that the optimization of the fault-tolerance policy assignment has to be addressed at the same time with the mapping of functionality. In Figure 10 we also see that replication (MR) is worst than even the straightforward re-execution (SFX). However, by carefully optimizing the usage of replication alongside re-execution (MXR), we are able to obtain results that are significantly better than re-execution only (MX).

Finally, we considered a real-life example implementing a vehicle cruise controller (CC). The process graph that models the CC has 32 processes, and is described in [START_REF] Pop | Analysis and Synthesis of Communication-Intensive Heterogeneous Real-Time Systems[END_REF]. The CC was mapped on an architecture consisting of three nodes: Electronic Throttle Module (ETM), Anti-lock Breaking System (ABS) and Transmission Control Module (TCM). We have considered a deadline of 250 ms, k = 2 and µ = 2 ms.

In this setting, the MRR produced a schedulable fault-tolerant implementation with a worst-case system delay of 229 ms, and with an overhead compared to NFT of 65%. If only one policy is used for fault-tolerance, as in the case of MX and MR, with 253 and 301 ms, respectively, the deadline is missed.

Conclusions

In this paper we have addressed the optimization of distributed embedded systems for fault-tolerance hard real-time applications. The processes are scheduled with static cyclic scheduling, while for the message transmission we use the TTP. We have employed two fault-tolerance techniques for tolerating faults: re-execution, which provides time-redundancy, and active replication, which provides space-redundancy.

We have implemented a tabu search-based optimization approach that decides the mapping of processes to the architecture and the assignment of fault-tolerance policies to processes. Our main contribution is that we have considered the interplay of fault-tolerance techniques for reducing the overhead due to fault-tolerance. As our experiments have shown, by carefully optimizing the system implementation we are able to provide fault-tolerance under limited resources.

Figure 2 .Figure 3 .

 23 Figure 2. Worst-Case Fault Scenario and Fault-Tolerant Techniques

1 .

 1 The schedules depicted are optimal.

Figure 4

 4 Figure 4. Combining Re-execution and Replication

Figure 6 .

 6 Figure 6. The General StrategyOptimizationStrategy(A, N) 1Step 1:B 0 = InitialBusAccess(A, N) 2 ψ 0 = InitialMPA(A, N, B 0 ) 3 if S 0 is schedulable then stop end if4Step 2: ψ= GreedyMPA(A, N, ψ 0 ) 5 if S is schedulable then stop end if 6Step 3: ψ = TabuSearchMPA(A, N, ψ) 7 return ψ end OptimizationStrategy

Figure 7 . 1 µ = 10 ms k = 1 µ = 10

 71110 Figure 7. Scheduling Replica Descendants

Figure 8 .

 8 Figure 8. Moves and Tabu History

Figure 9 .

 9 Figure 9. The Tabu Search Algorithm TabuSearchMPA(Γ, N, ψ) 1 --given a merged application graph Γ and an architecture N produces a policy 2 --assignment F and a mapping M such that Γ is fault-tolerant & schedulable 3 x best = x now = ψ; BestCost = ListScheduling(Γ, N, x best ) --Initialization 4 Tabu = ∅; Wait = ∅ --The selective history is initially empty 5 while x best not schedulable ∧ TimeLimit not reached do 6 --Determine the neighboring solutions considering the selective history 7 CP = CriticalPath(Γ); N now = GenerateMoves(CP) 8 --eliminate tabu moves if they are not better than the best-so-far 9 N tabu = {move(P i ) | ∀ P i ∈CP ∧ Tabu(P i )=0 ∧ Cost(move(P i )) < BestCost} 10 N non-tabu = N \ N tabu 11 --add diversification moves 12 N waiting = {move(P i ) | ∀ P i ∈ CP ∧ Wait(P i ) > |Γ|} 13 N now = N non-tabu ∪ N waiting 14 --Select a solution based on aspiration criteria 15 x now = SelectBest(N now ); 16 x waiting = SelectBest(N waiting ); x non-tabu = SelectBest(N non-tabu ) 17 if Cost(x now ) < BestCost then x = x now --select x now if better than best-so-far 18 else if ∃ x waiting then x = x waiting --otherwise diversify 19 else x = x non-tabu --if no better and no diversification, select best non-tabu 20 end if 21 --Perform selected move 22 PerformMove(x); Cost = ListScheduling(Γ, N, x) 23 --Update the best-so-far solution and the selective history tables 24 If Cost < BestCost then x best = x; BestCost = Cost end if 25 Update(Tabu); Update(Wait) 26 end while 27 return x best end TabuSearchMPA

Figure 1. System Architecture Example

	N 1	N 2	N 3	N 4
					S 0 S 0	S 1 S 1	S 2 S 2	S 3 S 3	S 0 S 0	S 1 S 1	S 2 S 2	S 3 S 3
				TTP bus	Slot Slot	TDMA Round TDMA Round	Cycle of two rounds Cycle of two rounds

Table 1 . Overheads of MXR compared to NFT Figure 10. Comparing MXR with MX, MR and SFX

 1

		D $SSOLFDWLRQ VL]H			E 1XPEHU RI IDXOWV SURFV µ			F µ SURFV N
	SURFV	N	PD[	DYJ	PLQ	N	PD[	DYJ	PLQ	µ	PD[	DYJ	PLQ

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


Torsten Kempf
email: torsten.kempf@iss.rwth-aachen.de

Malte Doerper

R Leupers

G Ascheid

H Meyr

Tim Kogel
email: tim.kogel@coware.com

Bart Vanthournout

A Modular Simulation Framework for Spatial and Temporal Task Mapping onto Multi-Processor SoC Platforms

Heterogeneous Multi-Processor SoC platforms bear the potential to optimize conflicting performance, flexibility and energy efficiency constraints as imposed by demanding signal processing and networking applications. However, in order to take advantage of the available processing and communication resources, an optimal mapping of the application tasks onto the platform resources is of crucial importance.

In this paper, we propose a SystemC-based simulation framework, which enables the quantitative evaluation of application-to-platform mappings by means of an executable performance model. Key element of our approach is a configurable event-driven Virtual Processing Unit to capture the timing behavior of multi-processor/multi-threaded MP-SoC platforms. The framework features an XML-based declarative construction mechanism of the performance model to significantly accelerate the navigation in large design spaces.

The capabilities of the proposed framework in terms of design space exploration is presented by a case study of a commercially available MP-SoC platform for networking applications. Focussing on the application to architecture mapping, our introduced framework highlights the potential for optimization of an efficient design space exploration environment.

Introduction

One of the most challenging tasks in modern System-on-Chip design projects is to map a complex application onto a heterogeneous architecture in adherence to the specified performance and cost requirements. The effective performance of processing elements is often confined by the communication architecture, since memory access latency does not keep pace with the increasing computational power. General purpose processors resolve the memory access bottleneck by using sophisticated cache and memory hierarchies. Unfortunately this approach is often not applicable for embedded applications due to the poor memory locality of stream driven and packet based data processing.

Instead, embedded processor architectures are increasingly equipped with Hardware Multi-Threading (HW-MT) [START_REF] Ungerer | A Survey of Processors with Explicit Multithreading[END_REF] to perform task switches with virtually no performance overhead. By that, the application inherent Task Level Parallelism (TLP) is exploited with the purpose of hiding the memory access latency. This effectively leads to a significant increase in processor utilization. The HW-MT technique is already widely employed in the network processor domain [START_REF] Lakshmanamurthy | Network Processor Performance Analysis Methodology[END_REF] but recently finds its way into advanced multimedia [START_REF] Rutten | A Heterogeneous Multiprocessor Architecture for Flexible Media Processing[END_REF] and wireless signal processing platforms [START_REF] Glossner | A Multithreaded Processor Architecture for SDR[END_REF].

Beside the immediate benefit of increased utilization, HW-MT can be considered as a lean operating system imple-mented in hardware to efficiently share the processing resources among multiple concurrent tasks. In analogy with today's software operating systems (SW-OS), the HW-MT concept bears the potential to bring a disciplined management of processing resources to the data processing domain. From the perspective of the functional tasks, this 'processing management' introduces a virtualization of the computational resources. This virtualization of the architectural elements represents an efficient concept to cope with the complexity of MP-SoC platforms: now the system architect can allocate processing and communication resources in a deterministic way [START_REF] Agerwala | Systems Trends and their Impact on Future Microprocessor Design[END_REF].

However, the spatial and temporal mapping of the functional tasks to processing elements as well as the mapping of the inter-task data exchange to a communication architecture while meeting performance and cost requirements is an unresolved challenge. In this paper we propose a SystemC based simulation framework, which enables the system architect to evaluate arbitrary task mappings by creating an abstract and yet sufficiently accurate performance model of the considered application together with the anticipated architecture.

The application is first represented as a set of untimed reactive SystemC tasks communicating through an unified Transaction Level Modeling (TLM) [START_REF] Grötker | System Design with SystemC[END_REF] interface. Next the processing requirements of each individual task are characterized by annotating the delay budgets to the communication events. Finally we introduce the concept of a Virtual Processing Unit (VPU) to capture the impact of shared processing elements to the SoCs performance. As an intermediate layer between the timed task network and the underlying event driven simulation kernel, the major purpose of the VPU is to compute timing of the multi-threaded task execution under the consideration of task swapping and preemption.

The major benefit of the outlined approach is the declarative construction of the performance model: the individual timing annotations as well as the mapping of the tasks onto the respective processing elements is specified by means of an eXtended Markup Language (XML) description. This generic mapping mechanism significantly shortens the iterative exploration cycle as well as improves model reuseability.

After the subsequent discussion of related work, we present the envisioned MP-SoC design flow and give an intuitive introduction of the task model. The following section 4 introduces the VPU concept and defines in detail the operational semantic. The value of our approach is highlighted by a large scale case-study in the context of the networking application domain.

Related Work

System Level Design is considered the appropriate way to deal with the ever increasing complexity and heterogene-ity of SoC architectures [START_REF] Keutzer | System-level design: Orthogonalization of concerns and platform-based design[END_REF]. Various actor-oriented frameworks are proposed to capture arbitrary Models of Computation (MoC) for the purpose of system level modeling and tool supported paths to exploration, implementation and/or verification [START_REF] Grötker | System Design with SystemC[END_REF][START_REF] Balarin | Metropolis: An integrated electronic system design environment[END_REF][START_REF] Gajski | SpecC: Specification Language and Methodology[END_REF]. The modeling strategy presented in this paper can be implemented on top of any of these MoC generic frameworks. We selected SystemC mainly because of the broad user acceptance and commercial tool support.

Complementary to our top-down refinement flow, the Component Based Design paradigm [START_REF] Dziri | Unified Component Integration Flow for Multi-Processor SoC Design and Validation[END_REF] advocates the bottom-up platform composition from a parameterizable IP library, containing off-the-shelf processing elements, communication fabrics and hardware dependent Software layers. This approach is clearly advantageous for the rapid exploration and implementation of the general purpose portion of the application [START_REF] Cesario | Component-Based Design Approach for Multicore SoCs[END_REF], whereas our approach is focused on application specific architectures executing the data-processing part.

The highest possible abstraction level for design space exploration and application mapping is static performance analysis [START_REF] Jersak | Context-Aware Performance Analysis for Efficient Embedded System Design[END_REF][START_REF] Pop | Holistic scheduling and analysis of mixed time/eventtriggered distributed embedded systems[END_REF]. Other approaches are closer related to simulation frameworks for top-down exploration and refinement like ARTEMIS [START_REF] Pimentel | Exploring Embedded-Systems Architectures with Artemis[END_REF], MESH [START_REF] Paul | Schedulers as Model-Based Design Elements in Programmable Heterogeneous Multiprocessors[END_REF], STepNP [START_REF] Bensoudane | Stepnp: A system-level exploration platform for network processors[END_REF] and work on abstract RTOS modeling [START_REF] Madsen | Networkon-chip modeling for system-level multiprocessor simulation[END_REF][START_REF] Gerstlauer | RTOS Modeling for System Level Design[END_REF].

The ARTEMIS project [START_REF] Pimentel | Exploring Embedded-Systems Architectures with Artemis[END_REF] is focused on an automated refinement of coarse-grain Kahn Process Network algorithm models to fine-grain architecture models for the purpose of design space exploration and synthesis.

Similar to our approach, the Modeling Environment for Software and Hardware (MESH) [START_REF] Paul | Schedulers as Model-Based Design Elements in Programmable Heterogeneous Multiprocessors[END_REF] project is concerned with modeling of heterogeneous MP-SoC platforms above the cycle-level accuracy. Here, schedulers are considered as the central modeling element to capture the dynamic and datadependent nature of MP-SoC platform mapping.

The SystemC based STepNP [START_REF] Bensoudane | Stepnp: A system-level exploration platform for network processors[END_REF] simulation framework also advocates the joint consideration of communication architecture and application specific processing elements. STepNP is focused on the early integration of Instruction-Set Simulators (ISS) into cycle-level TLM platform models [START_REF] Quinn | A System Level Exploration Platform and Methodology for Network Applications Based on Configurable Processors[END_REF], whereas in our approach processing elements and interconnect are situated on a higher packet-level TLM abstraction layer.

Madsen et al. propose the combined modeling of NoC and RTOS scheduling at a yet higher abstraction level, where the application tasks are only represented as set of timing budgets for processing and communication without any functional information [START_REF] Madsen | Networkon-chip modeling for system-level multiprocessor simulation[END_REF].

Work on RTOS modeling [START_REF] Gerstlauer | RTOS Modeling for System Level Design[END_REF] and generation [START_REF] Mooney | A Hardware-Software Real-Time Operating System Framework for SoC's[END_REF] employs similar modeling techniques as our approach, but particularly addresses the selection and configuration of the Software RTOS for general purpose processing.

Our modeling framework addresses quantitative performance analysis during the early conceptualization of highly complex Network-on-Chip (NoC) enabled MP-SoC platforms. The unique transparent mapping mechanism presented in this paper combines the flexibility of non-functional performance analysis with an accuracy within few percent of fully cycle accurate TLM simulation [START_REF] Bussaglia | A Highly Efficient Modeling Style for Heterogeneous Bus Architectures[END_REF].

System Level Design Flow

We first give an overview of the complete flow, before we introduce the design space exploration framework. Then we motivate the concept of task modeling, where we introduce the Virtual Architecture Mapping methodology to capture the effect of task execution on dedicated hardware as well as on single-threaded processor cores.

Design Flow Overview

The overall flow follows the multi-level SoC design strategy proposed by Magarshack and Paulin [START_REF] Magarshack | System-on-chip Beyond the Nanometer Wall[END_REF], which separates MP-SoC development into four distinctive phases.

• The functional phase deals with development of Hardware independent Software and application specific algorithms. We assume, that this phase also comprises the partitioning of the application into a set of loosely coupled functional blocks and the extraction of Task Level Parallelism (TLP). For the performance relevant data processing portion of typical signal processing and networking applications, this architecture independent partitioning is mostly straight forward and can be immediately derived from the algorithmic block diagram. • The MP-SoC platform phase covers the systemarchitecture specification by integration of high level IP blocks, along with the spatial and temporal mapping of the application to the MP-SoC platform. We particularly address this phase, which is concerned with the full functional and architectural complexity of MP-SoC platforms. Additionally, high-level IP creation and basic IP creation are concerned with the development of the individual SoC components like e.g. embedded processors or interconnect technologies. These two phases are not in the scope of this paper.

MP-SoC Mapping Phase

As depicted in figure 1, our MP-SoC framework follows the well-known y-chart principle [START_REF] Lieverse | A Methodology for Architecture Exploration of Heterogeneous Signal Processing Systems[END_REF], where a set of functional application models is merged with a set of architecture models in a dedicated mapping step. As an extension of the general y-chart paradigm, in our case the timing is separately specified during the mapping phase to keep it independent from both the functional model as well as the architecture model. This mechanism is the key to enhance the reusability of architecture and application models as well as the flexibility during design space exploration. In reference to the flexible and highly abstracted mapping mechanism, the developed embodiment of the y-chart principle is called Virtual Architecture Mapping (VAM).

Figure 1. Virtual Architecture Mapping

In our previous work we have conceived a well defined packet-level TLM paradigm [START_REF] Kogel | Virtual Architecture Mapping: A SystemC based Methodology for Architectural Exploration of System-on-Chip Designs[END_REF] for efficient modeling of embedded applications and the anticipated communication architecture. The available set of generic, parameterizable on-chip communication models cover shared buses as well as full scale on-chip networks [START_REF] Kogel | A Modular Simulation Framework for Architectural Exploration of On-Chip Interconnection Networks[END_REF]. The simulation environment also contains a comprehensive set of analysis tools for functional and performance validation.

One key aspect for efficient design space exploration is a declarative specification mechanism, i.e. the following aspects of the MP-SoC architecture are defined by an XML based configuration file, which contains:

• the configuration of the timing model (basically the number of required cycles per task execution), • the number of available processors and number of supported concurrent threads per processor, • the mapping of the application tasks to processors and threads, • the instantiation, parameterization and interconnection of the communication nodes, • the instantiation and address mapping of the memory architecture.

During the elaboration phase of the simulation, the architecture specification is extracted from the configuration files and bound to the application model by means of Virtual Architecture Mapping. During the simulation run, evaluation modules connected to the architecture models collect and aggregate statistical information like resource utilization, latency, and throughput. On completion of the simulation, this statistical information is visualized by means of histogram and communication graph views. Based on the collected data, the system architect may modify the MP-SoC architecture and/or the application mapping until the requirements are met.

Task Modeling

This paragraph introduces the task modeling. Tasks are represented by their pure functionality and an individual timing model. The functionality is pure C/C++ code, whereas the timing model influences only the notification time of externally visible events. These annotated times characterize the architecture implementation of the task and are derived from the required processing time of the anticipated processing element to execute the task's functionality.

Following to the notation scheme of the Tagged Signal Model (TSM) [START_REF] Lee | A framework for comparing models of computation[END_REF] we will now introduce a formal representation of the timing annotation. After some fundamental definitions, the modeling of a functional process is derived.

Elementary Definitions: An event e consists of a time tag t ∈ T and a value v ∈ V ADT . In our packet-level TLM paradigm, a value is represented as an Abstract Data Type (ADT), which is basically a C++ class object. Predefined members of this ADT are a priority, a delay and a state. The tag and the value fields of the event are accessible by the point operator, i.e. e i .value.priority denotes the priority field of event e i . A signal s is a set of events, which can be viewed as a subset of T × V.

In the following considerations functional SystemC processes are represented as timed Communicating Extended Finite State Machines (tCEFSM) to reason about the timing annotation and mapping mechanism. A tCEFSM is a 7-tuple (I, O, Z, f, U, D busy , D delay ) with The tCEFSM is activated on the arrival of a new input event and instantaneously responds with a state transition and possibly the generation of one or more output events. To model the busy time of the task during the processing of the state transition, the next activation is not possible before the time ∆t busy has elapsed as illustrated in the upper part of figure 2. Additionally the generated events are projected into the future to account for the period ∆t i,d between task activation and event generation. Note that this scheme is sufficiently expressive to capture the notion of pipelined processing elements with ∆t busy < ∆t i,d , i.e. the processing of a new input event starts before the generation of the result.

Figure 2. VPU Performance Model

By guarding the activation of the tCEFSM during the busy periods and delaying the generated events, the externally visible behavior of the tCEFSM corresponds to the task execution on the anticipated processing element. Compared to nonfunctional task representation by means of processing budgets, our coarse-grain annotation of the functional SystemC processes yields a very accurate model of the timing characteristic. Additionally the simulation speed is significantly faster than on a target instruction set simulator.

This modeling methodology enables mapping of functional tasks to single-threaded processors as well as to dedicated hardware blocks. In the following section we introduce the concept of a Virtual Processing Unit (VPU) to enhance the introduced methodology to model shared processing resources.

VPU

We will now present the Virtual Processing Unit concept. First we introduce an intuitive introduction of the functionality and in the following paragraph the operational semantic of this generic SystemC model is derived.

VPU Introduction

The VPU enables the system architect to investigate the mapping of the application tasks with respect to space and time. Spatial mapping denotes the assignment of a task to one of the physical processing elements in the MP-SoC platform. Temporal mapping refers to the allocation of a time budget (derived from the number of processing cycles) on this particular processing element. Note that the task itself remains untouched and no recompilation is required to explore the design space, as the total simulation environment is configured by an XML description during the simulations initialization phase.

An example depicted in figure 2 illustrates the timing annotation and VPU mapping mechanism. The upper part of figure 2 shows two tasks and their individual timing characteristic, which are spatially mapped to a single VPU instance. The bottom of figure 2 shows the resulting timing in response to an assumed scenario. In the following we discuss the event sequence to illustrate the impact of the VPU:

First task 1 is activated by the external init T 1 event, executes the first portion of its functionality, and generates the external request T 1 event after 10 time units . In the meantime, the activation event init T 2 has already occurred, but task 2 cannot start execution before the first task is finished and swapped out. The VPU takes this additional delay into account and notifies the external event to activate the execution of task 2 at the correct time. In the given scenario, the communication request from task 1 returns before task 2 has finished the first portion of its functionality. Since task 1 is configured to have a higher priority, task 2 is preempted and not resumed before task 1 has completed its functionality. The request generated by the functionality of task 2 is delayed by the additional preemption time, thus the externally visible event of this request is notified at the corresponding time of concurrent task execution.

Of course, the new task mapping capabilities are compliant with our existing communication models. As outlined in the previous chapter, the complete MP-SoC platform phase is now supported by a versatile exploration framework.

Operational Semantic

According to the Tagged Signal Model (TSM) we introduce a formal representation of the timing annotation and the VPU mapping mechanism.

The concept of a VPU generalizes the modeling of a SW-OS as well as HW-MT processing elements. Following the Virtual Architecture Mapping (VAM) mechanism, the VPU mapping is achieved by manipulation of the externally visible event tags. Before the incorporation of any specific Real Time Operating System (RTOS), our transparent mapping scheme and parameterizable VPU enables the efficient design space exploration without modifying of the functional tasks.

By mapping different functional tasks represented as timed CEFSMs to one VPU, the VPU guards the activation of all tasks against incoming events as illustrated in figure 3. In order to calculate the tags of all incoming and generated events, the VPU maintains two data structures:

The Priority Queue U P Q is a list of events e i ∈ T × V, which stores incoming events. By that the individual busy times ∆t busy,i of the associated tasks are taken into account. The associated method schedule processes(U P Q ) schedules the next active task from the list of pending events in the Priority Queue U P Q without removing the event from the queue. An additional method remove f inished processes(U P Q ) removes the activating event of a finished task from the Priority Queue U P Q .

A Delay Queue U DQ is a list of events e i ∈ T × V, which projects generated events into the future according to their tags. The event tags are calculated with respect to the individual delay annotations ∆t delay,i .

Additionally the VPU calculates the delay penalty of task swapping and task preemption. Along these lines we define a VPU to be a 7-tuple In the following we elaborate the operational semantics of the VPU functions and illustrate the work-flow of the VPU model by means of the example depicted in figure 3.

P V P U = (S I , S O , E Internal , U P Q , U DQ , U V P U , f V P U ) • a set
Events arriving on the incoming signals S V P U,CO activate the function f P Q activate . This function inserts the arriving event into the Priority Queue U P Q and in case of preemption or idle state the VPU directly activates the further processing of the arrived event. The function f V P U,P Q update handles the tag manipulation of both pending events for activation of the mapped tasks as well as outgoing events generated by the tasks. On every execution of f V P U,P Q update with a non-empty priority queue, the VPU checks whether a new task needs to be scheduled from the set of pending events in the Priority Queue U P Q (line 3). In case an event has been scheduled for the first time (line 4), the delayed activation of the functional task takes the penalty for task swapping into account (line 6 and 7).

0 function f P Q update { 1 remove f inished processes(U P Q ); 2 if (U P Q .notEmpty()) { 3 if (e tmp =
Recall that the activation of a functional task always returns immediately and the VPU performs the required timing manipulation of the events. The product of the return value nbr cycles and the VPUs clock period denotes the individual timing annotation of the activated task (line 7). At the same time the new events generated during the task activation are inserted into the Delay Queue U DQ . These events remain inside this queue until their tag is due. As depicted in figure 3, sending of the projected events is handled by the functions f DQ,update and f DQ,activate .

Task preemption occurs when the current task has a lower priority than the selected task. In this case all generated events in the Delay Queue U DQ and the tags of already activated processes in the Priority Queue U P Q have to be delayed (lines 17 -20). The preemption time is calculated from the busy time ∆t busy of the displacing processes and the required swapping time ∆t swap .

Figure 2 illustrates a typical execution sequence in case of preemption. At time 30 the response of task 1 displaces the execution of task 2. Originally event request T 2 would occur at time 15 + ∆t 2,d0 = 15 + 25 = 40. Instead, the event is delayed by ∆t 1,d1 + ∆t swap = 15 time units. Resuming task 2 at time 45 causes another ∆t swap tag increment of event request T 2 , which finally occurs at time 60.

Coming back to the discussion of f V P U,P Q update , the tag incrementation of already generated events in case of task resuming is performed in lines 24 -27. Finally the next activation of f V P U,P Q update occurs after the current task is finished, i.e. after the busy time of the active process ∆t busy plus the swapping penalty ∆t swap (line 32). If no events are pending in the priority queue, the VPU switches to idle state and waits for the arrival of new events (line 35).

As already mentioned the functions f DQ,update and f DQ,activate maintain the Delay Queue U DQ , where:

• The function fDQ,activate inserts the incoming events at the functional signal into the Delay Queue UDQ. • The function f DQ,update manages the sending of due events to the architectural signals of the VPU.

In summary, the VPU enables the transparent mapping of multiple functional tasks onto a shared processing resource. The configurable ∆t swap parameter models of the impact on performance during task swapping of a slow SW-OS compared to hardware supported HW-MT. The modular implementation of the framework allows the customizing the task scheduling algorithm by overloading the function schedule process(U P Q ). This enables the incorporation and early investigation of the RTOS scheduling policy.

NPU Case Study

To demonstrate the fidelity of the outlined approach, this section presents the results of a design project accomplished with the introduced design methodology. We have selected an IPv4 forwarding application with Quality of Service (QoS)

Reference Architecture

The capability of the introduced methodology has been evaluated in the context of the Intel IXP2400 NPU [START_REF]Intel Network Processors[END_REF]. The task characterizations in terms of memory accesses as well as computation cycles are taken from the original Intel documentation [START_REF] Lakshmanamurthy | Network Processor Performance Analysis Methodology[END_REF] and are illustrated in table 1.

The reference architecture of Intel consists of 8 RISC-like processing elements each implementing 8 concurrent hardware threads. These processors have been modeled as VPUs, where each VPU instantiates 8 functional tasks to model the 8 threads of each processor. Since HW-MT processors swap tasks within a single clock cycle the VPU swap time ∆t swap is one cycle. The communication network of the IXP2400 architecture comprises 7 exclusive next-neighbor connections and 3 global shared buses. To achieve the required OC-48 performance (corresponding to 2.5 Gbit/s) the timing budget to process a minimum size 48 Byte packet is only 147ns.

In this section, we illustrate the exploration capabilities of our framework, focussing on the task mapping of the IPv4 application to the Intel architecture.

Design Space Exploration

The mapping of the application tasks onto various VPU configurations reveals the impact of processing element features like execution speed and HW-MT support. To achieve a fair comparison between the considered task mappings, the processing and communication requirements of all functional tasks are tied to the values in table 1. All VPUs are modeled with a frequency of 600 MHz.

Three alternative spatial task mappings depicted in figure 4 are evaluated: according to the functional software pipeline (figure 4a) each VPU concurrently executes the whole application. Second, figure 4b shows a context software pipeline, where each VPU concurrently executes 8 instances of the same task. The third option depicted in figure 4c represents

Table 1. Reference Mapping

Our traffic scenario is a typical IP traffic profile with an effective data rate of 2.06 Gbit/s. Investigation of the three introduced software pipelines shows, that the functional pipeline falls short to achieve the throughput requirements, as a throughput of appr. 1.89 Gbit/s is reached. Therefore in the following discussion the functional pipeline will be omitted, whereas the context and mixed pipeline will be further investigated.

The impact of temporal task mapping is examined by means of the context-and the mixed-pipeline systems and two different VPU configurations. First a non priority based simulation and second a priority based simulation is evaluated. Depending on the QoS class of each received IPv4 packet the priority is determined, e.g. video and voice packets are of high priority, whereas flooding packets are of low priority. This scheduling mechanism influences the temporal execution of the different tasks mapped to each VPU. Preferring higher priority packets, task preemption as well as task stalling occurs to speed up the processing of high priority packets.

Figure 5. Latency Measurements

The simulation results depicted in figure 5 show, that priority based task scheduling in the VPUs achieves a significant reduction of approximately 40% in the latency of high priority voice packets. As a tradeoff the average latency of all processed packets rises by a factor of 2.6. These tradeoff illustrates the crucial impact of this kind of system architecture decisions on the system performace.

In summary the results of the case-study demonstrate the capabilities of the simulation framework in terms of flexibility for design space exploration as well as high simulation speed. As soon as the SystemC model of the application is available a single engineer can carry out the task mapping experiments within a few hours or days, as only configuration files have to be modified. The simulation speed of this highly complex MP-SoC architecture model for IP forwarding is in the range of 100,000 cycles per second on a 2.0 GHz Linux host, which is roughly 2 orders of magnitude faster than the ISS based simulator in the Intel Software Development Kit [START_REF]Intel Network Processors[END_REF].

Conclusion

We propose a system level simulation framework for early investigation of MP-SoC platform architectures in the context of the application. The major contribution of this paper is a highly flexible timing annotation and task mapping mechanism to capture the performance impact of single-and multithreaded processing elements. Here the concept of a Virtual Processing Unit enables the rapid exploration of spatial and temporal application mappings to arbitrarily complex multiprocessor platforms with no design overhead.

The major advantage of our modeling approach is the combination of high simulation speed, modeling efficiency and accuracy to rapidly evaluate architectural alternatives. Together with the Network-on-Chip simulation environment [START_REF] Kogel | A Modular Simulation Framework for Architectural Exploration of On-Chip Interconnection Networks[END_REF] the resulting MP-SoC framework covers the exploration of the com-plete design space spread by multiple heterogeneous processing elements and complex communication architectures.

Our exploration framework has been successfully applied to the customization of an MP-SoC platform, which performs IP forwarding with Quality of Service support. This complex case study illustrates the potential of the exploration capabilities of the developed framework.

Our future work will focus on the incorporation of RTOS specific services and the additional deployment of analytical analysis-and optimization-techniques.

•

  a set of input events I ⊆T ×V ADT and output events O ⊆T ×V ADT • a finite, non-empty set of explicit states Z. • a set of variables U = (u 1 , . . .), which represent the implicit state. • a state transition function f : Z * × I → Z * × O , where Z * denotes the set of all implicit and explicit states • a set of busy periods D busy = {∆t busy,i } • a set of processing delays D delay = {∆t i,d }

  of input signals S I = S V P U,CI ∪ S V P U,F I , where S V P U,CI denotes a set of input signals connected to the on-chip communication network and S V P U,F I denotes a set of input signals connected to the associated functional tasks. • a set of output signals S O = S V P U,CO ∪S V P U,F O , where S V P U,CO denotes a set of output signals connected to the on-chip communication network and S V P U,F O denotes a set of output signals connected to the associated functional tasks. • a set of internal events E Internal = { e P Q,update , e DQ,update } • a Priority Queue U P Q ⊆ T ∈ V and a Delay QueueU DQ ⊆ T ∈ V • a set of internal variables U V P U = { u busy , u priority , ∆t swap },where a state variable u busy , which is initialized as false a variable u priority retains the priority of the active process a swapping time ∆tswap depending on the VPU's status • a set of functions f V P U :

Figure 3 .

 3 Figure 3. Virtual Processing Unit (VPU) f P Q activate being sensitive to external events on the signals S V P U,CI connected to the communication network f P Q update being sensitive to the internal event e P Q,update f DQ activate being sensitive to events on the signals S V P U,F I connected to the associated functional tasks f DQ update being sensitive to the internal event e DQ,update

Figure 4 .

 4 Figure 4. Software Pipelines functionality and demonstrate the framework's exploration capabilities during a case study of a state-of-the-art Network Processing Unit (NPU) platform.

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