Cristiano Forzan
email: cristiano.forzan@st.com

Davide Pandini
email: davide.pandini@st.com

Modeling the Non-Linear Behavior of Library Cells for an Accurate Static Noise Analysis

Modeling the Non-Linear Behavior of Library Cells for an Accurate Static Noise Analysis

Cristiano Forzan, Davide

INTRODUCTION

Because of the increasing clock frequencies, the use of highperformance design styles, like domino logic and pass-transistor logic, and the growing importance of the wiring coupling capacitance with respect to the gate and interconnect ground capacitance, the crosstalk-induced noise has become one of the limiting factors of the performances and functionality of large VLSI digital designs. Therefore, Static Noise Analysis (SNA) is a crucial task in the sign-off verification phase of the top-down ASIC design flow [START_REF] Levy | ClariNet: A Noise Analysis Tool and Methodology for Deep-Submicron Design[END_REF][2] [START_REF] Shepard | Global Harmony: Coupled Noise Analysis for Full-Chip RC Interconnect Networks[END_REF]. Basically, noise analysis consists of two different steps: first, the crosstalk-injected noise glitch amplitude and width (or area) are computed for the net under consideration (i.e., the victim net); then, the total noise glitch is obtained with the combination of the noise injected by the neighboring aggressor nets, and the noise propagated through the victim driver cell. In the second step, the noise at the victim receiver is compared against dynamic noise margins [START_REF] Zolotov | Noise Propagation and Failure Criteria for VLSI Designs[END_REF], represented by the Noise Rejection Curve (NRC). When the noise waveform width (or area) and amplitude are in the NRC failure region (i.e., above the curve), the noise analysis tool flags an error.

In several approaches, either the propagated noise is not considered at all, or the propagated and injected noise are evaluated separately. The noise propagating from the input to the output of the victim driver cell is usually obtained from precharacterized tables as a function of the input noise glitch area (or width) and height. In contrast, the noise injected on a victim net by adjacent aggressor nets through coupling capacitances is typically computed with network Model Order Reduction (MOR) techniques [3][5], or analytical macromodels that capture the relevant physical parameters of the noise waveform [START_REF] Vittal | Crosstalk Reduction for VLSI[END_REF], and by assuming a linear model of both the aggressor and the victim driver cells (the Thevenin-equivalent circuit for the aggressor drivers, and the holding resistance for the victim driver). The linearity assumption allows using superposition thus simplifying the worst-case identification that occurs when all the noise glitch peaks are aligned. However, in digital systems the library cells have a strong non-linear behavior, and a simple summation of the two noises may lead to a large underestimation of the total noise, thus potentially leaving many functional failures undetected. This problem was investigated in [START_REF] Zolotov | Noise Propagation and Failure Criteria for VLSI Designs[END_REF], where Zolotov et al. proposed an iterative approach to represent the victim driver with a Thevenin-equivalent circuit consisting of a pulsed voltage source and a resistance, in order to capture the non-linear behavior of the driver with a linear model, and carry out a noise analysis using MOR techniques and linear superposition. However, their approach may still yield large errors in both the noise peak (-18%) and width (-20%). Such large underestimations in the total noise glitch would leave many potential functional failures undetected in SNA. This paper is organized as follows: in Section 2 our macromodel for modeling the victim driver non-linear behavior is presented, and experimental results showing the effectiveness of our method are reported and discussed in Section 3. Finally, Section 4 summarizes some conclusive remarks.

PROPOSED MACROMODEL

In our approach, the victim driver is modeled with a Voltage-Controlled Current Source (VCCS) I DC , similarly to [START_REF] Zolotov | Noise Propagation and Failure Criteria for VLSI Designs[END_REF]. This current source is a non-linear function of both the cell input and output voltages, and is expressed as:

) , (

out in DC V V f I , (1)
which is obtained during a pre-characterization step, by performing a simple DC analysis, where V in and V out are swept across the characterization range corresponding to the typical voltage swing of the given technology.

A distributed RC network including the coupling capacitances represents the interconnections within the noise cluster1 , the aggressor driver linear models are Thevenin equivalent circuits (where V TH is a saturated ramp and R TH is the driving resistance) obtained as in [START_REF] Dartu | Calculating Worst-Case Gate Delay Due to Dominant Capacitance Coupling[END_REF], and the victim and aggressor receivers can be modeled by their input capacitances. Since the total noise waveform must be accurately evaluated at the victim driver output (or the victim net driving point), the coupled interconnect network is modeled at the driving points. Therefore, the driving point impedance of the interconnect network is represented by a coupled-model, which can be obtained with moment-matching techniques following the approach presented in [START_REF] Forzan | Nonlinear Macromodels of Large Coupled Interconnect Networks[END_REF]. The corresponding noise cluster macromodel of a victim and two coupled aggressors is shown in Figure 1.

Although this macromodel contains the non-linear VCCS I DC represented by the load curves (1), linear analysis and superposition can still be exploited by using the VCCS values computed during the pre-characterization step. Moreover, since the noise cluster macromodel is a simple circuit, the total noise waveform can be accurately and efficiently computed by means of a dedicated engine embedded into the noise analysis tool. Our approach can be straightforwardly extended to clusters with several aggressors with different switching directions and phase alignments.

EXPERIMENTAL RESULTS

In order to highlight the non-linear behavior of the victim driver cell, a simple test case in 0.13 m technology, consisting of two adjacent coupled nets, was considered. The wiring parasitics were extracted from two 500 m parallel-running interconnects, designed on metal layer 4, where the aggressor cell is an inverter and the victim driver is a 2-input nand. The results from circuit simulations performed with ELDO™ [START_REF]ELDO TM User Guide[END_REF] and reported in Table 1 clearly demonstrate that linear superposition between injected and propagated noise may induce a significant underestimation of the total noise. As a consequence, SNA based on NRCs can be quite inaccurate and may fail to report several noise-induced functional failures. Our approach has been tested on several noise clusters in 0.13 m and 90nm technology, and its accuracy evaluated against circuit simulations, and the error was always within few percents. The speed-up obtained with our approach was about 20X with respect to ELDO™, thus yielding a practical approach for noise analysis.

CONCLUSIONS

In this work we have proposed a macromodel for the victim driver non-linearity and generates a very accurate representation of the total noise glitch waveform at the victim driver output, when both propagated and crosstalk-injected noise are present. Our approach has been validated on a broad range of victim-aggressor configurations, and the experimental results show an excellent accuracy with respect to circuit simulations, with a significant computational speed-up. Future work will focus on developing a complete methodology for static noise analysis based on our macromodel.

R

  Figure 1. Noise cluster macromodel

Table 1 . Injected and propagated noise combination

 1

	Noise	ELDO™	Linear superposition	Error%	Our macromodel	Error%
	Peak (V)	0.345	0.269	-22.0	0.354	2.6
	Area (V•ps)	174.3	82.18	-52.8	175.7	0.8

Table 2

 2

shows the numerical results of two in-phase aggressors and one propagating noise glitch through the victim driver (2input nand).

Table 2 . Worst-case overlapping between two aggressors and one propagating noise glitch

 2

	Noise	ELDO™	Our macromodel	Error%
	Peak (V)	0.919	0.947	3.1
	Area (V•ps)	496.2	508.7	2.5

A victim net and its neighboring coupled aggressors are referred as noise cluster, or simply as cluster. 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) 1530-1591/05 $ 20.00 IEEE


Ajith Chandy

Tom Chen

Performance Driven Decoupling Capacitor Allocation Considering Data and Clock Interactions

We propose a sensitivity-based method to allocate decaps incorporating leakage constraints and tighter data and clock interactions. The proposed approach attempts to allocate decaps not only based on the power grid integrity criteria, but also based on the impact of power grid noise on timing criticality and robustness. The resulting algorithm reduces the power grid noise to below a threshold and improves the performance or timing robustness of the circuit at the same time.

I. INTRODUCTION

Traditional methods to reduce the power grid noise to below a threshold involves filling all the white spaces on chip with decoupling capacitors (decaps) and/or manually allocating decaps to the noise prone parts on the chip in an effort to keep the overall power supply noise low [START_REF] Chen | Power Supply Noise Aware Floorplanning and Decoupling Capacitance Placement[END_REF]- [START_REF] Chen | On-chip Decoupling Capacitor Optimization for High-performance VLSI Design[END_REF]. The conventional device for on-chip decaps is the gate capacitance of transistors. With continued CMOS scaling, the dielectric leakage of thin gate oxide devices will be significant and may become a limiting factor for its usage [START_REF]IC Power Distribution Challenges[END_REF]. An alternative to gate capacitance is the metal-insulator-metal (MIM) capacitors [START_REF] Ding | High-performance mim capacitor using ald high-k Hf O 2 -Al 2 O 3 laminate dielectrics[END_REF], [START_REF] Ishikawa | High-capacitance Cu/T a 2 /O 5 /Cu MIM structure for SoC applications featuring a single-mask add-on process[END_REF]. However, MIN capacitors add more complexity to CMOS process and cost. The premise of this paper is that the gate capacitance, or its variations, will continue to be used as decaps for high performance VLSI chips, and the overall trend of leakage current associated with the decaps is increasing. Therefore, we should use limited amount of decap to achieve the highest quality and performance possible under a leakage power constraint. In addition to the simple method of filling all white space on a chip with decaps, sensitivity based methods [START_REF]Optimal Decoupling Capacitor Sizing and Placement for Standard Cell Layout Designs[END_REF], [START_REF] Su | Fast Analysis and Optimization of Power/Ground Networks[END_REF], [START_REF]Simulation and Optimization of the Power Distribution Network in VLSI circuits[END_REF] have been proposed to minimize the power grid noise. In a sensitivity based approach, the amount of decaps is allocated based on the sensitivity of power grid noise in the form of voltage droop as a function of decaps at each location of the chip. This iterative process stops when all the available decaps are allocated, resulting in an allocation with the maximum possible improvement of power grid noise. However, after reducing the maximum power grid noise to below a given threshold, allocating more decaps to an area where no critical timing paths exist will add power consumption with little impact on performance. A better use of the remaining decaps is to allocate them based on the sensitivity of performance improvement and timing robustness.

