Kunhyuk Kang
email: kang18@ecn.purdue.edu

Bipul C Paul
email: paulb@ecn.purdue.edu

Kaushik Roy
email: kaushik@ecn.purdue.edu

Statistical Timing Analysis using Levelized Covariance Propagation *

Variability in process parameters is making accurate timing analysis of nano-scale integrated circuits an extremely challenging task. In this paper, we propose a new algorithm for statistical timing analysis using Levelized Covariance Propagation (LCP). The algorithm simultaneously considers the impact of random placement of dopants (which makes every transistor in a die independent in terms of threshold voltage) and the spatial correlation of the process parameters such as channel length, transistor width and oxide thickness due to the intra-die variations. It also considers the signal correlation due to reconvergent paths in the circuit. Results on several benchmark circuits in 70nm technology show an average of 0.21% and 1.07% errors in mean and the standard deviation, respectively, in timing analysis using the proposed technique compared to the Monte-Carlo analysis.

Introduction

Timing verification is necessary for efficient integrated circuit design to achieve a desired performance. Conventionally, static timing analysis [START_REF] Hitchcock | Timing verification and the timing analysis problem[END_REF] is used for the timing verification of digital integrated circuits. However, as the scaling of technology continues, static timing analysis fails to provide a realistic timing information [START_REF] Visweswariah | Death, taxes and failing chips[END_REF]. This is mainly due to the ever-increasing variability in the process parameters such as channel length, transistor width, oxide thickness and the random placement of dopants in the channel.

Process variations can be classified into two main categoriesintra-and inter-die variations. Due to inter-die variations, the same device on a die can have different characteristics across different dies (i.e., dies from one wafer, from wafer to wafer, and from wafer lot to wafer lot). Intra-die variations, on the other hand, are the variations of transistor characteristics within a single die. As we are moving towards sub-100nm technology regime, intra-die process variations are becoming increasingly significant [START_REF] Borkar | Parameter variations and impact on circuits and microarchitecture[END_REF]. Intra-die variations in length, width and oxide thickness, are expected to exhibit some spatial correlations among devices located close to each other (systematic variation). For example, transistors close to each other are expected to have similar parameter variation than the ones that are far apart in a die. The effect of random placement of dopants (threshold voltage variation), on the other hand, is different in every transistor irrespective of their spatial location [START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. In addition to this, signal correlation due to the reconvergent paths under process variation also plays a significant role in circuit timing.

An accurate timing analysis should therefore, simultaneously consider the three issues, namely; (1) spatial correlation of the process parameters such as channel length, transistor width and the oxide thickness, (2) random placement of dopants, and (3) the signal correlation due to the reconvergent paths. Several efforts have been made to independently model these effects to provide algorithms called Statistical Timing Analysis, to obtain the timing information of circuits under process variation. However, to the best of our knowledge, no algorithm is available for timing analysis considering all the above three effects simultaneously. For example, in [START_REF] Visweswariah | First-order Incremental Block-Based Statistical Timing Analysis[END_REF][START_REF] Devgan | Block-based Static Timing Analysis with Uncertainty[END_REF][START_REF] Agarwal | Computation and refinement of statistical bounds on circuit delay[END_REF], intra-die variations of process parameters are modeled as independent random variables (without spatial correlation). Chang et.al. [START_REF] Chang | Statistical Timing Analysis Considering Spatial Correlations using a Single PERT-like Traversal[END_REF], proposed a PERT-like traversal algorithm for statistical timing analysis considering the spatial correlation of process parameters as well as the signal correlation due to reconvergent paths. In this technique, the correlated process parameters are transformed into a set of uncorrelated principle components to compute the circuit delay. A block-based statistical timing analysis method is also proposed in [START_REF] Le | STAC: Statistical Timing Analysis with Correlation[END_REF] to obtain circuit delay under process variation considering both the spatial correlation and the signal correlation due to reconvergent paths. However, none of the above methods consider the effect of random placement of dopants, spatial correlation of process parameters and the signal correlation due to reconvergent paths simultaneously. Neglecting any of these effects may result in unrealistic timing information of the circuit [START_REF] Bowman | Impact of Die-to-Die and Within-Die Parameter Fluctuations on the Maximum Clock Frequency Distribution for Gigascale Integration[END_REF].

In this paper, we propose a new statistical timing algorithm that simultaneously considers the above three effects. We employ the grid based model proposed in [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF] to incorporate the spatial correlation of process parameters such as length, width and oxide thickness. The effect of random placement of dopants is considered by representing the threshold voltage of each transistor as an independent random variable. The circuit delay is calculated considering the above effects using Levelized Covariance Propagation (LCP). In this technique, the timing information at the output of all gates in a single logic level is calculated and propagated to the next logic level. The timing information includes the arrival time (mean and variance) at the output of each gate in a particular logic level and the covariance among different outputs. The signal correlation due to reconvergent paths is also considered while calculating the timing information at a particular logic level. We use the proposed algorithm to calculate the circuit delays of several ISCAS benchmark circuits under process variation and compared the results with the Monte-Carlo analysis.

The rest of the paper is organized as follows. In section 2, we discuss the modeling of process variation. Section 3 describes gate delay model considering the effect of process variation. In section 4, the proposed algorithm is discussed in detail. Section 5 presents the experimental results on several ISCAS benchmark circuits.

Modeling the Process Variation

In this work, we consider channel length, transistor width, oxide thickness and threshold voltage as random process parameters which Inter-Die Variation Intra-Die Variation Systematic Figure 1. Rectangular Grid Model [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF] can be represented by a normal distribution [START_REF] Nassif | Modeling and Analysis of Manufacturing Variations[END_REF]. We also assume that the variation in the above parameters are mutually independent. The process parameters can be divided into two groups based on their statistical behavior. The parameters such as the length, width and the oxide thickness will exhibit spatial correlations among different transistors close to each other. Therefore, for a group of transistors depending on their proximity, a single random variable can be used to represent the variation in the above process parameters. The threshold voltage, on the other hand, will be different for each transistor in a die due to the effect of random placement of dopants. Hence, separate random variables are to be used to represent the threshold voltages of all the transistors.

The following subsections explain how we model the spatial correlation and the random placement of dopants.

Modeling Spatial Correlation

To capture the effect of spatial correlation of process parameters among different transistor locations, we use the rectangular grid model proposed in [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF]. In this model, the die area is divided by a multi-level quad-tree partitioning as shown in Fig. 1. All the transistors in a particular grid are assumed to experience the same parameter variation. The tree structure forms a hierarchical relationship among all the grids. A grid is defined to be a parent of a lower level grid if they share a common region. All the transistors in a grid at the bottom most level experience the same parameter variations. The spatial correlation of parameter variation among transistors in different grids is governed by their parent grids.

For every grid (at all levels), we maintain a single random variable for each process parameter. The parameter variation of a transistor in any grid at the bottom most level is represented by the sum of the variation in that particular grid and the variations in all its parent grids. For example, the variation of channel length of transistors in grid [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF][START_REF]Berkeley Predictive Transistor Model[END_REF] (at the bottom most level (Fig. 1)) is represented as,

L(2, 1) = L0 + ∆L2,1 + ∆L1,1 + ∆L0,1 (1)
where L(2, 1) is the random variable which represents the variation in the channel length in grid [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF][START_REF]Berkeley Predictive Transistor Model[END_REF]. L0 is the nominal value of the channel length. ∆L(2, 1), ∆L(1, 1) and ∆L(0, 1) represent the deviation in channel length in grids (2, 1), (1, 1) and (0, 1) respectively. The covariance of the process parameters between different grids is obtained depending on their common parent grids. For example, the random variables representing the channel length in grid [2,1], [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF][START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF] and [START_REF] Agarwal | Path-Based Statistical Timing Analysis Considering Inter-and Intra-Die Correlations[END_REF]16] are expressed as,

L(2, 1) = L0 + ∆L2,1 + ∆L1,1 + ∆L0,1 L(2, 2) = L0 + ∆L2,2 + ∆L1,1 + ∆L0,1 L(2, 16) = L0 + ∆L2,16 + ∆L1,4 + ∆L0,1
In this example, L(2, 1) and L(2, 2) share two parent grids ∆L1,1 and ∆L0,1, while L(2, 1) and L(2, 16) share only ∆L0,1. Thus, the covariance between L(2, 1) and L(2, 2) will be two times that of the covariance between L(2, 1) and L(2, 16). For the case of 3 level grid structure shown in Fig. 1, a 16×16 covariance matrix is necessary for each process parameter to represent the correlation between any two grids in the bottom most level. Also note that, since the top-most level is the parent grid of all the grids, it represents the inter-die variation. While the intra-die variation of the process parameters is represented by all other levels of girds. Hence, by using this model, intra-and inter-die variations can be considered simultaneously.

Random Placement of Dopants

