In this paper, we introduce a novel technique called Local Sense for detecting appliance usage events in a household by leveraging existing home power infrastructure. Specifically, the Local Sense technique works by purely analyzing the records taken from the main power meter. The main power meter is installed in a household to measure the overall real time aggregated power consumption in terms of wattage and voltage for the whole load of appliances in a household. The Local Sense technique requires no additional apparatuses being installed in existing household power infrastructure, which significantly reduces the cost for enabling the location-aware power usage information over existing techniques. The idea behind the Local Sense system is to reflect the fact that different outlets are with different power line impedances, which causes different power dissipation even for the same appliance usage. By identifying the additional power dissipation, detecting the appliance usage events at outlet levels is therefore possible. The proposed technique is validated in a research lab and preliminary results demonstrate the effectiveness of the proposed system.

Current timing analysis tools deal with combinational circuit composed of primitive gates. In this paper, we are investigating ways to do timing analysis of combinational circuits with complex gates. Two possible approaches are proposed. The first approach is to design path sensitization criterion for circuits which is composed of complex gates. Another approach is first to transform complex gates to primitive gates and then using existing tools to perform timing analysis. A sensitization criterion is proposed for general complex gates where the functionality and delay information are given. Two commonly used complex gates, XOR and multiplexer, are examined and simplified sensitization criteria are generated. The gate expansion is performed on different delay models to show the compatibility between the original circuit and the transformed one. A general gate expansion algorithm is provided in this paper which can be used for general complex gates. From the experiment, we learned that the first approach can be performed in less computation time than the second one. The circuit delay obtained with the first approach is also smaller and more accurate than that obtained by the second approach.

Both long- and short-path delays are used to determine the valid clocking for various complementary metal-organic-semiconductor (CMOS) circuits such as single phase latching, asynchronous, and wave pipelining. Therefore, accurate estimation of both long and short path delays is very crucial in the designing and testing of high speed CMOS circuits. Most of the previous approaches in detecting long and short sensitizable paths assume that the rising and falling of gate delays are either fixed or bounded. In fact the gate delay of CMOS circuits may also depend on how many and which inputs are rising or falling and the arrival times of those rising or falling inputs. For instance, the delay for a two-input CMOS NAND gate may vary as much as a factor of two based on whether one input or two inputs are changing. We shall refer a gate delay model which considers these factors as data dependent delay model. Gray et al. (1992) have proposed an approach based on simulation with event pruning to deal with this type of delay model. In this paper, we propose several algorithms to compute the longest and shortest sensitizable path delays based on a data dependent delay model. A proposed algorithm which is based on a combination of modified static (topological) timing analysis and path sensitization techniques seems to offer the best performance. The results obtained have shown to be more accurate than the traditional path sensitization approach based on bounded delay model.

In many designs a large portion of path delay faults is not robustly testable. In this paper, we investigate testing strategies for robustly untestable faults. We show that the quality of nonrobust tests may be very poor in detecting small defects caused by manufacturing process variation. We demonstrate that better quality nonrobust tests can be obtained by including timing information into the process of test generation. A good nonrobust test can tolerate larger timing variations on the off-inputs. We also show that not all nonrobustly untestable path delay faults may be ignored in high quality delay testing. Functional sensitizable paths are nonrobustly untestable but, under some faulty conditions, may degrade the performance of the circuit. However, up till now, there was no strategy for generating tests for such faults. In this paper, we present algorithms for generating high quality nonrobust and functional sensitizable tests. We also devise an algorithm for generating tests for validatable nonrobust faults which have a high quality in detecting defects but are hard to be generated automatically. Our experimental results show that the quality of delay testing increases if validatable and high quality nonrobust tests, as well as tests for functional sensitizable path delay faults are included.

