waashk/dblp huggingface dataset:
acceleration techniques for dynamic vector compaction. we present several techniques for accelerating dynamic vector compaction for combinational and sequential circuits. a key feature of all our techniques is that they significantly improve the computation times without adversely affecting the quality of test sets that can be derived using state-of-the-art compaction methods. our techniques are based on three key ideas: (1) identification of support sets, (2) target fault switching, and (3) use of dynamic equivalent and untestable fault analysis. all these techniques are useful in significantly reducing the number of faults that have to be considered by a test generator or a fault simulator in a dynamic vector compaction system. for fault simulation, support sets quickly identify a large subset of faults that are guaranteed to be undetectable by a given input sequence. for test generation, support sets identify a large subset of faults that are guaranteed to be undetectable by any extension of a partially specified test sequence. experimental results on iscas 89 benchmark circuits and large production vlsi circuits are included. for full scan designs, our acceleration techniques reduce the overall computation times by a factor of 2 to 3 without adversely affecting the quality (size) of the computed test sets or their fault coverages. the improvement factors obtained are higher for larger circuits. the acceleration techniques enabled the computation of compact test sets for large production circuits that the base test generation system was unable to process in more than 2 cpu days on a silicon graphics mips 4400 workstation. results for sequential circuits also show that our acceleration techniques significantly improve the computation times for dynamic vector compaction.
register-transfer level estimation techniques for switching activity and power consumption. we present techniques for estimating switching activity and power consumption in register-transfer level (rtl) circuits. previous work on this topic has ignored the presence of glitching activity at various data path and control signals, which can lead to significant underestimation of switching activity. for data path blocks that operate on word-level data, we construct piecewise linear models that capture the variation of output glitching activity and power consumption with various word-level parameters like mean, standard deviation, spatial and temporal correlations, and glitching activity at the block's inputs. for rtl blocks that operate on data that need not have an associated word-level value, we present accurate bit-level modeling techniques for glitching activity as well as power consumption. this allows us to perform accurate power estimation for control-flow intensive circuits, where most of the power consumed is dissipated in non-arithmetic components like multiplexers, registers, vector logic operators, etc. since the final implementation of the controller is not available during high-level design iterations, we develop techniques that estimate glitching activity at control signals using control expressions and partial delay information. experiments on example rtl designs resulted in power estimates that were within 7% of those produced by an inhouse power analysis tool on the final gate-level implementation.
an iterative improvement algorithm for low power data path synthesis. we address the problem of minimizing power consumption in behavioral synthesis of data-dominated circuits. the complex nature of power as a cost function implies that the effects of several behavioral synthesis tasks like module selection, clock selection, scheduling, and resource sharing on supply voltage and switched capacitance need to be considered simultaneously to fully derive the benefits of design space exploration at the behavior level. recent work has established the importance of behavioral synthesis in low power vlsi design. however, most of the algorithms that have been proposed separate these tasks and perform them sequentially, and are hence not able to explore the tradeoffs possible due to their interaction. we present an efficient algorithm for performing scheduling, clock selection, module selection, and resource allocation and assignment simultaneously with an aim of reducing the power consumption in the synthesized data path. the algorithm, which is based on an iterative improvement strategy, is capable of escaping local minima in its search for a low power solution. the algorithm considers diverse module libraries and complex scheduling constructs such as multicycling, chaining, and structural pipelining. we describe supply voltage and clock pruning strategies that significantly improve the efficiency of our algorithm by cutting down on the computational effort involved in exploring candidate supply voltages and clock periods that are unlikely to lead to the best solution. experimental results are reported to demonstrate the effectiveness of the algorithm. our techniques can be combined with other known methods of behavioral power optimization like data path replication and transformations, to result in a complete data path synthesis system for low power applications.
transient power management through high level synthesis. the use of nanometer technologies is making it increasingly important to consider transient characteristics of a circuit's power dissipation (e.g., peak power, and power gradient or differential) in addition to its average power consumption. current transient power analysis and reduction approaches are mostly at the transistor- and logic-levels. we argue that, as was the case with average power minimization, architectural solutions to transient power problems can complement and significantly extend the scope of lower-level techniques.in this work, we present a high-level synthesis approach to transient power management. we demonstrate how high-level synthesis can impact the cycle-by-cycle peak power and peak power differential for the synthesized implementation. further, we demonstrate that it is necessary to consider transient power metrics judiciously in order to minimize or avoid area and performance overheads. in order to alleviate the limits on parallelism imposed by peak power constraints, we propose a novel technique based on the selective insertion of data monitor operations in the behavioral description. we present enhanced scheduling algorithms that can accept constraints on transient power characteristics (in addition to the conventional resource and performance constraints). experimental results on several example designs obtained using a state-of-the-art commercial design flow and technology library indicate that high-level synthesis with transient power management results in significant benefits -- peak power reductions of up to 32% (average of 25%), and peak power differential reductions of up to 58% (average of 42%) -- with minimal performance overheads.
analytical bound for unwanted clock skew due to wire width variation. under modern vlsi technology, process variations greatly affectcircuit performance, especially clock skew which is very timingsensitive. unwanted skew due to process variation forms a bottleneckpreventing further improvement on clock frequency. impactfrom intra-chip interconnect variation is becoming remarkable andis difficult to be modeled efficiently due to its distributive nature.through wire shaping analysis, we establish an analytical boundfor the unwanted skew due to wire width variation which is thedominating factor among interconnect variations. experimental resultson benchmark circuits show that this bound is safer, tighterand computationally faster than similar existing approach.
generalized resource sharing. resource sharing is one of the main tasks in high-level synthesis, and although many algorithms have addressed the problem there are still several limitations which restrict the generality and applicability of current algorithms. most clique-partitioning-based algorithms use local and inaccurate cost-functions which result in inefficient results. this paper presents algorithms for the resource sharing problem on registers and functional units, and shows how they overcome the limitations of existing algorithms. the main characteristics of this work are: interleaved register and functional unit merging in a global clique partitioning based framework, accurate merging cost estimation, accurate interconnect cost estimation, relative control cost taken into account and efficient false loop elimination. the results obtained show significant improvements in the delay of designs, while also minimizing area, specially for large designs with many sharing possibilities.
an analytical high-level battery model for use in energy management of portable electronic systems. once the battery becomes fully discharged, a battery-powered portable electronic system goes off-line. therefore, it is important to take the battery behavior into account. a system designer needs an adequate high-level model in order to make battery-aware decisions that target maximization of the system's lifetime on-line. we propose such a model: it allows a designer to predict the battery time-to-failure for a given load and provides a cost metric for lifetime optimization algorithms. our model also allows for a tradeoff between the accuracy and the amount of computation performed. the quality of the proposed model is evaluated using a detailed low-level simulation of a lithium-ion electrochemical cell.
accurate layout area and delay modeling for system level design. the problem of estimating design quality measures to accurately reflect design tradeoffs and efficiently explore the design space is discussed. specifically, interest is centered on predicting the layout area and delay of a given structural rt level design. clearly, current rt level cost measures are highly simplified and do not reflect the real physical design. in order to establish a more realistic assessment of layout effects, a layout model which accurately and efficiently accounts for the effects of wiring and floorplanning on the area and performance layout of rt level designs is proposed. benchmarking has shown that this model is quite accurate
latency effects of system level power management algorithms. a power management algorithm for an embedded system reduces system level power dissipation by shutting off parts of the system when they are not being used and turning them back on when they are required. algorithms for this problem are online in nature since they must operate without knowledge of the arrival time or service requirements of future requests. in this paper, we present online algorithms to manage power for embedded systems. we perform an empirical analysis of these algorithms and give theoretical justification for the empirical results. effective power management strategies have an adverse impact on the latency of the system for which the strategy is designed. typically, the more aggressive the power management scheme, the greater the increase in the latency of the system. in this paper, we prove an upper bound on the additional latency of the system introduced by power management strategies. moreover, we show that this upper bound occurs each time the system is shutdown and hence is an important system design parameter.in addition, service time and latencies have an effect on power management strategies since they alter the length and occurrences of idle periods which. we study this phenomenon experimentally, by modeling the disk drive of a laptop computer as an embedded system. the results show that if service times of arriving requests are modeled, the relative performance of algorithms can change leading to non-adaptive algorithms performing better than adaptive ones. we compare the performance of adaptive and non-adaptive power management algorithms. in particular, our experimental results show that an "immediate" shutdown strategy that shuts down the system whenever it encounters an idle period performs surprising better than sophisticated adaptive algorithms suggested in the literature. we provide an analytical explanation for the effectiveness of power management strategies.
portable parallel test generation for sequential circuits. a parallel test generation algorithm, propertest, for sequential circuits that is portable across a range of mimd parallel architectures is discussed. it uses prioritized execution to ensure consistent speedups as the number of processors is increased. this consistency is achieved without loss of fault coverage with increase in the number of processors. this also permits the use of parallel processing to improve the fault coverage when the execution time is bounded. results on iscas 89 benchmark programs are provided on a shared memory machine, a message passing machine, and a network of workstations. propertest was run unchanged on these different architectures
test-model based hierarchical dft synthesis. with increasing design sizes and adoption of system on a chip (soc) methodology, design synthesis and test automation tools are hitting capacity and performance bottlenecks. currently, hierarchical synthesis flows for large designs lack complete designfor-test (dft) support. with this paper, we address a solution, involving the introduction of test models in a traditional dft synthesis flow, that we term hierarchical dft synthesis (hds). we discuss the use of core test language (ctl) based test models combined with physical and timing models to provide a complete flow for chip-level dft. in doing so we address some challenges the new flow presents such as design rule checking (drc), dft architecting and optimization. we describe methods to overcome these challenges thereby presenting a new methodology to handle complex next generation designs.
achievable bounds on signal transition activity. transitions on high capacitance busses in vlsi systems result in considerable system power dissipation. therefore, various coding schemes have been proposed in the literature to encode the input signal in order to reduce the number of transitions. in this paper we derive achievable lower and upper bounds on the expected signal transition activity. these bounds are derived via an information-theoretic approach in which symbols generated by a source (possibly correlated) with entropy rate h are coded with an average of r bits/symbol. these results are applied to, 1.) determine the activity reducing efficiency of different coding algorithms such as entropy coding, transition coding, and bus-invert coding, 2.) bound the error in entropy-based power estimation schemes, and 3.) determine the lower-bound on the power-delay product. two examples are provided where transition activity within 4% and 8% of the lower bound is achieved when blocks of 8 and 13 symbols respectively are coded at a time.
an integrated design flow for a via-configurable gate array. in this work we present a complete physical design flow for a via-configurable gate array (vcga). the vcga is an array of prefabricated logic blocks and fixed metal masks. the block consists of via-configurable functional cells and a via-decomposable flip-flop. an m1-m2 via mask is used to define the block's functionality. interconnects are customized using via masks. we developed a physical design flow for vcga, which integrates a set of effective techniques. here, we highlight the packing, cell-binding, and detailed-routing problems. we use our design flow to compare the vcga-based and standard-cell/fpga-based designs. experimental results show the efficiency of our flow.
via-configurable routing architectures and fast design mappability estimation for regular fabrics. in this paper, we describe a new via-configurable routing architecture which shows a much better throughput and performance than the previous structures. we demonstrate how to construct a single-via-mask fabric to reduce the mask cost further, and we analyze the penalties which it incurs. to solve the routability problem commonly existing in fabric-based designs, an efficient white-space allocation and an incremental cell movement scheme are suggested, which help to provide a fast design convergence and early prediction of circuit's mappability to a given fabric.
on the np-completeness of regular 2-d fpga routing architectures and a novel solution. several industrial fpga routing architectures have been shown to have no efficient routing algorithms (unless p=np). here, we further investigate if the intractability of the routing problem on a regular 2-d fpga routing architecture can be alleviated by adding routing switches. we show that on this routing architecture, even with a substantial increase in switching flexibility, a polynomial time, predictable routing algorithm is still not likely to exist, and there is no constant ratio bound of the detailed over global routing channel densities. we also show that a perfect routing is unachievable on this architecture even with near complete (maximum) switching flexibility.we also discuss a new, greedy routing architecture, that possesses predictable and other desired routing properties, yet requires fewer routing resources than regular architectures. this theoretical result may suggest an alternative approach in routing architecture designs.
a heuristic to determine low leakage sleep state vectors for cmos combinational circuits. input vector control has been used to minimize the leakage powerconsumption of a circuit in sleep state. in this paper, we presenta novel heuristic for determining a low leakage vector to beapplied to a circuit in sleep state. the heuristic is a greedy searchbased on the controllability of nodes in the circuit and uses thefunctional dependencies among cells in the circuit to guide thesearch. results on a set of iscas and mcnc benchmark circuitsshow that in all cases our heuristic returns a vector having aleakage within 5% of that of the vector obtained using an extensiverandom search, with orders of magnitude improvement incomputational speed.
frugal linear network-based test decompression for drastic test cost reductions. in this work we investigate an effective approach to construct a linear decompression network in the multiple scan chain architecture. a minimal pin architecture, complemented by negligible hardware overhead, is constructed by mathematically analysing test data relationships, delivering in turn drastic test reductions. the proposed network drives a large number of internal scan chains with a short input vector, thus allowing significant reductions in both test time and test volume. the proposed method constructs an inverter-interconnect based network by exploring the pairwise linear dependencies of the internal scan chain vectors, resulting in a very low cost network that is nonetheless capable of outperforming much costlier compression schemes. we propose an iterative algorithm to construct the network from an initial set of test cubes. the experimental data shows significant reductions in test time and test volume with no loss of fault coverage.
energy optimization for a two-device data flow chain. many applications running on today's portable devices use multiple power-consuming devices simultaneously, often in the form of a dataflow chain which involves transfer of data between devices through buffers. some of these devices have the ability to scale their performance and power simultaneously by tuning one of their parameters (generically called the device speed). we address the problem of minimizing the energy consumed by a two-device data flow chain by choosing the speed profiles of the two devices and the "cycle time" of the intermediate buffer. determining the speed profiles (functions of time) to minimize the energy functional, in general, requires variational techniques. however, based on certain observations about device power-speed relations and application performance constraints, we were able to solve the problem analytically in two steps - device characterization and cycle time optimization. the effectiveness of the technique was demonstrated for two practical applications of dataflow chains - cd recording and vcd playback with up to 45% and 64% energy improvements, respectively.
battery optimization vs energy optimization: which to choose and when? batteries are non-ideal energy sources - minimizing the energy consumption of a battery-powered system is not equivalent to maximizing its battery life. we propose an alternative interpretation of a previously proposed battery model, which indicates that the deviation from ideal behavior is due to the buildup of "unavailable charge" during the discharge process. previously, battery-aware task scheduling algorithms and power management policies have been developed, which try to reduce the unavailable charge at the end of a given workload. however, they do not account for the occurrence of rest periods (user enforced, naturally occurring, or due to finite load horizon), which are present in a variety of workloads. we first obtain an analytical bound on the recovery time of a battery as a function of the extent of recovery. then, we shown that the effect of the rest periods is to reduce the improvement of battery-charge optimizing techniques over traditional energy-optimizing techniques. under certain conditions, the policy that only minimizes energy consumption can actually achieve a longer battery lifetime than a battery-aware policy. a formal criterion based on the recovery time is proposed to choose between a candidate battery-aware policy and a candidate energy-aware policy. we also model the battery discharge process as a linear time invariant system and obtain the frequency response of a battery. this is then used to study the effect of task granularity on the improvement achieved by battery-aware task scheduling. it was observed that the response time of typical batteries are of the order of seconds to several minutes. this, along with the charge recovery effect, was seen to cause battery-aware task scheduling methods to become ineffective for both very fine-grained (less than 10 ms) and very coarse-grained (greater than 30 mm) task granularities.
system level verification of digital signal processing applications based on the polynomial abstraction technique. polynomial abstraction has been developed for data abstraction of sequential circuits, where the functionality can be expressed as polynomials. the method, based on the fundamental theorem of algebra, abstracts a possibly infinite domain of input values, into a much smaller and finite one, whose size is calculated according to the degree of the respective polynomial. the abstract model preserves the system's control and data properties, which can be verified by model checking. experiments show that our approach does not only allow an automatic verification, but also gives considerably better results than existing methods.