In scaled CMOS devices, there exists a statistical fluctuation in the number of dopants in the channel, which can be translated into a threshold-voltage variation [START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. This discrete dopant effect on threshold voltage variation is incorporated by employing the following equation [START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF] into the simulator while computing the variation of threshold voltage of each transistor.

σ V th = q Cox r NaW 0 dm 3LW (2)
σ V th represents the standard deviation of threshold variation due to random placement of dopants, q is electron charge, Cox is the oxide capacitance, Na is the substrate doping concentration, and W 0 dm represents the maximum depletion layer width. L and W are the channel length and width of the transistor, respectively.

Considering the effect of random placement of dopants, threshold voltages of all the transistors are represented by independent random variables with normal distribution. The variance of each random variable is obtained from Eq. (2).

Modeling the gate delay

Usually gate delay is a complicated non-linear function of the process parameters. In this work, we use first order Taylor's series expansions [START_REF] Chang | Statistical Timing Analysis Considering Spatial Correlations using a Single PERT-like Traversal[END_REF][START_REF] Visweswariah | First-order Incremental Block-Based Statistical Timing Analysis[END_REF] to approximate the delay distribution as follows,

D = D0 + n X i siXi (3)
D0 represents the nominal value of the gate delay (µD) without variation. We use Sakurai's gate delay model [START_REF] Sakurai | Delay analysis of series-connected MOSFET circuits[END_REF] to obtain the nominal delay of each gate in the circuit. Xi's are the sources of variation, which are modeled as normal random variables. Xi can be any process parameter such as channel length, width, oxide thickness and the threshold voltage, that affects the delay of a specific gate. si is the sensitivity of the gate delay to the variation in process parameter Xi. All si's are extracted through HSPICE simulation by varying the process parameters from their nominal value. The variance of the delay of a gate can be obtained as,

σ 2 D = n X i s 2 i σ 2 X i (4)
where σX i is the standard deviation of the random variable Xi.

Statistical Timing Analysis

The major challenge in statistical timing analysis is to incorporate the effect of signal correlation due to process variation. The signal correlation occurs due to both spatial correlation of process parameters and the random placement of dopants (affects the signal correlation on reconvergent paths). Hence, estimating the correlation between any two signals in a circuit will require a computation involving a large number of random variables which represent the process variation. While, the number of variables representing the variation in length, width and oxide thickness with spatial correlation can be limited by using the rectangular grid model explained in section 2.1, variation in threshold voltage (due to random placement of dopants) has to be represented by a large number of random variables (equal to the total number of transistors in a circuit).

To reduce the computational complexity of the above problem we propose a new algorithm for statistical timing analysis of circuits under process variation. The algorithm computes the signal arrival time at the output edge of each gate in a particular logic level. The arrival time information is then propagated to calculate the timing information of the next logic level. Finally, at the primary output, the circuit delay is obtained by applying the MAX function on all primary output arrival times. This technique is named as Levelized Covariance Propagation (LCP). Since the timing information (signal arrival times and their correlation) is always confined to a single logic level, in this technique the problem of signal correlation can be handled easily. Furthermore, we need only a few random variables (equal to the number of transistors in a gate) to effectively incorporate the effect of random placement of dopants.

Levelized Covariance Propagation

In this technique, the timing information at the output edges of a particular logic level is calculated using the signal information at its input edges and the delays of all gates in that logic level. The calculated timing information is then propagated to the next logic level. The statistical timing information contains;

1. The mean and the variance of signal arrival time at each output edge.

2. The covariances among the output signal arrival times.

3. The covariance between the output arrival time and the process parameters.

The above information is required to calculate the arrival times at the output of any gate considering the effects of process variation and the reconvergent paths. Consider the example circuit shown in Fig. 2. In this figure, the signal arrival time at the output edge of any gate (e.g., G1) depends on the gate delay, the signal arrival times at its inputs and their correlation information. The signal correlation at the inputs occurs due to (1) spatial correlation of process parameters and (2) the reconvergent paths (e.g., paths 1 and 2 in Fig. 2). Similarly, the correlation between the arrival times at the outputs of gates G1 and G2 is necessary to calculate the signal information at the next logic level. Furthermore, the delay of a gate depends on the signal arrival time at its corresponding input due to the spatial correlation of process parameters. For example, consider the signal path shown in Fig. 3. In the figure, signal to the input 1 of gate 3 propagates through gates 1 and 2. Since gates 1, 2 and 3 are closely located (within the same grid), the delays of these gates are highly correlated due to the spatial correlation of process parameters. Consequently, the delay of gate 3 (input 1 to output) will be strongly dependent on the signal arrival time at input 1, which is a function of the delays of gates 1 and 2. On the other hand, the signal to the input 2 of gate 3 propagates through gates 4 and 5, which are not geometrically close to gate 3 (located at different grids). Hence, the delay of gate 3 (input 2 to output) will be weakly correlated to the signal arrival time at input 2. Therefore, the geometric information of the preceding gates along with the input arrival time is necessary to accurately calculate the delay of a gate.

We explain below the methodology to calculate the statistical timing information at the outputs of a logic level.

Mean and variance

The mean and the variance of signal arrival time at the output edge of a gate is calculated using the input arrival time and the corresponding gate delay. To show how we calculate the signal information at the output edges, let us consider the example of a 2-input gate. The mean and the variance of the signal arrival time at the output of the gate can be obtained using the MAX function as follows,

Aout = MAX(Ain,1 + D1, Ain,2 + D2) (5)
where Ain,1, Ain,2 are respectively, the signal arrival times at input 1 and 2. D1 and D2 are the corresponding pin-to-pin delays of the gate. The mean (µA out ) and the sigma (σA out ) are obtained using the technique described in [START_REF] Clark | The Greatest of a Finite Set of Random Variables[END_REF] as follows,

µA out = µS 1 Φ(α) + µS 2 Φ(-α) + βφ(α) (6) σ 2 Aout = (µ 2 S 1 + σ 2 S 1 )Φ(α) + (µ 2 S 2 + σ 2 S 2 )Φ(-α) + (µS 1 + µS 2 )βφ(α) -µ 2

Aout

where,

Si = Ain,i + Di; i = 1, 2 (7)
µS i = µA in,i + µD i σ 2 S i = σ 2 A in,i + σ 2 D i + 2 • cov(Ain,i, Di) µA in,i
,σA in,i , µD i and σD i are the mean and the standard deviation of input arrival time and the gate delay, respectively. cov(Ain,i, Di) are the covariance between the input arrival time and the corresponding gate delay. α and β in Eq. ( 6) are given by,

α = (µS 1 -µS 2 )/β (8) β 2 = σ 2 S 1 + σ 2 S 2 -2σS 1 σS 2 ρ (9)
where, ρ = cov(S1, S2)/σS 1 σS 2 (10) cov(S1, S2) = cov(Ain,1, D2) + cov(Ain,2, D1) + cov(Ain,1, Ain,2) + cov(D1, D2) Φ(α) and φ(α) in Eq. ( 6) represent the CDF (cumulative distribution function) and PDF (probability density function) of standard normal distribution, respectively.

The mean (µA out ) and variance (σ 2 Aout ) of the arrival time at the output of a 2-input gate thus, can be obtained using the signal information of the input edges such as input arrival time information (µA in,i and σA in,i , i = 1, 2), gate delay information (µD i and σD i ) and the covariance information ( cov(Ain,1, Ain,2), cov(Ain, D) and cov(D1, D2)). µAin,i, σAin,i and cov(Ain,1, Ain,2) are obtained from the previous logic level. µD i , σD i are obtained using Eq. ( 3) and 4. cov(D1, D2) can be calculated using Eq. ( 3) and ( 4) as follows,

cov(D1, D2) = cov(D1,0 + n X i s1,iXi, D2,0 + n X i s2,iXi) = n X i n X j s1,is2,jcov(X1,i, X2,j) (11)
where Xi's are the random variables representing the parameter variation in length, width, oxide thickness and the threshold voltage. Since D1 and D2 represent the delay of the same gate, they are correlated by the parameter variations of all the transistors in that gate. While due to the spatial correlation, a single random variable can be used to represent the variation in a process parameter (length, width, or oxide thickness) for all transistors in the gate, theoretically separate variables should be used to represent the variation in threshold voltage (due to the random placement of dopants) of individual transistor. However, the covariances among the threshold voltage variations of different transistors will be zero (cov(X V th i , X V th j ) = 0; i = j, where X V th represents the variation in threshold voltage). Hence, the Eq. ( 11) is simplified to,

cov(D1, D2) = n X i s1,is2,iσ 2 X i (12)
where σX i 's are the standard deviation of the process parameter Xi. σ V th of each transistor in the circuit is pre-calculated and hence, no additional random variable is required in the algorithm to incorporate the threshold voltage variation due to random placement of dopants. cov(D1, D2) carries the information regarding the V th variation of all transistors in a gate. This information is used to calculate the correlation between the signals in reconvergent paths. Finally, cov(Ain, D) is obtained as follows,

cov(Ain, D) = cov(Ain, D0 + X i siXi) (13) = X i sicov(Ain, Xi)
where si's are the sensitivity of the gate delay to parameter variations. cov(Ain, Xi) is the covariance between the input signal arrival time and the process parameter variation, and is obtained from the previous logic level. Xi's are the random variables representing the variation in length, width and the oxide thickness. The correlation between the input arrival time and the threshold voltage variation will be zero due to the random placement of dopants.

Covariance among the output signals

We have mentioned above that in order to calculate the signal arrival time (µA out and σA out ) at the output of a gate in a particular logic level, covariance between the input signals are obtained from the previous logic level. In other words, the signal correlation information among all output edges of a particular logic level needs to be propagated to the next logic level. Consider the example circuit shown in Fig. 2. The covariance between the arrival times at the outputs of G1 and G2 can be expressed as,

cov(Aout,1, Aout,2) = cov(MAX(a1,1, a1,2), MAX(a2,1, a2,2)) (14)
where Aout,1 and Aout,2 are the signal arrival times at the output of gates G1 and G2, respectively. ai,j's are given by, ai,j = Ain,i,j + Di,j; i, j = 1, 2

where Ain,i,j represents signal arrival time at the j'th input of the i'th gate and Di,j is the corresponding pin-to-pin gate delay. In order to solve Eq. ( 14), we used the following relationship given in [START_REF] Clark | The Greatest of a Finite Set of Random Variables[END_REF].

cov(X, M AX(Y1, Y2))

= cov(X, Y1)Φ(α) + cov(X, Y2)Φ(-α) (16)
where, α can be obtained using Eq. ( 8). Using the above relationship, Eq. ( 14) can be rewritten as,

cov(Aout,1, Aout,2) (17)
= cov(a1,1, a2,12)Φ(αa) + cov(a1,2, a2,12)Φ(-αa)

= cov(a1,1, a2,1)t11 + cov(a1,1, a2,2)t12

+ cov(a1,2, a2,1)t21 + cov(a1,2, a2,2)t22 t11 = Φ(αa,1)Φ(αa,2), t12 = Φ(αa,1)Φ(-αa,2) t21 = Φ(-αa,1)Φ(αa,2), t22 = Φ(-αa,1)Φ(-αa,2) (a2,12 = MAX(a2,1, a2,2)) cov(a1,i, a2,j) are calculated as follows, cov(a1,i, a2,j) = cov(Ain,1,i, Ain,2,j) + cov(Ain,1,i, D2,j)

+ cov(Ain,2,j, D1,i) + cov(D1,i, D2,j) (18

)
where the first term in the right hand side of Eq. ( 18) is obtained from the previous logic level. The second and third terms are calculated using Eq. ( 13). The last term in Eq. ( 18) is obtained as follows,

cov(D1,i, D2,j) = X k X l s 1,i,k s 2,j,l cov(X 1,k , X 2,l ) (19)
where X1 and X2 are the random variables representing the process parameter variations in gate 1 and 2, respectively. s 1,j,k is the sensitivity of k'th parameter to the i'th delay of gate 1 (similarly s 2,j,l is the sensitivity of l'th parameter to the j'th delay of gate 2). Following the above method, the covariances among the arrival times at all output edges can be calculated. The covariance information is stored in an N × N matrix and propagated to the next logic level. Note that, the use of the above correlation information in timing analysis automatically takes care of the signal correlation due to the reconvergent paths.

Complexity of the Algorithm

In this section, we present a run-time complexity analysis of the proposed algorithm. Let us assume there are N number of gates and m logic levels in a given circuit. The computational complexity of the algorithm involves the calculation of (1) Means and variances, (2) covariances among the signal arrival times and (3) the covariances between signal arrival time and the process parameters. The computation time for (1) and ( 3) has linear dependency on the number of gates in a particular level. In addition to that, the computation time of (3) also depends on the number of random variables representing the spatial correlation of process parameters. On the other hand, the computation time for (2) depends quadratically on the number of gates in a particular logic level. This is because the covariances between all possible pairs of output signals are computed. Hence, the overall runtime complexity of the proposed algorithm can be expressed as,

m X i O(ni) + O(ni × k) + O(n 2 i ) (23)
where k is number of random variables representing the spatial correlation and ni is the number of gates in the i'th logic level. It can be seen that the complexity of the proposed algorithm depends mostly on the number of gates in a logic level. If ni is large, the overall complexity will be dominated by the third term (O(n 2 i )) in Eq. ( 23) and will quadratically depend on ni.

Simulation Results

The proposed statistical timing algorithm was implemented in C. We used this algorithm to calculate the circuit delay of several ISCAS benchmark circuits. All the circuits were synthesized using BPTM 70nm technology [START_REF]Berkeley Predictive Transistor Model[END_REF]. We assumed 15% (3σ) variation in channel length, width, oxide thickness and the threshold voltage for all our experiments. A 16 × 16 rectangular grid structure is used to model the spatial correlation of parameters such as length, width and oxide thickness.

In order to verify the proposed algorithm, we also compared the simulation results with Monte-Carlo simulation. For a considerable accuracy in the analysis, we chose to run 10000 iterations for Monte-Carlo simulation. Fig. 5 shows the circuit delay distribution of IS-CAS c499 benchmark circuit. It can be observed from the figure that the circuit delay distribution obtained using the proposed algorithm (considering both spatial correlation and the effect of random placement of dopants) closely matches with the Monte-Carlo simulation result. However, the circuit delay analysis considering only the spatial correlation (case 2) provides optimistic results compared to the Monte-Carlo simulation. More specifically, statistical timing analysis considering only spatial correlation under-estimates the mean of the delay, while considering only the effect of random placement of dopants under-estimates the variance of the delay [START_REF] Bowman | Impact of Die-to-Die and Within-Die Parameter Fluctuations on the Maximum Clock Frequency Distribution for Gigascale Integration[END_REF].

Table . 1 shows the circuit delays of several ISCAS benchmark circuits considering both the spatial correlation and the effect of random placement of dopants (LCP). It also shows the error in mean and standard deviation of the circuit delay compared to the results obtained through Monte-Carlo simulation (MC). Results show that the average errors in mean and standard deviation were 0.21% and 1.07%, respectively.

Conclusion

In this paper, we proposed a new statistical timing algorithm using Levelized Covariance Propagation. This algorithm incorporates both the spatial correlation and the effect of random placement of dopants in the channel in calculating the circuit delay distribution. The simulation results on several ISCAS benchmark circuits show that the proposed algorithm matches with Monte-Carlo simulation. We have also shown that the complexity of the algorithm depends quadratically on the number of gates in a logic level.

Figure 2 .

 2 Figure 2. Example of signal correlation

Figure 3 .

 3 Figure 3. Dependency of gate delay on the input arrival time

Figure 5 .

 5 Figure 5. Circuit delay distribution of c499; case 1: with considering the spatial correlation, case 2: with considering both the spatial correlation and the random placement of dopants

0,1 1,2 2,6 2,5 2,2 2,1 1,1 1,4 1,3 2,8 2,7 2,4 2,3 2,14 2,13 2,10 2,9 2,16 2,15 2,12 2,11

Table 1 . Simulation results for ISCAS benchmark circuits

 1

	Circuit	No. of logic TR depth	MC	Mean delay(ps) LCP error (%)	MC	delay sigma(ps) LCP error (%)	CPU-time (s) MC LCP
	c74L85	148	11	118.78	119.01	0.20	12.22	12.12	0.81	1.86	0.28
	c74181	372	17	197.26	197.35	0.05	18.44	18.50	0.37	2.87	0.39
	c432	590	28	531.06	530.91	0.03	26.74	26.73	0.06	4.03	0.55
	c1908	1582	38	531.30	533.13	0.34	38.54	38.05	1.28	11.81 0.63
	c880	1642	30	364.48	364.00	0.13	31.11	31.17	0.18	12.87 0.86
	c499	1816	29	380.43	381.46	0.27	29.91	28.93	3.28	14.48 0.67
	c3540	3638	43	609.63	612.54	0.48	40.64	40.24	0.99	24.55 1.19
	c5315	6284	45	558.80	557.73	0.19	45.81	46.82	2.19	46.10 2.78
	c6588	9472	122	1646.40 1648.52	0.13	123.82 123.78	0.03	63.19 3.70

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

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

* The work is sponsored in part by Marco Gigascale Systems Research Center (GSRC), Intel Corp. and Semiconductor Research Corp. (SRC).

Covariance between the signal arrival time and the process parameters

The covariance between signal arrival time at the output of a 2-input gate and the process parameters can be expressed as,

where X is set of the random variables representing the variation in length, width and the oxide thickness. Ain's and D's are respectively, the arrival times at the inputs and the corresponding pin-to-pin delays of the gate. cov(Ain,1, X) and cov(Ain,2, X) are obtained from the previous logic level. cov(Di, X) is calculated using Eq. (3) as,

where Xj's are random variables representing the spatial correlation of the process parameters. cov(Xj , X)'s are obtained using the covariance matrix described in section 2.1. Similarly, the covariance between all output signals and the process parameters are obtained and the covariance information is stored in an N × M matrix (M is the number of random variables used to model the spatial correlation of process parameters) and propagated to the next logic level.

Statistical Timing Analysis Algorithm

Fig. 4 shows the flow diagram of the proposed algorithm. The algorithm starts with levelizing the logic gates in a given circuit. In the second step, the algorithm is initialized by feeding the signal information to the primary inputs of the circuit. The signal information contains;

• The mean (µA in ) and the variance (σ 2

A in ) of signal arrival time at each primary input.

• The covariances among the input signals (cov(Ain,i, Ain,j); i, j = 1, 2, ..., n;, where n is the number of primary inputs).

• The covariance between the input arrival time and the process parameters (cov(Ain, X)).

Based on the signal information at the primary input, the signal information at the output edges of logic level 1 is calculated using the method described in the previous section. The signal information is then propagated to the next logic level. Finally, at the primary output we apply the MAX function to calculate the circuit delay. Dcircuit = MAX(APO,out,1, APO,out,2, ..., AP O,out,n)

where AP O,out,i is the arrival at the i'th primary output, and n represents the total number of primary outputs.


Shahin Nazarian

Massoud Pedram

Emre Tuncer

Tao Lin

Amir H Ajami

Modeling and Propagation of Noisy Waveforms in Static Timing Analysis

A technique based on the sensitivity of the output to input waveform is presented for accurate propagation of delay information through a gate for the purpose of static timing analysis (STA) in the presence of noise. Conventional STA tools represent a waveform by its arrival time and slope. However, this is not an accurate way of modeling the waveform for the purpose of noise analysis. The key contribution of our work is the development of a method that allows efficient propagation of equivalent waveforms throughout the circuit. Experimental results demonstrate higher accuracy of the proposed sensitivity-based gate delay propagation technique, SGDP, compared to the best of existing approaches. SGDP is compatible with the current level of gate characterization in conventional ASIC cell libraries, and as a result, it can be easily incorporated into commercial STA tools to improve their accuracy.

Introduction

STA tools require accurate delay models for gates and interconnects. The function of a gate delay model is to take a (noisy) input waveform at the far-end of the interconnect (e.g., in_u in Figure 1) and produce the waveform for the gate output (out_u.) This process is known as the gate delay propagation.

Most STA tools model the noisy input waveform at in_u with an equivalent linear waveform, eff , with a single reference point (input arrival time) and a constant slope (an effective input slew.) However, different waveforms with identical arrival time and slew when applied at in_u can result in very different propagation delays through 4INV x . Generally speaking, as the crosstalk noise becomes more significant in current technologies, using only a reference point and a constant slope to convey the timing information for a signal transition adversely impacts the accuracy of STA tools. More precisely, the actual shape of the input waveform should be considered to ensure accuracy.

R C C R C C R C C R C C R C C R C C C m C m C m

INVx

2

Conventional Gate Delay Propagation Techniques

Point-Based

A technique, denoted as P1, sets the input slew of eff to the time from the 0.1V dd to 0.9V dd crossing points of the noiseless waveform as though the waveform had not been affected by the noise. Another technique, called P2, uses the time from the earliest 0.1V dd crossing point to the latest 0.9V dd crossing point of the noisy waveform as the effective slew of eff . Both techniques set the 0.5V dd point of the eff to the latest 0.5V dd crossing point. P1 and P2 may be too optimistic in some cases because of the way that they calculate the slew of eff . They can also be too pessimistic in other cases because of the way they calculate the arrival time.

Least Squared Error-Based

A technique, denoted by LSF3, finds eff such that the sum of the squares of the sampled differences between eff and the input noisy waveform is minimized. LSF3 can show pessimistic or optimistic behavior because it is simply a mathematical approach to match a waveform without any consideration of the logic gate behavior.

Energy-Based

Inspired by the Elmore delay idea [START_REF] Elmore | The transient response of damped linear networks with particular regard to wideband amplifiers[END_REF], another technique, denoted as E4, passes eff through the latest 0.5V dd crossing point of the noisy voltage waveform. The slope is then selected such that the area which is encapsulated by that line, and straight lines v 1 (t) = 0.5V dd and v 2 (t) = V dd is equal to the area that is enclosed by the noisy input and lines v 1 and v 2 . In general, the more times the noisy waveform passes through the 0.5V dd level, the higher is the probability for this approach to produce pessimistic estimates.

2.4

Weighted Least Squared Error-Based Recently, a technique, which we will denote as WLS5, has been suggested in [START_REF] Hashimoto | Equivalent waveform propagation for static timing analysis[END_REF] that multiplies a weight factor to each squared term in the minimization equation of LSF3. This factor is defined as the derivative of the output to input signal for the noiseless input. WLS5-Step 1: Finding the derivative of the output to the noiseless input. For each logic cell, the derivative of the output to the noiseless input waveform, noiseless , is calculated as: , which are in turn set to time instances at which the noiseless input crosses the 0.1V dd and 0.9V dd levels, respectively. WLS5-Step 2: Finding eff . WLS5 finds eff with coefficients a and b such that Equation 2 is minimized (P denotes the number of sampling points in this paper):

dt t v dt t v t v t v t noiseless in noiseless out noiseless in noiseless out noiseless ) ( ) ( ) ( ) ( ) ( (1
1 0 2 } )) ( ) ( )( ( { P k k k noisy in k noiseless b t a t v t ( 2
)
The noiseless critical region in WLS5 acts as a filter. If the noise distortion occurs outside the noiseless critical region, then it will be ignored. Our experiments confirm that limiting the noise consideration to this range only, makes WLS5 inaccurate. Moreover, the higher the number of aggressors is, the higher is the probability that WLS5 underestimates the arrival time and/or slew at the output of the gate by a large amount.

Another weak point of WLS5 is that it is meaningful as long as the noiseless input and output waveform overlap each other; otherwise, the derivative of output to input is undefined. Therefore, WLS5 cannot be applied to gates with large intrinsic delay such as multi-stage gates, and/or those with large fanout loadings, where the input and output transitions may not overlap.

SGDP: Sensitivity-Based Gate Delay Propagation

This section describes the main steps of the proposed SGDP.

Calculation

Steps SGDP-Step 1: Finding the derivative of the output to the noiseless input. This step is the same as that in WLS5.

SGDP-

Step 2: Estimation of the derivative of the output to the noisy input. This step produces an approximation of eff , which denotes the derivative of the output with respect to the noisy input voltage waveform. ) is minimized. Equation 3 is an approximation of out using the first two terms of Taylor series: To address the weakness of WLS5 for gates with nonoverlapping input and output voltage transitions, SGDP adds additional pre-and post-processing steps as follows: SGDP-Additional step for non-overlapping input and output waveforms only: SGDP shifts the output back in time by an amount such that 0.5V dd for both the input and output voltage waveforms coincide. It then performs SGDP-Steps 1, 2, and 3. Finally, it shifts the equivalent input line forward in time by .

) 3 ( } )) ( ) ( ( ) ( ) ( 2 1 ) ) ( ) ( ( ) ( { 2 1 0 b t a t v t v t b t a t v t k k noisy in k noisy in k eff P k k k noisy in k eff

4

Experimental Results

Accuracy Comparison

Table 1 shows the gate delay errors for all of the techniques discussed in this paper, including SGDP, compared to Hspice. The gate delay was calculated as the difference between the 0.5V dd crossing points of the input and output waveforms.

Configuration I is the one depicted in Figure 1 with total coupling value of 100fF. We used standard inverter cells of an industrial TSMC 0.13µ cell library in our experiments. Both aggressor and victim line inputs, in_x and in_y, were 1000 m long and were given a slew of 150ps. Configuration II includes two aggressors x1 and x2 each with 100fF total coupling capacitance. These aggressors and the victim line, y, were each 500 m long and modeled similarly to the interconnects in Figure 1. 200 noise injection timing cases in a range of 1ns were analyzed for each configuration. Results are reported in Table 1. SGDP shows higher accuracy compared to all existing techniques. For instance, for configuration II, the average (maximum) delay error reduction is 2.6ps (4.8ps) compared to WLS5, which is the most accurate technique among the conventional ones. Therefore SGDP reduces the average (maximum) delay error by %15 (%10) over WLS5.

Run-Time Comparison

Although the worst case computational complexity of all techniques including the SGDP can be proved to be of linear order with respect to P, in practice, we observed different run times. On average P1, P2, and LSF3, and E4 take about 40µs and WLS5 takes about 60µs to accomplish delay propagation through a typical logic gate on a Sun Blade 1000 machine. In contrast, both WLS5 and SGDP (with P = 35) take about 65µs. The SGDP run-time can be reduced by using smaller P values. However small P tends to result in lower timing analysis accuracy.

Conclusions

This paper presented a technique to efficiently propagate gate delay information for noisy waveform for the purpose of STA. Without any additional library characterization, it utilizes the sensitivity of the output to the noisy input waveform to model the impact of the shape of the waveform. Experiments demonstrate that this technique is more accurate than any existing technique e.

Figure 1 .

 1 Figure 1. Our experimental setup. R=8.5 , C=4.8fF.

Figure 2 .

 2 Figure 2.b depicts eff , eff , and eff out v as calculated by SGDP.

Figure 2 .

 2 Figure 2. Waveforms of a) noiseless , and b) eff , eff , and eff out v .

  )

	where	v noiseless in	(t	)	and	v noiseless out	(t	)	are the noiseless input and its
	resulting output voltage values at time t, respectively. Note that
	noiseless	(t	)	is equal to the ratio of output slew to noiseless input
	slew (Figure 2.a.) This weight factor is non-zero only for points in
	a critical region, called the noiseless critical region, and is
	considered to be zero outside that region. The noiseless critical
	region is defined between noiseless first t	and noiseless last t

