waashk/dblp huggingface dataset:
vlsi placement using uncertain costs. many objective functions used to evaluate placement quality contain uncertain parameters. while these values (e.g., channel width, cell area, wire length, and circuit delay) can be estimated, they cannot be precisely known until the layout is finished or sometimes until the chip is fabricated. as a result, current automatic placement algorithms must use `expected'' values in their objective functions providing one possible estimate of placement nquality. an algorithm that uses the full range of potential values when computing placement cost can yield a more credible prediction of placement quality and reveal more about the structure of optimal configurations. in this paper, we propose an interval-based approach to modeling uncertainty in automatic placement algorithms. we illustrate our methodology by implementing an interval branch-and-bound placement algorithm. using this example, we demonstrate how interval operators can be used to compute bounds on placement cost and to determine minimum-cost configurations. we also test the performance of our algorithm and analyze the results.
diagnosis of interconnect faults in cluster-based fpga architectures. fault diagnosis has particular importance in the context of field programmable gate arrays (fpgas) because faults can be avoided by reconfiguration at almost no real cost. cluster-based fpga architectures, in which several logic blocks are grouped together into a coarse-grained logic block, are rapidly becoming the architecture of choice for major fpga manufacturers. the high density interconnect found within clusters greatly complicates the problem of fpga diagnosis. we propose a technique for the testing and diagnosis of cluster-based fpga architectures. we present a hierarchical approach to define a set of fpga configurations in which each fault is detectable, and each fault pair is differentiable. the cornerstone of this work is the concise expression of the distinguishing conditions of each fault pair. experimental results demonstrate that nearly 100% fault coverage and diagnostic resolution are achieved with a low number of test configurations.
identification of unsettable flip-flops for partial scan and faster atpg. state justification is a time-consuming operation in test generation for sequential circuits. in this paper, we present a technique to rapidly identify state elements (hip-hops) that are either difficult to set or unsettable. this is achieved by performing test generation on certain transformed circuits to identify state elements that are not settable to specific logic values. two applications that benefit from this identification are sequential circuit test generation and partial scan design. the knowledge of the state space is shown to be useful in creating early backtracks in deterministic test generation. partial scan selection is also shown to benefit from the knowledge of the difficult-to-set hip-hops. experiments on the iscas89 circuits are presented to show the reduction in time for test generation and the improvements in the testability of the resulting partial scan circuits.
equivalent waveform propagation for static timing analysis. this paper proposes a scheme that captures diverse input waveformsof cmos gates for static timing analysis. conventionallythe latest arrival time and transition time are calculated from thetimings when a transient waveform goes across pre-determinedreference voltages. however, this method cannot accurately considerthe impact of waveform shape on gate delay, when crosstalk-inducednon-monotonic waveforms or inductance-dominant stepwisewaveforms are injected. we propose a new timing analysisscheme called "equivalent waveform propagation". the proposedscheme calculates the equivalent waveform that makes the outputwaveform close to the actual waveform, and uses the equivalentwaveform for timing calculation. the proposed scheme can copewith various waveforms affected by resistive shielding, crosstalknoise, wire inductance etc. in this paper, we devise a method tocalculate equivalent waveform. the proposed calculation methodis compatible with conventional methods in gate delay library andcharacterization, and hence our method is easy to be implementedwith conventional static timing analysis tools.
timing analysis considering spatial power/ground level variation. spatial power/ground level variation causes power/ground level mismatch between driver and receiver, and the mismatch affects gate propagation delay. this paper proposes a timing analysis method based on a concept called “pg level equalization” which is compatible with conventional sta frameworks. we equalize the power/ground levels of driver and receiver. the charging/discharging current variation due to equalization is compensated by replacing output load. we present an implementation method of the proposed concept, and demonstrate that the proposed method works well for multiple-input gates and rc load model.
optimal buffered routing path constructions for single and multiple clock domain systems. shrinking process geometries and the increasing use of ip components in soc designs give rise to new problems in routing and buffer insertion. a particular concern is that cross-chip routing will require multiple clock cycles. another is the integration of independently clocked components. this paper explores simultaneous routing and buffer insertion in the context of single and multiple clock domains. we present optimal and efficient polynomial algorithms that can be used to estimate communication overhead for interconnect and resource planning in single and multi-clock domain systems. experimental results verify the correctness and practicality of our approach.
regularity extraction via clan-based structural circuit decomposition. identifying repeating structural regularities in circuits allows the minimization of synthesis, optimization, and layout efforts. we introduce in this paper a novel method for identifying a set of repeating circuit structures, referred to as templates, and we report on using an efficient binate cover solver to select an appropriate subset of templates with which to cover the circuit. our approach is comprised of three steps. first, the circuit graph is decomposed in a hierarchical inclusion parse tree using a clan-based decomposition algorithm. this algorithm discovers clans, grouping of nodes in the circuit graph that have a natural affinity towards each other. second, the parse tree nodes are classified into equivalence classes. such classes represent templates suitable for circuit covering. the final step consists of using a binate cover solver to find an appropriate cover. the cover will consist of instantiated templates and gates that cannot be covered by any templates. we describe the results of applying this algorithm to several circuits, and show that the algorithm is effective in extracting structural regularity.
configuration bitstream compression for dynamically reconfigurable fpgas. field programmable gate arrays (fpgas) holds the possibility of dynamic reconfiguration. the key advantages of dynamic reconfiguration are the ability to rapidly adapt to dynamic changes and better utilization of the programmable hardware resources for multiple applications. however, with the advent of multi-million gate equivalent fpgas, configuration time is increasingly becoming a concern. high reconfiguration cost can potentially wipe out any gains from dynamic reconfiguration. one solution to alleviate this problem is to exploit the high levels of redundancy in the configuration bitstream by compression. in this paper, we propose a novel configuration compression technique that exploits redundancies both within a configuration's bitstream as well as between bitstreams of multiple configurations. by maximizing reuse, our results show that the proposed technique performs 26.5-75.8% better than the previously proposed techniques. to the best of our knowledge, ours is the first work that performs inter-configuration compression.
variability in sub-100nm sram designs. many components of variability become larger percentage design factors with decreasing feature size. hence, the small transistors in sram cells are particularly sensitive to these variations. the sram cell transistors in sub-100-nm designs may contain fewer than 100 channel dopant atoms. to achieve a robust design with such variability, one must enhance the normal static-noise-margin and write-trip-point analysis, often with monte carlo simulations using statistical transistor models including the process and mismatch fluctuations. similar challenges exist for the sense amplifiers normally used with sram arrays. except with very low speed designs, yield to speed can be substantially reduced by variations between nominally matched sense amplifier transistors as well as by the variability resulting in a very worst memory cell low read current. this also increases the hazards of delay timing with dummy paths and dummy cells and increases the need for at-speed testing prior to repair.
a formal approach to nonlinear analog circuit verification. this contribution presents an approach to nonlinear dynamic analog circuit verification. the input-output behavior of two systems is analyzed to check whether they are functionally similar. the algorithm compares the implicit nonlinear state space descriptions of the two systems on the same or on different levels of abstraction by sampling the state spaces and by building a nonlinear one-to-one mapping of the state spaces. some examples demonstrate the feasibility of our approach.
interconnect yield model for manufacturability prediction in synthesis of standard cell based designs. a sound ic design methodology must be supported by adequate manufacturability assessment tools. these tools should assist a designer in predicting ic manufacturing cost in as early a design stage as possible. in this paper a yield model is proposed that takes as input a standard cell netlist and produces as output a yield estimate without performing placement and routing. this yield model has been successfully used to predict the interconnect yield of standard cell designs that were implemented with two place and route tools. the proposed yield model can be used as a crucial component in the objective function of a circuit synthesis tool as well as in technology mapping optimization.
java as a specification language for hardware-software systems. the specification language is a critical component of the hardware-software co-design process since it is used for functional validation and as a starting point for hardware- software partitioning and co-synthesis. this paper pro poses the java programming language as a specification language for hardware-software systems. java has several characteristics that make it suitable for system specification. however, static control and dataflow analysis of java programs is problematic because java classes are dynamically linked. this paper provides a general solution to the problem of statically analyzing java programs using a technique that pre-allocates most class instances and aggressively resolve memory aliasing using global analysis. the output of our analysis is a control dataflow graph for the input specification. our results for sample designs show that the analysis can extract fine to coarse-grained concurrency for subsequent hardware-software partitioning and co-synthesis steps of the hardware-software co- design process to exploit.
jmtp: an architecture for exploiting concurrency in embedded java applications with real-time considerations. using java in embedded systems is plagued by problems of limited runtime performance and unpredictable runtime behavior. the java multi-threaded processor (jmtp) provides solutions to these problems. the jmtp architecture is a single chip containing an off-the-shelf general purpose processor core coupled with an array of java thread processors (jtps). performance can be improved using this architecture by exploiting coarse-grained parallelism in the application. these performance improvements are achieved with relatively small hardware costs. runtime predictability is improved by implementing a subset of the java virtual machine (jvm) specification in the jtp and trimming away complexity without excessively restricting the java code a jtp can handle. moreover, the jmtp architecture incorporates hardware to adaptively manage shared jmtp resources in order to satisfy jtp thread timing constraints or provide an early warning for a timing violation. this is an important feature for applications with quality-of-service demands. in addition to the hardware architecture, we describe a software framework that analyzes a java application for expressed and implicit coarse-grained concurrent threads to execute on jtps. this framework identifies the optimal mapping of an application to a jmtp with an arbitrary number of jtps. we have tested this framework on a variety of applications including idea encryption with different jtp configurations and confirmed that the algorithm was able to obtain desired results in each case.
clock scheduling and clocktree construction for high performance asics. in this paper we present a new method for clock schedulingand clocktree construction that improves the performance ofhigh-end asics significantly.first, we compute a clock schedule that yields the optimumcycle time and the best possible clock distribution with respectto early and late mode; in particular the number of criticaltests is minimized. second, individual arrival time intervalsare computed for all endpoints of the clocktree. finally, weconstruct a clocktree that realizes arrival times within theseintervals and exploits positive slacks to save power consumption.we demonstrate the superiority of our method to previousapproaches by experimental results on industrial asics withup to 194 000 registers and more than 160 clock domains. weimproved the clock frequencies by 5-28% up to 1.033 ghz (in hardware).
pattern generation for a deterministic bist scheme. recently a deterministic built-in self-test scheme has been presented based on reseeding of multiple-polynomial linear feedback shift registers. this scheme encodes deterministic test sets at distinctly lower costs than previously known approaches. in this paper it is shown how this scheme can be supported during test pattern generation. the presented atpg algorithm generates test sets which can be encoded very efficiently. experiments show that the area required for synthesizing a bist scheme that encodes these patterns is significantly less than the area needed for storing a compact test set. furthermore, it is demonstrated that the proposed approach of combining atpg and bist synthesis leads to a considerably reduced hardware overhead compared to encoding a conventionally generated test set.
an efficient procedure for the synthesis of fast self-testable controller structures. the bist implementation of a conventionally synthesized controller in most cases requires the integration of an additional register only for test purposes. this leads to some serious drawbacks concerning the fault coverage, the system speed and the area overhead. a synthesis technique is presented which uses the additional test register also to implement the system function by supporting self-testable pipeline-like controller structures. it will be shown, that if the need of two different registers in the final structure is already taken into account during synthesis, then the overall number of flipflops can be reduced, and the fault coverage and system speed can be enhanced. the presented algorithm constructs realizations of a given finite state machine specification which can be trivially implemented by a self-testable structure. the efficiency of the procedure is ensured by a very precise characterization of the space of suitable realizations, which avoids the computational overhead of previously published algorithms.
statistical timing analysis with two-sided constraints. based on a timing yield model, a statistical static timing analysis technique is proposed. this technique preserves existing methodology by selecting a "device file setting" that takes into account within-die statistical variations, and with which to run traditional static timing analysis in order to meet the desired yield. using process-specific "generic paths" representing critical paths in a given process technology, our approach can be used early in the design process, most importantly during the pre-placement phase. within-die variations are taken care of using a simple model that assumes positive correlation, which leads to upper and lower bounds on the timing yield. our approach also handles both setup and hold timing constraints.
a single-path-oriented fault-effect propagation in digital circuits considering multiple-path sensitization. various satisfiability problems in combinational logic blocks as, for example, test pattern generation, verification, and netlist optimization, can be solved efficiently by exploiting the fundamental concepts of propagation and justification. therefore, fault effect propagation gains further importance. for the first time, we provide the theoretical background for a single path oriented fault effect propagation considering both single and multiple path sensitization. we call this approach spop. furthermore, we formulate necessary and sufficient sensitization conditions for spop. from these conditions the best suited algebra for propagation can be derived. experimental results for stuck--at test pattern generation demonstrate that the new approach is orthogonal to d--frontier based methods. we achieve substantial improvements with respect to test pattern generation time and quality.
adaptation of partitioning and high-level synthesis in hardware/software co-synthesis. previously, we had presented the system cosyma for hardware/software co-synthesis of small embedded controllers. target system of cosyma is a core processor with application specific co-processors. the system speedup for standard programs compared to a single 33mhz risc processor solution with fast, single cycle access ram was typically less than 2 due to restrictions in high-level co-processor synthesis, and incorrectly estimated back end tool performance, such as hardware synthesis, compiler optimization and communication optimization. meanwhile, a high-level synthesis tool for high-performance co-processors in co-synthesis has been developed. this paper explains the requirements and the main features of the high-level synthesis sytem and its integration into cosyma. the results show a speedup of 10 in most cases. compared to the speedup, the co-processor size is very small.
formal specification and verification of a dataflow processor array. we describe the formal specification and verification of the vgi parallel dsp chip [1], which contains 64 compute processors with ~30k gates in each processor. our effort coincided in time with the &ldquo;informal&rdquo; verification stage of the chip. by interacting with the designers, we produced an abstract but executable specification of the design which embodies the programmer's view of the system. given the size of the design, an automatic check that even one of the 64 processors satisfies its specification is well beyond the scope of current verification tools. however, the check can be decomposed using assume-guarantee reasoning. for vgi, the implementation and specification operate at different time scales: several steps of the implementation correspond to a single step in the specification. we generalized both the assume-guarantee method and our model checker mocha to allow compositional verification for such applications. we used our proof rule to decompose the verification problem of the vgi chip into smaller proof obligations that were discharged automatically by mocha. using our formal approach, we uncovered and fixed subtle bugs that were unknown to the designers.
decomposing refinement proofs using assume-guarantee reasoning. model-checking algorithms can be used to verify, formally and automatically, if a low-level description of a design conforms with a high-level description. however, for designs with very large state spaces, prior to the application of an algorithm, the refinement-checking task needs to be decomposed into subtasks of manageable complexity. it is natural to decompose the task following the component structure of the design. however, an individual component often does not satisfy its requirements unless the component is put into the right context, which constrains the inputs to the component. thus, in order to verify each component individually, we need to make assumptions about its inputs, which are provided by the other components of the design. this reasoning is circular: component a is verified under the assumption that context b behaves correctly, and symmetrically, b is verified assuming the correctness of a. the assume-guarantee paradigm provides a systematic theory and methodology for ensuring the soundness of the circular style of postulating and discharging assumptions in component-based reasoning.we give a tutorial introduction to the assume-guarantee paradigm for decomposing refinement-checking tasks. to illustrate the method, we step in detail through the formal verification of a processor pipeline against an instruction set architecture. in this example, the verification of a three-stage pipeline is broken up into three subtasks, one for each stage of the pipeline.
sigma: a simulator for segment delay faults. lucent technologieswe propose an efficient combinational circuit simulation technique for the recently proposed segment delay fault model. after simulation of a vector pair, activated segments are traced using a depth-first search. a segment numbering scheme finds the number of faults to be simulated. a labeling technique generates edge labels to compute a unique label for each segment fault. the use of labels avoids explicit storing of fault lists and allows efficient access to previously detected segment faults. experimental results demonstrate several advantages of the segment delay fault model. first, the total number of faults remains manageable for small segment lengths. second, many segments, not included in any robustly testable path fault, may have robust segment delay fault tests. generating tests for such segments may increase the delay defect coverage.
fast identification of untestable delay faults using implications. we propose a novel algorithm to rapidly identify untestable delay faults using pre-computed static logic implications. our fault-independent analysis identifies large sets of untestable faults, if any, without enumerating them. the cardinalities of these sets are obtained by using a counting algorithm that has quadratic complexity in the number of lines. since our method is based on an incomplete set of logic implications, it gives only a lower bound of the number of untestable faults. a post-processing step can list the untestable faults, if desired. targeting untestable delay faults for test generation by an automatic test pattern generation (atpg) tool can be avoided. the method works on the segment delay fault model and its special case, the path delay fault model, to identify robustly untestable, non-robustly untestable, and functionally unsensitizable delay faults. results on benchmark circuits show that many delay faults are identified as untestable in a very short time. for the benchmark circuit c6288, our algorithm identified 1.978 x 10^20 functionally unsensitizable path faults in 3 cpu seconds.
improved interconnect sharing by identity operation insertion. this paper presents an approach to reduce interconnect cost by insertion of identity operations in a cdfg. other than previous approaches, it is based on systematic pattern analysis and automated transformation selection. the cost function controlling transformation selection is derived with statistical experiments and is optimized using practical benchmarks. the results show significantly reduced interconnect cost for most register architectures and application examples.