Maxime Daisy
email: maxime.daisy@ensicaen.fr

David Tschumperlé
email: david.tschumperle@ensicaen.fr

Olivier Lézoray
email: olivier.lezoray@ensicaen.fr

A Fast Spatial Patch Blending Algorithm for Artefact Reduction in Pattern-based Image Inpainting

Keywords: I.3.3 [Computer Graphics]: Picture/Image Generation-[I.3.4]: Computer Graphics-Graphics Utilities I.4.4 [Image Processing and Computer Vision]: Restoration-[I.4.9]: Image Processing and Computer Vision-Applications inpainting, spatial, patch, blending, patch-based

Figure 1: Illustration of our proposed spatial patch blending algorithm for image inpainting. From left to right : color image with area to reconstruct, reconstruction result with the inpainting algorithm from [Criminisi et al. 2004], our reconstruction result.

Introduction

Filling unkown or removing undesired contents from images, known as image inpainting, is a widely used tool today. Movie producers for example, use it to remove microphones or scratches from new and older movie sequences. As this kind of reconstruction tool is employed by users that want their images to look more realistic, it must obviously not damage the perceptual and visual quality of the processed images. In the state of the art, there mainly exist two kinds of inpainting methods. Geometry-based methods [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Bertalmio | Image inpainting[END_REF]Tschumperlé and Deriche 2005] provide techniques to propagate image structures by extrapolating the local geometry. Unfortunately, these methods are often unable to synthesize non-local structures like textures. On the contrary, in pattern-based methods [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF][START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF]], user-selected image areas are reconstructed by copying patches from the known image zones, to those unkown. These methods work well to reconstruct textures. Even with some variations, like avering several patches [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF], they generally do not provide good result in terms of global geometry consistency. Hybrid methods also exist [START_REF] Sun | Image completion with structure propagation[END_REF], but there are always some cases where reconstruction let some artefacts appear. Recently, [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]] introduced a spatial patch blending technique to perceptually reduce these reconstruction artefacts, without any changes in the way geometry is inpainted. Unfortunately, this method cannot be used for production work due to computational burden and memory overload.

The paper addresses these two issues and is organized as follows. First, the principle of spatial patch blending is presented through a complete summary of the method. Then, we redesign the blending algorithm and show the various improvements it implies. Finally, we illustrate the relevance of our approach by commented results and comparisons with some state-of-the-art methods.

Patch Blending Context and Previous Work

In [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF] was proposed a method that allows reducing artefacts produced by any patch-based inpainting algorithm [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF][START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF]] in an image I. A result image J is produced where possible inter-patch seams and inconsistencies are cleverly hidden, rendering the image perceptually more pleasant. In this method, it is proposed to modify the process of any patch-based inpainting algorithm so that it provides additional information. The latter is used to perform the two steps of our artefact reduction technique, namely: 1) the artefact detection 2) the spatial patch blending.

• Artefact Detection. This first step of this method is empirically based on the two following hypothesis. For a reconstructed image I which reconstruction patch locations are stored in a map U : p ∈ I → q ∈ I, it is hypothesized that: 1) there are sharp color or luminosity variations where artefacts are located, and 2) patches from remote locations seem probably differents. The idea is first to combine the latter to estimate a set of points E where the strongest artefacts are located. Then, the map σ : p ∈ I → σ(p) ∈ R of blending amplitudes is computed, and gives to each point p inside a mask M a weight depending on its distance to the nearest artefact locations and strengths (cf. Fig. 2, and (3) of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]). • Spatial Patch Blending. In classic patch-based inpainting methods, the reconstruction of an image is a kind of patchwork. Patches are iteratively extracted from the image, cut up, and the remaining pieces are pasted inside M to complete the given image. The main idea of the spatial patch blending is to point out the fact that parts of the individual patches are discarded during sequential compositing, but these parts contain valuable information that could have been used if a different insertion order had been used. In this method, the scrapped offcuts are kept and spatially blended in order to reduce seams between the pieces of patches pasted side by side. This method is defined as a pixelwise process, and for each point p ∈ M , the set Ψp of patches overlapping at p is extracted. Then, a combination of all the pixels where all the patches ψq ∈ Ψp overlap is computed as follows:

J(p) = ψq ∈Ψp w(q,p) ψq (p-q) ε+ ψq ∈Ψp w(q,p) (1)
The gaussian weight function w(p, q) = e d(q,p) 2 σ 2