Table 1 : Accuracy comparison among all techniques.

 1

			Delay Error (ps)
	Method	Configuration I	Configuration II
		Max	Avg	Max	Avg
	P1	81.3	29.3	134.2	48.5
	P2	82.7	24.5	144.5	51.3
	LSF3	75.1	30.9	110.8	45.4
	E4	82.3	14.5	145.3	33.4
	WLS5 42.4	10.3	49.3	17.4
	SGDP 38.3	9.2	44.5	14.8

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


Mehrdad Reshadi
email: reshadi@cecs.uci.edu

Nikil Dutt
email: dutt@cecs.uci.edu

Generic Pipelined Processor Modeling and High Performance Cycle-Accurate Simulator Generation

Detailed modeling of processors and high performance cycleaccurate simulators are essential for today's hardware and software design. These problems are challenging enough by themselves and have seen many previous research efforts. Addressing both simultaneously is even more challenging, with many existing approaches focusing on one over another. In this paper, we propose the Reduced Colored Petri Net (RCPN) model that has two advantages: first, it offers a very simple and intuitive way of modeling pipelined processors; second, it can generate high performance cycleaccurate simulators. RCPN benefits from all the useful features of Colored Petri Nets without suffering from their exponential growth in complexity. RCPN processor models are very intuitive since they are a mirror image of the processor pipeline block diagram. Furthermore, in our experiments on the generated cycle-accurate simulators for XScale and StrongArm processor models, we achieved an order of magnitude (~15 times) speedup over the popular SimpleScalar ARM simulator.

