Shervin Sharifi
email: shervin@cad.ece.ut.ac.ir

Javid Jaffari

Mohammad Hosseinabady
email: mohammad@cad.ece.ut.ac.ir

Ali Afzali-Kusha

Zainalabedin Navabi
email: navabi@ece.neu.edu

Simultaneous Reduction of Dynamic and Static Power in Scan Structures

Power dissipation during test is a major challenge in testing integrated circuits. Dynamic power has been the dominant part of power dissipation in CMOS circuits, however, in future technologies the static portion of power dissipation will outreach the dynamic portion. This paper proposes an efficient technique to reduce both dynamic and static power dissipation in scan structures. Scan cell outputs which are not on the critical path(s) are multiplexed to fixed values during scan mode. These constant values and primary inputs are selected such that the transitions occurred on non-multiplexed scan cells are suppressed and the leakage current during scan mode is decreased. A method for finding these vectors is also proposed. Effectiveness of this technique is proved by experiments performed on ISCAS89 benchmark circuits.

Introduction

Power dissipation during test can be much larger than that of normal operation [START_REF] Girard | Survey of Low-Power Testing of VLSI Circuits[END_REF]. However, power constraints are defined for normal mode of operation. Since the current trend is to adopt low-power design techniques and to reduce the package size by exactly matching power dissipation during the circuit normal mode of operation, power constraints defined for the normal operation during the design phase may be much lower than the power consumed during test mode. Therefore, these constraints can be easily exceeded during test causing severe reliability problems. Therefore reducing power dissipation during test application is becoming a critical objective in today's VLSI circuit designs. Moreover, using special cooling equipment to remove excessive heat produced during test application is prevented by the trend toward circuit miniaturization, which makes it especially important to reduce power during test [START_REF] Girard | Survey of Low-Power Testing of VLSI Circuits[END_REF].

Power consumption in CMOS circuits can be dynamic or static. Dynamic dissipation occurs as a result of switching activities because of short-circuits current and charging and discharging of load capacitances. Static power consumption is the other portion of the power dissipation in CMOS circuits. Leakage currents including sub-threshold source-to-drain leakage, reverse bias junction band-to-band tunneling, gate oxide tunneling, and other current drawn continuously from the power supply cause static power dissipation.

Leakage current will become an important component in total power consumption because of its exponential relation with decrement in transistor threshold voltage and gate oxide thicknesses that are scaled down in the newer technologies. Since the dynamic power consumption has been the dominant part of power in the older technologies, test power solutions have focused only on this portion of total power dissipation, while static power dissipation is becoming very significant in circuit testing [START_REF] Kaushik Roy | Test Consideration for Nanometer Scale CMOS Circuits[END_REF].

Scan-based test is the most popular design-for-test (DFT) technique because of its low impact on performance and area. Power problem is a critical issue in this technique. In scan-based test, test vectors are shifted into the scan chains in order to be applied to the circuit-under-test (CUT). Transitions in the scan chain propagate into the CUT and produce several levels of unnecessary switching activities resulting in power dissipation.

Previous works on reducing scan power consumption have tried to reduce switching activity of the circuit.

In this paper, we present a novel solution for power problem in scan-based test. This solution not only reduces the switching activity, but reduces the static power which is consumed in the circuit during test. Hardware area and the required modifications are minimal. Our technique does not have any impact on test time and the maximum working frequency of the circuit in the normal mode. It requires no extra control signals and does not have any routing overhead. Fault coverage is not affected by this method.

The next section reviews some related previous works and Section 3 provides some required backgrounds. The proposed method is explained in Section 4. Section 5 describes and discusses the results and concludes the paper.

Previous works

Many research works have tried to solve the power problem in scan-based test architectures. [START_REF] Wang | An Automatic Test Pattern Generator for Minimizing Switching Activity During Scan Testing Activity[END_REF] proposed an ATPG which exploits all possible "don't cares" that occur during scan shifting, test application, and response capture to minimize switching activity in the circuit under test.

When a scan-based circuit is in the scan mode, transitions of the scan chain may propagate to the combinational part and cause unnecessary power dissipation. In test-per-scan schemes, intermediate values of scan chains do not contribute to the fault coverage. So by preventing scan chain transitions from affecting circuit inputs during scan operations, test power can be reduced without affecting the fault coverage.

[4] proposes a scan chain modification methodology that transforms the stimuli to be inserted to the scan chain through logic gate insertion between scan cells, reducing scan chain transitions.

In [START_REF] Hertwig | Low Power Serial Built-In Self-Test[END_REF], scan cells are modified such that scan chain transitions are completely isolated from the combinational part of the circuit.

In enhanced scan structures, hold latches are inserted at scan cell outputs. Before starting a new scan operation, previous values of the scan cells are latched. Therefore, CUT inputs remain unchanged when test data is being shifted in the scan chain.

Reference [START_REF] Sankaralingam | Inserting Test Points to Control Peak Power During Scan Testing[END_REF] presents a procedure for inserting test points at the outputs of scan elements of a full-scan circuit in such a manner that the peak power during scan testing is kept below a specified limit while maintaining the original fault coverage. The main drawback of this approach is addition of a global signal to enable test points.

In [START_REF] Sharifi | Reducing Test Power, Time and Data Volume in SoC Testing Using Selective Trigger Scan Architecture[END_REF], data required for updating scan vectors are shifted in a separate chain which is included in the design for compression purposes. Scan chain contents are updated after shifting the required data. So the transitions at circuit inputs are limited to the differences between two subsequent scan vectors. [START_REF] Huang | Reduction of power consumption in scan-based circuits during test application by an input control technique[END_REF] proposes an input control technique to reduce the transition count of the combinational part of a full-scan circuit during test application.

If a pattern can be applied to the PIs during scan such that the propagation through the combinational circuit can be reduced or even eliminated, then the unnecessary power consumption can be saved. An algorithm called C-algorithm is proposed which finds such an input pattern for reducing the number of transitions using a Dalgorithm-like method.

As mentioned before, in scaling the transistor physical dimensions and hence the supply voltage due to reliability constraints, the threshold voltage and the gate oxide thickness of the transistors should also be scaled down to keep the drive capability of the transistor and the performance of the digital circuits. This reduction of the threshold voltage and the oxide thickness leads to an exponential increase in the subthreshold and gate leakage current respectively. Several methods have been proposed to address the problem of the static power increase [START_REF] Roy | Leakage current mechanisms and leakage reduction technique in deep-submicrometer CMOS circuits[END_REF]. One of them named input vector control uses a vector which leads to the lowest leakage current and applies it to the primary inputs of the circuit in the standby mode [START_REF] Halter | A gate-level leakage power reduction method for ultra-low-power CMOS circuits[END_REF], [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF].

In [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF] an attribute is introduced for each circuit primary input which is called leakage observability. Similar to observability in the area of test pattern generation, the leakage observability indicates the degree to which the value of a particular circuit input is observable in the magnitude of leakage from power supply. In other words, it predicts the average effect on leakage if a primary input is set to a 1 or to a 0. We have extended this attribute to intermediate signals, so it can be used as a directive when justifying transition blocking values on intermediate lines through setting circuit inputs to proper values.

Background

For a CMOS circuit, total power consists of dynamic and static components at active mode. Dynamic power is proportional to the number of transitions in circuit, and static part of power is due to leakage currents of gates.

A. Dynamic Power Estimation

Ignoring direct-path short-circuit current, dynamic power dissipation is mostly due to charging and discharging of load and internal capacitances, which can be obtained as follows:

i j ij ij ij DD i Li i DD Dynj Dyno Dyn V C V C V f P P P 2 2 1 (1)
In the above, P dyno and P dynj are dynamic powers due to the load and internal capacitances, respectively. f is the clock frequency. i represents the gate i and j denotes the jth internal node in a gate. The switching activities at gate i and at the jth internal node of gate i are represented as i and ij , respectively. V ij is the voltage swing of the jth internal node of gate i, which is equal to V DD -V th . C Li and C ij are the load capacitance and the jth internal node capacitance of gate i, respectively.

B. Static Power Estimation

The total leakage current of a logic gate includes two major components, namely, subthreshold and gate leakage.

The subthreshold leakage current is one of the important components of leakages in CMOS digital circuits. This component exponentially increases with the reduction of the threshold voltage [START_REF] Roy | Leakage current mechanisms and leakage reduction technique in deep-submicrometer CMOS circuits[END_REF]. Using the Berkeley short-channel IGFET (BSIM) MOS transistor model [START_REF] Sheu | BSIM: Berkely short-channel IGFET model for MOS transistors[END_REF], the subthreshold current is approximated as

kT qV V V V V nkT q Sub DS DS S T GS e Ae I 1 0 (2)
Where kT/q is the thermal voltage, n is the subthreshold swing coefficient of the transistor, V DS is the drain to source voltage, V GS is the gate to source voltage, V T0 is the zero bias threshold voltage, is the body effect coefficient, is the drain induced barrier lowering (DIBL) coefficient, and

8 . 1 2 0 e q kT L W C A eff eff ox (3)
Here, µ 0 is the zero bias mobility and C ox is the gate oxide capacitance per unit area. Equation (2) suggests that the subthreshold current for each transistor be estimated when the terminal voltages are known. For the transistors in a logical gate, the terminal voltages depends on the gate input signals as well as the gate topology. The voltages may be easily calculated for a parallel combination of transistors (e.g., the pull-up network of an n-input NAND gate) where V DS 's are the same for all parallel transistors. This is not the case for the transistors in series (e.g., in the pull-down network of an NAND gate).

The gate leakage is due to the tunneling of an electron (or hole) from the bulk silicon through the gate-oxide potential barrier into the gate [START_REF] Mukhopadhyay | Gate leakage reduction for scaled devices using transistor stacking[END_REF]. Direct tunneling is modeled as shown below [START_REF] Schuegraf | Hole injection SiO2 breakdown model for very low voltage lifetime extrapolation[END_REF].

ox ox ox ox ox ox DT T V V B T V A J 2 3 2 1 1 exp (4)
Where J DT is the direct tunneling density, V ox is the drop across the thin oxide, ox is the barrier height for the tunneling particle (electron or hole), and T ox is the oxide thickness. A and B are physical parameters and can be found in [START_REF] Schuegraf | Hole injection SiO2 breakdown model for very low voltage lifetime extrapolation[END_REF] with more details. It can be observed from Equation [START_REF] Sinanoglu | Modeling Scan Chain Modifications for Scan-in Test Power Minimization[END_REF] shows that the tunneling current increases exponentially with a decrease in oxide thickness as well as increase in V ox . The latter depends on the biasing condition which is related to the gate topology and input signal. Therefore, the input pattern of each gate strongly affects the subthreshold as well as the gate leakage current.