defines the way patches are blended together during the process. This function strongly depends on the distance function d. In [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF], they have used the minimal distance from the point p to every point in the piece of pasted patch ψq. As shown in Fig. 3, this method provides clearly good results in terms of artefact reduction regarding a classical patch-based inpainting result. On the other hand, the memory usage for storing the map U is too important. Then, even if it is reasonable as compared to these of the inpainting process, the computation time does not allow this method to be used easily and interactively. The main reason is that as many distance maps as reconstruction patches have to be computed. This makes the computation time to be very dependant of the mask size used for the inpainting. In addition, the size of E is a little bit overestimated by the artefact detection. In this pixel per pixel process, this causes the computation to increase noticeably. The weaknesses of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF] have brought us to redesign some parts of their algorithm to make it faster while maintaining the good perceptual quality of the results. The contributions we propose through this paper are mainly based on the enhancement of the spatial patch blending algorithm in terms of time consumption, but also memory usage.

Enhanced Spatial Patch Blending

We propose here a spatial patch blending algorithm for patternbased inpainting algortihms. Firstly, this method is described as it is, and then we discuss the different enhancements in comparison with the method of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]. • Spatial blending reformulation. At first sight, the method we propose seems to be very different from [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]]. Rather than independently computing each final pixel J(p) by looking for every p ∈ M , the set of local features that allows computing (1), we propagate each patch feature at once on the pasting neighbourhoods of p. Loop on each point p is replaced by a loop on all patches ψq pasted in I during the inpainting. This second loop needs much less computing iterations (approximatly n 2 /2 less where n × n is the inpainting patch dimension). This loop factorization is theorically possible only if the bandwidth σ(p) of the blending is considered as constant on the whole image. This obviously not the case. To do so, a multiscale approach is adopted. The loop on patches is repeated as many times as the number of different scales that can be considered in the values of σ (we have quantized these values into N scales). As N can be chosen small enough (typically of about ten scales, smaller values would leads to some discontinuities in the blending), the looping repetition factor due to the multi-scale aspect of our algorithm remains much less important than the average gain of n 2 /2 at a specified scale. This makes the final algorithm very interesting in terms of complexity compared to the approach of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]. Algorithm 1 details the whole principle of our multi-scale spatial blending method.

One can notice that this method of blending acts like a postprocessing of the image inpainting result, but requires to modify the considered patch-based inpainting algorithm, for the reconstruction patches locations and the reconstruction points to be stored.

• Differences with the previous approach. The differences of our method compared to the approach of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]] are the following:

Quantized spatial blending scales: Our optimized algorithm considers a quantized version of the spatial blending amplitude map σ. The set of the blending results Js are computed for each scale σs ∈ [1, N ] ⊂ N and are then merged in a final image J. This image contains pixels of J1, J2, . . . , JN depending on the local (quantized) scale defined in σ(p). The storage of all blending scales Js can be easily avoided by transferring directly all the pixels computed at a scale s to the final image J. In this case, the last loop of Algorithm 1 has to be done in the main scale loop (line 5).

Modified weight function:

The spatial patch blending is locally performed as a linear combination of all the patches that would have overlapped with a different inpainting order. One can demonstrate that with this new algorithm, the weighting function w(p, q) of each patch (also used in ( 1)) depends only on the distance from a point to the neighbour reconstruction points rather than the distance from a point to a piece of pasted patch (as described in [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]).

Algorithm 1: Fast spatial patch blending for inpainting algorithms. This is mainly thanks to this approximation that our optimized spatial blending version of the algorithm of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]] can be reformulated. From an experimental point of view, one can notice that the difference between the results produced with the two weight functions are very difficult to see in the final blending results.

Mask-external spatial patch blending: In Algorithm 1, the spatial blending is naturally extended to the outside of the inpainting mask M . In terms of visual appeal, this is very interesting since a smooth transition is created between the known colors and these of the reconstructed area. All the results presented in the following section take advantage of this special feature. To respect the classic inpainting formalism, one can constraint pixels from outside the mask not to be modified by our spatial patch blending (by copying all known pixels from I to the final image J at the end of the process).

Performance improvement: The gain performance of our approach as compared to [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF], and the comparison with the state-of-the-art approaches of [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF]] (inpainting without spatial patch blending) and Photoshop (very fast, based on [START_REF] Wexler | Spacetime completion of video[END_REF][START_REF] Barnes | Patchmatch: a randomized correspondence algorithm for structural image editing[END_REF]) is illustrated Fig. 5. In order to show the efficiency of our new method, we have made some experimentations. Fig. 5 summarizes the results on a set of medium-sized image1 , and mainly gives us three interesting informations. First, the gain of time between the approach of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]] and our method depends on the kind of processed images (mainly depending on the size of M ), but is very significant in each case (from 6 to 30 times faster for the presented examples). Then, there is no meaningful difference of computation time between method in [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF] and ours. This means that there is no additional cost to process our spatial patch blending algorithm after a classic patch-based inpainting. Also, one can see that the content-aware filling algorithm [START_REF] Wexler | Spacetime completion of video[END_REF][START_REF] Barnes | Patchmatch: a randomized correspondence algorithm for structural image editing[END_REF]] provided in Photoshop is noticeably faster than our method, but is most likely using material accelerations like GPU processing or multi-core programming. This is not the case of our method, provided with standard C++ implementation with no acceleration.