Introduction

Efficient and intuitive modeling of processors and fast simulation are critical tasks in the development of both hardware and software during the design of new processors or processor based SoCs. While the increasing complexity of processors has improved their performance, it has had the opposite effect on the simulator speed. Instruction Set Simulators simulate only the functionality of a program and hence, enjoy simpler models and well established high performance simulation techniques such as compiled simulation and binary translation. On the other hand, cycle-accurate simulators simulate the functionality and provide performance metrics such as cycle counts, cache hit ratios and different resource utilization statistics. Existing techniques for improving the performance of cycleaccurate simulators are usually very complex and sometimes domain or architecture specific. Due to the complexity of these techniques and the complexity of the architecture, generating retargetable high performance cycle-accurate simulators has become a very difficult task.

To avoid redevelopment of new simulators for new or modified architectures, a retargetable framework uses an architecture model to automatically modify an existing simulator or generate a customized simulator for that architecture. Flexibility and complexity of the modeling approach as well as the simulation speed of generated simulators are important quality measures for a retargetable simulation framework. Simple models are usually limited and inflexible while generic and complex models are less productive and generate slow simulators. A reasonable tradeoff between complexity, flexibility and simulation speed of the modeling techniques has been seldom achieved in the past. Therefore, automatically generated cycle-accurate simulators were more limited or slower than their manually generated counterparts.