To avoid complex calculations for estimation of total leakage we have used an HSPICE BSIM4 simulator to obtain total leakage currents for the transistors of the gates with different input signal levels. The results are stored in several tables containing the leakage of each gate for a given input pattern.

Finally, the total leakage power can be expressed as follows [START_REF] Rabaey | Digital Integrated Circuits[END_REF].

i DD i Sub Sub V I P , ( 5
)
Where I Sub,i is the standby leakage current through each gate i.

C. Leakage Observability

As mentioned before, [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF] introduced an attribute named leakage observability which is used for each primary input line. Leakage observability represents a measure of difference between overall leakage costs when a primary input line is set to one or zero. In other words, the magnitude of this attribute for each primary input line indicates how a binary value on that line can influence the total leakage. The leakage observability of input line i is defined by [START_REF] Sankaralingam | Inserting Test Points to Control Peak Power During Scan Testing[END_REF] [START_REF] Sankaralingam | Inserting Test Points to Control Peak Power During Scan Testing[END_REF] Lavg(i, v) is the average leakage cost for input i forced to value v. Calculation of leakage observability in [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF] is performed in reverse topological order on a network. Leakage observabilities of all lines are calculated, but only leakage observabilities on input lines are used in [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF] to find the minimum leakage pattern.

. 0 , 1 , i L i L i L avg avg obs

The Proposed Method

The proposed method tries to reduce both dynamic and static power dissipation during scan-based testing without affecting performance and with minimal area overhead.

Some previous solutions like [START_REF] Hertwig | Low Power Serial Built-In Self-Test[END_REF] and enhanced scan try to reduce dynamic power dissipation during scan by isolating scan chain transitions from the combinational parts of the circuit by adding latches or tri-state buffers to the scan-cell outputs (pseudo-inputs of the combinational part of the circuit). These methods cause performance degradation by adding logic to the outputs of all scan cells.

Our proposed method tries to block some of scanchain transitions without affecting the performance of the circuit during normal operation. These transitions are blocked by using multiplexers at scan-cell outputs which allow applying desired values while scanning the vectors in the chain. To avoid performance degradation, multiplexing is performed only on those pseudo-inputs that are not on the critical path(s) of the circuit. If primary inputs of the circuit are accessible, any desired value can be applied to the multiplexed pseudo-inputs and primary inputs of the circuit during the scan phase. We call primary inputs and multiplexed inputs as controlled inputs of the circuit. Transitions on the nonmultiplexed pseudo-inputs can still affect the combinational part hence resulting in unnecessary power dissipation.

The proposed method minimizes or eliminates this power dissipation by trying to suppress these transitions as near as possible to their origin (scan cell outputs). This is performed by applying appropriate patterns to the controlled inputs of the circuit. This method significantly reduces power dissipation during scan operations. The structure of this method for a full-scan sequential circuit is shown in Figure 1. Controlled inputs are shown with dashed lines.

Combinational Logic

Shift Enable

Primary Inputs

Scan Chain

Figure 1 The proposed method

As stated before, static power dissipation will be the dominant portion of the total power dissipation in future technologies. The proposed structure is used in order to reduce the static power dissipation. The static power reduction is based on an input vector control technique combined with a method which reorders gate inputs. In the input vector control technique, an input pattern is applied to the circuit inputs which minimize the leakage current. In our structure, this pattern can be applied to the circuit through the set of controlled inputs.

Therefore, in order to reduce both dynamic and static power dissipations, an appropriate pattern should be found to be applied to the controlled inputs during scan mode. When the scan operation finishes and scan values reach their corresponding scan cells, the circuit enters its normal mode of operation. In the normal mode, inserted multiplexers are switched to scan cell outputs and scan cell contents are applied to the circuit pseudo-inputs. The select line of a multiplexer can be connected to the shift enable signal available in all scan structures. In all scan structures, all scan cells receive the shift enable signal. So no extra control signal is required for this method.

An algorithm is also proposed which finds the desired vector. This vector should minimize the leakage current while suppressing the transitions originated from non-multiplexed pseudo-inputs.

The proposed method consists of these major steps. 1. Identifying pseudo-inputs suitable for being multiplexed and adding multiplexers to them (performed by AddMUX() procedure) 2. Finding the appropriate vector for controlled inputs (performed by the procedure called FindControlledInputPattern() ) The first step identifies pseudo-inputs which can be multiplexed without affecting the performance. This step is performed as follows: First, the critical path delay of the circuit is extracted. Then, the multiplexers of those inputs which affect the critical path delay are removed.

The next step is finding the appropriate pattern for the controlled inputs which minimizes the leakage current and suppresses the scan chain transitions.

An algorithm is proposed to find such an input pattern. The basic idea is that there are many vectors that can disable transitions propagating from noncontrolled pseudo-inputs of the circuit. This algorithm is based on a method of finding transition-blocking vectors which is directed by leakage observability. This algorithm is similar to C-Algorithm [START_REF] Huang | Reduction of power consumption in scan-based circuits during test application by an input control technique[END_REF], but is extended and directed by leakage observability.

To describe the proposed procedure (FindControlledInputPattern()), some concepts should be defined first.

Based on values assigned to controlled inputs, transitions may propagate to some nodes. These nodes are called tn (transition node). Set of all transition nodes is called Transition Node Set (TNS). Each tn is connected to input of a gate. Each of these gates is called tg and set of all tgs is called Transition Gate Set (TGS).

FindControlledInputPattern() 1.Initialize TNS to the set of non-multiplexed pseudo-inputs. value, Goto a e.if all inputs of the target_gate have non-controlling value, add its output line(s) to TNS Until all nodes of TNS are processed 2.For each transition node in updated TNS, put its target gate in TGS As stated before, leakage observability is used to direct the process of finding the input control pattern.

The algorithm should make decisions in different steps to limit the large space of possible solutions. Two important types of decisions are made in this algorithm. The first decision should be made when the algorithm selects which input of a transition gate is to be set to the controlling value. The second type of decision is made in the Justification process. Justification in this algorithm is performed by a PODEM-like method. In each step of this algorithm, one transition point is tried to be suppressed by applying a controlling value to the input(s) of its target gate. So the objective is setting an internal node to the desired value. Mapping this objective to values required at the controlled inputs is performed by the Backtrace procedure. Backtrace starts from the objective node and traverses internal lines toward the controlled inputs. On its way toward the controlled inputs, when reaching a new gate, Backtrace selects one of the gate inputs with a don't care value. Both of these types of decisions are made based on leakage observability.

In [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF], leakage observability was used only in the primary input lines in order to find the minimum leakage vector. We have extended the use of leakage observability to all circuit lines in order to direct the FindControlledInputPattern() procedure.

According to the definition of leakage observability, larger leakage observability means larger difference between average leakages in '1' and '0' states of a line. Therefore, when deciding on inputs of a gate, if the value to be set is '1' ('0'), we choose the input with minimum (maximum) leakage observability. Using this directive allows us to select a low leakage vector out of all possible vectors which can block the scan chain transitions.

When FindControlledInputPattern() finishes its work, there are still some controlled inputs that are not assigned values. These don't care controlled inputs can be used to further reduction of power consumption. A simulation-based method is used to find the minimumleakage vector for these inputs. The appropriate values for these don't care inputs to reduce the total circuit leakage current can be found by applying several random inputs and examining the total leakage for each of them. The number of the required simulations is far less than the total possible vectors [START_REF] Halter | A gate-level leakage power reduction method for ultra-low-power CMOS circuits[END_REF].

After finding the appropriate vector for the controlled inputs, they are applied to the circuit to find the values of the internal nodes of the CUT. These values are used as directives to change input of each gate in order to reduce the total gate leakage. As mentioned before the leakage current of a gate is strongly related to the pattern applied to that gate. So in some cases changing the inputs of a gate can be helpful for reducing its leakage.

For example, as can be observed from Figure 1, the leakage current of a NAND2 gate is strongly different in "01" and "10" states. So changing the order of inputs such that it will result in "01" rather than "10" can further decrease the total leakage in scan mode. This method is used globally for the circuit and the best order of inputs is found and applied to the circuit.

Results and Conclusions

To verify the improvement in power dissipation, the proposed technique was compared with the traditional scan structure; also, the input control structure [START_REF] Huang | Reduction of power consumption in scan-based circuits during test application by an input control technique[END_REF] was implemented and compared with our technique. The proposed method was implemented using C++ language and tested on ISCAS89 benchmarks. A technology mapping was used to map the circuit to a library, which contains only NAND gates, NOR gates, and inverters. SPICE simulation results were obtained for CMOS 45nm technology with the supply of 0.9v. The minimum feature size of 45nm was chosen for the channel length while the widths were selected for the minimum power delay product.

Our experiments were performed using test vectors generated by ATOM [START_REF] Hamzaoglu | New Techniques for Deterministic Test Pattern Generation[END_REF]. No test vector reordering or scan cell reordering was performed in these experiments. By applying reordering techniques, further improvements can be achieved.

Table I compares dynamic and static parts of power dissipated in the combinational part of the ISCAS89 circuit shown for traditional scan, input control technique and the method proposed here. The values in the dynamic columns must be multiplied by the working frequency to give the actual dynamic power. Static portion of power is not currently as effective as the dynamic one in the total dissipated power, but it will outreach the dynamic portion in future technologies. This table shows a fair amount of reduction in power dissipation especially in the dynamic portion.

The proposed method has reduced the total power dissipation including static and dynamic power while it does not have any impact on test time. It also does not affect the critical path of the circuit, so it does not affect the maximum working frequency of the circuit. It does not incur routing overhead since inputs of the multiplexer can be locally connected to Vcc or Gnd. It also requires no extra control signal since it uses the Shift Enable signal as its control signal (This signal is available in all scan cells of the circuit).

This method can be used as an efficient lowoverhead solution for power problem in scan-based DFT structures.

AddMUX() 1 .

 1 Find delay of critical path(s) of the circuit 2.For each pseudo-input PI a.Add a multiplexer to PI b.If the critical path delay of the circuit has changed after inserting the multiplexer, remove the multiplexer