II. PROPOSED APPROACH AND ALGORITHM

The proposed approach consists of two phases. In the first phase, decaps are allocated to reduce the power grid noise to a specified threshold. A sensitivity based approach, similar to that in [START_REF]Optimal Decoupling Capacitor Sizing and Placement for Standard Cell Layout Designs[END_REF], is used in this phase. Once the maximum VDD droop is reduced to below the threshold, the remaining decaps are allocated in the second phase. The goal of the second phase is to allocate the remaining decaps to improve the overall system performance. It uses the sensitivity of gate delay with respect to decap, ∂(gate delay) ∂(decap) , to gauge the worthiness of adding decap at a given location.

The value ∂(gate delay)

∂(decap)
cannot be found directly. We therefore break it down according to the chain rule as illustrated in Equation 1.

∂(gate delay) ∂(decap) = ∂(gate delay) ∂(VDD droop) × ∂(VDD droop) ∂(decap) (1)
The first term on the R.H.S. of Equation 1 can be calculated using direct sensitivity analysis with a polynomial equation. The second term on the R.H.S. of Equation 1 is calculated using the adjoint sensitivity method [START_REF]Optimal Decoupling Capacitor Sizing and Placement for Standard Cell Layout Designs[END_REF], [START_REF] Su | Fast Analysis and Optimization of Power/Ground Networks[END_REF], [START_REF] Pillage | Electronic Circuit and System Simulation Methods[END_REF], [START_REF] Director | The Generalized Adjoint Network and Network Sensitivities[END_REF].

Based on the required sensitivity values described previously in this section, the proposed algorithm iteratively calculates the amount of decaps at a given location. There are three constraints considered during the decap allocation process:

• the magnitude of power grid droop at any location must be less than a pre-defined threshold. • the total amount of decaps to be placed on a chip determined by the leakage power budget of the chip. • the total amount of decap associated with a given grid point limited by the available space around the grid point.

Table I shows the steps in the proposed algorithm. The sensitivity values used in the algorithm is calculated at each grid point location representing it's surrounding area. Once the sensitivity at each grid point is known, the amount of decaps for each location is determined using a Linear Programming (LP) formulation.

The LP formulation considers the interaction between the clock and data signals under the influence of added decaps. The setup time and hold time constraints are strictly enforced when considering adding decaps at a given location. This is extremely important for critical max. timing paths and min. timing paths as speeding up data signals relative to clock signals and vice versa by added decaps can potentially create timing violations. Table II illustrates the LP formulation. The objective parameter, T , is the clock cycle time that is expected after the addition of decaps in the system. The first constraint of the LP is to maximize the change in clock cycle time of the most critical path. The second constraint ensures that the hold time constraint is satisfied with the added decaps.

III. SIMULATION RESULTS

A power grid with 18x18 C4 bumps in a commercial 0.18µm CMOS process is used in our experiments. The die size is around 5x5mm 2 . A total of four critical paths in terms of both maximum delay time and minimum delay time are

Minimize

: T Subject to :

(S gi * D i ) + (S c1i * D i ) -(S c2i * D i ) + P D j ≤ T (S c2i * D i ) -(S c1i * D i ) -(S gi * D i ) ≤ P D j j = 1 . . . total number of paths d i ≤ D d i ≤ max(d i )
where,

D i = d i + (X 1 * d i1 ) + (X 2 * d i2 ) + ...
observed during the process of decap allocation using the proposed algorithm. The gate switching current of all gates (on or off the 4 signal paths) are modeled using triangular current sources. The current sources are attached to their corresponding grid points. SPICE simulations are used to calculate the adjoint sensitivities.

Two different power cases resulting in two different switching current distributions are studied, where Power Case 1 has more switching activities than Power Case 2. The pre-defined threshold for power grid droop is set to 10% and 8.33% of the nominal supply voltage for Power Case 1 and 2, respectively. The first iteration of the algorithm aims at eliminating all the power grid droops greater than the pre-defined threshold. Initially there were 168 and 10 violations of the pre-defined thresholds in Power Case 1 and 2, respectively. 55nf and 4.01nf were allocated during the first iteration for Power Case 1 and 2, respectively, and all the threshold violations were eliminated after the first iteration. The remaining decaps were allocated in the subsequent iterations for performance improvement. The total decap budget for both power cases is 70nf. After 4 iterations, the potential for performance improvement measured by the sensitivity has been reduced to below a threshold. The allocated decaps are 55nf, 5nf, 5.24nf and 3nf for 4 iterations for Power Case 1; and 4.01nf, 5.25nf, 3nf, and 3nf for 4 ietrations for Power Case 2.

To determine the effectiveness of the proposed algorithm, we compare our results with the results obtained using the existing sensitivity based approach in [START_REF]Optimal Decoupling Capacitor Sizing and Placement for Standard Cell Layout Designs[END_REF]. We also examine the effectiveness of taking the clock and data interaction into account when allocating decaps for performance improvement. These simulation results are compared with the results where only data signal delays are considered during decap allocation. All simulations were performed using a test chip structure of 5x5mm 2 with the two power cases. Table III shows the performance improvement and the final power grid droop in term of percentage of nominal VDD after the decap allocation process has terminated.

IV. CONCLUSIONS

The proposed algorithm demonstrated its ability to eliminate power grid noise violations and to achieve the maximum performance improvement possible. One may argue that the amount of performance improvement of 1.233% is small compared to delay improvements using conventional timing optimization methods. First, the proposed method is not intended to replace the conventional timing optimization methods. Rather, it is used after the timing optimization is done to further improve performance or timing robustness. Second, the amount of improvement depends very much on the power grid design, circuit's switching activities, and circuit's sensitivity to power grid droop.

TABLE I STEPS

 I IN THE DECAP ALLOCATION ALGORITHM

	Do until No Decap budget remaining{
	1	Simulate Original Network;
	2	Extract data from output file;
	3	Use data to reconstruct Adjoint Network;
	4	Simulate Adjoint Network;
	5	Extract data from output file;
	6	Calculate sensitivity ∂(V DD droop) ∂(decap)
		using adjoint sensitivity method;
	7	Calculate over all sensitivity ∂(gate delay) ∂(decap) ;
	8	Input required data values;
	9	Formulate the LP problem;
	10	Solve the LP problem;
	11	Recalculate the remaining Decap Budget;}

TABLE III NORMALIZED

 III CHANGE IN OP. FREQ. AND WORST CASE DROOP AS % OF V DD FOR POWER CASES 1 AND 2

	Cases	Power case 1	Power case 2
	Condition	Freq.	max	Freq.	max
			droop		droop
	Before decap addition	1	12	1	8.67
	After decap addition	1.0377	7	1.00257 8.14
	(existing method [2])
	After decap addition	1.0477	7.8	1.00313 8.3
	(data signals)
	After decap addition	1.0505	8	1.01182 8.31
	(data & clock signals)

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


Kameshwar Chandrasekar

Michael S Hsiao
email: hsiao@vt.edu

Integration of Learning Techniques into Incremental Satisfiability for Efficient Path-Delay Fault Test Generation *

In recent years, several Electronic Design Automation (EDA) problems in testing and verification have been formulated as Boolean Satisfiability (SAT) instances due to the development of efficient general-purpose SAT solvers. Problem-specific learning techniques and heuristics can be integrated into the SAT solver to further speed-up the search for a satisfying assignment. In this paper, we target the problem of generating a complete test-suite for the path delay fault (PDF) model. We provide an Incremental Satisfiability framework that learns from (1) static logic implications, (2) segment-specific clauses, and (3) unsatisfiability cores of each untestable partial PDF. These learning techniques improvise the test generation for path delay faults that have common testable and/or untestable segments. The experimental results show that a significant portion of PDFs can be excluded dynamically in the proposed incremental SAT formulation for large benchmark circuits, thus potentially achieving speed-ups for PDF test generation.

Introduction

The increasing clock frequencies and reduced feature sizes have made delay testing a necessity. While various fault models have been proposed to capture the effect of delay defects, the path delay fault (PDF) model is the most accurate in characterizing the cumulative effect of distributed delays along each path in a circuit. However, the main bottleneck in the PDF model is the exponential number of paths in a circuit. As a result, Automatic Test Pattern Generation (ATPG) suffers from temporal explosion if each path delay fault needs to be targeted in the circuit. In order to reduce the number of PDFs that need to be considered for test generation, several methods have been proposed to identify the untestable PDFs a priori. In [START_REF] Heragu | Fast Identifi cation of untestable delay faults using implications[END_REF], static logic implications are used to identify many untestable path delay faults in a circuit. Other methods have been proposed in [START_REF] Li | Effi cient Identifi cation of Non-Robustly Untestable Path Delay Faults[END_REF][START_REF] Shao | An Efficient Method to Identify Untestable Path Delay Faults[END_REF] to quickly identify the untestable PDFs. In general, these techniques identify a set of PDFs that are untestable and predict a lower * supported in part by NSF Grants CCR-0196470 and CCR-0305881.