Colored Petri Net (CPN) [START_REF] Jensen | Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use[END_REF] is a very powerful and flexible modeling technique and has been successfully used for describing parallelism, resource sharing and synchronization. It can naturally capture most of the behavioral elements of instruction flow in a processor. However, CPN models of realistic processors are very complex mostly due to incompatibility of a token-based mechanism for capturing data hazards. Such complexity reduces the productivity and results in very slow simulators. In this paper, we present Reduced Colored Petri Net (RCPN), a generic modeling approach for generating fast cycle-accurate simulators for pipelined processors. RCPN is based on CPN and reduces the modeling complexity by redefining some of CPN concepts and also using an alternative approach for describing data hazards. Therefore, it is as flexible as CPN but far less complex and can support a wide range of architectures. Figure 1 illustrates the advantages of our approach using an example pipeline block diagram and its corresponding RCPN and CPN models. It is possible to convert an RCPN to a CPN and hence reuse the rich varieties of analysis, verification and synthesis techniques that have been proposed for CPN. The RCPN is intuitive and closely mirrors the processor pipeline structure. RCPN provides necessary information for generating fast and efficient cycle-accurate simulators. For instance, our XScale [START_REF]Intel® XScale Microarchitecture for the PXA250 and PXA210 Applications Processors[END_REF] processor cycle-accurate simulator runs an order of magnitude (~15 times) faster than the popular SimpleScalar simulator for ARM [2].

Related Work

Detailed micro-architectural simulation has been the subject of active research for many years and several models and techniques have been proposed to automate the process and improve the performance of the simulators.

ADL based approaches such as ISDL [START_REF] Hadjiyiannis | ISDL: An instruction set description language for retargetability[END_REF], nML [START_REF] Fauth | Describing instructions set processors using nML[END_REF], and EXPRESSION [START_REF] Halambi | EXPRESSION: A Language for Architecture Exploration through Compiler/Simulator Retargetability[END_REF] take an operation-centric approach and automate the generation of code generators. These ADLs describe instruction behaviors in terms of basic operations, but do not explicitly support detailed pipeline control-path specification which limits their flexibility for generating micro-architecture simulators. The Sim-nML [START_REF] Rajesh | Processor modeling for hardware software codesign[END_REF] language is an extension to nML to enable cycle-accurate modeling of pipelined processors. It generates slow simulators and cannot describe processors with complex pipeline control mechanisms due to the simplicity of the underlying instruction sequencer.

Hardware centric approaches, such as BUILDABONG [START_REF] Teich | A joined architecture/compiler environment for ASIPs[END_REF] and MIMOLA [START_REF] Zimmerman | The MIMOLA design system: A computer-aided processor design method[END_REF], model the architectures at the register transfer level and lower levels of abstraction. This level of abstraction is not suitable for complex microprocessor modeling and results in very slow cycleaccurate simulators. Similarly, ASim [START_REF] Emer | A performance model framework[END_REF] and Liberty [START_REF] Vachharajani | Microarchitectural exploration with Liberty[END_REF] model the architectures by connecting hardware modules through their interfaces. Emphasizing reuse, they use explicit port-based communication which increases the complexity of these models and have a negative effect on the simulation speed.

SimpleScalar [2] is a tool-set with significant usage in the computer architecture research community and its cycle-accurate simulators have good performance. It uses a fixed architectural model with limited flexibility through parameterization. Babel [START_REF] Mong | A Retargetable Micro-architecture Simulator[END_REF] was originally designed for retargeting the binary tools and has been recently used for retargeting the SimpleScalar simulator. Running as fast as SimpleScalar, UPFAST [START_REF] Onder | Automatic generation of microarchitecture simulators[END_REF] takes a hardware centric approach and requires explicit resolution of all pipeline hazards. Chang et al [START_REF] Chang | Fast Specification of Cycle-Accurate Processor Models[END_REF] have proposed a hardware centric approach that implicitly resolves pipeline hazards in the cost of an order of magnitude slow down in simulation performance. FastSim [START_REF] Schnarr | Fast Out-Of-Order Processor Simulation Using Memoization[END_REF] uses the Fast-Forwarding technique to perform an order of magnitude (5-12 times) faster than SimpleScalar. Fast-Forwarding is one of very few techniques with such a high performance; however, generating simulators based on this technique is very complex. To decrease this complexity, Facile [START_REF] Schnarr | Facile: A language and compiler for highperformance processor simulators[END_REF] has been proposed to automate the process. But the automatically generated simulators suffer significant loss of performance compared to FastSim and run only 1.5 times faster than SimpleScalar. Besides, modeling in Facile requires more understanding of the Fast-Forwarding technique rather than the actual hardware being modeled.

LISA [START_REF] Pees | LISA-machine description language for cycleaccurate models of programmable DSP architectures[END_REF] uses the L-chart formalism to model the operation flow in the pipeline and simplifies the handling of structural hazards. It has been used to generate fast retargetable compiled simulators. The flexibility of LISA is limited by the L-chart formalism and handling behaviors, such as data hazards, requires explicit coding in C language. Operation State Machine (OSM) [START_REF] Qin | Flexible and Formal Modeling of Microprocessors with Application to Retargetable Simulation[END_REF] models a processor in two layers: hardware layer and operation layer. The hardware layer captures the functionality and connectivity of hardware components, simulated by a discrete event simulator. The operation layer captures the flow of operations in the hardware using Finite State Machines (FSMs). The FSMs communicate with the underlying hardware components by exchanging tokens (events) through Token Manager Interfaces (TMI), which define the meaning of these tokens. The generated simulators in this model run as fast as SimpleScalar.

Petri Nets have also been used for modeling processors [START_REF] Razouk | The use of Petri Nets for modeling pipelined processors[END_REF]. They are very flexible and powerful and additionally, allow several formal analyses to be performed. Simple Petri Net models are also easy to visualize. Colored Petri Nets [START_REF] Jensen | Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use[END_REF] simplify the Petri Nets by allowing the tokens to carry data values. However, for complex designs, as that of processor pipeline, their complexity grows exponentially which makes modeling very difficult and significantly reduces simulation performance. In this paper, we propose the Reduced Colored Petri Net (RCPN) model which benefit from Petri Net features while being simple and capable of deriving high performance cycle-accurate simulators. It is an instruction-centric approach and captures the behavior of instructions in each pipeline stage at every clock cycle via modified and enhanced Colored Petri Net concepts.

Reduced Coloured Petri Net

To describe the behavior of a pipelined processor, operation latencies and data, control and structural hazards must be captured properly. A token based mechanism, such as CPN, can easily model variable operation latencies and basic structural and control hazards. Because of architectural features such as register overlapping, register renaming and feedback paths, capturing data hazards using a token based mechanism is very complex and difficult. In RCPN, we redefine the concepts of CPN to make it more suitable for processor modeling and fast simulation. As for the data hazards, we use a separate mechanism that is explained in Section 3.1.