Figure 2

 2 Figure 2 Leakage current of NAND2 gate in 45nm technology

  Save the assigned values on controlled inputsAfter trying each transition gate, TNS and TGS are updated. Process of updating TNS and TGS are described here:

	2.Update TNS, TGS
	3.Repeat
	a.	Get a gate from TGS with the largest output
	capacitance (mc_tg). The corresponding tn
	is called mc_tn.
	b.	cv = controlling value of mc_tg.
	c.	is_transition_blocked = false;
	d.	Repeat
		i.	Select an input node candidate_input
		of gate mc_tg with don't care value
		(other than mc_tn).
		If there is more than one option, select
		based on leakage observability).
		ii.	is_transition_blocked =
			Justify(candidate_node, cv)
			(Justify() is directed by leakage
			observability)
		iii.	If (is_transition_blocked=true) Goto f
	e.		Until all don't care inputs of the
			mc_tg are checked
	f.	Add all fan-out nodes of mc_tg to TNS
	g.	Update TNS, TGS
	Until TGS becomes empty
	4.Update TNS, TGS
	1.Repeat
	a.Get a node tn

i from TNS b.target_gate= gate connected to the tn i output c.if target_gate is NOT, XOR, XNOR or FANOUT, add its output line(s) to TNS, Goto a d.if any input of the target_gate has controlling

Table I . Power dissipation for our proposed and prior structures

 I

	Circuit	Traditional Scan Structure Dynamic (/f) (µW/Hz) Static (µW)	Input Control [8] Dynamic (/f) (µW/Hz) Static (µW)	Proposed Structure(µW) Dynamic (/f) (µW/Hz) Static (µW)	Improvement Compared with Traditional Scan (%) Dynamic Static	Improvement Compared With Input Control [8] (%) Dynamic Static
	s344	5.88E-8	27.99	5.72E-8	27.50	3.24E-8	23.89	44.82	14.65	43.23	13.12
	s382	6.43E-8	27.58	5.51E-8	26.69	2.38E-8	24.42	62.90	11.46	56.73	8.50
	s444	8.00E-8	33.72	6.92E-8	33.30	2.44E-8	27.99	69.44	17.00	64.67	15.95
	s510	8.46E-8	47.93	8.18E-8	47.50	8.22E-8	45.96	2.92	4.11	-0.41	3.24
	s641	5.69E-8	59.07	1.77E-8	56.97	1.78E-8	48.97	68.80	17.10	-0.5	14.05
	s713	6.30E-8	66.15	1.85E-8	64.90	1.82E-8	52.10	71.06	21.23	1.25	19.71
	s1196	3.10E-8	115.54	3.06E-8	117.75	2.52E-8	95.78	18.61	17.09	17.50	18.65
	s1238	3.19E-8	121.56	3.39E-8	124.75	2.59E-8	96.38	18.64	20.70	23.63	22.74
	s1423	2.24E-7	128.22	1.93E-7	130.23	5.43E-8	117	75.77	9.02	71.83	10.43
	s1494	3.56E-7	177.52	3.48E-7	179.86	3.52E-7	164.87	9.52	7.12	7.45	8.33
	s5378	8.90E-7	327.52	1.29E-8	332.02	1.17E-8	315	98.68	3.82	9.50	5.12
	s9234	1.50E-6	819.98	1.68E-8	854.52	1.57E-8	772.36	98.95	5.80	6.96	9.61

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)


Jérôme Collet
email: jerome.collet@edf.fr

Michael Richard
email: michael-m.richard@edf.fr

A Generic Method for Density Forecasts Recalibration

Keywords: Density forecasting, Rosenblatt transform, PIT series, calibration, bias correction

We address the calibration constraint of probability forecasting. We propose a generic method for recalibration, which allows us to enforce this constraint. It remains to be known the impact on forecast quality, measured by predictive distributions sharpness, or specific scores. We show that the impact on the Continuous Ranked Probability Score (CRPS) is weak under some hypotheses and that it is positive under more restrictive ones. We used this method on temperature ensemble forecasts and compared the quality of the recalibrated forecasts with that of the raw ensemble and of a more specific method, that is Ensemble Model Output Statistics (EMOS). Better results are shown with our recalibration rather than with EMOS in this case study.

Introduction

Due to the increasing need for risk management, forecasting is shifting from point forecasts to density forecasts. Density forecast is an estimate of the conditional probability distribution. Thus, it provides a complete estimate of uncertainty, in contrast to point forecast, which is not concerned whith uncertainty. Two alternative ways to evaluate density forecast exist.

• The first one was proposed by T. Gneiting: Probabilistic forecasting aims to maximize the sharpness of the predictive distributions, subject to calibration, on the basis of the available information set. Calibration means predictive distributions are consistent with observations, it is more formally defined in [START_REF] Gneiting | Probabilistic forecasting[END_REF]; sharpness refers to the concentration of the density forecast, and even in the survey paper of T. Gneiting, it is not formally defined. An important feature of this framework is that we face a multi-objective problem, which is difficult. • The second way is the use of a scoring rule, which assesses simultaneously calibration and sharpness. Concerning the well-known CRPS scoring rule, Hersbach [START_REF] Hersbach | Decomposition of the continuous ranked probability score for ensemble prediction systems[END_REF] showed that it can be decomposed into three parts: reliability (or calibration) part, resolution (or sharpness) part, and uncertainty, which measures the intrinsic difficulty of the forecast. Bröcker [START_REF] Bröcker | Reliability, sufficiency, and the decomposition of proper scores[END_REF] generalized this result to any proper score, that is any score which is minimal if the forecasted probability distribution is the true one (w.r.t the available information). Recently, Wilks [START_REF] Wilks | Enforcing calibration in ensemble postprocessing[END_REF] proposed to add an extra miscalibration penalty, in order to enforce calibration in ensemble postprocessing. Nevertheless, even if the score we use mixes calibration and sharpness, the framework is essentially different from the first one.

Besides these two alternative ways of evaluation, probabilistic forecast is mainly used in two different contexts: finance and economics, and weather forecast. In finance and economics, calibration is the unique objective, so a recent survey on "Predictive density evaluation" [START_REF] Corradi | Predictive density evaluation[END_REF] is in fact entirely devoted to the validation of the calibration, without any hint of sharpness. In weather forecast, both ways of evaluation are used. For a quick view on forecasting methods in atmospheric sciences, one can look at [START_REF] Wilks | Statistical methods in the atmospheric sciences[END_REF]. In the works of T. Gneiting [START_REF] Gneiting | Calibrated probabilistic forecasting using ensemble model output statistics and minimum crps estimation[END_REF] [7], and in the seminal work of Krzysztofowicz [START_REF] Krzysztofowicz | Bayesian processor of output: a new technique for probabilistic weather forecasting[END_REF], the goal is to improve sharpness, while preserving calibration. Nevertheless, one can state that there is no formal test of calibration in these works. In [START_REF] Fortin | Probabilistic forecasting from ensemble prediction systems: Improving upon the best-member method by using a different weight and dressing kernel for each member[END_REF], the only measure used is the CRPS, and [START_REF] Gogonel | Improving the calibration of the best member method using quantile regression to forecast extreme temperatures[END_REF] addresses exclusively the calibration issue.

Here, we are interested in the first method of evaluation: calibration constraint and sharpness objective. Indeed, risk management involves many stakeholders and thus, calibration is a key feature of trust between stakeholders since it impacts all of them. For example, EDF also faces a regulatory constraint: the French technical system operator imposes that the probability of employing exceptional means (e.g., load shedding) to meet the demand for electricity must be lower than 1% for each week (RTE, 2004), so EDF has to prove the calibration of its forecasts. Even inside EDF, many different business units may be involved in the management of a given risk, so calibration is compulsory to obtain confidence between risk management stakeholders.

The consequence is that we face a multi-criterion problem, the goal of our contribution is to allow us to enforce the calibration constraint, in a generic way. Furthermore, we show that, even if the evaluation framework is the proper score use, recalibrating leads in many cases to an improvement, and to a very limited loss in other cases.

The remainder of this chapter will be organized as follows. The next section explains the principle of the method. The third part provides some theoretical results while the fourth is devoted to a case study.

Principle of the method

The Probability Integral Transform (PIT, Rosenblatt, 1952) is usually a measure of the calibration of density forecasts. Indeed, if Y ∼ F and is continue, the random variable F(Y ) ∼ U[0, 1]. Thus, we can find in the literature many tests based on this transformation to evaluate the correct specification of a density forecast. In our case, it is used firstly to recalibrate the forecasts.

Let's look at the following case: let E be the set of all possible states of the world; for each forecasting time j the forecaster knows the current state of the world e( j), and uses it to forecast. For example, in the case of a statistical regression model, E is the set of the possible values of the regressors, in the case of the post-processing of an weather forecasting model, E is the ensemble. The conditional estimated distribution is G e , whereas the true one is F e . So the PIT series is:

PIT ≡ G e( j) (Y j ) j . • A.2.1: G e is invertible ∀ e ∈ E.
If E is discrete, we assume that the frequency of appearance of each state of the world e is p e . Then, under the assumption A.2.1, the c.d.f of the PIT is:

C(y) ≡ Pr( G(Y) ≤ y) ≡ ∑ e p e F e • G -1 e (y).
Note that all the results obtained under the hypothesis that E is discrete are still valid in continuous case, even if we only treat the discrete case in this article.

• A.2.2: F is invertible.

We propose to use C to recalibrate the forecasts. For each quantile τ ∈ [0, 1], we use the original model to forecast the quantile τ C , such that Pr( G(Y) ≤ τ c ) = τ. We remark that this implies τ c = C -1 (τ). This correction makes sense since under the assumptions A.2.1 and A.2.2:

Pr(C • G(Y) ≤ y) = Pr( G(Y) ≤ C -1 (y)) = C •C -1 (y) = y,
which means that the recalibrated forecasts are uniformly distributed on the interval [0,1].

Note that this method is close to the quantile-quantile correction as in [START_REF] Michelangeli | Probabilistic downscaling approaches : Application to wind cumulative distribution functions[END_REF] but here, we are concerned by PIT recalibration, which allows us to consider the conditional case.

Impact on global score

If we evaluate our method on the basis of calibration, it ensures this constraint is enforced. But it is important to know if our method is still useful even if one of the probability forecasting users prefers to use scores, for example the Continuous Ranked Probability Score (CRPS).

The CRPS:

CRPS(G, x) = +∞ -∞ (G(y) -1 {x ≤ y} ) 2 dy ,
with G a function and x the observation, is used to evaluate the whole distribution, since it is minimized by the true c.d.f of X.

However, since we have:

CRPS(G, x) = 2 1 0 L τ (x, G -1 (τ))dτ , (1)
as shown in [START_REF] Ben Taieb | Forecasting uncertainty in electricity smart meter data by boosting additive quantile regression[END_REF], with L τ the Pinball-Loss function :