Recently published results have shown that, for many circuits, only a small percentage of path delay faults is robust testable, Among the robust untestable faults, a significant percentage is not nonrobust testable either. In this paper, we take a closer look at the properties of these nonrobust untestable faults with the goal of determining whether and how these faults should be tested. We define a path delay fault to be functional redundant (f-redundant) if, regardless of the delays at all other signals, the circuit performance will not be determined by the path. These paths are false paths-regardless of the delays of all signals. Therefore, these paths cannot and need not be tested. We present a sufficient condition for functional redundancy. We will show that nonrobust untestable faults are not necessarily f-redundant. For those nonrobust untestable but functional irredundant (f-irredundant) faults, the corresponding path may become a true path, and thus may determine the circuit performance under the faulty condition. We present an efficient algorithm for identifying f-redundant path delay faults. Results show that a significant percentage of path delay faults are f-redundant for ISCAS'85 benchmark circuits. Identification of f-redundant faults has two important applications: 1) it provides a more realistic fault coverage measure (as the number of detected faults divided by the total number of f-irredundant faults), 2) For circuits with a large number of paths, testing only a subset of paths becomes a common practice. The path selection process can be guided to avoid selecting f-redundant paths. To illustrate this application, we present an algorithm for selecting a set of f-irredundant path delay faults that includes at least one of the longest f-irredundant paths for each signal in the circuits.

Earlier research results have shown that for many designs, a large portion of path delay faults is not robustly testable.In this paper, we investigate the test strategy for the non-robustly testable faults.We first present some experimental results to show that the quality of a non-robust test set may be very poor in detecting small delay defects caused by manufacturing process variation.We further show that a better set of non-robust tests can be obtained by including timing information in test generation.A good non-robust test can tolerate a larger timing variation on the off-inputs of the path than a poor test.An algorithm for generating such better quality non-robust tests is presented.We present experimental results to compare quality of non-robust test sets with and without using our method.We also present an algorithm, as well as experimental results, for generating validatable non-robust tests.

Both long and short path delays are used to determine the valid clocking for various CMOS circuits such as single phase latching, asynchronous and wave pipelining. Therefore, accurate estimation of both long and short path delays is very crucial in the designing and testing of high speed CMOS circuits. Most of the previous approaches in detecting long and short sensitizable paths assume that the rising and falling of gate delays are either fixed or bounded. We propose several algorithms to compute the longest and shortest sensitizable path delays based on a data dependent delay model. A proposed algorithm which is based on a combination of modified static (topological) timing analysis and path sensitization techniques seems to offer the best performance. The results obtained have shown to be more accurate than the traditional path sensitization approach based on the bounded delay model.>

We consider the problem of determining a valid clock setting for a combinational circuit. The performance of a circuit depends on its clock period. The shorter a valid clock period is, the better the performance is. We have proposed two new bounds for clock period by considering a type of paths called functionally sensitizable paths. Then these results are extended to wavepipelined circuits. We have compared the new bounds with the previously proposed bounds and it has been shown that these new bounds may have better performance for certain combinatorial circuits. We have also given an example to show that the path delays obtained by two-vector model may not be valid when used for clock setting. The bounds on clock period can alternatively be viewed as optimization objectives. We present some experimental results to show various bounds on clock period for ISCAS benchmark circuits and discuss the potential complexity of optimizing circuits with these bounds.>

In this paper, we consider the problem of determining the smallest clock period for a combinational circuit. By considering both the long and short paths, we derive three independent bounds on the clock period. The first bound is the difference between the longest path delay and the shortest path delay. The other two take the functionality of the circuit into consideration and, therefore, are usually smaller than the first one. To bring in the functionality of the circuit, we make use of a new class of paths-called the shortest destabilizing paths-as well as the longest sensitizable paths. We also show that considering both the longest sensitizable path and the shortest destabilizing path together does not always give a valid bound. The bounds on the clock period can be alternatively viewed as optimization objectives. At the physical level, the complexity of optimization very much depends on the number of long and short paths present and the number of gates shared by them. We conducted preliminary experiments to study this.>

The estimation of signal stable ranges in a combinational circuit is an important issue for determining clock time in a synchronous system. An optimal clocking period time highly depends on the accuracy of the shortest path length as well as the longest path length in a combinational circuit. In this paper, a sensitization criterion for the short path is first proposed. Based on this sensitization criterion, an accurate model for calculation of signal stable range can be created. This will allow the output stable range of a gate to be the union of its inputs when the input leads hold a controlling value, rather than to be always the intersection. Then, an LS-algorithm for calculation of signal stable ranges is presented in which both the sensitizable shortest path and the sensitizable longest path are considered. It avoids the exhaustive search by tracing the path sensitization and eliminates some conservative restriction to get more accurate results in a more efficient way, compared to the previous approaches. The speedup and the improved accuracy of the proposed LS-algorithm showed promising experimental results.>