Figure 2(a) shows a very simple pipeline structure with two latches and four units and Figure 2(b) shows the CPN model that captures its structural hazards. In this figure, circles show places (states), boxes show transitions (functions) and black dots represent tokens. In CPN, a transition is enabled when it has one token of proper type on each of its input arcs. An enabled transition can fire and remove tokens from its input places and generate tokens for its output places. In this pipeline, if latch L 2 is available and a proper instruction is in latch L 1 , then the functionality of unit U 2 is executed, L 2 is occupied and L 1 becomes available for next instruction. This behavior is represented by the availability of tokens in Figure 2(b). Here, whenever U 1 is enabled, it removes the token of L 1 and puts it in P 1 . Then, if L 2 has a token, U 2 can fire and move a token from P 1 to L 1 and from L 2 to P 2 . In other words, whenever a token is in place L 1 , it means that latch L 1 in Figure 2(a) is available and unit U 1 can send a new instruction into it; and whenever a token is in place P 1 , it means that an instruction is available in latch L 1 and unit U 2 or U 4 can use it. The back-edges (dotted lines) create circular loops. The number and complexity of these loops in the CPN of a typical pipeline grows very rapidly with its size. These loops not only make the CPN models very complex, they are also the main obstacle in generating high performance simulators.

RCPN(c) models

The RCPN model is based on the same concept as CPN; i.e. when a transition is enabled, it fires and removes tokens from the input places and generates tokens for the output places. In RCPN processor models, structural hazards, control hazards and variable operation latencies are naturally modeled by tokens, places, transitions and delays. To simplify processor models, we redefine these concepts in RCPN as follows:

Places: A place shows the state of an instruction. To each place a pipeline stage is assigned. A pipeline stage is a latch, reservation station or any other storage element in the pipeline that an instruction can reside in. For each pipeline stage that an instruction may go

L1 U1 U2 U3 U4 L1 L2 end end S3 S2 S1 •L1 U1 U2 U3 U4 P1 P2 •L2 •• U1 U3 U2 U4 L1 L2
through, there will be at least one place in the model. Each pipeline stage has a capacity parameter that determines how many tokens (instructions) can reside in it at any time. We assume when instructions finish they go to a final virtual pipeline stage, called end, with unlimited capacity. The places to which this virtual final stage is assigned represent the final state of the corresponding instructions. In RCPN, each place is shown with a circle in which the name of the corresponding pipeline stage is written. Places with similar name share the capacity of their pipeline stage. The tokens of a place are stored in its pipeline stage.

Transition: A transition represents the functionality that must be executed when the instruction changes its state (place). This functionality is executed (fired) when the transition is enabled. A transition is enabled if its guard condition is true and there are enough tokens of proper types on its input arcs AND the pipeline stages of the output places have enough capacity to accept new tokens. A transition can directly reference non-pipeline units such as branch predictor, memory, cache etc. The transition may use the functionality of these units to determine the type, value and delay of tokens that it sends to its output places.

Arc: An arc is a directed connection between a place and a transition. An arc may have an expression that converts the set of tokens that pass through the arc. For deterministic execution, each output arc of a place has a priority that shows the order at which the corresponding transitions can consume the tokens and become enabled.

Token: There are two groups of tokens: reservation tokens that carry no data and their presence in a place indicates the occupancy of the place's corresponding pipeline stage; and instruction tokens that carry complex data depending on the type of the instruction.

Instruction tokens are the main focus of the model since each instruction token represents an instruction being executed in the pipeline. In other words, RCPN describes how an individual instruction flows through stages of the pipeline. In any RCPN, there is one instruction independent sub-net that generates the instruction tokens, and for each instruction type, there is a corresponding sub-net that distinctively describes the behavior of instruction tokens of that type. Figure 2(c) shows the RCPN model of the simple pipeline shown in Figure 2(a). The model is divided into three sub-nets: S 1 , S 2 and S 3 . S 1 describes the instruction independent portion that generates two types of instruction tokens. Note that as long as state L 1 has room for a new token, transition U 1 can fire. In fact, because of our new definition of "transition enable", an RCPN model can start with a transition as well as a place. Any sub-net can generate an instruction token and send it to its corresponding sub-net. This is equivalent with instructions that generate multiple micro operations in a pipeline (e.g. Multiple LoadStore instruction in XScale). As in real processor, instruction tokens never go through circular paths 1 .

A delay may be assigned to a place, a transition or a token. These delays have default values and can be changed at run time based on data values, etc. The delay of a place determines how long a token should reside in that place before it can be considered for enabling an output transition. The delay of a transition expresses the execution delay of the functionality of that transition. The delay of a token overwrites the delay of its containing place and has the same effect. By changing the delay of a token, a transition can indirectly change the delay of its output place.

Usually in microprocessors, the instructions that flow through a similar pipeline path have similar binary format as well. In other words, the instructions that go through the same functional units have similar fields in their binary format. Therefore, a single decoding scheme and behavior description can be used for such group of instructions which we refer to as an Operation Class. An operation 1 A token may stay in one stage and produce multiple tokens to go through the same path and repeat a set of behaviors.

class describes the corresponding instructions by using symbols to refer to different fields in their binary code. A symbol can refer to a Constant, a µ-operation or a Register. Using these symbols, for each operation class an RCPN sub-net describes the behavior of the corresponding instructions. During instruction decode, the actual values of these symbols are determined. Therefore, by replacing the symbols with their values, a customized version of the corresponding RCPN sub-net is generated for individual instances of instructions. Figure 4(b) shows examples of such operation classes. The details of using symbols and the decode algorithm are described in [START_REF] Reshadi | An Efficient Retargetable Framework for Instruction-Set Simulation[END_REF].

Capturing Data Hazards

To capture data hazards, we need to know when registers can be read or updated and if an instruction is going to update a register, what its state is at any time. In many processors, registers may overlap 2 and hence modifying one may affect the others. On the other hand, generally instructions use different pipeline stages to read source operands, calculate results, or update destination operands. Therefore, instructions must be able to hold register values after reading or before updating registers.

Figure 3-Register structure

Addressing all the above issues with a token based mechanism is very complicated and hence, in RCPN we use an alternative approach that explicitly supports a lock/unlock (semaphore) mechanism for accessing registers, temporary locations for register values, and registers with overlapping storage for data. As Figure 3 shows, we model registers at three levels:

Register File: It defines the actual storages for data, register renaming and pointer to instructions that will write to a register. There may be multiple register files in a design.

Register: Each register has an index and points to proper storages of the register file. Multiple registers, can point to the same storage areas to represent overlapping.

Register Reference (RegRef): Each RegRef points to a register and has an internal storage for storing the register value. A symbol in an operation class that points to a register is replaced by a proper RegRef during decode. In fact, RegRefs represent the pipeline latches that carry instruction data in real hardware. During simulation, this is almost equivalent with renaming registers for each individual instruction. RegRefs' internal values are used in the computations and the instructions access and update registers through RegRefs' interfaces. The interface is fixed and includes: canRead(), true if register is ready for reading; canRead(s), true if the instruction that is going to update the corresponding register is in state s at the time of call; read(), reads the values of corresponding register and stores it in the internal storage of RegRef; canWrite(), true if the register can be written; reserveWrite(), assigns the current RegRef pointer and its containing instruction as the writers of the corresponding register; writeback(), writes the internal value of the RegRef to the corresponding register and may reset its writer pointers; and read(s), instead of reading the value of the corresponding register, it reads the internal value of the writer RegRef whose containing instruction is in state s at the time of call. The read(s) interface provides a simple and 2 E.g. overlapping register-banks in ARM or register windows in SPARC. In RCPN, data hazards are explicitly captured by using Boolean interfaces, such as canRead, in the arcs' guard conditions; and using normal interfaces, such as read, in the transitions. These pairs of interfaces must be used properly to ensure correctness of the model. Whenever read(), reserveWrite() or read(s) appears in a transition, canRead(), canWrite() or canRead(s) must appear in the guard condition of its input arc, respectively.

The implementation of these interfaces may vary based on architectural features such as register renaming. For example, in a typical implementation of these interfaces, transition T 1 first checks r.canWrite() to check write-after-write and write-after-read hazards for accessing register r. Then it calls r.reserveWrite() to prevent future reads or writes. After calling r.writeback()in another transition, register r can be safely read or written. In RCPN, a symbol in an operation class that points to a constant is replaced by a Const object during decode. The Const object provides the same interface as of RegRef with proper implementation. For example, its canRead() always returns true; its writeback() does nothing and so on. In this way, data hazards can be uniformly captured using symbols in the operation class.

The next section demonstrates most of the RCPN modeling capabilities via an example. To model the feedback path, two arcs with different priorities come out of place L 1 and enter the ALU instruction sub-net. If the first arc, with priority 0, cannot read the value of first source operand, then the second arc, with priority 1, verifies that the writer instruction of operand s 1 is in the state L 3 and then reads it. Otherwise, the instruction is stalled in L 1 . After reading the source operand and reserving the destination for writing, the result is calculated in transition E and stored in the internal value of the destination d. This value is finally written back in transition W e .

Example RCPN Processor Model