L τ (x, y) = τ(x -y)1 {x ≥ y} + (y -x)(1 -τ)1 {x < y} ,
with y the forecast, x the observation and τ ∈ [0, 1] a quantile level, and that L τ is easier to work with, we use this scoring rule to obtain results on CRPS.

L τ is used to evaluate quantile forecasts. Indeed, it is a proper scoring for the quantile of level τ, since its expectation is minimized by the true quantile of the distribution of X.

To begin with, we will prove that under some hypotheses, our correction improves systematically the quality of the forecasts in an infinite sample. Then we will show that under less restrictive hypotheses, our correction deteriorates only slightly-in the worst case-the quality of the forecasts in a more realistic case, e.g finite sample.

∑ e p e η e (F -1 e (τ))

2 as max η e → 0, (2)
with p e the frequency of appearance of the state e.

This result allows us to find conditions for improvement of the expectation of the Pinball-Loss score, with additional following conditions.

• A.3.1.5: η or f -1 is a constant, or max e (•)/min e (•) < 3 + 2 √ 2 for both η e and f -1 e , ∀ e ∈ E,

• A.3.1.6: the correlation between η and f -1 , σ f -1 or σ η is null. Here the correlation is used as a descriptive statistics notation, even if the series η and f -1 are deterministic. The null correlation means that the difference between the true probability distribution function and the model have the same magnitude in low and in high density regions.

Under the assumption A.3.1.5 or

A.3.1.6, if ∃ ν ≥ 0 (sufficiently small) ∀ e ∈ E ∀ y ∈ R; |η e (y)| ≤ ν, we show that (proof in Appendix): 0 ≤ E Y [ L τ -L τ c ] and (3)
0 ≤ E Y [CRPS G,C•G ] , (4) with
E Y [CRPS G,C•G ] ≡ E Y [CRPS(G, Y) -CRPS(C • G, Y) ].
In other words, with those restrictions, our recalibration systematically improves the quality of the forecasts. Indeed, remember that the expectation of the Pinball-Loss score is minimized by the true quantile of the distribution of Y and negatively oriented. Thus, the lower the expectation of the Pinball-Loss score, the better.

Impact on score: bounds on degradation

In reality, we cannot obtain the corrected probability level τ c ∈ [0, 1], and we need to estimate it. If we want to upper bound the degradation, we can study the more realistic case of

E Y [L τ c -L τ ] ≡ E 1 n n ∑ j=1 L τ (y j , G -1 j ( τ c )) -L τ (y j , G -1 j (τ)) , (5)
with τ, τ c ∈ [0, 1]. In our case study, τ c is obtained empirically, on the basis of the available PIT values. Thus, we have a consistant estimator of τ c and one can rewrite (5

) such as E Y [ L τ (Y, G -1 (Q τ )) ] -E Y [ L τ (Y, G -1 (τ)) ],
with Q τ a random variable converging in distribution to a Normal distribution with mean τ c and a variance decreasing at the rate 1 n .

In such a case, it is still possible to obtain bounds concerning the error induced by our correction. Under the assumptions A.

• A.3.2.1: F e and G e are C 2 ∀ e ∈ E. • A.3.2.2: ∀ y ∈ R, ∀ e ∈ E, |F e (y) -G e (y)| ≤ ε, with ε ∈ [0, 1]. • A.3.2.3: the derivatives of G e are lower bounded ∀ e ∈ E , ∀ τ ∈ [0, 1] by 1/ξ , on the intervals [G -1 e (0 ∨ (τ -ε)), G -1 e (1 ∧ (τ + ε))] , with ξ ∈ ]0, +∞[. • A.3.2.4: ∀ e ∈ E, ∀ τ ∈ [0, 1], f e (G -1 e (τ c )) ≤ β , with β ∈ ]0,
E Y [L τ c -L τ ] ≤ 2 ε 2 ξ + C λ n and (6)
| E Y [CRPS G,C•G ]| ≤ 2 2 ε 2 ξ + C λ n (7) with C = (1-τ)αξ 3 2 +C int +C abs , C int = ξ 2 β 2 1 + αξ 2 + α 2 ξ 4 4
,

C abs = M ξ 3 6 1 + 3ξ 3 α 2 + 3ξ 3 α 2 4 + ξ 3 α 3 8
and λ n , the variance of Q τ

This inequality shows that our recalibration deteriorates only slightly the quality of the forecasts in the worst case. Obviously, it also shows that our method improves only slightly the quality, but remember that our goal is to enforce the validity constraint, which is achieved.

Case study

We use our method on ensemble forecasts data set from the European Centre for Medium-Range Weather Forecasts (ECMWF). One can see in [START_REF] Gneiting | Calibration of medium-range weather forecasts[END_REF] that the statistical post-processing of the medium range ECMWF ensemble forecast has been addressed many times. The extended range (32 days instead of 10 days) has been addressed in some studies, but with the same methods and tools. We will show here that our recalibration method, despite its genericness, is competitive with a standard post-processing method. We dispose of temperature forecasts in a 3-dimensional array. The first one represents the date of forecasts delivery. The forecasts were made every Monday and Thursday from 11/02/13 to 02/02/17. Since 3 observations are missing, we have 413 dates of forecasts delivery. The second dimension is the number of the scenario in the ensemble member, and we have 51 scenarios. The third dimension is the forecast horizon. Since we have 32 days sampled with a forecast every 3 hours, it produces 256 horizons.

We study the calibration and compare the CRPS expectation using directly the ensemble forecast, the so-called Ensemble Model Output Statistics (EMOS) method and our recalibration method with a Cauchy Kernel dressing for the ensembles. We choose a Cauchy Kernel in order to address problems with the bounds of the ensembles. Indeed, a lot of observations were out of the bounds of the ensemble, which produces a lot of PIT with value 0 or 1. Thus, to avoid this problem, we need to use a Kernel with heavy tail.

During the last 12 years, the ECMWF has changed its models 27 times, which means a change every 162 days on average. Thus, it is important to use a train sample significally smaller than 162 days. However, it is also important to dispose of enough observations to obtain a consistant estimator of τ c . Our method obtains good results with 30 days used for the recalibration but the algorithm to minimize in order to find the parameters of the EMOS in the R package EnsembleMOS doesn't converge if we use less than 60 days (at least with our data set). Thus, we chose to use 60 days for the recalibration.

To recalibrate the forecasts for a particular forecasting day and a particular horizon (remember that we have 256 horizons), we use the forecasts made for the same horizon, over the 60 previous dates of forecast delivery for the two methods. However, with our method, we use a linear interpolation based on the PIT series formed by these 60 previous days to recalibrate the forecasts. The linear interpolation is also used to calculate the different quantile levels when we are not working with EMOS (in that case, for the recalibration or to calculate the quantile, we use the Normale distribution with the fitted parameters). Note that the hypotheses concerning only G e are verified ∀ e ∈ E. Besides, even if we cannot verifiy the other hypotheses, we show expected results

Let's start with the calibration property: As expected, we can see in table 1 that our method allows us the test of validity to be passed while the use of the raw ensemble fails. The EMOS also failed to pass the test. Clearly, our method is useful to ensure the calibration property. But how about the quality of the density forecast? In order to evaluate the impact of our correction on the forecast quality, we are interested in the CRPS expectation.

We can see in figure 1 that EMOS as well as our method are more efficient than the raw ensemble for little horizons. However, the EMOS deteriorates clearly the quality of the forecasts when the horizon grows, contrarily to our method which deteriorates only slightly the quality of the forecasts, when it is the case. Fig. 1 Comparison of EMOS and our method CRPS expectation with that of raw ensemble The empty line corresponds to our method and the dashed one to the EMOS Thus, this study highlights perfectly the usefulness of our method, which is very simple to use. Indeed, it shows that it allows us to ensure the validity constraint, with a limited negative impact on the quality.

Chapter 1 A Generic Method for Density Forecasts Recalibration 5 Appendix

Here are gathered all the proofs concerning the results presented in the chapter. The first section is concerned by proofs of results in an infinite sample and the second by result in a finite sample.

Lemma 1. E Y [ L τ -L τ c ] = ∑ e p e G -1 e (τ) G -1 e (τ c )
(F e (y)τ)dy , with τ,τ c ∈ [0, 1] and p e the frequency of appearance of the state e. Under the assumption A.2.1, we prove Lemma 1.

Proof. We have:

E Y [ L τ -L τ c ] = ∑ e p e E Y [ L τ (Y, G -1 e (τ)) ] -E Y [ L τ (Y, G -1 e (τ c ) ] . (8)
First, we only focus on a particular e. Thus, we are interested in :

E Y [ L τ (Y, G -1 e (τ)) ] -E Y [ L τ (Y, G -1 e (τ c ) ] ≡ E Y,e [ L τ,τ c ].
For ease of notation and comprehension, we suppress e in the notation since there is no confusion. Moreover, we suppose, for ease of notation again (and since we 11 obtain the same result if we inverse the inequality) that G -1 (τ) ≤ G -1 (τ c ). So, we have:

E Y [ L τ,τ c ] = +∞ -∞ [y -G -1 (τ)] τ + [G -1 (τ) -y] 1 {y≤G -1 (τ)} f Y (y) dy - +∞ -∞ [y -G -1 (τ c )] τ + [G -1 (τ c ) -y] 1 {y≤G -1 (τ c )} f Y (y) dy = [G -1 (τ c ) -G -1 (τ)] τ + [G -1 (τ) -G -1 (τ c )] F • G -1 (τ) -G -1 (τ c ) [ F • G -1 (τ c ) -F • G -1 (τ) ] + G -1 (τ c ) y=G -1 (τ) y v f Y (y) u dy .
Using integral by parts, we have:

E Y [ L τ,τ c ] = [G -1 (τ c ) -G -1 (τ)] τ + G -1 (τ) y=G -1 (τ c ) F(y) dy = G -1 (τ) y=G -1 (τ c ) [ F(y) -τ ] dy .
Replacing it in (8) finishes the demonstration

Impact on score: conditions for improvement

In this section, the reader can find the proofs of results mentioned in Sect.3.1 of the chapter. We first demonstrate how to approximate the difference of L τ expectation before showing that under some hypotheses, our correction improves systematically the quality of the forecasts.

Rewriting the difference of L τ expectation

Under the assumptions A.2.1, A. Proof. Remember: Let H be a functional, h a function, α a scalar and δ an arbitrary function.

We can write the expression of the functional evaluated at f + δα as follow:

H[h + δ α] = H[h] + dH[h + δ α] dα | α=0 α + 1 2 d 2 H[h + δ α] dα 2 | α=0 α 2 + • • • + Rem(α) ,
with Rem(α) the remainder. Denote: For ease of notation, denote ∆ PL e [F e + δ e α] ≡ ∆ PL F,δ,e . Choosing H = ∆ PL e , h = F e and η e = αδ e (even if we use αδ e in the developpemnt in order to use functional derivatives, directional derivatives and the implicit function theorem), we have:

∆ PL[h] = ∑ e p e h -1 e (τ)
∆ PL F,δ,e ∼ ∆ PL e [F e ] + d∆ PL F,δ,e dα | α=0 α + 1 2 d 2 ∆ PL F,δ,e dα 2 | α=0 α 2 + Rem e (α) = ∂ ∆ PL F,δ,e ∂ α | α=0 , τ c =τ + ∂ ∆ PL F,δ,e ∂ τ c | α=0 , τ c =τ dτ c dα α + ∂ 2 ∆ PL F,δ,e ∂ α 2 | α=0 , τ c =τ + 2 ∂ 2 ∆ PL F,δ,e ∂ α∂ τ c | α=0 , τ c =τ dτ c dα α 2 2 + ∂ 2 ∆ PL F,δ,e ∂ τ 2 c | α=0 , τ c =τ dτ c dα 2 + ∂ ∆ PL F,δ,e ∂ τ c | α=0 , τ c =τ d 2 τ c dα 2 α 2 2
+Rem e (α) .

To calculate dτ c dα , we will use the equation which link τ c and α:

∑ e p e F e • (F e + δ e α) -1 (τ c ) = τ.
Using the implicit function theorem, we find:

dτ c dα = ∑ e p e δ e • F -1 e (τ)
Now, we need to calculate partial derivatives:

∂ ∆ PL F,δ,e ∂ α | α=0 , τ c =τ = ∂ (F e +δ e α) -1 (τ) (F e +δ e α) -1 (τ c ) (F e (y) -τ)dy ∂ α | α=0 , τ c =τ = 0 ;
d 3 ∆ PL F,δ,e dα 3 = ∂ ∆ PL F,δ,e ∂ τ c d 3 τ c dα 3 + 3 ∂ 2 ∆ PL F,δ,e ∂ τ c ∂ α d 2 τ c dα 2 + 3 ∂ 2 ∆ PL F,δ,e ∂ τ 2 c d 2 τ c dα 2 dτ c dα + ∂ 3 ∆ PL F,δ,e ∂ α 3 + 3 ∂ 3 ∆ PL F,δ,e ∂ τ c ∂ α 2 dτ c dα + 3 ∂ 3 ∆ PL F,δ,e ∂ τ 2 c ∂ α dτ c dα 2 + ∂ 3 ∆ PL F,δ,e ∂ τ 3 c dτ c dα 3 .
Let's calculate the partial derivatives of order 3:

∂ 3 ∆ PL F,δ,e ∂ α 3 | α=0 , τ c =τ = 0 ; ∂ 3 ∆ PL F,δ,e ∂ τ 3 c | α=0 , τ c =τ = 2 f e • F -1 e (τ) f e • F -1 e (τ)
;

∂ 3 ∆ PL F,δ,e ∂ τ 2 c ∂ α | α=0 , τ c =τ = -2 f e • F -1 e (τ) f e • F -1 e (τ) 3 (δ e • F -1 e (τ)) -2 δ e • F -1 e (τ) f e • F -1 e (τ) 2 ; ∂ 3 ∆ PL F,δ,e ∂ τ c ∂ α 2 | α=0 , τ c =τ = f e • F -1 e (τ) f e • F -1 e (τ) 3 δ e • F -1 e (τ) 2 -2 δ e • F -1 e (τ) f e • F -1 e (τ) 2 δ e • F -1 e (τ)
.

Moreover, we have:

d 2 τ c dα 2 = ∑ e p e 2δ e • F -1 e (τ) -f e • F -1 e (τ) f e • F -1 e (τ)
δ e • F -1 e (τ).
Since η e , its first, second and third derivatives are finite in F -1 e (τ), it is also the case for δ e and the partial derivatives are finite. Furthermore, f e , δ e and their derivatives are bounded (since η e and their derivatives are bounded), which implies that the second derivatives of ∆ PL e [F e + δ e α] are also bounded. Thus, under these conditions, M exists. Then, we can write (αδ e ) 2 = 0, αδ e → 0, which shows that Rem e (α) is negligible compared to

d 2 ∆ PL F,δ,e dα 2 .
Moreover, since ∀ e ∈ E the functions F e are C 3 and the functions f e and their derivatives are bounded by a constant which doesn't depend on e, ∀ e ∈ E, the development is valid for all directions and thus, since η e = G e -F e , we have: To finish the demonstration, remark that Lemma1 proves that:

E Y [ L τ -L τ c ] ∼ ∑ e p e η e (F -1 e (τ)) f e (F -1 e (τ)
∆ PL[G] = E Y [ L τ -L τ c ].

Systematic improvement of the quality

Under the assumption A.

Proof. Prove (3) is equivalent to show that ∆ PL[G]
is positive, and if we rewrite:

∆ PL[G] ∼ (2E[ f -1 η] -E[ f -1 ]E[η])E[η] ,
it is clear that the assumption A. However, we need more argumentation to understand the complete utility of the assumption A.3.1.5. Let's look at one of the two worst cases: only two states of the world, the correlation coefficient ρ = -1, η > 0 (the other case is when ρ = 1 and η < 0 ) and at each bound of the support of δ and f -1 , there is half of the probability mass. We also consider that the ratios between max and min of the supports are equal. If we define max e = M and min e = M r , one has the following equation:

1 2 = 2(r 2 + 1) (r + 1) 2 -1.
Solving this equation in r produces the expected result concerning the ratio between max and min values of η and f -1 . Now, let's prove (4). According to (1), we have:

E Y [CRPS G,C•G ] = 2 +∞ -∞ 1 0 L τ (y, G -1 (τ)) -L τ (y, G -1 •C -1 (τ))dτ f Y (y)dy.
We can rewrite :

E Y [CRPS G,C•G ] = 2 +∞ -∞ 1 0 L τ (y, G -1 (τ)) f Y (y) dτ dy -2 +∞ -∞ 1 0 L τ (y, G -1 •C -1 (τ)) f Y (y) d τdy ,
and using the Fubini-Tonelli theorem, one obtains:

E Y [CRPS G,C•G ] = 2 1 0 E Y [ L τ -L τ c ]dτ (9)
≥ 0.

Impact on score: bounds on degradation

Under the assumptions A. 6) and (7).

Proof. adding and substracting E

Y [ L τ (Y, G -1 (τ c )) ] to E Y [L τ c -L τ ], we obtain: E Y [L τ c -L τ ] = E Y [ L τ (Y, G -1 (Q τ )) ] -E Y [ L τ (Y, G -1 (τ c )) ] +E Y [ L τ (Y, G -1 (τ c )) ] -E Y [ L τ (Y, G -1 (τ)) ] ,
and finally:

E Y [L τ c -L τ ] = E Y,e [ L τ (Y, G -1 e (Q τ )) ] -E Y,e [ L τ (Y, G -1 e (τ c )) ] -E Y [ L τ -L τ c ].
To begin with, we treat the third term on the right side. We have:

E Y,e [ L τ,τ c ] = G -1 e (τ) y=G -1 e (τ c )
[ F e (y)τ ] dy .

Using the change of variable y = G -1 e (z) and taking the absolute value, we find:

|E Y,e [ L τ,τ c ]| = τ z=τ c (F e • G -1 e (z) -τ) 1 g e (G -1 e (z))
dz .

Now, one needs to distinguish two cases.

If τ > τ c , one has:

| E Y,e [ L τ,τ c ] | = τ z=τ c (F e • G -1 e (z) -τ) 1 g e (G -1 e (z)) dz ≤ τ z=τ c (F e • G -1 e (z) -τ) ξ dz . Since | F e (z) -G e (z) | ≤ ε, ∀z ∈ R, ∀e ∈ E, one obtains | F e • G -1 e (z) -z | ≤ ε, ∀z ∈ [0, 1],
∀e ∈ E and then:

• if z = τ, one has F e • G -1 e (τ) -τ ≤ ε, • if z = τ c , F e • G -1 e (τ c ) -τ) = F e • G -1 e (τ c ) -τ c + τ c -τ .
Moreover, one has:

| τ c -τ | = ∑ e p e τ c -F e • G -1 e (τ c ) ≤ ∑ e p e F e • G -1 e (τ c ) -τ c ≤ ε ,
and finally:

F e • G -1 e (τ c -τ) ≤ F e • G -1 e (τ c ) -τ c + | τ c -τ | ≤ 2 ε .
One deduces, when τ > τ c :

| E Y,e [ L τ,τ c ] | ≤ 2 ( τ -τ c ) ε ξ .
When τ < τ c , one obtains:

| E Y,e [ L τ,τ c ] | ≤ τ c z=τ (F e • G -1 e (z) -τ) ξ dz ,
and using the same arguments as previously:

| E Y,e [ L τ,τ c ] | ≤ 2 ( τ c -τ ) ε ξ .
Hence, one concludes that:

| E Y,e [ L τ,τ c ] | ≤ 2 | τ -τ c | ε ξ .
To finish, replacing E Y,e [ L τ,τ c ] in (8), we have:

| E Y [ L τ -L τ c ] | ≤ 2 ε 2 ξ .
Now let's focus on the remainder on the right side. First, we only focus on a particular e. Thus, we are interested in :

E Y [ L τ (Y, G -1 e (Q τ )) ] -E Y [ L τ (Y, G -1 e (τ c )) ] ≡ E Y,e [L τ c -L τ c ].
For ease of notation and comprehension, we suppress e in the notation since there is no confusion. So, we have:

E Y [L τ c -L τ c ] = 1 2 -τ E Y G -1 (Q τ ) -G -1 (τ c ) + 1 2 E Y |Y -G -1 (Q τ )| -|Y -G -1 (τ c )| .
We find:

E Y [L τ c -L τ c ] ≤ 1 2 E Y |Y -G -1 (Q τ )| -|Y -G -1 (τ c )| -G -1 (Q τ ) + G -1 (τ c ) +(1 -τ) E Y G -1 (Q τ ) -G -1 (τ c ) .
Let's focus on the second term on the right side. Using a Taylor series approximation around τ c ∈ [0, 1] and the Taylor-Lagrange formula for the remainder, one has:

G -1 (Q τ ) = G -1 (τ c ) + 1 g(G -1 (τ c )) (Q τ -τ c ) + g (γ) g(γ) 3 (Q τ -τ c ) 2 2 , with γ = τ c + (Q τ -τ c ) θ , and 0 < θ < 1.
And so

(1 -τ) E Y G -1 (Q τ ) -G -1 (τ c ) ≤ (1 -τ) α ξ 3 2 λ n .
Now, one can study the first term on the right side. Some useful remarks before the next: one can easily see that the study of such a function can be restricted to a study on the interval I y :=] -∞, G -1 (τ c )], since we can find results on the interval [G -1 (τ c ), ∞[ using the same arguments.

Let's define G -1 (Q τ ) ≡ Z τ , G -1 τ c ≡ G -1 (τ c ) and f G -1 τc Y ≡ f Y (G -1 (τ c ))
, for ease of notation. Thus, we are interested in calculating:

1 2 G -1 τc y=-∞ f Y (y) ( E Z τ [ |G -1 τ c -Z τ | + |Z τ -y| ] -G -1 τ c + y) =E Zτ [ |Z τ -y|-Z τ ]+y dy . (10)
However, the function studied in the integral is complicated to work with. So, one will prefer to use its integral version, that is,

E Z τ [ |Z τ -y| -Z τ ] + y = y u=-∞ d du (E Z τ [ |Z τ -u| -Z τ ] + u) du .
For the bounds of the integral, the upper one is obvious. To justify the lower one, it is important to note that lim E

Z τ [ |Z τ -y| -Z τ ] + y = 0, y → -∞.
Indeed, one has:

E Z τ [ |Z τ -y| -Z τ ] + y = y z=-∞ (y -z) h(z) dz + ∞ z=y (z -y) h(z) dz + ∞ z=-∞ (y -z) h(z) dz = y z=-∞ 2(y -z) h(z) dz = 2y H(y) - y z=-∞ 2z h(z) dz ,
with h and H the p.d.f and the c.d.f of the variable Z t . If the variable Z τ has a finite mean, lim , h(y) = 0, y → -∞, and thus it is clear that the choice of -∞ for the lower bound of the integral is the good one.

At this stage, it is not easy to see the usefulness of the transformation, but it will be after the following calculus:

d du (E Z τ [ |Z τ -u| -Z τ ] + u) = 1 + d du u z=-∞ (u -z) h(z) dz + d du ∞ z=u (z -u) h(z) dz .
Finally, we have:

d du (E Z τ [ |Z τ -u| -Z τ ] + u) = u z=-∞ h(z) dz - ∞ z=u h(z) dz + 1 = H(u) -( 1 -H(u) ) + 1 = 2 H(u).
Now, it is clear that this transformation could help us for the calculus of (10) since it is equivalent to study: for our calculus, and then we will study the impact of such a manipulation.

G -1 τc y=-∞ f Y (y)
Let's start with the first task. Using an integral by part on Half Int:

G -1 τc y=-∞ f G -1 τc Y u y u=-∞ H(u) du v dy .
One obtains:

Half Int = y f G -1 τc Y y u=-∞ H(u) du G -1 τc y=-∞ - G -1 τc y=-∞ y f G -1 τc Y H(y) dy = G -1 τc u=-∞ f G -1 τc Y [ G -1 τ c -u ] u H(u) v du = f G -1 τc Y u G -1 τ c - u 2 2 H(u) G -1 τc u=-∞ - G -1 τc u=-∞ f G -1 τc Y u G -1 τ c - u 2 2 h(u) du . Since u G -1 τ c -u 2 2 = (u-G -1 τc ) 2 2 - (G -1 τc ) 2 2
, we have:

Half Int = f G -1 τc Y G -1 τc u=-∞ (u -G -1 τ c ) 2 2
h(u) du . Now, using the change of variable G(u) = z, a Taylor series approximation around τ c and the Taylor-Lagrange formula, one has the following approximation for Half Int:

f G -1 τc Y 2 τ c z=0 1 g(G -1 τ c ) 2 (z -τ c ) 2 + g (γ) g(G -1 τ c ) g(γ) 3
(zτ c ) 3 + g (γ) 2 4g(γ) 6 (zτ c ) 4 φ (y)dy , with φ the p.d.f of the random variable Q τ . Using the Jensen inequality and since 0 ≤ z ≤ τ c , we find:

|Half Int| ≤ f G -1 τc Y 2 ξ 2 2 λ n + αξ 4 2 λ n + α 2 ξ 6 8 λ n ≤ 1 2
C int λ n .

Since λ n , which is the variance of the random variable Q τ , is decreasing with n, let's study: Since one supports the hypothesis that f Y is bounded, using the mean value theorem, one has:

∆ f ≡ G -1
∆ f ≤ G -1
∆ f ≤ M   y G -1 τ c - y 2 2 y u=-∞ H(u) du G -1 τc y=-∞ - G -1 τc y=-∞ y G -1 τ c - y 2 2 H(y)dy   = M (G -1 τ c ) 2 2 G -1 τc u=-∞ H(u) du + G -1 τc u=-∞ (u -G -1 τ c ) 2 2 - (G -1 τ c ) 2 2 H(u) du = M G -1 τc u=-∞ H(u) v (u -G -1 τ c ) 2 2 u du = M   (u -G -1 τ c ) 3 6 H(u) G -1 τc u=-∞ - G -1 τc u=-∞ (u -G -1 τ c ) 3 6 h(u) du   .
Finally, we obtain with the same change of variable and Taylor approximation as previously:

∆ f ≤ M 6 τ c z=0 1 g(G -1 τ c ))
(τ cz) + g (γ) 2g(γ) 3 (τ cz) . Since C int and C s do not depend on e, this result remains meaningful when we are interested in the conditional expectation with respect to the random variable E and so E Y [L τ c -L τ ] ≤ 2 ε 2 ξ + C λ n . Moreover, using (9), we prove (7)

  +∞[ and f e the derivatives of F e . • A.3.2.5: f e are continuous over the interval [-∞, G -1 e (τ c )] ∀ e ∈ E and their derivatives are bounded, i.e ∀y ∈ R, ∀ e ∈ E, | f e (y)| ≤ M, with M ∈ ]0, +∞[ and f e the derivative of F e . • A.3.2.6: the derivatives of g e are bounded, i.e ∀y ∈ R, ∀ e ∈ E, |g e (y)| ≤ α, with α ∈ ]0, +∞[ and g e the derivative of G e .

  3.1.1, A.3.1.2, A.3.1.3 and A.3.1.4 and using functional derivatives and the implicit function theorem, we prove (2).

h - 1 e

 1 (τ c ) (F e (y)τ)dy = ∑ e p e ∆ PL e [h e ] .

3 ≤

 3 Rem e (α). Now, let's focus on the remainders. Following the Taylor-Lagrange inequality, if M such that d 3 ∆ PL F,δ,e dα M exists, we have | Rem e (α) | ≤ M|α 3 | 3! . Let' s find conditions for the existence of M. The third derivative is:

d 3 ∆ 3 =

 33 PL F,δ,e dα M 1 δ 3 e and hence |Rem e (α)| ≤ |M 1 ||αδ e | 3 3! which implies that lim Rem e (α)

2 as

 2 max η e → 0.

3 . 1 . 5

 315 or A.3.1.6, if ∃ ν ≥ 0 (sufficiently small) ∀ e ∈ E ∀ y ∈ R; |η e (y)| ≤ ν, we show (3) and (4):

  3.1.6 ensures the positivity of ∆ PL[G].

  du dy ≡ Half Int. A difficulty remains, though. Indeed, f Y in unknown, and in consequence, not easy to work with. That's why, at first, one will use f G -1 τc Y

  ) du dy .

Table 1

 1 Success rate to 5% K-S test

		Raw Ensemble	EMOS	Our Method
	Success rate in %	14	0.39	96

We have calculated the PIT series for each horizon (256), and use 5% K-S test for each of them. The success rate is the percentage of horizons passing the test.

  2.1, A.3.2.1, A.3.2.2, A.3.2.3, A.3.2.4, A.3.2.5 and A.3.2.6 we prove (

  Thus, one has EY,e [L τ c -L τ c ] ≤ (C int +C s )λ

														3
														2	φ (z) dz
	≤	M 6	ξ 3 2	λ n	+	3ξ 3 α 4	λ n	+	3ξ 3 α 2 8	λ n	+	ξ 3 α 3 16	λ n
	≤	1 2	C s λ n	.
											n


Baosheng Wang
email: baosheng@ece.ubc.ca

Yuejian Wu
email: yuejian@nortelnetworks.com

André Ivanov
email: ivanov@ece.ubc.ca

A Fast Diagnosis Scheme for Distributed Small Embedded SRAMs

Keywords: Distributed Small Embedded SRAMs, Memory Diagnosis, Data Retention Fault, SPC, PSC, Diagnosis Time

, with neglectable extra area cost.

Introduction

Currently, one of the System-on-a-Chip (SoC) paradigms is associated with a trend that an increasingly large number of small SRAMs are widely embedded for buffering data between different computational components [START_REF] Bommireddy | Test and debug of networking SoCs -a case study[END_REF]. As the embedded SRAMs (e-SRAMs) are increasingly dense, the ability for fault diagnose becomes more important. The diagnosis of such memories is not only important for locating the faulty cells such that repair can be done to improve the production yield, but also important for debugging the memory circuits for process improvement during the product development stage.

Difficulties with the diagnosis of distributed small e-SRAMs lie in the following: (i) External testers become increasingly incapable of diagnosing deeply embedded memories with limited external observability and controllability. Built-in-Self-Diagnosis (BISD) appears to be the only known cost-effective solution for such problems. (ii) For large numbers of relatively small e-SRAMs, the use of separate BISD controllers/circuitry can amount to unacceptable test area overheads. (iii) The spatial distribution occurring with several small e-SRAMs renders the routing of wires required for delivering patterns and analyzing the responses to be problematic, especially if a single BISD controller is to be shared by many SRAMs to keep overhead low. (iv) Their diagnosis time is dominated by the time for diagnosing Data Retention Faults (DRFs), which, in practice, are diagnosed by performing a read operation following a predetermined delay (e.g., 100 ms) [START_REF] Wang | Reducing embedded SRAM test time under redundancy constraints[END_REF]. In other words, the total diagnosis time for these small e-SRAMs is at least a couple of hundred milliseconds, regardless of the memory size/capacity and diagnosis methodology, e.g., parallel or sequential diagnosis.

To overcome the above challenges, previous work mainly focuses on developing diagnosis architectures that support parallel BISD with a single shared BISD controller [START_REF] Deng | A parallel built-in self-diagnosis scheme for embedded memory[END_REF][START_REF] Wang | A built-in self-test and self-diagnosis scheme for heterogeneous SRAM clusters[END_REF][START_REF] Aitken | A modular wrapper enabling high speed BIST and repair for small wide memories[END_REF][START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]. The parallel diagnosis of distributed small e-SRAMs minimizes the diagnosis area overhead without negatively affecting the diagnosis coverage, while allowing a dramatic reduction in the total diagnosis time. However, the scheme in [START_REF] Deng | A parallel built-in self-diagnosis scheme for embedded memory[END_REF] only supports multiple small e-SRAMs of the same size, which is usually impractical in a real SoC. The architecture in [START_REF] Wang | A built-in self-test and self-diagnosis scheme for heterogeneous SRAM clusters[END_REF][START_REF] Aitken | A modular wrapper enabling high speed BIST and repair for small wide memories[END_REF] has a separate general data background generator and control signal generator associated with each memory. This scheme is generally not feasible for diagnosing multiple distributed small e-SRAMs due to the routing and area penalty. The bidirectional serial interface used in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] for delivering patterns and collecting responses not only simplifies the routing from the BISD controller to the memories under diagnosis, but also solves the serial fault masking problem of the single-directional serial interface used in [START_REF] Nadeau-Dostie | A serial interfacing technique for built-in and external testing of embedded memories[END_REF][START_REF] Nadeau-Dostie | Serial interfacing for embeddedmemory testing[END_REF]. Unfortunately, a March element with the bidirectional serial interface in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] can detect at most one fault. Thus, the memory diagnosis capability is dependent on the defect rate. This results in long diagnosis time, even under a reasonable defect rate. More importantly, all the previous work fails to consider the DRF which dominates the time for small e-SRAMs diagnosis. As a result, the diagnosis coverage is compromised and the diagnosis time reduction is overstated.