Figure 5: Illustration of execution time comparison between our method, method of [START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF], with state-of-the-art methods. The less, the better.

Results and Reproducibility

Some results provided by our method are illustrated Fig. 6 and compared to state-of-the-art methods. Spatial patch blending is clearly demonstrated through our examples and our way of making it faster allows now this method to be used interactively. In addition, a software integration of our method has been made and the source code is now available to the community, making our fast spatial patch blending algorithm fully reproducible:

• The source code of our technique is available as a function named inpaint patch() in G'MIC [Tschumperlé 2013] source codes.

• A dedicated filter has been added to the G'MIC plugin for the open source GIMP2 software, allowing non specialist people to use it easily thanks to an enhanced graphical user interface. (f) Result obtained with [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF]].

(g) Result obtained with photoshop. [2009; 2007] (h) Our result.

(i) Masked color image.

(j) Result obtained with [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF]].

(k) Result obtained with photoshop. [2009; 2007] (l) Our result.

  (a) A reconstructed image where artefacts are to be detected. (b) The superimposed set E with the associated amplitudes σ result of the artefact detection in 2(a).

Figure 2 :

 2 Figure 2: Illustration of the artefact detection result.

Figure 3 :

 3 Figure 3: Results of a spatial patch blending (zoomed). From left to right : masked image, result of patch-based inpainting[START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF]], result of[START_REF] Daisy | Spatial patch blending for artefact reduction in pattern-based inpainting techniques[END_REF]].

Input:

  Inpainted image I, Inpainting mask M , Number of scales N . Output: Image J with spatially blended patches. Initialize P = Ordered list of original patch center locations (p, q) 1 pasted in M during the inpainting; Initialize C = Ordered list of patch pasting locations (x, y) of during 2 inpainting; Initialize σ = Estimated local blending amplitude (section 2); 3 Initialize σ = Uniform quantization of σ in N levels (σ1, . . . , σ N ); 4 // Computation of the spatial blending levels Js // for differents σs for s ∈ [1, N ] ⊂ N, do 5 Initialize Js = Result color image of the blending at scale s, 6 initialized to 0 for all pixel in M , and I(p) elsewhere; Initialize A = Scalar accumulation image of the size of I, 7 initialized to 0 for all pixels in M , and 1 elsewhere; Initialize φ = Image of size m × m, containing a centered 8 Gaussian of variance σs; for k ∈ P do 9 Add the patch of size m × m of I located at P (k) to the 10 image Js at C (k) ; Add the image φ of the gaussian weights in A at C (k) ; 11 Divide Js by A (normalisation of the added colors).

  12 // Combine all the blending scales // in a result image. for p ∈ M , do 13 s = σ(p) ; 14 J (p) = J s(p) ; 15 (a) Weights used in [Daisy et al. 2013]. (b) Weights use in our new method.

Figure 4 :

 4 Figure 4: Illustration of the difference between weights of [Daisy et al. 2013] (a), and those used in our fast spatial patch blending algorithm (b).

  Masked color image.

Figure 6 :

 6 Figure 6: Comparison with several state-of-the-art methods (zoomed).

http://daisy.users.greyc.fr/@publications:id=fspba.dtl.2013

http://www.gimp.org/


J Jiang
email: jie.jiang@uni-passau.de

M Aparicio

M Comte

F Azaïs

M Renovell

I Polian
email: ilia.polian@uni-passau.de

MIRID: Mixed-Mode IR-Drop Induced Delay Simulator

Keywords: Digital CMOS IC, Test, Power Noise, IR-drop, Simulation

IR-drop effects are increasingly relevant in context of both design and test. We introduce the event-driven simulator MIRID that calculates the impact of IR-drop to the circuit timing. MIRID performs the simulation on two abstraction levels: timing effects in the gate-level net-list; current and voltage waveform propagation in the electrical model of the powerdistribution network (PDN). Switching events at the logic gates are forwarded to the electrical model, where induced currents and their impact on the neighboring PDN nodes are computed. From this information, values of voltages at the Vdd and ground terminals of logic gates are determined, which in turn are used to calculate accurate switching delays of the gates. MIRID supports a generic interface to electrical models, allowing for a seamless integration of arbitrary models of PDN and gate timing. We report experiments based on a simple PDN model that was introduced previously and incorporates a pre-characterized library. The simulation accuracy is validated by matching the results from MIRID and SPICE.

I. INTRODUCTION