bound on the number of untestable PDFs. However, integrating these techniques into the test generation algorithm leads to an additional overhead for the ATPG engines that directly work on the circuit structure and use different logic systems [START_REF] Fuchs | RESIST:A Recursive Test Pattern Generation Algorithm for Path Delay Faults considering Various Test Classes[END_REF][START_REF] Shao | Path delay fault test generation for standard scan designs using state tuples[END_REF][START_REF] Battacharya | Test Generation for Path Delay Faults using Binary Decision Diagrams[END_REF]. More recently, in [START_REF] Padmanaban | Using ZBDDs and BDDs for effi cient identifi cation of testable path delay faults[END_REF], the authors propose a Zero-suppressed Binary Decision Diagram (ZBDD) based technique to identify all the testable PDFs in a circuit. The PDFs are stored as a ZBDD and set operations are used to remove all the untestable PDFs from the ZBDD. Subsequently, an ATPG engine can be invoked to generate the test vectors for all the testable PDFs identified by their technique.

Boolean Satisfiability (SAT) was first used for delay testing in [START_REF] Chen | A Satisfi ability-Based Test Generator for Path Delay Faults in Combinational Circuits[END_REF], in which all the paths in a circuit are enumerated, and hence it may not be applicable for large circuits. In [START_REF] Kim | On Applying Incremental Satisfi ability to Delay Fault Testing[END_REF], the authors suggest that incremental SAT is suitable for PDF testing. They provide a basic framework to generate non-robust test vectors for all the PDFs in the circuit. However, their framework is devoid of problem-specific learning techniques that can improve the performance of the SAT solver. To improve the performance of SAT, it has been suggested in [START_REF] Ganai | Combining strengths of circuit-based and CNF-based algorithms for a high performance SAT solver[END_REF][START_REF] Lu | A Circuit SAT solver with Signal Correlation Guided Learning[END_REF][START_REF] Arora | Enhancing SAT based Equivalence Checking using static logic implications[END_REF] that circuit-related information can enrich the clause database of the SAT solver for equivalence checking and model checking problems. This opens an opportunity for problem-specific learning to discover the knowledge that could enhance the SAT solver.

In our work, we present efficient learning techniques to incrementally reduce the number of paths that need to be considered, thereby speeding up the Incremental SAT solver, for PDF test generation. We target the problem of generating a complete test suite for all the path delay faults in a circuit. The contributions of our work are as follows:

1. We convert the static logic implications in a circuit into clauses and add them to the clause database of SAT solver. Since implications were shown to be efficient in identifying the untestable PDFs in a circuit, they will help to quickly identify the untestable path delay faults during test generation. we add these clauses along with the sensitization constraints for each fanout-free segment.

( -e ) ( c ) ( h ) ( -f ) ( j ) ( i ) ( l ) ( k ) ( m ) ( -c )
(-f + -h) (e + f + h) (-e + i) (-g + i) (e + g + -i) (h + -j) (i + -j) (-h + -i + j) (j + -l) (k + -l) (-j + -k + l) (-c + m) (-j + m) (c + j + -m) (-i + -m + -o) (i + m + -o) (-i + m + o) (i + -m +o)
3. When an untestable partial PDF is encountered during test generation, we extract the unsatisfiable core of clauses. These clauses are used to identify other untestable PDFs, on the fly, during test generation.

The experimental results show that a significant portion of PDFs can be excluded dynamically in the proposed incremental SAT formulation for large benchmark circuits, thus potentially achieving speed-ups for PDF test generation.

The rest of the paper is organized as follows. In Section 2, we provide a brief introduction to incremental SAT and path delay faults. In Section 3, we describe the mechanism to add static logic implications and learned segment clauses to the SAT solver. Section 4 presents the idea of extracting unsatisfiable cores for untestable PDFs and using them to avoid other untestable path delay faults. The experimental results on ISCAS 85 and ISCAS 89 circuits are reported in Section 5 and Section 6 concludes the paper.

Preliminaries

Incremental Satisfi ability (ISAT)

The Boolean Satisfiability problem is to determine whether a satisfying variable assignment, V , exists for a given Boolean formula, Φ(V ), commonly expressed in conjunctive normal form (CNF). A CNF is a conjunction of clauses, where each clause is a disjunction of literals. A literal is a variable occurring in its positive or negative polarity. The general form for the formula is as follows:

Φ(v 1 , v 2 , ...v n ) = C 1 .C 2 . ...C m (1)
where,

• Φ is a propositional formula in CNF

• v i is the i th Boolean variable in the CNF • C j is the j th clause in the CNF
In conventional SAT, all the clauses in the CNF are manipulated to find a satisfying variable assignment for Φ. In the case of incremental SAT, we partition the clauses into different groups. Initially, only a single partition of clauses is in the clause database. If a satisfying assignment is found for the existing set of clauses, we add the next partition of clauses iteratively. If no satisfying assignment is found in an iteration, then the SAT solver can stop and report that no satisfying assignment exists for Φ, since a subset of clauses in Φ cannot be satisfied.

Incremental SAT is advantageous if the SAT solver can conclude that Φ is unsatisfiable using a smaller set of clauses. In the worst case, we have to add all the partitions into the clause database of the SAT solver. It should be noted that the solver can proceed from its previous variable assignments when we add-in the next partition of clauses to the SAT solver in the subsequent iteration. Since a huge number of untestable PDFs exist in a circuit [START_REF] Cheng | Classifi cation and Identifi cation of Nonrobust Untestable Path Delay faults[END_REF], and many untestable path delay faults have common untestable segments, incremental SAT can identify the untestable PDFs in groups and speed up the test generation.

Path Delay Fault Testing

For each structural path in the circuit from the primary input to the primary output, two path delay faults are associated -rising PDF and falling PDF. In order to detect a path delay fault, we require two test vectors < t 1 ,t 2 >, where a rising (falling) transition is asserted at the beginning of the path for the corresponding rising (falling) PDF. In addition to the initial transition, we sensitize the off-path inputs of the path to propagate the transition to the output. A test < t 1 ,t 2 >, for a given path delay fault, is said to be robust if the test can detect the fault independent of other path delay faults in the circuit. On the other hand, if the path delay fault can be masked by the presence of other faults in the circuit, then the test < t 1 ,t 2 > is called a non-robust test. In our work, we target non-robust tests, since non-robust test generation is a direct application of incremental SAT and the non-robust conditions are present in robust tests as well. Nevertheless, the proposed techniques can be extended to robust test generation or any other circuit problem that is an application of incremental satisfiability by modifying the incremental clauses for each iteration in the CNF.

For non-robust PDF test generation, it is sufficient to sensitize the off-path inputs in the second test vector t 2 , such that the on-path transition propagates to the primary output. In Figure 1, we demonstrate the non-robust test generation for PDFs using incremental satisfiability. The circuit is illustrated in Figure 1 (A). The consistency clauses for the gates in the circuit is given in part (B) of the Figure . The sensitization clauses for each segment is shown in part (C). We start from segment ad ↑ and recursively add the sensitization clauses for the fanout segments. The recursive addition of segments is illustrated by the tree structure in Figure 1 (D). When a fanout stem is reached (eg. segment h j ↑), we add the segments in its branches recursively in a depth-first fashion. In this example, we first add jl ↑. If we reach a primary output during recursion, then all the sensitization clauses for the current PDF have been satisfied, and the variable assignments at the primary inputs is the test vector for that PDF. In this example, the rising path delay fault at a-d -e-hj -l is testable. Then, we backtrack in the segment recursion tree, delete the sensitization clauses of jl ↑ and try to sensitize the next fanout segmentjm ↑. If the SAT solver reports that a partial PDF is untestable, all PDFs with this partial PDF as a prefix are untestable. In this example, the partial rising PDF adehjm is untestable. So, the ATPG can backtrack immediately in the segment recursion tree without sensitizing the segment mp. In this way, the ATPG proceeds for all the paths in the circuit and generates test vectors for all the testable PDFs.

Static Learning

In general, for solving circuit problems using Boolean Satisfiability, the clauses for all the gates in the circuit are built to form the complete clause database. It has been shown in [START_REF] Ganai | Combining strengths of circuit-based and CNF-based algorithms for a high performance SAT solver[END_REF][START_REF] Lu | A Circuit SAT solver with Signal Correlation Guided Learning[END_REF][START_REF] Arora | Enhancing SAT based Equivalence Checking using static logic implications[END_REF] that additional constraints can be added to the clause database to speed up the search process. In order to take advantage of static learning for path delay faults, we add the static logic implications, generated from the circuit, as well as certain segment-specific clauses to the clause database. It should be noted that these clauses are quickly generated in a preprocessing technique and are computed only once, before the actual test generation.

Static Logic Implications

The implications in a circuit provide useful information that helps to deduce relations between different lines in the circuit. They have been widely used to detect a huge number of untestable path delay faults in [START_REF] Heragu | Fast Identifi cation of untestable delay faults using implications[END_REF][START_REF] Li | Effi cient Identifi cation of Non-Robustly Untestable Path Delay Faults[END_REF][START_REF] Shao | An Efficient Method to Identify Untestable Path Delay Faults[END_REF]. In the Boolean Satisfiability domain, implications can be seen as the circuit information that aid in accelerating the Boolean Constraint Propagation (BCP) (the most time consuming routine in the SAT solver [START_REF] Zhang | Chaff: Engineering an Effi cient SAT solver[END_REF]). In order to speed up the SAT solver and detect untestable path delay faults faster, during ATPG, we convert the implications into clauses and add them to the circuit CNF. As direct implications are already encoded in the circuit clauses, we add only the indirect implications and extended backward implications to the circuit CNF. These implications are generated using the techniques proposed in [START_REF] Zhao | Static Logic Implications with application to redundancy identifi cation[END_REF].