This paper proposes a new diagnosis scheme targeting total diagnosis time reduction for distributed small embedded SRAMs while still maintaining acceptable control signal routing complexity and corresponding area overhead. Our designs are based on those proposed in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]. We use a pair comprised of a Serial to Parallel Converter (SPC) and a Parallel to Serial Converter (PSC) to replace the bi-directional serial interface in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] for each e-SRAM. This avoids the problems of the serial fault masking and defect rate dependent diagnosis. We combine the proposed scheme with an effective design-for-test (DFT) technique known as "No Write Recovery Test Mode" (NWRTM) [START_REF] Yang | Open defects detection within 6T SRAM cells using a No Write Recovery Test Mode[END_REF] for diagnosing DRFs without incurring any extra delay time. Together, these improvements yield a high coverage at the expense of a relatively short execution time and a low area overhead for diagnosing multiple, small distributed e-SRAMs.

The remainder of this paper is organized as follows. In Sec. 2, we briefly review the diagnosis architecture in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]. The detailed scheme designs for reducing the diagnosis time of distributed small SRAMs are proposed in Sec. 3. The diagnosis evaluations, i.e., diagnosis coverage analysis, diagnosis time comparison, and diagnosis area overhead estimation, are discussed in Sec. 4. Finally, Sec. 5 draws some conclusions.