Power supply noise is becoming an important concern for VLSI system design in deep submicron regime [START_REF] Shepard | Noise in deep submicron digital design[END_REF]. It reduces the actual voltage levels supplied to the gates of the device, which has a detrimental impact on signal integrity. Excessive power supply noise can degrade circuit performance by inducing additional signal delay, or even lead to functional failure of logic gates [START_REF] Chen | Power supply noise analysis methodology for deep submicron VLSI design[END_REF]. Moreover, as technology scales, designs are becoming more sensitive to power supply noise due to reduced power supply voltage and increased power density [START_REF] Saleh | Clock skew verification in the presence of IR-drop in the power distribution network[END_REF].

Two major components are referred by power supply noise: the inductive voltage noise (Ldi/dt) that depends on the rate of change of the instantaneous currents flowing through parasitic inductive elements of the network; and the resistive voltage noise (IR) that depends on the instantaneous currents flowing through the resistive elements of the network [START_REF] Weste | CMOS VLSI Design[END_REF]. Compared to package interconnect, PDN is predominantly resistive. Voltage fluctuations of power supply are mainly caused by IR noise. In this paper, we focus on the IR-drop effects in PDNs.

IR-drop has been studied with the purpose of reducing overall IR-drop effect as much as possible at chip level. A number of commercial tools (such as Redhawk [5], PrimeRail [6] and HyperLynx [7]) can do IR-drop analysis taking certain inputs in the design stage and targeting power network verification throughout physical implementation. Various supply network and circuit models are proposed for estimating power supply noise due to IR-drop [START_REF] Nassif | Technology trends in power-gridinduced noise[END_REF]. Most of these works are based on a vectorless approach with the primary target of identifying critical areas to help designers by power network design. In other words, these commercial tools predict IR-Drop (using statistical models) but not the induced delay using a drivenevent simulation. This is a classic design approach to the IR-Drop phenomenon.

PDN-related impact on delay is also of interest in context of testing. Testing of small-delay defects (SDD) in circuits requires an adequate fault coverage, which can be heavily affected by the process variation [START_REF] Jiang | On the optimality of K longest path generation algorithm under memory constraints[END_REF]. The nominal delay of gates are considered by ATPG for SDD testing while extra delay can be induced by noises in practice. Estimation of IR-drop induced delay is important by evaluation of test patterns for SDD, and even improve test compaction technology [START_REF] Jiang | Levelized low cost delay test compaction considering IR-drop induced power supply noise[END_REF]. Power analysis is also essential for scan testing. Peak power consumption during test cycles of scan testing has to be controlled to avoid noise phenomena [START_REF] Badereddine | Structural-based power-aware assignment of don't cares for peak power reduction during scan testing[END_REF]. Accurate and yet efficient simulation of IR-drop-induced delays is required because electrical-level simulation is prohibitively expensive for large circuits and pattern counts.

We propose a mixed-mode simulation algorithm for IRdrop induced delays in the circuit. The gate-level eventdriven simulator MIRID (Mixed-Mode IR-Drop Induced Delay Simulator) provides a compromise between the accuracy of SPICE and the efficiency of an IR-drop-unaware gate-level delay simulator and is applicable to academic and industrial benchmark circuits. The algorithm is applicable to any power network design which is encapsulated by a generic interface. We report experiments based on a pre-characterized library created for a resistive PDN design. We investigate both the accuracy of the IR-drop induced delay calculation and the runtime.

This paper is organized as follows. An overview of the simulation is given in Section II. The electrical precharacterization is introduced in Section III. Section IV presents the simulation algorithm. Experimental results are given in section V. Finally section VI concludes the work.

II. SIMULATION OVERVIEW

As illustrated in Figure 1, the simulation engine MIRID performs an event-driven logic simulation for applied test vector Patterns. The IR-drop induced delays Delays are given as outputs by the engine. The simulator provides generic interfaces to a PDN model PM and a timing model TM for calculation of gate delays. Mapping from gates to power supply nodes is defined in advance according to the PDN topology and other electrical parameters in the PDN model.

Switching signals during the logic simulation are reported via the interface as events S-event(s, t, v) where v is the new value assigned to s at time t. The voltage level of a power supply node n in VDD/GND network can be acquired by the simulator through the interface. These voltages are computed by the PDN model, which uses a different set of events, Devents, to capture the distribution of currents over the PDN.

Both Sand D-events are sorted by the time t, and processed in order by the simulation engine. If the output s out of gate g driven by s switches to a new value v , new event S-event(s out , t + δ, v ) will be generated where δ is the delay of g. The gate delay δ may differ from its nominal value due to the IR-drop effect. It is obtained via the interface to a timing model, which takes parameter values from the active simulation environment, such as voltage swings of the upstream gate and the switching gate, the load capacitance of the switching gate or other parameters according to the implementation of the timing model. In our experiment the interfaces between the models are built based on a precharacterization library [START_REF] Aparicio | Pre-characterization procedure for a mixed mode simulation of IR-drop induced delays[END_REF] containing pre-computed tables for gate delay and current draw induced by the switching activity, and the distribution of the current through the PDN structure as well.

