How long does an integrated circuit take to produce its result? To answer the question, we must tackle the difficult and complex false path detection problem first. The viability analysis is one of the most sophisticated approaches to the false path detection problem. On the other side, as the technology scales down, the gate delay variation has made a significant impact on the circuit reliability. Nevertheless, so far the previous timing analyzers have invariably used the worst-case gate delay in their false path detection algorithms, missing some important false or true path timing behavior. In this paper, we propose a solid method of viability analysis under delay variation to solve the false path detection problem under delay variation, which has never been addressed by the prior works of timing analysis. In addition to the thorough theoretical results, to cope with the runtime problem in evaluating the viability for large circuits in practice, we propose an efficient viability evaluation technique that is able to soothe the complexity of the numbers of input vectors. We tested the proposed method on ISCAS benchmark circuits and carry bypass adders under delay variation, and showed its effectiveness and usefulness on the false path aware statistical timing analysis.

In recent years, there has been a lot of research into statistical static timing analysis (SSTA) to compute the critical path delay of a circuit under timing variation. In order to compute the true critical path delay, however, false paths that cannot be sensitized by any input vector must be identified first. Since SSTA is unable to capture the dynamic timing behavior of a circuit, it is completely blind to false paths, and thus it overestimates the circuit timing. In this paper, we propose a new concept of timing analysis approach called statistical dynamic timing analysis (SDTA), which is able to precisely express the statistical behavior of dynamic transitions at the output of gate into a compact form and to directly evaluate and propagate the expressions throughout the circuit, by which the false paths can be cleaned effectively. In addition, to be practical, we propose a couple of techniques that enable a fast computation of the SDTA. We tested the proposed approach on ISCAS benchmarks and carry skip adders under timing variation to show its accuracy in computing the distribution of the true critical path delay of a circuit. In summary, compared to the previous approach of false path-aware statistical timing analysis, our timing analysis technique is able to reduce the accuracy error in the mean and standard deviation of true critical path delay distribution from 9.8% to 1.9% and from 29.4% to -3.4%, respectively.

The timing closure problem (e.g., meeting timing/clock period constraint) is one of the most important problems in the design automation. However, the rapid increase of the impact of the process variation on circuit timing makes the problem much more complicated and unpredictable to tackle in synthesis. This paper addresses a new problem of high-level synthesis (HLS) that effectively takes into account the timing variation. Conventional HLS may simply avoid the timing variation problem by considering the worst case or constant delay model of hardware resources, which are certainly not viable solutions. To overcome the impact of timing variation in HLS, this paper addresses the following two problems: 1) how can the statistical static timing analysis (SSTA) used in logic synthesis be modified and effectively applied to the delay and yield computation in HLS? and 2) how can scheduling and resource binding tasks effectively solve the HLS problem with the objective of minimizing latency under yield constraint? Through an extensive experimentation, we confirm that the proposed variation-aware HLS algorithm is able to reduce the latency by 19.7% under 90% performance yield constraint, compared with the result by conventional timing variation-unaware HLS .

This work proposes a new yield computation technique dedicated to HLS, which is an essential component in timing variation-aware HLS research field. The SSTAs used by the current timing variation-aware HLS techniques cannot support the following two critical factors at all: (i) non-Gaussian delay distribution of `module patterns' used in scheduling and binding and (ii) correlation of timing variation between module patterns. However, without considering these factors, the synthesis results would be far less accurate in timing, being very likely to fail in timing closure. Even though there are advances in the logic level for SSTAs that support (i) and (ii), the manipulation and computation of (i) and (ii) in the course of scheduling and binding in HLS are unique in that there are no concepts of module sharing and performance yield computation in the logic level. Specifically, we propose a novel yield computation technique to handle the non-Gaussian timing variation of module patterns, where the sum and max operations are closed-form formulas and the timing correlation between modules used in computing performance yield is preserved to the first-order form. Experimental results show that our synthesis using the proposed yield computation technique reduces the latency by 24.1% and 28.8% under 95% and 90% performance yield constraints over that by the conventional HLS, respectively. Further, it is confirmed that our synthesis results are near optimal with less than 3.1% error on average.

The timing closure problem is one of the most important problems in the design automation. However, the rapid increase of the impact of the process variation on circuit timing makes the problem much more complicated and unpredictable to tackle in synthesis. This work addresses a new problem of high-level synthesis (HLS) that effectively takes into account the timing variation. Specifically, the work addresses the following four problems: (1) how can the statistical static timing analysis (SSTA) used in logic synthesis be modified and applied to the delay and yield computation in HLS? (2) how does the resource binding affect yield? (3) how does the scheduling affect yield? (4) how can scheduling and resource binding tasks be combined together to efficiently solve the problem with the objective of minimizing latency under yield constraint?