The problem of identifying one of the longest sensitizable paths in a circuit is called a critical path problem. Several critical path algorithms have been proposed in the last few years. However, due to the long computation time required to produce accurate results, these algorithms may not be able to generate any result for large designs with many long false paths unless the accuracy of the results is compromised. Parallel processing seems to be an appropriate way to speed up the required computation. In this paper, we study the parallel algorithms for critical path problem. We first present a sensitization criterion. Based on this sensitization criterion an algorithm called DT-algorithm, which is a variation of the D-algorithm with stable time range of signals also taken into consideration, is developed. The DT-algorithm is especially suitable and can be used to determine the sensitizability of a given path in a parallel processing environment. We also present an implementation of parallel DT-algorithm that can be executed on a shared memory multiprocessor. The experimental results show that a reasonable speed-up can be obtained.>

We study the problem of choosing gate implementations to reduce circuit area while retaining the circuit performance. To incorporate timing analysis into area reduction, we propose to utilize the information provided by a sensitization criterion in computing the slacks of the gates. Not all sensitization criteria can be adopted in our approach. Some conditions were imposed to define a class of sensitization criteria which can guarantee that the circuit performance will be preserved. A greedy area reduction heuristic is proposed, and then an improved version of the Brand-Iyengar and the static sensitization criteria are plugged into the heuristic to obtain results for comparison (D. Brand, V. Iyengar, 1986).>

Recently published results have shown that, for many circuits, only a small percentage of path delay faults is robust testable. Among the robust untestable faults, a significant percentage of them is not non-robust testable either. In this paper, we take a closer look at the properties of these non-robust untestable faults with the goal of determining whether and how these faults should be tested.>

An important aspect of the critical path problem is deciding whether a path is sensitizable. Three new path sensitization criteria are proposed in a general framework. Other path sensitization criteria can be presented in the same framework, enabling them to be compared with each other. An approximate criterion is also proposed and used to develop an efficient critical path algorithm for combinational circuits.>

The problem of selecting a set of paths to optimize the performance of a combinational circuit is studied, assuming that gate resizing and buffer insertion are the two possible optimizing techniques for reducing the delay of a circuit. The objective of the path selection problem is to select as small as possible a set of paths to ease the optimization processing to guarantee that the delay of the circuit is no longer than a given threshold tau if the delays of all the selected paths are no longer than tau . It is shown that the path selection is different from path sensitization. An input vector-oriented path selection algorithm is proposed. Because it may be infeasible for complex circuits with many primary inputs, a path-oriented algorithm is also developed and implemented. Experimental results on ISCAS85 benchmark circuits show a potentially big improvement for the optimization process.>

In this paper we study the problem of selecting a set of paths to optimize the performance of a circuit.We assume that gate resizing is the optimizing technique used to reduce the delay of a circuit.That is, during the optimization process the topology of a circuit remains the same and the gate delays are reduced.The objective of the path selection problem is to select as few paths as possible so that when the delays of all selected paths are shortened, the delay of the optimized circuit is guaranteed to meet its performance requirement.We first propose an input vector oriented path selection algorithm.Due to the fact that the input vector oriented algorithm may be not feasible for complex designs with many input pins, we have designed and developed a path oriented algorithm.For some ISCAS circuits, less than 10% of the long paths are selected by our path oriented algorithm.

Article Free Access Share on An efficient parallel critical path algorithm Authors: Li-Ren Liu Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , David H. C. Du Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Hsi-Chuan Chen Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 535–540https://doi.org/10.1145/127601.127728Published:01 June 1991Publication History 11citation431DownloadsMetricsTotal Citations11Total Downloads431Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Since the delay of a circuit is determined by the delay of its longest sensitizable paths (such paths are called critical paths), the problem of estimating the delay of a circuit is called critical path problem. One important aspect of the critical path problem is to decide whether a path is sensitizable. A framework which allows various previously proposed path sensitization criteria to be compared with each other in a unified way is presented. An exact path sensitization criterion and a looser path sensitization criterion based on the framework are also proposed.>

The estimation of signal stable ranges in combinational circuits is an important issue for setting clock time in a synchronous system. The authors first propose a sensitization criterion for the shortest path, and they then use a path-oriented approach to reduce search space. Considering the possible case where the signal stable range at the output of a gate could be the union of inputs, one can obtain more accurate results than with the intersection approach.>