III. ELECTRICAL MODELS

As indicated above, the generic interfaces provided to the simulator contain functions of mapping the logic gates to the power supply nodes, determining the voltage levels on power supply nodes, and the gate delay induced by voltage drop on the gate. The implementation of these functions highly depends on the PDN configuration. In our experiments we consider the block under test (BUT) on the chip. Power and ground supply networks are modeled by grids with resistors in horizontal and vertical lines. Each gate is mapped to a grid node in the VDD/GND network.

The current drawn due to switching of the gates and its distribution through the resistors of the PDN are calculated and then used to compute the voltage drop at each node, using the Ohm's law. The current draw and the delay of a switching gate depend on the power supply levels, which are likely to be affected by IR-drop induced by neighboring gates, and by the load capacitance of the gate. Thus the computation of current draw and delay takes the gate environment into account, which is presented by three variable parameters as follows:

• Edge: The rising or falling input transition of the gate • Supply and input swings: The voltage swing of the upstream gate (V swing1 ) and the considered gate (V swing2 ), defined by Equations ( 1) and ( 2) where V dd 1 (t) and Gnd 1 (t) (resp. V dd 2 (t) and Gnd 2 (t)) are the power supply and ground supply levels of the upstream gate (resp. considered gate), as illustrated in Figure 2

V swing1 (t) = V dd 1 (t) -Gnd 1 (t) (1)
V swing2 (t) = V dd 2 (t) -Gnd 2 (t) (2)
• Load capacitance: Equivalent capacitance C load of the downstream gates connected to the considered gate Moreover, the implementation of the interface functions depends on the CMOS technology used by the circuits for the simulator. A pre-characterization of standard gates in terms of the current draw and the delay, as well as a pre-characterization of the current distribution in the PDN are needed. SPICE simulations were performed for 45nm CMOS technology to pre-characterize current draw and delay of gates under all possible conditions which are likely to occur in a realistic environment. That is, all combinations of voltage swings between 100% and 80% of the nominal power supply swings for V swing1 and V swing2 , load capacitance values from one to five times the elementary equivalent capacitance and input transition edges (rising and falling) for all standard gates. Section III-A and III-B detail the computation of gate delay and current draw, respectively. Section III-C gives the distribution model of current through PDN grids.

Gnd 1 Gnd 2 Vdd 1 Vdd 2 Gnd Vdd Time V swing2 /2 V swing1 /2 Voltage V swing1 V swing2 t 0 t 1 V input V output Vdd1 Gnd1 Vdd2 Gnd2 Vdd1 Gnd1 Vdd2 Gnd2 V input V output

A. Gate Delay

The propagation delay δ is defined as the duration between the time t 0 at which the input signal of the gate crosses half of its excursion (V swing1 /2) and the time t 1 at which the output signal of the gate crosses half of its excursion (V swing2 /2), as illustrated in Figure 2 for an example of 2 inverters.

The variation of the delay in function of a single variable parameter (V swing1 , V swing2 or C load ) can be approximated by a linear function, when the other two parameters hold to their nominal values. The three variable parameters are independent, thus the delay function can be given by a polynomial of the first order for each variable parameter and for all combinations of the variables. That is, a polynomial function of V swing1 , V swing2 and C load with coefficients depending on the input edge (rising or falling) and the switching input of a gate. Sets of polynomial coefficients are provided in the library for all possible conditions.

B. Current Draw

The current drawn by a switching gate from the power and ground supplies is a time variant function. Rather than deriving an analytical expression for the current, we employ pre-calculated current waveforms, where each waveform is represented by an array of discrete values with picoseconds resolution. Different waveforms are required for different values of V swing1 , V swing2 and C load . We pre-calculate the waveforms for a number of load capacitance values C load , between one and five times the elementary equivalent capacitance, assuming V swing1 = V swing2 = 100%. The currents for different voltage swing values are obtained by a linear transformation. The details can be found in our prior work [START_REF] Aparicio | Pre-characterization procedure for a mixed mode simulation of IR-drop induced delays[END_REF].

Sets of reference current waveforms and corresponding shift/multiplying factors are saved for different gates, switching inputs and transition edges in the pre-characterization library. The current drawn by a switching gate from the VDD and GND supply networks can be obtained by modifying the appropriate reference current according to the environmental conditions.

C. Current Distribution in PDN Grid

The instantaneous current induced by the switching activity will be distributed in PDN resistors. The PDN grid is modeled by a resistive 100 × 100 power grid, each grid node serves as a power supply node for gates. Horizontal and vertical grid resistances can be predefined arbitrarily. For each node on the grid edge, different power supply voltages can be predefined as well. The current distribution model is established by simulating such a grid with a current source in the center, at the corner and in the band area of the grid.