Each implication is converted into a clause as follows. Suppose we have a static implication: a → b. The clause equivalent of this implication is ( ¯a + b). Similarly, for all the implications obtained from the circuit, we add the corresponding clauses to the circuit CNF. Because of the low computational overhead involved in generating static logic implications, this step is simple. Though simple, it can enrich the clause database with additional constraints that will increase the deductive power of the SAT solver.

Segment-specifi c learned clauses

In incremental satisfiability for path delay fault testing, we solve the clauses for partial PDFs first and then augment the clause database incrementally. The clauses added for each increment corresponds to the sensitization of a segmentfault (also referred as segments in the sequel). The initial segments (partial PDFs) that form the common prefix for various path delay faults (see Figure 2 (A)) are targeted once and are re-used while backtracking in the path recursion. Similarly, the segments in the latter part of the circuit (near the primary outputs) may be the common post-fixes for different path delay faults (see Figure 2 eration methods do not account for the latter scenario in the circuit. Moreover, in order to sensitize each segment, we add only the on-path and off-path clauses. It will be beneficial to the SAT solver if we add the clauses that prune the conflict search subspace for that segment. When a segment is encountered multiple times as a prefix/postfix, these clauses will guide the SAT solver to avoid the associated conflictspace and reach at a conclusion more quickly. Motivated by these factors, we learn the clauses that can be added along with the sensitization constraints, for each segment, to speed up the SAT solver. As a pre-processing step, we assert the sensitization constraints for each segment and perform an all-solutions SAT search [START_REF] Li | A novel SAT all-solutions solver for effi cient preimage computation[END_REF]. We store the conflict-induced clauses, generated during the SAT search, as learned segment clauses. All these conflictinduced clauses constrain the solution space for the target segment. These clauses should be satisfied (a necessary condition) for detecting any PDF involving this segment. It should be noted that a proper subset of the conflict clauses define a solution super-space for that segment. Hence, these clauses represent constraints for the given segment and will preserve the satisfiability of the original problem.

In general, solving for the sensitization constraints of a single segment is very easy. Moreover, it is not necessary to complete the all-solutions SAT search for every segment, since each conflict clause can be individually stored as a learned segment clause. Considering the time constraints, it may be sufficient to learn the clauses only for certain segments, instead of all the segments. Due to the nature of segment recursion from input to output in incremental SAT, the segments with large number of fanout paths is more likely to be traversed fewer times (Figure 2 (A)) as compared to the segments with the same number of fanin paths (Figure 2 (B)). We use a scoring mechanism to determine the segments that will be traversed many times during PDF test generation. We assign the number of fanin paths in each segment (found using a linear time algorithm) as its score. Then, we compute the weighted average of all the scores and learn for segments whose scores are higher than the weighted average. Since the segments with higher scores will be encountered more times during ATPG, it is necessary to quickly traverse these segments to accelerate the ATPG.

Dynamic Learning from Unsatisfi able Cores of untestable partial PDFs

Defi nition 1 Given an unsatisfiable CNF formula Φ, a subset of clauses, φ ⊆ Φ that is unsatisfiable by itself is called an unsatisfiable core of clauses.

The unsatisfiable cores were initially used to validate a SAT solver in [START_REF] Zhang | Validating SAT solvers Using an Independent Resolution-Based Checker: Practical Implementations and other Applications[END_REF][START_REF] Goldberg | Verifi cation of Proofs of Unsatisfi ability for CNF Formulas[END_REF]. In their work, all the conflict clauses that are generated during SAT search and their resolvent clauses are stored externally. They propose an algorithm to generate an unsatisfiable core from these clauses. Starting from the final conflict clause, the algorithm backtraces through the resolvent clauses. Finally, the set of all original clauses reached during the backtrace is identified as the unsatisfiable core. We use the same procedure to generate the unsatisfiable core. However, we do not need to store the conflict clauses externally, since our objective is to extract the unsatisfiable core rather than validate the SAT solver.

In the segment recursion of incremental SAT, we obtain a partial PDF that is untestable. The corresponding clauses in the database of the SAT solver form an unsatisfiable CNF.

The sensitization clauses in the unsatisfiable core for this CNF can be mapped to a group of segments that cannot be sensitized together. All the path delay faults that contain these segments are guaranteed to be untestable. They are called the untestable core of segments (or simply untestable core) in the sequel. A motivating scenario is given in Figure 3. Suppose we obtain an unsatisfiable CNF corresponding to an untestable partial PDF (a

-b -c -d -e -f -g -h -i).
The untestable core of segments is found to be {ab, e f , hi}. It can be concluded that all the path delay faults that contain all these three segments are untestable. This will help to avoid testing for other untestable path delay faults and to speed up the test generator. After encountering each untestable partial PDF, we identify the untestable core of segments and store them in a table, T . If any partial PDF contains all segments of any untestable core, then that PDF is guaranteed to be untestable. Before choosing a segment for path recursion, we need to look up the table, T , to check if the current partial PDF will cover any of the untestable core of segments. If it covers any untestable core of segments, we ignore that segment and look for the next segment in the path recursion. This step helps to avoid one iteration of adding clauses, solving for SAT and deleting clauses in the incremental SAT framework.

Consider the untestable core of segments (UC) and the current partial PDF (PP) as sets of segments. If an untestable core of segments is a subset of the partial PDF, UC ⊆ PP, then we have to backtrack in the path recursion. However, checking for a subset in the table of unsatisfiability cores, for every iteration of ISAT, is time consuming. As an alternative, we introduce a single watched segment technique (motivated by the two-literal watching rule in zChaff [START_REF] Zhang | Chaff: Engineering an Effi cient SAT solver[END_REF]) to look for subsets on the fly.

While adding an untestable core to the table, T , we assign one segment, which is not yet chosen in the path recursion, as the watched segment for that row. For each segment, we store a watched list that contains the row numbers of the table, T , where it is a watched segment. Please note that each row corresponds to an untestable core. During test generation, before a segment is chosen, we traverse the rows of T in its watched list. For each row/untestable core, we search for the next available segment to be assigned as the watched segment for that core. If no free segment is available, then that core has been covered and we can conclude that the corresponding partial PDF is untestable.

The watched segment technique is explained in the following example. Let P = {s 1 , s 2 , s 3 , s 4 } be the set of segments in the current partial PDF, and we have to choose s 5 as the next segment in the path recursion. Let The watched list for s 5 contains row 1 and row 3 in the table. For row 1, {s 1 , s 3 } have already been chosen in P, and {s 7 , s 9 } are free segments. So, we can change the watched segment and assign s 7 or s 9 as the next watched segment. However, for row 3, all the other segments in that row have already been chosen in P. This means that the untestable core in row 3 will become a subset of the partial PDF if we choose s 5 . Therefore, we avoid s 5 and look for the next segment in the segment recursion to proceed with the test generation. Note that we did not consider row 2 during this entire manipulation and it is not necessary to update the watched segments for the backtracks in segment recursion.

Experimental Evaluation

The above techniques were implemented in C++ and integrated with zChaff [START_REF] Zhang | Chaff: Engineering an Effi cient SAT solver[END_REF], downloaded from the web-site [START_REF] Malik | Boolean Satisfi ability Research Group at Princeton[END_REF]. However, the proposed techniques can be integrated into any DPLL based SAT solver. In fact, it may be beneficial if we use a SAT solver with sophisticated incremental SAT solving capabilities such as MINISAT [START_REF] Een | An Extensible SAT solver[END_REF]. zChaff was chosen since it has an inbuilt feature to extract unsatisfiable cores. The experiments were conducted on a 3 GHz Pentium 4 machine with 1 GB RAM running the Linux OS. A non-robust PDF ATPG was implemented to generate test vectors for all the path delay faults in ISCAS 85 and ISCAS 89 benchmark circuits with a time limit of 5000 seconds. We compare our technique with [START_REF] Kim | On Applying Incremental Satisfi ability to Delay Fault Testing[END_REF] only, since it is the most recent Boolean Satisfiability technique proposed for PDF test generation.

The experimental results are shown in Table 1. For each circuit, the number of fanout-free segments and the number of path delay faults are first reported. Next, the results of PDF ATPG using incremental SAT are listed for (1) no learning (similar to the ISAT in [START_REF] Kim | On Applying Incremental Satisfi ability to Delay Fault Testing[END_REF]), (2) static learning only, and (3) combined static and dynamic learning. The final column of the table reports the total number of detected PDFs by all three methods. Note that each method is able to complete detection of all testable PDFs in the circuit. Under the Static-learning ISAT, both the number of clauses added and the time taken for test generation are reported. For the combined static and dynamic learning, the number of PDFs excluded due to unsatisfiability cores during dynamic learning, the number of PDFs excluded as a percentage (%) of total number of untestable PDFs, and the time taken for test generation are given.

From Table 1, it is observed that there is an improvement in time for many circuits, such as c1908, c2670, c3540, s5378 and s9234. The efficacy of dynamic learning is demonstrated by the number of untestable path delay faults identified by the untestable cores. The untestable cores are able to dynamically identify that more than 20% of the PDFs are eligible to be excluded during ATPG for most of the circuits. While there is some overhead in pruning the number of PDFs, the corresponding speedup is also obtained for larger circuits. For several small circuits, there is no appreciable improvement in time taken to complete the test generation. It is likely that the clauses added, during static learning for fanout-free segments, and the unsatisfiability cores, take more time than simply running the original SAT solver without learning for these cases. Finally, it should be noted that the implementation of the proposed techniques and the variable ordering are deciding factors for the performance of a SAT solver. In zCHAFF, the solver has to re-adjust its clause database and variables' status, every time a new clause is added incrementally. So the addition of many statically learned clauses may lead to a significant time-overhead as seen in c1355.

Conclusion and Future Work

In this work, we introduce static and dynamic learning techniques for an incremental satisfiability framework. We use the framework to generate a complete non-robust test suite for the path delay fault model in a circuit. We learn from static logic implications and segment-specific clauses, at each iteration of the increment, in order to enrich the clause database of the SAT solver. We use the unsatisfiability cores of unsatisfiable CNFs, generated for untestable PDFs, to identify other untestable path delay faults. Experimental results show that these unsatisfiable cores help to identify a large number of untestable PDFs and they are subsequently avoided during test generation. Potential directions for future research include:

• Represent all the PDFs as a ZBDD [START_REF] Padmanaban | Using ZBDDs and BDDs for effi cient identifi cation of testable path delay faults[END_REF] and use the ZBDD structure for ISAT. This representation will help to physically remove the untestable PDFs on-the-fly.

• Generate test vectors for a particular subset of PDFs (e.g., critical paths only), by representing them as a ZBDD and proceed with ISAT.

• Provide a seamless integration of these techniques into a specialized incremental SAT solver like MINISAT [START_REF] Een | An Extensible SAT solver[END_REF].

2 .

 2 For each fanout-free segment in the circuit, we try to sensitize the segment-fault constraints individually and store the conflict clauses generated during the search as learned segment clauses. Then, during the ATPG,

  + d) (-b + d) (a + b + -d) (c + e) (d + e) (-c + -d + -e) (-e + -h)