In Branch instruction sub-net, the dotted arcs represent reservation tokens. Therefore in this example, when a branch instruction is issued, it stalls the fetch unit by occupying latch L 1 with a reservation token and disabling the fetch transition. In the next cycle, this token is consumed and the fetch unit is un-stalled. An alternative implementation is flushing L 1 and L 2 latches in transition B instead of using reservation tokens.

The LoadStore instruction sub-net demonstrates the use of token delay in transition M to model the variable delay of memory (cache). It also shows how data dependent delays can be modeled in RCPN. The component mem, referenced in this transition, can be used from a library or reused from other designs.

Figure 5-RCPN sub-nets

Processor RCPN models can be converted to standard CPN and use all the tools and algorithms that is available for CPN. Details of this conversion and more complex examples capturing VLIW and multiissue machines as well as RCPN model of the Tomasulo algorithm are detailed in our technical report [START_REF] Reshadi | RCPN: Reduced Colored Petri Nets for Efficient Modeling of Pipelined Processors and Generation of Very Fast Cycle-Accurate Simulators[END_REF].

Cycle-accurate Simulation

RCPN can generate very fast cycle-accurate simulators. Like any other Petri Net model, an RCPN model can be simulated by locating the enabled transitions and executing them concurrently. Searching for enabled transitions and handling concurrency can be very time consuming in generic Petri Net models especially if there are too many places and transitions in the design. However, a more careful look at the RCPN model reveals some of its properties that can be utilized to simplify these two tasks and speed up the simulation significantly.

Of the two groups of tokens in RCPN, reservation tokens carry no data and are used only to show unavailability of resources. Since transitions represent the functionality of an instruction between two pipeline stages, reservation tokens alone can not enable them. Therefore, only places that have an instruction token may have an enabled output transition. While a place may be connected to many transitions in different sub-nets, an instruction token only goes through transitions of the sub-net corresponding to its type. In other words, based on the type of an instruction token, only a subset of output transitions of a place may be enabled. Since the structure of RCPN model is fixed during simulation, for every place and instruction type the list of transitions that may be enabled can be statically extracted from the model before simulation begins. This list is sorted based on the priorities of output arcs of the place and processed accordingly. Figure 6 shows the pseudo code that extracts this list for each place in RCPN and each instruction type in the ISA and stores it in sorted_transitions table. This code is called before program simulation begins and hence has no runtime overhead for simulation. 7 shows the pseudo code for processing the output transitions of a place. It is called in each clock cycle to process the instructions that are in a particular state (place p). For each instruction, it finds the first transition that can be executed and move the instruction to its next state. The corresponding transitions list is looked up from the sorted_transitions table.

Figure 7-Processing places with instruction tokens

In RCPN, enabled transitions execute in parallel; tokens are simultaneously read from input places at the beginning of a processor cycle, and then, in parallel, written to the output places at the end of the cycle. Therefore, the simulator must ensure that the variables representing such places are all read before being written during a cycle. The usual, and computationally expensive solution, is to model such places using a two-list algorithm (similar to master/slave latches). This approach uses two token storages per place-one of them is read from, and the other written to in the course of a cycle. At the end of the cycle, the tokens in the written-to storage are copied to the read-from storage.

In general, we can ensure that all tokens from the previous cycle are read-from before being written-to by evaluating all places (or their corresponding pipeline stages) in reverse topological order. Therefore, only very few places that are referenced in a circular way, because of feedback paths like state L 3 in Figure 5, need to implement a two-list algorithm. The resulting code is considerably faster since it avoids the overheads of managing two storages in the two-list algorithm. Note that in CPN, this well-known optimization is not applicable because all resource sharings are modeled with circular loops of places. 8 shows the main body of our simulation engine. In the main loop, after updating the places that implement the two-list algorithm, all places are processed in reverse topological order. At the end of each iteration, the instruction independent sub-net of the model, which is responsible for generating the instruction tokens, is executed.

Experiments

To evaluate the RCPN model, we modeled both StrongArm [21] and XScale [START_REF]Intel® XScale Microarchitecture for the PXA250 and PXA210 Applications Processors[END_REF] processors using the ARM7 instruction set. StrongArm has a simple five stage pipeline. XScale is an in-order execution, outof-order completion processor with a relatively complex pipeline structure shown in Figure 9. The ARM instruction set was implemented using six operation-classes [START_REF] Reshadi | An Efficient Retargetable Framework for Instruction-Set Simulation[END_REF]. Using these operation classes, it took only one man-day for StrongArm and only three mandays for XScale to develop both the RCPN models and the simulators.

Figure 9-XScale pipeline

To evaluate the performance of the simulators we chose benchmarks from MiBench [23] (blowfish, crc), MediaBench [START_REF] Lee | Mediabench: A tool for evaluating and synthesizing multimedia and communications systems[END_REF] (adpcm, g721) and SPEC95 [25] (compress, go) suites. These benchmarks were selected because they use very few simple system calls (mainly for IO) that should be translated into host operating system calls in the simulator. We used arm-linux-gcc to generate the binary code of the benchmarks. The compiler only uses ARM7 instruction-set and therefore we only needed to model those instructions. The simulators were run on a Pentium 4/1.8 GHz/512 MB RAM.

Figure 10 compares the performance of the simulators generated from RCPN model with that of SimpleScalarArm. The first bar for each benchmark shows the performance of SimpleScalarArm simulator. This simulator implements StrongArm architecture and we disabled all checkings and used simplest parameter values to improve simulation performance. On the average this simulator executes 600k cycles/sec. The second and third bar for each benchmark shows the performance of our simulator for XScale and StrongArm processor models respectively. These simulators execute 8.2M cycles/sec and 12.2M cycles/sec on the average. SimpleScalar uses a fixed architecture for any processor model. Therefore, the complexity and performance of the simulator is similar across different models. On the other hand, RCPN models are true to the modeled processor and hence the complexity of generated simulators depends on the complexity of the processor that they simulate. Due to its simpler pipeline, the StrongArm simulator performs better that that of XScale. The RCPN based modeling approach does not impose any limitation on capturing instruction schedules. Therefore, by providing accurate models, the results of generated simulators can be fairly accurate. Such models are usually obtained by comparing the simulation results against either a base simulator or the actual hardware, and then refining the model information.

Figure 11-Clocks per instruction (CPI)

From modeling capability point of view, RCPN and OSM are comparable. However, OSM uses very few FSMs, e.g. only one FSM for StrongARM, and captures the pipeline through these FSMs and TMI software components. RCPN uses multiple sub-nets, each equivalent with an OSM, to explicitly capture the pipeline control. For example, there are six RCPN sub-nets in the StrongArm model. Only for capturing data hazards, RCPN relies on the fixed interface software components. Therefore, a larger part of processor behavior is captured formally in RCPN than in OSM. In other words, the non-formal part of OSM model (TMIs) is large enough that it needs a separate eventdriven simulation engine; but the non-formal part of RCPN model is a set of very simple functions for accessing registers. Nevertheless, RCPN based simulators run an order of magnitude faster than OSM based ones. Our simulators are as fast as FastSim while we use two simple optimizations and FastSim uses the very complex Fast-Forwarding technique. We can summarize the reasons of this high performance as follows:

• Because of RCPN features, we can reduce the overheads of supporting concurrency and searching for enabled transitions. • We apply partial evaluation optimization to customize the instruction dependent sub-nets for each instruction instance and hence improve their performance. • In RCPN, when an instruction token is generated, the corresponding instruction is decoded and stored in the token. Since the token carries this information, we do not need to re-decode the instruction in different pipeline stages to access its data. Furthermore, the tokens are cached for later reuse in the simulator. Since the simulator is generated automatically, debugging of the implementation of the simulator is (eventually) eliminated. Only the model itself must be debugged/verified. As [START_REF] Reshadi | An Efficient Retargetable Framework for Instruction-Set Simulation[END_REF] describes, using operation-classes and templates make debugging much simpler. Since RCPN is formal and can be converted to standard CPN, formal methods also can be used for analyzing the models.

Conclusion

In this paper, we presented the RCPN model for capturing pipelined processors. RCPN benefits from the same concepts as other Petri Net models and has two advantages: first, it provides an efficient way for modeling architectures; and second, it generates high performance cycle accurate simulators. RCPN models are very intuitive to generate because they are very similar to the pipeline block diagram of the processor. Our cycle-accurate simulators, for both StrongArm and XScale processors, run about 15 times on average faster than SimpleScalar for ARM, although XScale has a relatively complex pipeline.

The use of Colored Petri Net concepts in RCPN makes it very suitable for different design analysis and verification purposes. The clean distinction between different types of tokens and data hazard mechanism in addition to the structure of RCPN can be used to extract the necessary information for deriving retargetable compilers. The future direction of our research is to address these issues as well as extracting fast functional simulators from the same detailed RCPN models.

Acknowledgement

This work was partially supported by NSF grants: CCR-0203813 and CCR-0205712.

Figure 1 -

 1 Figure 1-Advantages of RCPN: Intuitive, Fast Simulation In this paper, Section 2 summarizes the related works. Section 3 describes the RCPN model and illustrates the details of the pipeline example of Figure 1. Section 4 explains the simulation engine and optimizations that are possible because of RCPN. Section 5 shows the experimental results and Section 6 concludes the paper.