In the first case, a current draw is modeled by a unitary current source in the center of the grid. A SPICE simulation is performed and the current values in the horizontal and vertical resistors of the grid are computed. As the current source is unitary, these values directly correspond to the desired distribution factor. The result shows that the current distribution is highly localized. Although the current spreads through all the resistors in the grid, its value is significant only through the resistors neighboring the current source. We define a sub-grid of m × n resistors outside which all currents are inferior to 1% and can thus be neglected. Although the current distribution depends on the position of the current draw in the grid, the same sub-grid can be used as distribution factor for all the nodes located in the central area of the PDN with an error inferior to 1%.

If the current is drawn from a node at the corner and in the band area of the PDN, which are defined as 10 × 10 nodes at each corner and bands with 10-nodes width between corners, respectively, dedicated distribution factors are computed. The error between the current distributions simulated with SPICE and computed using the pre-characterization factor is guaranteed to be less than 1%.

Obviously, the current draw distribution in the PDN grid also depends on the effective power supply at the extreme nodes at the border of the grid, which differ from the nominal value due to the activity of the neighboring blocks. We consider the globally static effect resulting from the average activity of the neighboring blocks. Static currents can be assumed to flow through the grid resistors in addition to the current draw distribution, which in turn presents the influence of the nonideal power supply values at the extreme nodes on the border. More details of the library pre-characterization are given in [START_REF] Aparicio | Pre-characterization procedure for a mixed mode simulation of IR-drop induced delays[END_REF].

IV. SIMULATION ALGORITHM

As given in Section II the simulation run is driven by switching events S-event(s, t, v). We define another event Devent(n, t, curr) with the object of a PDN node n to handle the current waveform curr induced by the switching activity at time t through the PDN grids. Both events are defined as follows.

• S-event(s, t, v) triggered when signal s changes its value to v at time t

• D-event(n, t, curr) for a PDN node n with current curr to be distributed in neighboring nodes at time t

As shown in Algorithm 1, the simulator takes the circuit netlist C and a set of test pattern pairs P as inputs, and provides interfaces to the electrical model of gate delay TM and the PDN model PM. In preprocessing phase each gate is mapped to a power supply node in VDD/GND network according to the PDN design. The simulation is run for each pattern pair (p 1 , p 2 ) in patterns in two consecutive time frames. The first pattern is applied to get the initial value of each signal, i. e. the conventional logic simulation is run by calculating the logic value of each gate function in order of gate level. In the second time frame, the simulation is run for the second pattern taking the IR-drop effect into account.

The event queue EQ is initialized by a set of Sevent(s, 0, v) where s is a primary input and v is the newly assigned value by p 2 at time 0, v differs from its previous value assigned by p 1 . Events in EQ are processed in increasing order of time. The variable t sim refers to the time of event processed currently. It is initially assigned with zero. If the event in processing is a signal assignment event Sevent(s, t, v), s is assigned with the new value v, and marked as a active signal. The handling of all active signals is given in Algorithm 3. Otherwise e is the event for current distribution D-event(n, t, curr), which is processed by distributing the current curr to neighbors of n by a function implemented in the interface to the PDN model. In our model for experiments, the function DistributeCurrent is implemented as shown in Algorithm 2.

In function DistributeCurrent, a corresponding matrix of dispersion factors DF sx×sy is obtained from the library with respect to the position of the node in PDN: in the center, at the corner or in the band area as defined in Section III-C. The neighboring area of n is defined as a rectangular area of size sx × sy with n in the center. Each new S-event(sout, tsim + δ, v ) insert new events into event queue sort event queue by the event time 3. For each active signal s the voltage swing V swing1 on the upstream gate g pred is first calculated by GetP owerSwing as defined in Equation 1 using the voltage values at corresponding power supply nodes. For the resistive PDN model used in the experiments, the voltage value at a power supply node can be obtained by applying the Ohm's law with given grid resistance, saved current in resistors and the voltage supply level at each extreme node on the PDN border.

For each gate g fed by s, the voltage swing V swing2 is then computed in the same way. The current induced by the switching input s is calculated by function CalculateCurrent using V swing1 , V swing2 and the load capacitance C load as inputs. Both functions CalculateCurrent and GetP owerSwing are defined in the interface to PDN model P M . Events Devent(n vdd , t sim , curr vdd ) and D-event(n gnd , t sim , curr gnd ) are then generated for current distribution to neighbors of power supply nodes n vdd and n gnd of g at time t sim . If the output s out of gate g differs from its previous value, a new switching event S-event(s out , t sim + δ, v ) is generated where the event time is given by the active simulation t sim added by the gate delay δ and v is the new value. The function of delay is provided in the interface to the timing model T M . In our model it is given by a polynomial with coefficients obtained from the pre-characterization library according to the simulation environment, as given in Section III-A. The parameters of the function are the voltage swings V swing1 and V swing2 , and the load capacitance of g as well.