Figure 1 .

 1 Figure 1. Incremental SAT for Non-Robust PDF testing

2 Figure 2 .

 22 Figure 2. Prefix & Postfix partial PDFs

Figure 3 .

 3 Figure 3. Unsatisfiable core of segments

  us consider the following UTC, a table of untestable core of segments, where * denotes the watched segment in each row. UTC = {{s 1 , s 3 , s 5 * , s 7 , s 9 }, (Row 1) {s 5 , s 10 , s 15 * , s 20 }, (Row 2) {s 1 , s 3 , s 5 * }} (Row 3)

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)


Mohammed El Rhabi
email: elrhabi@gmail.com

Abdelilah Hakim
email: abdelilah.hakim@gmail.com

Zouhir Mahani
email: zouhir.mahani@gmail.com

A tool for scanning document-images with a photophone or a digicam

In this work, we propose a tool to scan a document-image acquired with a cameraphone. Firstly, we try to reduce the noise in the document-image. Then we build a new image by cropping or by perspective rectifying the denoised one. From this step, we can expect the document to a real quadrangle. The new document is analyzed and we try to find images, logo or non text element in the documentimage with the aid of an image segmentation. At this stage, we provide deux parts of the document image: the text part and the "non text" part of the document-image (images, logos, non ...). The text part of the document-image is enhanced by an original pde's based model that we proposed. The "non text" document is enhanced by classical methods such as retinex processing. Then, we merge both parts of the document image by a poisson image editing. The effectiveness and the robustness of the proposed process are shown on numerical examples in real-world situation (images acquired from cameraphones).

Introduction

Computer vision based documents recognition could be an interesting way to dematerialize informations to manage clients and company's internal documents, offering enterprise wide fast access to business critical information while enhancing the achitecture in place. Typically the dematerialized document formats are PDF.

Here, the problem could be separated as least in five steps: noise reduction, perpective rectifying, segmentation : text and non text parts of the document-image, text and image enhancement and a merge of enhanced parts. In the computer vision approaches, low cost cameras (webcam, cameraphone, ...) could introduce some distortions and noise artifacts, see [START_REF] Baird | The State of the Art of Document Image Degradation Modeling[END_REF] for an overview of document image degradation modeling. Document images are supposed to be obtained from a mobile device -a cameraphone more exactly, but could also come from any digital camera. In the following, we will only suppose the device to be a cameraphone as this is the case where most of the problems occur.

The image restoration images by PDE's based models starts to produce signifiant results as images with the diffusion of documents to remove noise while preserving important information for readability ([2,3,5,6]) or to separate the back to front ink interferences ( [START_REF] Moghaddam | RSLDI: Restoration of single-sided low-quality document images[END_REF]) . These works have shown that could be improved up to 30% recognition rate of OCR by restoring the document images.

Generally speaking, an image u could be seen as the product of a reflectance v and the illumination effect I (see [START_REF] Horn | Robot Vision[END_REF]). This model has been used in [START_REF] Kim | Joint nonuniform illumination estimation and deblurring for bar code signals[END_REF][START_REF] Dumas | An evolutionary approach for blind deconvolution of barcode images with nonuniform illumination[END_REF][START_REF] Rhabi | Method of restoring a blurred image acquired by means of a camera fitted to a communication terminal[END_REF] to restore blurred barcode signals under nonuniform illumination.