Review of Previous Work

We begin by briefly reviewing the basics of the diagnosis architecture developed in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] for diagnosing distributed small e-SRAMs. To achieve low area overhead, a shared single BISD controller is adopted, which includes an address trigger to enable the address generators located local to each memory, a data background generator, and a control signal generator. The memory address generators are designed to be local to each memory to simplify routing. To overcome the data routing challenge and the serial fault masking problem arising from the single-directional serial interface [START_REF] Nadeau-Dostie | A serial interfacing technique for built-in and external testing of embedded memories[END_REF][START_REF] Nadeau-Dostie | Serial interfacing for embeddedmemory testing[END_REF], a bi-directional serial interface is designed to deliver patterns and collect responses. These responses are routed back to the controller and compared with the expected values, bit by bit for each memory. Once a defective cell has been detected, it can be replaced with a spare cell if it is available. This diagnosis scheme is shown in Figure 1.

The DiagRSMarch algorithm used in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] is based on a March C-algorithm [START_REF] Marinescu | Simple and efficient algorithms for functional RAM testing[END_REF], but can detect all the faults covered by March CW [START_REF] Wu | RAMSES: a fast memory fault simulator[END_REF] algorithm, which extends March C-by considering multiple data backgrounds.

The bi-directional serial interface in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] improves the single-directional serial scan circuit structures in [START_REF] Nadeau-Dostie | A serial interfacing technique for built-in and external testing of embedded memories[END_REF][START_REF] Nadeau-Dostie | Serial interfacing for embeddedmemory testing[END_REF] during the data application and observation, such that no fault can be masked by a preceding fault and all the fault cells can be correctly identified. An example of this bidirectional interface technique is shown in Figure 2. With such a serial interface, at most one fault can be detected for each March element. In other words, the total diagnosis process is dependent on the defect rate. For a general manufacturing process with a reasonable defect rate, this diagnosis scheme will result in long diagnosis time. Moreover, the authors of [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] do not consider the diagnosis of DRFs. Not considering DRFs limits diagnosis coverage and also mitigates the diagnosis time reduction achieved due to their proposed architecture since the time required for the diagnosis of DRFs usually dominates the small e-SRAM total diagnosis time.

The Fast Diagnosis Scheme

Architectural Overview

To improve the architecture in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] A time-efficient method to diagnose DRFs is referred to as the "No Write Recovery Test Mode (NWRTM)" in [START_REF] Yang | Open defects detection within 6T SRAM cells using a No Write Recovery Test Mode[END_REF]. We adopt this method here as well. Since this technique only requires a single control gate for the entire e-SRAMs to disable pre-charge bit lines during DRF diagnosis, an NWRTM signal is routed to all the memories. This signal is added into the control generator to enable the DRF diagnosis for all e-SRAMs.

For fair comparison, we use the March CW algorithm in [START_REF] Wu | RAMSES: a fast memory fault simulator[END_REF] for the proposed diagnosis scheme. According to the above discussions, our proposed diagnosis scheme is shown in Figure 3. an idle or no-op mode. If a memory is not equipped with an idle or no-op mode, the memory is placed in a read mode however with data read ignored. Since our PSC shifting path does not involve the memories, there is no fault masking effect. The comparator array in the central controller compares these responses with the expected values bit by bit. Once a defective cell is found, the diagnosis information, e.g., failure addresses, data background, etc., will be either registered for on-chip repair or scanned out for off-line analysis.

Similarly to that described in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], a pattern is written to each address only once for the largest memory or memories. For smaller ones, however, the same pattern could be written on each address multiple times as the addresses wrap around. It should be pointed out that the responses obtained from a smaller e-SRAM will change as soon as the addresses wrap around for the first time, due to the read-modify-write operations of the March C-. Knowing when the addresses wrap around requires memory size information. This paper chooses to store this information in the BISD controller, just like that in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], so that the comparison in the BISD controller can tolerate those redundant read/write operations.

Serial to Parallel Converter (SPC)

In the proposed diagnosis scheme, SPCs receive the patterns delivered from the Data Background Generator of the BISD controller and apply these patterns to the corresponding e-SRAMs in parallel.

If the serial pattern from the Data Background Generator is shifted from the least significant bit (LSB) to the most significant bit (MSB) and the SPC also converts the patterns from the LSB to the MSB, different types of SPCs will be needed. E.g., if both pattern delivery and conversion are performed from LSB to MSB, the converted pattern for the widest e-SRAM and smaller one would be DP [c-1:0] and DP [c-1: c-c'], respectively, when the Data Background Generator delivers a pattern denoted as DP [c-1:0], where c and c' is the IO number of the widest e-SRAM and the narrower one respectively. This is because the first (c-c') bits of patterns for the narrower e-SRAMs are shifted out of the SPC and get lost. However, the expected patterns delivered to the narrower e-SRAMs should be DP [c'-1:0]. This mismatch may reduce diagnosis coverage.

To prevent the potential coverage loss, we design the pattern delivery and conversion for all memories according to the following: the serial pattern is shifted from the MSB to the LSB and its corresponding SPC coverts the patterns from the MSB to the LSB. As a result, the corresponding conversion from the Data Background Generator will also be modified as that from the MSB to LSB. With this appropriate design, all the patterns are correctly delivered in parallel to every small e-SRAM under diagnosis.

Parallel to Serial Converter (PSC)

The proposed PSCs collect diagnosis responses from each e-SRAM in parallel and convert them into serial ones. These serialized response sequences are shifted back to the BISD controller from the LSB to MSB.

Although the response analysis for each e-SRAM is in a serial manner, the response sequences from all the memories are analyzed in parallel.

Since all the PSCs are independent of each other, they can be designed to be the same for each e-SRAMs, i.e., to go from LSB to MSB. To separate the memory output from the shifting components, a scan type of DFFs are adopted. An example PSC is shown in Figure 5. In Figure 5, the diagnosis responses are first captured into c' registers in parallel. This is followed by the memory entering an idle mode when shifting the memory responses back to the BISD controller for evaluation. If a memory does not have an idle mode, we can place the memory in read mode with read data ignored during the shift operation of the PSC. Since the memory does not interfere with shift operation of the PSC, there will be no negative impact on diagnosis coverage due to the extra read operations. However, an extra scan_en signal is required to control the capture of memory test response and the shift or serialization of the captured test response. It should be pointed out that the serialization operation of the PSC with the memory in an idle mode does not compromise at-speed diagnosis coverage. This is because in the read-modify-write operations used in the March C-, e.g., (R0 W1), the only signals that change after the R0 and before the W1 are the read/write enable (WEN) and data inputs. As long as we ensure that the WEN and data inputs do not change until the last shift operation in the PSC, the shift operation does not change at-speed coverage of the WEN decoding and data input circuitry.

Diagnosis of Data Retention Faults

To diagnose DRFs, we adopt a previously proposed lowpenalty DFT technique from [START_REF] Yang | Open defects detection within 6T SRAM cells using a No Write Recovery Test Mode[END_REF], referred to as "No Write Recovery Test Mode (NWRTM)".

Like the methodology in [START_REF] Meixner | Weak write test mode: an SRAM cell stability design for test technique[END_REF] and [START_REF] Champac | Bit line sensing strategy for testing for data retention faults in CMOS SRAMs[END_REF], in NWRTM, a special write cycle is created to distinguish a good cell from a faulty cell when subjected to a DRF caused by an open defect on the pull-up PMOS. A typical 6T SRAM cell with storage node A and complementary storage node B, shown in Figure 6, is used to illustrate the differences between the specifically designed "No Write Recovery Cycle (NWRC)" and a normal write cycle. The bitline precharge circuit of NWRTM is also shown in Figure 6, where the signal NWRTM is used to switch between the NWRC and a normal write cycle. In Figure 6, during a normal W1 cycle, node B is pulled down by the bitline BLb that is driven to "true" GND by the write control logic; and node A is pulled up by its pull-up PMOS. Here, "true" GND means that the node is driven to the GND voltage level by an active device. Due to the latch mechanism of the memory cell, the cell flips its value from "ZERO" to "ONE" as long as the voltage difference between nodes A and B reaches a threshold. In [START_REF] Meixner | Weak write test mode: an SRAM cell stability design for test technique[END_REF] and [START_REF] Champac | Bit line sensing strategy for testing for data retention faults in CMOS SRAMs[END_REF], by setting the bitlines BL and BLb to a given voltage level between Vcc and GND during the write operation, a good cell fails to flip while a faulty cell does. Similarly, we set the voltage level of BL and BLb to "float" GND and "true" GND respectively. Here, "float" GND means the node voltage level is at GND but not actively driven by any device. This causes the opposite result, i.e., a good cell succeeds at flipping its logic value while a faulty cell fails to do so. For the above example, a good cell has no problem writing a "ONE" because node B can be pulled down by the bitline BLb and the cell can flip to "ONE" due to the latch mechanism. However, a faulty cell subject to a DRF fails to flip because the voltage level of node A never exceeds that of node B. The voltage level of node A always remains at GND since (i) lacking the PMOS or path to the supply rail, node A cannot be pulled to "ONE" regardless of how low the node B voltage level reaches. Thus, the latch in this faulty cell malfunctions; and (ii) there are no charge sharing effects with bitline BL because it is set at "float" GND. GND is the lowest achievable voltage level and node A remains at GND. Consequently, the voltage level of node A never exceeds that of node B and the faulty cell fails to flip. Therefore, DRFs are detected under NWRTM.

P R E W L B L B L b A B N W R T M V c c G N D
Like a normal write operation, a NWRTM write operation can successfully write a good cell and may fail to write a defective cell causing DRFs. Therefore, the NWRTM can be merged with any March test by simply adding two extra NWRCs just before the normal write [START_REF] Yang | Open defects detection within 6T SRAM cells using a No Write Recovery Test Mode[END_REF]. Other DFT techniques do not share this advantage. Hence, NWRTM is the best in terms of test time for DRFs among all existing DFT techniques.

Evaluations

Diagnosis Coverage Analysis

Compared with the diagnostic scheme in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the proposed scheme simply replaces the bi-directional serial interface with a pair of SPC and PSC. All the other components in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] are preserved. In terms of diagnostic coverage, the adoption of the March CW in this paper provides the same coverage as the serialized March C-used in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]. However, due to the use of the NWRTM, the proposed scheme achieves additional coverage of DRFs. As a result, the diagnosis coverage of the proposed diagnosis scheme is increased compared with that of those in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] because its diagnosis capacities in DRFs and other defects not causing faulty logical behaviors but possibly causing reliability problems.