All new events are inserted into EQ. After the insertion EQ is sorted by the event time again.

As given in Algorithm 1, after all active signals are handled as given above, they are unmarked. And the next event in EQ is to be processed in the same way. This iterative process continues until EQ is empty, i.e. all events in queue are processed and no new events are generated during the processing. The simulation flow ends then.

V. EXPERIMENTS

The first experiment aims at validating the accuracy of the IR-drop induced delay calculated by MIRID by matching it with SPICE simulations of identical circuits. The simulation was performed to a chain of 14 inverters. As shown in Figure 3, each inverter is connected to a power supply node in 100×100 resistive PDN grid. Only the connected nodes with neighboring resistors in one network are drawn. Test pattern pair (1, 0) is applied to the single primary input, the current and voltage curves in each PDN resistor from both simulation flows are compared to each other. It turns out that the results from both simulations match well to each other. The slight difference in current and voltage curves can be neglected in consideration of their impact on gate delay. Another validation is done to the ISCAS circuit c17, which contains 2 INV, 3 NOR2 and 4 NAND2 gates. All gates are connected to a power supply node (50, 50) in the PDN networks. For an applied test pattern the current and voltage curves at the node given by MIRID and SPICE are compared in Figure 6 and Figure 7, respectively. Difference in amplitude can be observed due to the fact that SPICE takes more electrical parameters into account while our simulator uses approximated electrical models of PDN and gate delay. The impact on the delay is reflected by the time at which the voltage curve gets back to its nominal value. It can be observed that the difference in delay from both simulation is very slight and thus acceptable. and the switching activity, another experiment was performed to a dedicated design with maximal 100 × 9 inverter chains. Each chain comprises of 8 inverters G 0 , . . . , G 7 connected as follows:

G 0 G 1 G 2 G 3 G 4 G 5 G 6 G 7 in 1 out 1 i,j i-1,j i,j+1 i+1,j i,j-1 (a) An 8-inverter chain placed in a 3 × 3 grid i,j (
in 1 → G 0 → G 1 . . . → G 7 → out 1
where in 1 and out 1 are primary input and output. The connection of the gates in a 3 × 3 PDN is illustrated in Figure 8a. G 0 and G 4 are connected to node (i -1, j), G 1 and G 5 are connected to node (i, j + 1), G 2 and G 6 are connected to node (i + 1, j), G 3 and G 7 are connected to node (i, j -1). Such a placement in a 3 × 3 grid is repeated 9 times in a 5 × 5 grid for 9 inverter chains. As shown in Figure 8b, a inverter chain is placed in the 3 × 3 area with the node (i, j) at the central position. All 9 chains are placed in areas with corresponding nodes in the center, which are marked by solid dots.

Simulations were performed to N copies of 9 inverter chains. (For N = 2, another set of 9 inverter chains is placed at the same position as the first one.) Figure 9 illustrates the ratio of the IR-drop induced delay in simulation runs for N = 1 . . . 100. It can be seen that delay induced by IR-drop increases linearly with the value of N, which is proportional to the number of switching inverters.

The simulator was run for several ISCAS and NXP circuits with test pattern pairs for small delay faults generated by our in-house ATPG tool [START_REF] Jiang | On the optimality of K longest path generation algorithm under memory constraints[END_REF]. Rather than using full-custom layouts of the circuits, we created, for each simulated circuit, a PDN consisting of 100 × 100 nodes and connected each gate to the center of the PDN. The IR-drop induced delay is estimated by comparing the transition propagation time with and without IR-drop effect. The transition propagation time corresponds to the total delay of gates on the longest sensitized path.

As given in Table I, column 2 contains the number of gates, the number of test pattern pairs is given in column 3, column 4 presents the average transition propagation time under impact of IR-drop effect. The ratio of additional induced delay compared to the delay calculated using the nominal values is given in column 5. Column 6 gives the average number of switching activity during the simulation. The last column presents the average CPU runtime per test. As shown in the table, the IR-drop induced delay has a positive correlation to the number of switching activities, and so does the runtime. Though p35 has less gates than p45, it has a more complicated structure and thus more switching events are activated, which in turn induce longer propagation time. The IR-drop induced delay increase observed for the larger circuits matches well with values around 3% that have been previously reported in the literature [START_REF] Jiang | Levelized low cost delay test compaction considering IR-drop induced power supply noise[END_REF].

VI. CONCLUSION

This paper presents a simulation flow running across the logical and the electrical domains to simulate IR-drop induced delay. The logic simulation engine performs timing simulation and is driven by switching events as the input transitions are propagated through sensitized paths in the circuit. A PDN model and an electrical model for gate delays are used for simulating the IR-drop effect in electrical domain. Interfaces between the simulation engine and the models are provided for calculating the gate delay and updating electrical parameters in the PDN. The interfaces can be adapted to any PDN design and electrical models without influences to the simulation engine basically. Experiments conducted on a resistive PDN design show good match to SPICE results and scalability to industrial circuits within reasonable runtime. In the future we will concentrate on the integration of more complex PDN models into the simulator and the development of algorithmic speed-up techniques suited for these models.

Fig. 1 :

 1 Fig. 1: Schematic illustration of the simulator

Fig. 2 :

 2 Fig. 2: Supply and input voltage swings and gate delay

Fig. 3 :

 3 Fig. 3: 14-inverters model for validation

Fig. 4 :

 4 Fig. 4: Current validation for 14-inverters chain

Fig. 5 :Fig. 6 :Fig. 7 :

 567 Fig. 5: Voltage validation for 14-inverters chain

Fig. 8 :Fig. 9 :

 89 Fig. 8: Model of 9 inverter chains

  Circuit Netlist C, Test Patterns P, Timing Model TM, itself) refers to a dispersion factor f ac i,j in the matrix. The current waveform of n is updated by adding the waveform of curr scaled by f ac i,j , i.e. each discrete current value curr If the time of next event in the queue differs from t sim , all active signals are handled as given in Algorithm

		Algorithm 3: ProcessActiveSignal(s)
		input : Timing Model TM, PDN Model PM, s
	PDN Model PM	begin
	Result: Gate delay of each switching gate	upstream gate g pred
	Preprocessing:	/ * get power swing V swing1 for the upstream
	begin		gate g pred	* /
	Assign each gate to a VDD and a GND power supply	Vswing1 ←-PM.GetPowerSwing(g pred , tsim)
	node	foreach gate g fed by s do
	begin foreach pattern pair (p1, p2) ∈ P do Run good simulation for first pattern p1		/ * get power swing V swing2 for commuting gate g Vswing2 ←-PM.GetPowerSwing(g, tsim) / * get induced current drawn from VDD and * /
	/ * Initialize event queue EQ with events S-event(s, 0, v) for each input s changing its value to v at time 0 InitializeEventQueue() tsim ←-0 while EQ not empty do Event e ←-first event in EQ tsim ←-time of e if e is S-event(s, t, v) then s ←-v Mark s as active signal	* /	GND power supply nodes for g curr vdd ←-PM.CalculateCurrent(n vdd , Vswing1, Vswing2, C load ) curr gnd ←-PM.CalculateCurrent(n gnd , Vswing1, Vswing2, C load ) / * create drop events new D-event(n vdd , tsim, curr vdd ) new D-event(n gnd , tsim, curr gnd ) calculate gate output of g if gate output sout switches to v then / * calculate gate delay δ ←-TM.CalculateGateDelay(Vswing1, Vswing2, * / * / * /
	else		C load )
	/ * e is D-event(n, t, curr)	* /	/ * create signal assignment event for
	PM.DistributeCurrent(n, t, curr)		gate output)	* /
	Remove e from EQ
	enext ←-next event in EQ
	/ * Process each active signal, if the
	time of enext differs from t sim

neighbor n (including Algorithm 1: IR-drop Simulation Data: * / if time of enext = tsim then foreach active signal s do ProcessActiveSignal(s) Unmark s as active signal Algorithm 2: DistributeCurrent input : PDN Model PM, n, t, curr begin DFsx×sy ←corresponding sx × sy dispersion factor matrix for n for i = 1 → sx do for j = 1 → sy do Neighbor n ←node at position (i, j) in the sx × sy neighboring area curr n ←current waveform saved for node n ; f aci,j ←dispersion factor at position (i, j) in the matrix Update curr n by adding current values in curr multiplied with f aci,j to curr n for time points t, t + 1, . . .

n k in curr is multiplied by f ac i,j and added to the corresponding value in curr n saved for time point t + k, where t is the event time and k is the index of curr k in curr (k = 0, 1, . . .).

After an event e is processed, it can be removed from the event queue EQ.

TABLE I :

 I Simulation for ISCAS and NXP circuits

	circuit #gates #patterns	ave. trans.	σ [%]	ave.	ave. CPU
				prop. time[ps]		#switching	time [s]
	c432	334	322	151.19	0.086	290	1
	c1908	871	1000	197.78	0.88	1004	2
	p35	27902	1000	573.35	5.33	19488	83
	p45	30584	1000	383.87	3.75	3034	13

ACKNOWLEDGMENT

This work was partially supported by the DFG (German National Science Foundation) grant Po 1220/1-2 and by the BFHZ (Bavarian-French University Center) grant FK-26-11.