MAIN MENUGo to Previous DocumentCD-ROM HelpSearch CD-ROMSearch ResultsPrintOn Bounding the Delay of a Critical Path∗Leonard [email protected]. [email protected] of Electrical and Computer EngineeringUniversity of California - Santa BarbaraSanta Barbara, CA, 93106-9560ABSTRACTProcess variations cause different behavior of timing-dependent effects across different chips. In this work, weanalyze one example of timing-dependent effects, cross-coupling capacitance, and the complex problem space cre-ated by considering coupling and process variations to-gether. The delay of a critical path under these condi-tions is difficult to bound for design and test. We develop amethodology that analyzes this complex space by decompos-ing the problem space along three dimensions: the aggressorspace, test space, and sample space. For design, we uti-lize an OBDD-based approach to prune the aggressor spacebased on logical constraints, which can be combined with aworst-case timing window simulator to prune based on bothlogical and timing constraints. After pruning, the reducedaggressor space can be used to derive a more accurate timingbound. Solving the problems in the test and sample spacesis postponed to the post-silicon stage, where we propose atest selection methodology for bounding the delay of everysample. This methodology is based on probability densityestimation and has a tradeoff between the number of tests toapply and the tightness of the delay bound obtained. Exper-imental results based on benchmark examples are presentedto show the effectiveness of the proposed methodology.1. INTRODUCTIONIn today’s deep-submicron designs, process variationscause different timing configurations for different siliconchips. To complicate timing further, timing-dependent ef-fects affect each chip differently since their effects dependon the timing of the signals involved. Process variationsmay cause the timing of two signals to match perfectly onone chip but not on another. Figure 1 depicts examples oftiming-dependent effects. For example, past research hasstudied the multiple input switching (MIS) effect on delay[3, 5], the automatic test pattern generation (ATPG) prob-lem under the effect of cross-coupling capacitance [8, 9, 15],and the impact of power noise [6, 11,12, 14].In this work, we focus on one of these effects, cross-coupling capacitance, mingled with process variations and∗This work was supported in part by NSF, Grant No.0312701 and SRC, project 2004-TJ-1173.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.ICCAD’06, November 5-9, 2006, San Jose, CACopyright 2006 ACM 1-59593-389-1/06/0011 ...$5.00.MIShazardscouplingpower noiseRCinput CslewclockskewclockjitterQclock-QdelayFigure 1: Path delay is affected by many differenttiming-dependent effectssolve two problems: (1) how to bound the timing of a crit-ical path for design, and (2) how to bound the timing of acritical path with tests for speed binning.Coupling’s effect on the timing of a victim path is based onthe timing alignment between its signals and the aggressors,where a full timing overlap has the largest impact and nooverlap has the least. Many models multiply the couplingcapacitance CC between an aggressor and a victim wire witha coupling factor, representing the severity of this alignment.This modified capacitance is added to the output loadingof a victim gate to change its timing. In static analysis,setting a global coupling parameter of xCC is a simple butinaccurate model of coupling, as not all gates in a path areaffected by xCC, causing overestimation of its timing.Worst-case timing# of silicon chipstiming boundby setting aglobal couplingparameter?Figure 2: Can we push in the timing bound foundby setting a global coupling parameter determinis-tically instead of empirically?Figure 2 illustrates how an xCC model might overestimatethe actual worst-case timing of a victim path. A commonindustrial practice to reduce this overestimation is to set thevalue x smaller than 2, where the value is determined em-pirically based on data from a previous design, process, ortapeout. In this work, we attempt to push in the timingbound for design and test without relying on this empiri-cal data. We provide deterministic solutions to reduce thecomplexity of the cross-coupling capacitance problem spacebased on several different perspectives, and provide addi-tional approximate solutions to estimate the delay bound ofa critical path in test.81Sample space(process variations)Test spaceAggressor spaceFigure 3: The 3 dimensions of the coupling problemFigure 3 shows how the coupling problem space is createdby the interaction between three dimensions:• Aggressor space: the logical and timing constraints in-volved in activating combinations of aggressors.• Test space: the various tests that can activate the re-quired aggressors for a given combination.• Sample space: process variations causing different de-lays for the same test on different chips.In an earlier work [16], an attempt to develop a statisti-cal timed ATPG revealed that searching the problem spacewith these dimensions mingled together is difficult. In thiswork, we propose to solve the problem along each dimensionseparately, reducing the complexity.In the pre-silicon stage, where we cannot assume the avail-ability of a statistical timing model that accurately modelsall effects from process variations, focusing only on pruningthe aggressor space makes more sense. It is questionable touse Timed ATPG to search for tests that worsen the delay ofa victim path because it requires an accurate timing modelto find the alignment of timing-dependent effects. Hence,its result is sensitive to the timing model. A slight changein the model may result in a completely different test set.Due to the difficulty in analyzing the path delay on a per-test basis, our methodology postpones the development ofthe final test set to expose the coupling effect on a pathuntil the post-silicon stage. Our main idea is that in thepre-silicon stage, we only need to (and can only) develop asuperset of tests. Then, a