This paper provide a tool to scan a document with cameraphone. After the segmentation process, the text enhancement is based on new method based on an isotropic ( [START_REF] Mahani | Text Enhancement by PDE's Based Methods[END_REF]) or anisotropic ([6]) diffusion to estimate the luminance (or the log of the luminance) of a document-image.

Our methods can produce three kinds of documents: black and white, grayscale or color ones. In all cases, input images are color pictures. Producing color documents should be seen as a different workflow, involving mostly the same algorithms as in the grayscale processing.

The paper is organized as follows : section 2 gives a brief description of a camera lens. Section ?? presents the non uniform illumination problem and defines a global model. Then two methods are given as solutions, namely a natural criterion afterward a pde's based model. Section ?? describes the method and shows how to implement it. Finally, some numerical results illustrate this work in Section 5.

Description

Most important image degradations are related to blur, poor contrast, Jpeg compression artifacts or even an inappropriate point of observation.

In figure 1, we show a flow chart of the processing sequence to be applied to restore document image. Input image (top of the flow chart) is the color Jpeg image sent by the cameraphone user. At the very bottom of this chart, output images are grayscale images, a black and white one (fax purpose) and optionally a thumbnail of the grayscale image. All other images shown on the chart are temporary images.

We can identify three major processing steps, which will be further explained with much more details :

-Denoising: if needed this processing step aims at reducing the noise of a color image. Here, we use for example the fast algorithm proposed in [START_REF] Chambolle | An algorithm for total variation minimization and applications, Special issue on mathematics and image analysis[END_REF].

-Dewarping : if we can identify the document page borders in the image, we build a new image by cropping or by perspective rectifying the denoised one. From this step, we can expect the document to fit a real quadrangle (see section 3). -Document-image segmentation : at this step, we try to separate text and "non text" parts in the documentimage. This segmentation is obtained by a constrained watershed(see [START_REF] Beare | A Locally Constrained Watershed Transform[END_REF]). -Text and "non text" enhancement (if applicable):

• Text enhancement : this processing step works as a bad contrast or non uniform illumination correction of the whole document. We refer to [START_REF] Mahani | Text Enhancement by PDE's Based Methods[END_REF][START_REF] Saoud | Document Scanning in a tough environment : application to cameraphones[END_REF]) where we describe our method to enhance text in document image by pde's based models.

• "Non text" enhancement (images or logo) by a retinex processing (see [START_REF] Rahman | Retinex processing for automatic image enhancement[END_REF]).

-The final document is obtained by the merge of both parts of the document (text and "non text" parts) by mean of a Poisson Image Editing (see [START_REF] Pérez | Poisson image editing[END_REF])

For the sake of simplicity, some processings have been expunged here. Indeed, some features are measured and collected all over the processing sequence to provide some user notifications about the input image quality and so our ability to deal with it. These features come from the range of graylevels or the amount of noise in each color channel. They are all merged to give some clues about the input image quality.

Page border based dewarping : A way to post-correcting the observation point

It is particularly relevant to produce straight documents as opposed to inclined ones (see fig. 2), photographers should not be stressed too much about perfectly framing the document. Even more, sending well aligned documents to faxes is important to enhance the final document legibility. When page borders are visible in an image, we can use them as a guideline to correct the point of view and make a new image which simulates a perfectly straight document.

First, page borders need to be detected. To perform such a detection we need some image preprocessing techniques to obtain image edges (see fig. 3).

As one can see, a first pass reduces information(fig. 3(a)) before extracting with Canny filtering the most important edges (fig. 3(c)) in the image. From here, these edges are only delivered as marked pixels.

One way to convert edge location to a line equation is achieved by using the Hough transform algorithm. The following equation describe a line :

ax + by + c = 0 (1)
Where (x, y) are the coordinates of the points lying on the line which parameters are (a, b, c). But our problem is to find parameters only knowing pixel edge locations. The Hough transform proposes a way to exchange the unknowns. Making the assumption that (x, y) are known there are two unknowns 3 which describe all lines that meet the point (x, y).

(1) is not well adapted (reasons are outside the scope of the paper), and typical Hough transform adopts a polar line representation (see 4).

So, a point (x 0 , y 0 ) in the image gives a set of lines represented as a sinus curve in the Hough space. Our Hough space behaves as an accumulator space, meaning for each point label as edge we accumulate the associated sinus curves in the Hough space. Peaks appear in the Hough space which are the detected lines we are looking for. Because a point in the Hough space represents the parameters of a line in the image.

Figure 5 represents the detected image edges , the associated Hough space representation, and fitted lines. Several lines are detected but we still don't know which ones constitute the page borders. So all sets of four lines are tested if they are good candidates to represent the page borders. Unrealistic sets are immediately rejected and a score is given to the other ones. This score is built from the assumptions that the good lines have extremities closed two by two and they constitute a quadrangle big enough in the image. Figure 6 shows selected edges from previous line detection: When a frame is detected, we only need to perform the perspective correction of the image. Perspective correction is performed by using bicubic interpolation, and is a real perspective transformation (homography) hence respectfull of original document proportions.

Separation Text -Non Text in the document-image

In this section, we need a tool to localize uniform background image regions from previous ink extraction method. Such a tool should be a constrained watershed algorithm (see [START_REF] Beare | A Locally Constrained Watershed Transform[END_REF]). Here, images can be viewed as a topographical relief, which are flooded progressively (see figure 7). In practice, we consider gradients magnitude of the image. In figure 8, we describe the first step of this process, we remove the text from the document image in order to obtain only the non text part of the document. Figure 9, we apply a filtered constrained watershed with the rational assumption that the biggest uniform region is probably the background of the document-image.

Numerical results

In this section, we present some simulation results showing the performance of the presented tool. We show the ability of the proposed process to successfully scan document-image acquired by camera in a tough environment.

We show how the step of segmentation is important is we would like to scan complex document-images, for example document acquired by a photophone from magazines or when we we have document-images containing text and images.

In all examples, the original images are acquired from a Sony Ericksson K800i (3.2 megapixels). Figure 11 shows an example of the dewarp-text enhancement by methods proposed in this paper. 0ne can see that page corners are not necessary in the image, only edges are required to detect frames.

Figure 12 shows the performance of our process to provide scanned quite complex documents. Here, after a segmentation which separates the text and images in the document-image, the texts in the document are enhanced by the method that we have proposed in [START_REF] Saoud | Document Scanning in a tough environment : application to cameraphones[END_REF]. As regards the "non text" part of the document, the images are enhanced by a retinex processing.

In figure 13, the acquired document needs all processes, namely a dewarp, a segmentation to separate text and image in the document, an enhancement for each parts of the segmented document-image., then a Poisson Image Editing (see [START_REF] Pérez | Poisson image editing[END_REF]) in order to merge both parts and to reconstruct a coherent document. This test is very interesting and our process has not only correctly cropped the document but the image enhancement give a good result. In figures 14, 15 and 16, we present some results for blackboard or whiteboard images. This use-case could be interesting for students and professionals who want to capture quickly informations with their cameraphones. For example students could have the slides of their course or when the meeting is over, but the whiteboard is chock full of lists, notes, diagrams, and to-do's you didn't have time to jot down yet. Instead of manually transcribing it all, you could pull out your cameraphone and snap a picture. Even if these images are very noisy (due to the acquisition process) our process gives good results, but in term of readabilty/printability.

Conclusion

In this paper, we present a tool for scanning document-images. We have described five steps to obtain a correct scan. So far we have shown that our process remains robust even in rought environment and in low lightning conditions. Moreover, the resulting process depends only on few fixed parameters. Moreover, we proved that this process allows to estimate a scanning version of a document-image acquired from a cameraphone in a robust and reproductible way.

Fig. 1 .

 1 Fig. 1. Global flow chart of the image processing involved in the document image processings improvement from qipit TM . Images are represented like circles, while processing steps are associated with quadrangles. Decisions look as diamonds. A color image is provided as input (top of the chart), and one may expect three output images (very bottom of the chart): a grayscale one, a fax image (black and white) and optionally a thumbnail of the grayscale image. Major processing steps are deblurring, dewarping, and ink extracting. Minor steps deal with user notifications (not mentioned here) or binarization.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Typical documents seen under an inclined point of view.

Fig. 4 .

 4 Fig. 4. Polar line representation -the couple of values (ρ, θ) describe a line in polar coordinates.

Fig. 5 .

 5 Fig. 5. Hough transformation to detect lines

  (a) Selected edges (b) Part of the score came from distances between lines extremities

Fig. 6 .

 6 Fig. 6. Selected edges (fig.6(a)) lead to the computation of a score. This score is partly based on the cumulative distance between segments end points (dashed lines in fig. 6(b))

Fig. 7 .

 7 Fig. 7. Watershed principle.

Fig. 8 .

 8 Fig. 8. Original document is seen under some classical mathematical operations.

Fig. 9 .

 9 Fig. 9. Separation text-non text information in a document-image.

Fig. 10 .

 10 Fig. 10. Example -Notice that page corners are outside the bounds of the image.

Fig. 11 .

 11 Fig. 11. Original document is seen under some perspective which makes it slanted. Text lines become parallel in the corrected document.

Fig. 12 .

 12 Fig. 12. Original image acquired from a Sony Ericsson K800i

Fig. 13 .

 13 Fig. 13. Original image acquired from a Sony Ericsson K800i

Fig. 14 .Fig. 15 .Fig. 16 .

 141516 Fig. 14. Original acquired from a Casio Computer co. ltd-Digital still camera

(a, b, c) are related to each other, so formally speaking only two unknowns remained


Mahmut Kandemir
email: kandemir@cse.psu.edu

Feihui Li
email: feli@cse.psu.edu

Guilin Chen
email: guilchen@cse.psu.edu

Guangyu Chen
email: gchen@cse.psu.edu

Ozcan Ozturk
email: ozturk@cse.psu.edu

Studying Storage-Recomputation Tradeoffs in Memory-Constrained Embedded Processing *

Fueled by an unprecedented desire for convenience and self-service, consumers are embracing embedded technology solutions that enhance their mobile lifestyles. Consequently, we witness an unprecedented proliferation of embedded/mobile applications. Most of the environments that execute these applications have severe power, performance, and memory space constraints that need to be accounted for. In particular, memory limitations can present serious challenges to embedded software designers. The current solutions to this problem include sophisticated packaging techniques and code optimizations for effective memory utilization. While the first solution is not scalable, the second one is restricted by intrinsic data dependences in the code that prevent code restructuring. In this paper, we explore an alternate approach for reducing memory space requirements of embedded applications. The idea is to re-compute the result of a code block (potentially multiple times) instead of storing it in memory and performing a memory operation whenever needed. The main benefit of this approach is that it reduces memory space requirements, that is, no memory space is reserved for storing the result of the code block in question.

Introduction and Motivation

One of the major challenges for embedded software writers is memory space limitation. While memory capacities attached to embedded systems keep increasing, the rate at which complexity and dataset sizes of embedded applications is increasing is much faster. Consequently, making best use of available memory space is becoming increasingly critical. This is true for diverse embedded application domains ranging from automobile control to disk processing. There are at least two current solutions to this memory problem. The first is to use sophisticated circuit/packaging techniques to cram as much memory as possible in as little area as possible. This solution is not scalable and is typically costly from both design and implementation perspectives. The second solution is to use software techniques to reduce memory space requirements by maximizing data reuse and exploiting data lifetime information. Recent studies explored this option in different directions that include both computation space and data space optimizations [8, 4, 5]. While the techniques in this group are effective in many embedded application domains as has been demonstrated by prior work, they are inherently limited by the intrinsic data reuse in the program and by potential overlap between lifetimes of different data structures. Consequently, in cases where there is not much data reuse to exploit and lifetimes of a large majority of data structures overlap with each other, such techniques cannot be very successful.

In this paper, we explore an alternate approach for reducing memory space requirements of embedded applications. The idea is to re-compute the result of a code block (potentially multiple times) instead of storing it in memory and performing a memory access whenever needed. In other words, we study the cases where re-computation can substitute for memory accesses. The main potential benefit of this approach is to reduce memory space requirements, that is, no space is reserved for storing the result of the code block in question. A potential disadvantage is the increase in execution cycles as re-computing a result each time it is required (in particular when the result has a high degree of locality) can be costly from the performance overhead viewpoint. However, this may not always be so since sometimes accessing a data generates misses in the on-chip storage, and visiting off-chip memory can cost tens of cycles (which also keeps increasing). In such cases, re-computation can bring performance benefits as well. Therefore, the performance impact of re-computation should be experimentally studied and quantified.

Focusing on array-intensive embedded applications that execute in memory-constrained systems, this paper makes the following contributions:

• We propose two integer linear programming (ILP) based techniques to study maximum savings that could come from re-computation. The first ILP strategy is a static one in which the status of a code block (i.e., whether its results should be stored or re-computed when needed) is decided at exactly one point during optimization. In contrast, the dynamic scheme re-evaluates the storage versus re-computation decision multiple times.

• We propose and evaluate a heuristic approach, and compare it to the ILP-based solution. Our experimental results reveal that the proposed heuristic performs very well for most of the time.

• We explain how our approach can be extended to handle multi-level memories, to account for data lifetimes, and to reduce memory space requirements under performance constraints.

Our experimental evaluation with six embedded applications demonstrates that re-computation based ILP and heuristic solutions are beneficial from both memory space and performance perspectives.

The remainder of this paper is organized as follows. Section 2 presents the formulation for the problem of minimizing the number of execution cycles under memory space constraints. Section 3 explains the solutions we propose. Section 4 discusses several extensions to our baseline approach. Finally, Section 5 concludes the paper with a summary.

Problem Formulation

We study our memory space optimization problem at two levels: static and dynamic. In the static approach, we decide for each computation whether its results should be stored in the memory or not at exactly one point during optimization, and this decision is maintained throughout the execution. More specifically, once we decide that the results of a computation will not be stored, we stick to this decision until the end of execution; i.e., each time we need the result of that computation, we re-compute it. In contrast, in the dynamic scheme, we consider the possibility of storing the results of a computation several times. Consequently, a computation whose results are not stored at the first time it is encountered can still have its result stored at a later step during execution (when it is re-computed). Clearly, this potentially brings additional benefits at the cost of additional implementation complexity. This paper evaluates both these schemes.

Our approach works on a graph called flow graph, which captures the producer-consumer relationship among different code blocks in the application. Each node of this graph is a code fragment whose granularity can be tuned. For example, each node can be an entire procedure, a loop nest, or a sub-nest (which is a small loop that contains a subset of the iterations of a loop nest in the application). The edges between the nodes indicate potential data flow between them. Specifically, a directed edge (arc) from a node to another indicates that the former generates a result which is subsequently used by the latter. It should be noted, though, this is a conservative approximation of real execution (with a particular input) since the data transfer implied by an edge may not be materialized due to control flow. We use T to denote the set of nodes in the flow graph, and assume that there is a unique terminal node in the flow graph. If this last assumption fails, we create a terminal node and connect it to all the other nodes in the graph that have no successors. We use N to denote the number of nodes in the flow graph being optimized. We also assign a level (starting with 1) to each node in the graph. Specifically, the level of node i is set to L+1, where L is the largest level among all the nodes from which we have an edge to node i. We use M to indicate the number of levels in the flow graph. In processing the flow graph for optimization purposes, we also use the term step to denote the processing of a level, i.e., each step corresponds to processing of a particular level in the graph.

Before going into our discussion of the static and dynamic schemes, let us study an example scenario that illustrates the tradeoffs between storage requirements and recomputation overheads. We consider the flow graph shown in Figure 1(a), and focus on two simple scenarios for illustrative purposes. In the first scenario, we assume that only the results of β 1 , β 2 , and β 3 are stored in memory, and results of all other nodes in the graph are re-computed when they are needed. In the second scenario, the results of nodes β 1 , β 2 , β 3 , β 4 , and β 6 are stored in memory, whereas nodes β 5 are β 7 are re-computed. In both the scenarios, it is assumed that the results of nodes β 4 , β 5 , β 6 , and β 7 are needed as output (i.e., none of them is temporary or intermediate data). In the first scenario, computing β 4 requires memory accesses for the results of β 1 and β 2 . Then, computing β 5 requires re-computation of β 4 since the result of the latter is not stored in memory. [START_REF] Austin | The SimpleScalar/ARM Toolset[END_REF] Note that this re-computation requires fresh accesses to memory for the results of β 1 and β 2 . Similarly, computing β 6 requires recomputation of β 4 . The remaining computations for this scenario as well as the computations/memory accesses for the second scenario can be identified using a similar strategy. The tables in Figure 2 give, for both the scenarios, the necessary memory accesses and re-computations. The entry in a cell (β x , β y ) in these tables indicates the necessary computation (C), re-computation (R), memory read (M r ), and memory write (M w ) of/for β y in order to compute the result of β x . Note that, while not storing the result of a computation can save memory space, it can also trigger lots of recomputations, whose performance implications should be accounted for. An important question then is to reduce execution cycles (improve performance) under a memory capacity constraint. tables in Figure 2 also reveal an interesting behavior of re-computation. Suppose that a particular node β i has p predecessor (β j1 through β jp ). Whenever we want to compute β i , we need to re-compute all β j k s whose results have not been saved in memory. This in turn requires re-computation of all predecessors of β j k s whose results have not been saved, and so on. For example, computation of β i in Figure 1(b) can trigger a lot of re-computations depending on how many of the preceding nodes have their results stored in memory. Obviously, this chain of re-computations can potentially increase overall execution cycles.

β1 β2 β3 β4 β5 β6 β7 β1 C, Mw - - - - - - β2 - C, Mw - - - - - β3 - - C, Mw - - - - β4 Mr Mr - C - - - β5 Mr Mr - R C - - β6 Mr Mr Mr R - C - β7 Mr Mr Mr R R R C β1 β2 β3 β4 β5 β6 β7 β1 C, Mw - - - - - - β2 - C, Mw - - - - - β3 - - C, Mw - - - - β4 Mr Mr - C, Mw - - - β5 - - - Mr C - - β6 - - Mr Mr - C, Mw - β7 - - Mr R R Mr C

Static Scheme

Let β i represent the ith computation in the flow graph of the application, where 1 ≤ i ≤ N . The memory space occupied by storing the results of β i is denoted by S(β i ), and the computation (or re-computation) time (in cycles) for β i is expressed using C(β i ). We assume that writing the result of β i into memory and accessing the stored result from memory take M w (β i ) and M r (β i ) cycles, respectively. We use the following 0-1 variable2 to indicate whether β i is (decided to be) stored in memory or not (when we process the point where it needs to be computed the first time):

αi = 1, if βi is stored in memory 0, otherwise
Based on these 0-1 variables, the total computation (or recomputation) cost of β i can be computed as follows:

C(βi) = αiMw(βi) + C(βi) + β j ∈pred(β i ) D(βj ),
where pred(β i ) denotes the set of immediate predecessors of node β i . The first term in this expression indicates the total cost of accessing the results of all the predecessors of β i . The second component gives cost of writing its result to the memory (if it is to be stored in memory), and the last term gives the cost of computing β i itself (note that, irrespective of whether the result of β i is stored in memory or not, it needs to be computed). For a given node

β i , D(β i )
gives the cost of accessing its result for the computation of some other node. It should be noticed that such an access can involve re-computation (depending on whether its result has already been stored in memory or not), which can in turn trigger cascade re-computations. Consequently, we have the following expression for D(β i ):

D(βi) = αiMr(βi) + (1 -αi)C(βi).
One can then formulate the overall cost of executing the entire application as the computation cost of the terminal node (denoted β s ). In mathematical terms:

C total = C(βs),
On the other hand, the total memory space consumption (S total ) can be calculated as:

S total = β i ∈T αiS(βi).
It is to be observed that this calculation implicitly assumes that once a memory space is allocated for the result of β i , this allocation is retained until the end of execution. While this certainly simplifies the formulation of the problem, it would be more realistic to assume that, once the result of β i is not needed by any other node in the flow graph, its memory is deallocated and (potentially) recycled for storing the results for other nodes. Constructing the expression for the memory space consumption in such a case requires taking into account lifetimes of (the results of) the flow graph nodes, and is discussed in Section 4.

Assuming that S max is the maximum allowable memory space consumption (i.e., storage capacity), we are now ready to formulate our optimization problem in formal terms: "Minimize C total under S total ≤ S max ."

The 0-1 variables are the only unknowns in this formulation, and the objective of any exact or heuristic solution would be to determine the values of these variables. In Section 3, we will present both exact and heuristic solutions to this optimization problem. Note that, it is also possible to define the dual of this problem, that is, minimizing storage occupancy under performance constraints.

Dynamic Scheme

In this scheme, it is possible to store the result of β i at each time step k, where 1 ≤ k ≤ M . Consequently, α i variables employed in the static scheme are not sufficient. Instead, we parameterize these variables with both i and k. In mathematical terms:

α i,k = 1, if βi is stored in memory at step k 0, otherwise
We need to change our cost formulation as well. Specifically, C(β i , k) denotes the cost of computing (or recomputing) β i at step k. There are two reasons for such a parameterization. First, it is possible that β i is not stored in memory at step k but later is decided to be stored (say, at step k where 1 ≤ k < k ≤ M ), when for example the available memory capacity changes dynamically. Second, due to the same reason, it is possible that we first decide to store it in memory but later delete it (and re-compute it whenever necessary following this deletion point). This second case will be detailed in Section 4. Our formulation is:

C(βi, k) = α i,k Mw(βi) + C(βi) + β j ∈pred(β i ) D(βj , k -1). D(βi, k) = α i,k Mr(βi) + (1 -α i,k )C(βi, k).
Note that, in computing C(β i , k), we use D(β j , k-1) since whatever we decide for β j in the previous step (step k -1) will dictate the cost of accessing it at the current step (step k). In addition to these formulations, we need an additional constraint if we assume that once the result of a node is decided to be stored, the memory space allocated for it is never deallocated (i.e., once stored, always stored):

α i,k -α i,k-1 ≥ 0.
Based on these constraints, we can formulate the overall cost of executing the entire application as:

C total = C(βs, M),
where β s is the terminal node in the flow graph. On the other hand, the total memory space consumption at step k (S total,k ) can be calculated as:

S total,k = β i ∈T α i,k S(βi).
An important advantage of the dynamic scheme is that it can adapt itself well to the dynamic changes in available memory space. For example, in a multi-programmed embedded environment, depending on the relative criticalities of simultaneously running applications, the memory space allocated to a particular application can change from one execution point to another. As a result, a node (β i ) that has been decided not to be stored in memory (due to space constraints) can later be stored in memory when more space becomes available. Consequently, in this dynamic scenario, it might make more sense to talk about time step-wise memory capacity limit, that is, S max,k , which denotes the maximum allowable memory consumption at step k. Obviously, the storage consumption at each step (that is, S total,k ) must be smaller than or equal to S max,k . Therefore, our performance optimization problem under memory constraint can be expressed as follows:

"Minimize C total under S total,k ≤ S max,k , where 1 ≤ k ≤ M ."

Proposed Solutions

In this section, we propose two different solutions to our memory space management problem. The first solution is based on zero-one integer linear programming (ILP). ILP is suitable for our particular memory utilization problem since our formulation of the problem described above lends itself to ILP computation very well. In this formulation, our objective is to determine α i (in the static scheme), or determine α i,k for each β i and time step k (in the dynamic scheme) -where 1 ≤ i ≤ N and 1 ≤ k ≤ M . However, one point needs to be clarified here. While the static scheme operates on a one-dimensional space (iterated by i), the dynamic scheme operates on a two-dimensional scheme (iterated by both i and k). This can potentially increase the number of 0-1 variables dramatically, making an ILP-based solution infeasible in some cases. However, it must be observed that, many of the (i, k) pairs are not feasible in practice anyway (for a given application), and the costs expressions involving them do not need to be constructed at all. This is because, for a given flow graph node represented by β i , the possible time steps that need to be considered are between the step where it is first encountered in processing the graph and the last step of the execution. In addition, one might be able to further shrink the feasible search space by taking into account the lifetimes of (the results of) the nodes, as will be further elaborated in Section 4. This ILP-based solution can be useful in its own right, but it can also be used for evaluating the quality of the heuristic solutions. That is, once a heuristic solution has been developed, the results it generates can be compared to those obtained through the ILP-based method. This can help one evaluate the quality of the heuristic in question, and refine it as necessary. Still, for very large problem sizes/applications, one may need to resort to fast heuristic solutions.

Our second solution to this optimization problem is a heuristic based on a greedy approach. In this approach, we consider all the nodes of the flow graph, and decide whether the result of each node should be stored in memory or not. To guide this decision, one obviously needs a metric or a cost function. Our approach to this problem can be explained as follows. For each node, we compute the number of potential consumers, i.e., the set of nodes that will use the result generated (produced) by this node directly or indirectly (again note that a potential consumer may not be an actual consumer at runtime due to dynamic flow of control). After this, we select the node with the maximum number of such consumers and decide to store its result in memory provided that doing so does not lead to consuming more memory space than the available capacity. In doing so, we also keep track of the memory space consumed (occupied) so far. In the next step, we select, from the remaining nodes, the one with the maximum number of consumers and schedule it if the memory capacity constraint allows doing so. We continue this way until all the nodes have been processed or the available memory capacity has already been reached. If this latter case occurs, the results of the remaining (unprocessed) nodes are decided not to be stored in memory; that is, they are marked for re-computation. The goal behind this heuristic is to store the most frequently used results as much as possible, thereby utilizing the available memory space in the most effective way. Notice that this heuristic tends to store the results of the nodes that reside in the upper portions of the flow graph as they are typically the ones whose results are used by many nodes (consumers).

Figure 3 gives a sketch of this heuristic solution. Considering the flow graph in Figure 1 once more and assuming that all the nodes in this graph require a memory space of the same size to store their results, and that the on-chip memory can hold the result of only one node, this heuristic would select β 4 among β 4 , β 5 , and β 6 (under the assumption that the results of β 1 , β 2 , and β 3 are already in memory), and store its result in memory. Note that, while this heuristic is a static one, it is easy to convert it to a dynamic one. In the dynamic version of the heuristic algorithm, one can take lifetimes of individual graph nodes into account, and also performs transfers between G and T , depending on the dynamic variations in available memory size. This can in turn lead to better utilization of available memory space.

Extensions

In this section, we discuss three important issues. The first issue is about making our approach more effective by taking into account lifetimes of data. Next, we discuss how our baseline approach can be extended to work with multilevel memories.

So far, we have assumed that when the results of a node is stored in memory, it remains there until the end of execution. In many cases, this may not be necessary as we can deallocate the memory space as soon as the result of that node is not needed anymore by any of the remaining nodes, i.e., it is dead. The time frame between the generation of the result and the point at which it is dead (i.e., it will not be needed in the rest of execution) is called its lifetime. It is to be noted that the lifetime for a given data (the result of a node) can be identified (conservatively) by analyzing the flow-graph. Identifying lifetimes means that, for each node β i , we need to determine the valid k values (where 1 ≤ k ≤ M ). It does not make sense to reserve a space for the result(s) of β i before we reach it during evaluation. And similarly, it is possible to save memory space by deallocating the memory space allocated to β i once it is last used. Therefore, for each β i , one can have the following bounds for k: k min,i ≤ k ≤ k max,i . Note that, k max,ik min,i gives the region in which the result of β i is live. Let L i refer to the lifetime of node β i . We can change the memory space consumption expression in the static scheme as follows:

S total = max{ βi∈T α i S(β i )}.
In this expression, T refers to a subset of T (which represents all nodes in the flow graph) with the property that life-times of all the nodes in T overlap with each other. The max expression finds the set T such that the cumulative memory space occupied by the results of all the nodes in it is the largest among all possible alternative T s. This can be incorporated into our ILP formulation by constraining the range of k for each β i and by dropping the constraints α i,kα i,k-1 ≥ 0 from consideration. We now discuss how our approach can be extended to work with multi-level memories. While our discussion mainly focuses on a two-level memory, it is straightforward to extend it to memory hierarchies with larger number of levels. We denote the first level and the second level memory using L1 and L2, respectively. Typically, the first level memory is smaller, faster, more power-efficient, and more expensive (in terms of dollars/bit) than the second level memory. We mainly focus on the static scheme here but it is not difficult to extend this description to the dynamic scheme. We first need some modifications to the definition of our 0-1 variables. Specifically, the new variables should distinguish between the two memory levels:

α i,L1 = 1, if β i is stored in L1 memory 0, otherwise α i,L2 = 1, if β i is stored in L2 memory 0, otherwise
An important design decision needs to be made about whether two copies of the same data (one in L1 and the other in L2) are allowed or not. If multiple copies are not allowed, we need the following additional constraint:

∀β i : α i,L1 + α i,L2 ≤ 1.
This constraint can easily be included into the ILP-based formulation. Based on these α i,L1 and α i,L2 variables, new cost formulations are as follows:

C(β i ) = α i,L1 M wL1 (β i ) + α i,L2 M wL2 (β i ) + C(β i ) + βj ∈pred(βi)
D(β j ).

D(β

i ) = α i,L1 M rL1 (β i ) + α i,L2 M rL2 (β i ) +(1 -(α i,L1 + α i,L2 ))C(β i ).
In this expression, M wL1 and M wL2 refer to memory write costs (in terms of execution cycles) for L1 and L2, respectively. Similarly, M rL1 and M rL2 denote the corresponding memory read costs. Then, the overall cost can be expressed as:

C total = C(β s ),
where β s is the terminal node in the graph. Finally, the total memory space consumptions in memories L1 and L2 can be computed as:

S total,L1 = βi∈T α i,L1 S(β i ).

S total,L2 = βi∈T α i,L2 S(β i ).

Consequently, assuming that S max,L1 (resp. S max,L2 ) is the maximum allowable memory space consumption (i.e., storage capacity) for memory L1 (resp. L2), we can formulate our optimization problem for two-level memory in formal terms:

"Minimize C total under S total,L1 ≤ S max,L1 and S total,L2 ≤ S max,L2 ."

We also want to mention that there are other possible memory constraints when a multi-level memory hierarchy is considered. For example, instead of the one above, one could try to minimize C total under σ 1 S total,L1 + σ 2 S total,L1 , ≤ S max where σ 1 and σ 2 are positive constants that satisfy σ 1 + σ 2 = 1.

Conclusions

Most embedded systems operate under tight memory and power constraints. Therefore, their performance requirements must be carefully balanced against their memory space requirements and power consumption. While stateof-the-art code/data optimization techniques try to make best use of available memory space, they are inherently restricted by available data reuse. The work presented in this paper takes an alternate approach where it employs recomputation instead of memory accesses if doing so is beneficial from performance and/or memory space occupancy viewpoints.

Figure 1 .

 1 Figure 1. Two example flow graphs.

Figure 2 .

 2 Figure 2. Two different scenarios for an example data-flow graph. The entry in a cell (βx, βy) indicates the necessary computation (C), recomputation (R), memory read (Mr), and memory write (Mw) of/for βy in order to compute the result of βx.

Figure 3 .

 3 Figure 3. The sketch of the heuristic algorithm (the static approach).

  T : the set of nodes in the flow graph G: the set of nodes whose results are decided to be stored S total : the current memory space occupation S total : the maximum allowable memory occupation

	ALGORITHM:
	compute the consumer set CSi for each node βi
	G = ∅
	S total = 0
	order the nodes according to non-increasing values of |CSi|
	while (there is still available space in memory and T = ∅)
	{
	select the node βi from T with the largest |CSi|
	if (S total + S(βi) ≤ Smax) then
	{
	remove βi from T
	add βi to G
	S total = S total + S(βi)
	}
	}

NOTATION:

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)

For example, if β 4 contains a statement such as b=a+3 and β 5 contains a statement such as c=b-2, re-computing β 4 (during the evaluation of β 5 ) would generate a computation like c=(a+3)-2 as b is not stored in memory.

A 0-1 variable is one that takes a value of 0 or 1. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

* This work was supported in part by NSF Career Award #0093082.