Figure 2 -

 2 Figure 2-An Example Pipeline structure(a) and its CPN(b) andRCPN(c) modelsThe RCPN model is based on the same concept as CPN; i.e. when a transition is enabled, it fires and removes tokens from the input places and generates tokens for the output places. In RCPN processor models, structural hazards, control hazards and variable operation latencies are naturally modeled by tokens, places, transitions and delays. To simplify processor models, we redefine these concepts in RCPN as follows:Places: A place shows the state of an instruction. To each place a pipeline stage is assigned. A pipeline stage is a latch, reservation station or any other storage element in the pipeline that an instruction can reside in. For each pipeline stage that an instruction may go

  modeling data forwarding through feedback or bypass paths.

Figure 4 (Figure 4 -

 44 Figure4(a) shows the block diagram of a representative out-oforder completion processor with a feedback path. Figure4(b) shows three types of instructions (operation classes) in this processor. Each instruction consists of symbols whose actual value is determined during instruction decode. For example, the L symbol in LoadStore is a Boolean symbol and is true for loads and false for store instructions. To show the flexibility of the model, we assume that the feedback path is used only for the first source operand of ALU instructions (s 1 ). Branch { offset: {Register | Constant} }; ALU { op: {Add | Sub | Mul | Div | …} d, s1: {Register} s2 : {Register | Constant} }; LoadStore { L: {true | false} r: {Register} addr: {Register | Constant} }; (a) (b) Figure 4-Representative out-of-order processor Figure 5 shows the complete RCPN model of the above processor. It contains one instruction independent sub-net and three instruction specific sub-nets. The boxes show the functionality of transitions and the codes above them show their guard conditions. The guard conditions are written in the form of [cond 1 , cond 2 …] which is equivalent with: cond 1 ∧ cond 2 ∧ …To model the feedback path, two arcs with different priorities come out of place L 1 and enter the ALU instruction sub-net. If the first arc, with priority 0, cannot read the value of first source operand, then the second arc, with priority 1, verifies that the writer instruction of operand s 1 is in the state L 3 and then reads it. Otherwise, the instruction is stalled in L 1 . After reading the source operand and reserving the destination for writing, the result is calculated in transition E and stored in the internal value of the destination d. This value is finally written back in transition W e .In Branch instruction sub-net, the dotted arcs represent reservation tokens. Therefore in this example, when a branch instruction is issued, it stalls the fetch unit by occupying latch L 1 with a reservation token

Figure 6 -

 6 Figure 6-Extracting and sorting transition subsets Figure7shows the pseudo code for processing the output transitions of a place. It is called in each clock cycle to process the instructions that are in a particular state (place p). For each instruction, it finds the first transition that can be executed and move the instruction to its next state. The corresponding transitions list is looked up from the sorted_transitions table.

Figure 8 -

 8 Figure 8-Main body of simulation engineFigure8shows the main body of our simulation engine. In the main loop, after updating the places that implement the two-list algorithm, all places are processed in reverse topological order. At the end of each

Figure 10 -

 10 Figure 10-Simulation performance (Million cycle/second) Figure 11 compares the CPI values of SimpleScalarArm and our StrongArm simulator. This figure shows that although our simulator runs significantly faster than SimpleScalar, the CPI values of the two simulators are almost similar. The ~10% difference is due to the accuracy of the information in the model used for generating the simulator. The RCPN based modeling approach does not impose any

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

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


O Villa

P Schaumont

I Verbauwhede

M Monchiero
email: monchier@elet.polimi.it

¡ G Palermo
email: gpalermo£@elet.polimi.it

Fast Dynamic Memory Integration in Co-Simulation Frameworks for Multiprocessor System on-Chip

In this paper is proposed a technique to integrate and simulate a dynamic memory in a multiprocessor framework based on C/C++/SystemC. Using host machine's memory management capabilities, dynamic data processing is supported without compromising speed and accuracy of the simulation. A first prototype in a shared memory context is presented.

Introduction

MultiProcessor Systems on-Chip (MPSoC) [START_REF] Wolf | Multiprocessor System on-Chips[END_REF] are an appealing solution for complex applications and are becoming feasible in contemporary technology. Especially for these complex systems, designers need frameworks to fast evaluate different possible implementations of the target architecture that covers interconnect, communications protocol, and topology is needed. Typical applications that run on MPSoC manage large amount of data (such as audio/video processing). Simulating these application, memory management capabilities are required. If these details are introduced in the model the memory's simulation becomes a significant portion of the workload for the simulator, affecting the performance in terms of simulation speed. Therefore a good memory model for exploration should: (I) allow the execution of complex applications with huge amounts of dynamic data (II) be accurate (III) have a low overhead (IV) be easy to design. The contribution of this paper is the development of flexible and efficient techniques based on the use of the host machine dynamic memory capabilities.

Framework

Today Co-Simulation frameworks for MPSoC are based on the integration of ISSs with simulation kernels. A typical simulation framework can be seen in Figure 2, where dashed boxes represent our contribution. In most of the traditional simulation frameworks, the memory subsystem is modeled as standard hardware modules. Unless complex

Figure 1. Simulation Framework

and slow dynamic memory models are added, static memories implemented as tables are used. In our approach, dynamic hardware memory modules are simulated using a cycle true memory wrappers to access at the operating system functions which manages the host machine memory management capabilities. Dynamic memory operations like allocation, write/read and deallocation are implemented as communications between the hardware modules, or ISS, and the shared memory's wrapper. These operations are mapped by the wrappers in the native host machine functions, improving simulation speed. The wrapper guarantees the simulation accuracy using parameters of delays which can be dynamic and data dependent. Mechanisms to manage pointer arithmetic for user defined data-types, to model finite size memories and to reserve pointers in a shared memory context are proposed. High level APIs used by the ISSs are also provided using a C formalism. Multiple dynamic shared memories are considered and methods to manage general data structures are work in progress.

Dynamic Shared Memory

An implementation of our solution for multiple dynamic shared memories is employed in a system composed of sev-

Figure 2. Shared Memory Implementation

eral processing elements and an interconnect. In Figure 2, the overall simulated system is shown, as well as the details of the shared memory subsystem. Interconnect and shared memories are developed in C++. The simulation kernel is based on C++ [1] and the ISSs are ARM simulators [2].

The wrapper is composed of a cycle true part, described as a Finite State Machine (FSM), and a functional part, composed of a pointer table and a translator. In the FSM the communication is performed following a handshake protocol and incoming signals are evaluated cycle by cycle. Operations as allocation, read/write and deallocation are identified by an input code (opcode). The opcode and the shared memory address (sm addr), which identifies the memory module, are the first data of every transaction between the ISSs and the wrapper. Endianess, data type translation and host machine functional calls are performed by the translator led by the FSM. Virtual pointers for the simulated architecture, real host pointers to retrieve the data in the host machine are stored in the pointer table, as well as the size of the allocated spaces, type of allocated spaces and a reservation bit used as semaphore to reserve the pointers. When an allocation operation is required, size (dim) and data type (type) must be sent. The FSM maps this communication in a calloc(dim, DATA SIZE) operation to the host machine using the translator. A pointer is then returned by the host machine and stored in the table with the type and dim information. A virtual pointer (Vptr) is sent back to the ISS completing the transaction. Every new allocation is a new entry in the pointers table and a finite size memory can be simulated denying other allocations when the sum of the dimension reaches a prefixed limit. When a write operation is required, the virtual pointer (Vptr) and the data (DataIn) are provided. The pointer table is checked in order to see if the Vptr is valid and to retrieve the real host machine's pointer (Hptr). The DataIn is stored in the Hptr host location. Similar mechanisms are adopted for a read operation. In this case, the data retrieved in the host memory is sent as output data (DataOut) to the communication port by the FSM. For a free operation (deallocation), it is necessary to provide the Vptr. Then the entry associated to the Vptr in the pointer table is removed, the table is re-compacted and the dimension of the deallocated memory is subtracted to the total memory size. Finally, a free function, with the correspondent Hptr as argument, is performed on the host. The generation of the Vptr is performed in such way that every new Vptr is obtained summing the value of the previous Vptr in the table with the size of the previous allocated space (see the table in Figure 2). The first Vptr's value is zero by default. If pointer arithmetic is used to access to the memory, incoming virtual pointers values that are not present in the table are received. In this case, the true host memory space is retrieved checking in the pointer table which space belongs to the Vptr. The Hptr is, therefore, calculated adding an appropriate offset. When indexed structures are exchanged, the dimension of the transmitted arrays must be also sent together with Vptr. I/O registers are substituted by I/O arrays, where the incoming and outgoing data are temporally stored until the communication is completed. Afterward, they are moved to the host machine, employing a similar mechanism used for scalar data. Data coherence is guaranteed in our design preserving the Vptr by means of the reservation bit which is set by an ISS that want to protect the pointer. To model data dependent latencies, a set of delay parameters can be used in the FSM. Multiple instances are easily managed, since the host machine provides the generation of a different host pointer for every allocation. High level APIs very similar to the host machine functions are used by the ISSs. Different hardware devices that might be connected on the system can access to the memories using low level communication.

Conclusions

Preliminary experimental results, obtained simulating the GSM algorithm, show that the overhead in terms of simulation speed introduced by this model is very low. Comparing the simulation speed of 4 ISSs with one memory and interconnect and this of 4 ISSs with interconnect and 4 memories we found a degradation of simulation speed of 20%.

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

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