Diagnosis Time Comparison

Since the DRFs diagnosis is not considered in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the reported diagnosis time reduction can be considered to be optimistic. With our proposed diagnosis scheme, the diagnosis time is much less than that in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF].

The DiagRSMarch algorithm in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]

Although not obvious, the reduction factor R will always exceed one in practice because the iteration number k is always much larger than one.

If the DRFs are considered, the extra diagnosis time for DRFs when using the diagnosis architecture in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] includes 8k units of extra complexities (i.e., (w0/r0) R+L , (w1/r1) R+L ) and 200ms delay time. In comparison, the proposed scheme requires only 2 units of extra test complexities (i.e., Nw0/Nw1 in [START_REF] Yang | Open defects detection within 6T SRAM cells using a No Write Recovery Test Mode[END_REF]) for DRFs diagnosis. In this case, the diagnosis time ratio R can be calculated as shown in Equation ( 4):

8 [7 ,8 ] 8 2 10 (2 2 ) proposed T knct R T n ct ( 4
)
where t, T [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] and T proposed are in ns.

From equation ( 4), the reduction ratio due to the proposed diagnosis scheme could be extremely high when DRFs diagnosis is included.

To quantitatively investigate the diagnosis time reduction, we use a case study in [START_REF] Wang | Designs for Reducing Test Time of Distributed Small Embedded SRAMs[END_REF] as the benchmark e-SRAMs,

where n = 512, c = 100 and t = 10ns. We assume that 1% of the memory cells are defective and all four different defect types in [START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] occur with equal likelihood.

From [START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the maximum numbers of the total faults for each of the benchmark e-SRAMs in [START_REF] Wang | Designs for Reducing Test Time of Distributed Small Embedded SRAMs[END_REF] would be 256. Since the M1 element in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] can cover 75% of those faults and each iteration of the M1 element can identify at most two faults, the minimum iteration number k can be calculated to be (256*0.75/2) = 96. Using these assumptions, we found this diagnosis time reduction factor R, without considering DRFs, is at least 84. If DRFs are considered, R for the e-SRAMs in [START_REF] Wang | Designs for Reducing Test Time of Distributed Small Embedded SRAMs[END_REF] can be at least 145.

Area Overhead Estimations

Area overhead of the proposed scheme is evaluated according to the required number of transistors to implement the scheme and the number of global wires.

Compared with the designs in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the proposed scheme adds only one extra global wire for the control of the PSC.

In terms of transistor count, the bi-directional serial interface [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] actually includes a set of 4:1 multiplxers and latches. In the proposed scheme, a SPC and a PSC together require two sets of shift registers and 2:1 multiplexers, one for selecting between normal and test inputs and the other for the scan DFFs in PSC. In terms of transistor count, we find that a D-flip-flop is equivalent to two 6T SRAM cells while a latch is equivalent to one 6T SRAM cells. Therefore, this total area overhead extra to [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] is three 6T SRAM cells per bit. Fortunately, this extra area can be neglectable in practice. For example, this area overhead is around 1.8% for the benchmark e-SRAMs in [START_REF] Wang | Designs for Reducing Test Time of Distributed Small Embedded SRAMs[END_REF] when applying both that in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF] and the proposed diagnosis scheme.

Conclusions

The major challenge of diagnosing distributed small e-SRAMs is not only the diagnosis area overhead in terms of diagnosis circuits and wires routing, but also the diagnosis time under high coverage requirements. This paper presented a significant improvement on the diagnosis architecture described in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]. By replacing the bi-directional serial interface used in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the proposed scheme greatly reduced diagnosis time. By adopting a previous DFT technique known as "NWRTM" to detect data retention faults, the proposed scheme achieved better coverage. Compared with those in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the evaluation results indicate that the diagnosis time under a reasonable 1% defect rate environment is reduced by a factor of at least 84 with 1.8% of the total cells area extra to that in [START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF].

  Figure 1. The diagnosis scheme in[START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF]

Figure 2 .

 2 Figure 2. Memory with bi-directional serial connections in the BISD mode

Figure 3 .

 3 Figure 3. The proposed diagnosis scheme The proposed scheme works as follows. Before each March element begins, a test pattern is serially delivered to all SPCs local to the e-SRAMs. Once the pattern delivery is complete, the controller triggers the local address generator to conduct a full March element before providing a new test pattern. During the read phase of each March element, once the memory responses are captured by the PSC, they are shifted back to the BISD controller, bit by bit, while the memory is in

Figure 4 .

 4 Figure 4. Designs for pattern delivery and SPC A design example of two co-existing small e-SRAMs with c = 4 and c'= 3 is shown in Figure 4 (a) and (b), respectively. Obviously, the widest e-SRAM has an IO number of 4 while the narrower one has an IO number of 3 in this example. It should be pointed out that a new diagnosis pattern is delivered to the SPC only once just before each March element begins.

Figure 5 .

 5 Figure 5. Design for a general PSC

Figure 6 .

 6 Figure 6. A typical 6T SRAM cell and its precharge control circuits for NWRTM

  SRAMs are applied to these memories through the Serial to Parallel Converters (SPCs). The responses from each e-SRAM are routed back to the BISD controller in a serial fashion through the Parallel to Serial Converter (PSC). These responses are compared with the expected values, bit by bit for each e-SRAM by the comparator array. Once a defective cell has been detected, the diagnosis information, e.g., the faulty address, applied data background, etc., will be registered for on-chip repair or shifted out for off-line analysis. To avoid worsening the diagnosis signals routing problem, we design both the SPC and the PSC to reside locally to a memory under diagnosis. In other words, in our scheme, each e-SRAM possesses its own SPC and PSC. Like that in[START_REF] Huang | A parallel built-in self-diagnostic method for embedded memory buffers[END_REF][START_REF] Huang | A parallel built-in selfdiagnostic method for embedded memory arrays[END_REF], the memory address generator for each e-SRAM are also designed to be local to each memory to save the test address routing area.

for shortened diagnosis time without imposing excessive area overhead, we propose a diagnosis scheme based on serial delivery but parallel application of patterns and serial analysis of responses. The patterns serially delivered to e-The global BISD controller is designed based on the largest (i.e., largest capacity) and the widest (largest IO number) e-SRAM (s).

  is based on rightshift operational RSMarch with extra March elements that include both left-shift operations and checkboard patterns. Therefore, assuming the largest/widest e-SRAM under diagnosis has a capacity of n words and IO number of c, the diagnosis time of the DiagRSMarch algorithm in [7, 8] without considering DRFs diagnosis is

	[7,8] T		17	9 knct nct		(17 9) k	nct	(1)
	where t is the diagnosis clock period (ns) and k is
	iteration number of M1 elements required in [7,8].
	Without DRFs diagnosis, the diagnosis time of the
	selected March CW algorithm for our proposed
	diagnosis scheme can be calculated as
	T	proposed	2 {(5 5 5 ( 1)) (3 3 2 ( 1)) log } n c nc n c nc c t (2)
	where (5n+5c+5n(c+1)) is the complexity of a parallel
	March C-algorithm with our diagnosis scheme;
	(3n+3c+2n(c+1))	log	2	c	represents the complexity due
	to the added March element in March CW for detecting
	intra-word and column decoder faults.
	The diagnosis time reduction we achieve with the
	proposed scheme is given by the following
	R	T	[7,8] proposed T	(10	n	5	c		(17 5 ) (5 k n c	n	9)	3 nc c	2 ) log n c	2	c

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