waashk/dblp huggingface dataset:
clock schedule verification under process variations. with aggressive scaling down of feature sizes in vlsi fabrication, process variations have become a critical issue in designs, especially for high-performance ics. usually having level-sensitive latches for their speed, high-performance ic designs need to verify the clock schedules. with process variations, the verification needs to compute the probability of correct clocking. because of complex statistical correlations, traditional iterative approaches are difficult to get accurate results. instead, a statistical checking of the structural conditions for correct clocking is proposed, where the central problem is to compute the probability of having a positive cycle in a graph with random edge weights. the proposed method only traverses the graph once to avoid the correlations among iterations, and it considers not only data delay variations but also clock skew variations. experimental results showed that the proposed approach has an error of 0.14% on average in comparisons with the monte carlo simulations.
efficient algorithms for buffer insertion in general circuits based on network flow. with shrinking vlsi feature sizes and increasing overall chip areas, buffering has emerged as an effective solution to the problem of growing interconnect delays in modern designs. the problem of buffer insertion in a single net has been the focus of most previous researches. however, efficient algorithms for buffer insertion in whole circuits are generally needed. in this paper, we relate the timing constrained minimal buffer insertion problem to the min-cost flow dual problem, and propose two algorithms based on min-cost flow and min-cut techniques, respectively, to solve it in combinational circuits. we compare our approaches to a traditional approach based on lagrangian relaxation. experimental results demonstrate that our approaches are efficient and effective. on the average, our approaches achieve 45% and 39% reduction, respectively, on the number of buffers inserted in comparison to the traditional approach.
optimal non-uniform wire-sizing under the elmore delay model. we consider non-uniform wire-sizing for general routing trees under the elmore delay model. three minimization objectives are studied: (1) total weighted sink-delays; (2) total area subject to sink-delay bounds; and (3) maximum sink delay. we first present an algorithm nwsa-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula. we show that nwsa-wd always converges to an optimal wire-sizing solution. based on nwsa-wd and the lagrangian relaxation technique, we obtained two algorithms nwsa-db and nwsa-md which can optimally solve the other two minimization objectives. experimental results show that our algorithms are efficient both in terms of runtime and storage. for example, nwsa-wd, with linear runtime and storage, can solve a 6201-wire segment routing-tree problem using about 1.5-second runtime and 1.3-mb memory on an ibm rs/6000 workstation.
integrated floorplanning and interconnect planning. the vlsi fabrication has entered the deep sub-micron era and communication between different components has significantly increased. interconnect delay has become the dominant factor in total circuit delay. as a result, it is necessary to start interconnect planning as early as possible. in this paper, we propose a method to combine interconnect planning with floorplanning. our approach is based on the wong-liu floorplanning algorithm. when the positions, orientations, and shapes of the cells are decided, the pin positions and routing of the interconnects are decided as well. we use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperatures to reduce running time. a temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. experimental results show that our approach performs well.
test generation for delay faults in non-scan and partial scan sequential circuits. a recently proposed transition fault model for sequential circuits is considered. in this fault model, a transition fault is characterized by the fault site, the fault type and the fault size. it was observed that neither a comprehensive functional verification sequence nor a sequence with a high stuck-at fault coverage gives a high transition fault coverage for sequential circuits. deterministic test generation for delay faults is required to raise the coverage to a reasonable level. here, a test generation algorithm for this fault model is presented. with the use of a fault injection technique, tests for transition faults can be generated by using a stuck-at fault test generation algorithm with some modifications. the test generator datest has been integrated with a sequential circuit delay fault simulator, tfsim. experimental results for iscas-89 benchmark circuits and some designs are presented. for partial scan circuits, a test application scheme for detecting transition faults is described. modifications on test generation and fault simulation algorithms required for partial scan circuits are presented. experimental results are presented
risa: accurate and efficient placement routability modeling. the prevalence of net list synthesis tools raises great concern on routability of cell placement created with state-of-the-art placement techniques. in this paper, an accurate and efficient placement routability modeling technique is proposed and incorporated into the prevailing simulated annealing approach. this accurate and efficient modeling is based on the supply versus demand analysis of routing resource over an array of regions on a chip. vertical and horizontal routability is analyzed separately due to the bias of routing resource in multiple-metal-layer asic designs. a special technique on net bounding box partitioning is also proposed and critical to the accuracy of this modeling at the presence of mega cells, which tend to cause local routing congestion. by incorporating this efficient modeling into the cost function of simulated annealing, experiments conducted on small to large industrial designs indicate that placement routability evaluated with a global router is greatly improved as a result of the proposed accurate modeling.
synthesis of cmos domino circuits for charge sharing alleviation. the charge sharing (cs) problem is one of notorious noise problems in domino circuits design and test. in this paper, this problem is thoroughly investigated by considering circuit topology and circuit function. the sensitivity of each domino gate to the cs problem is represented by the concept of cs-vulnerability. a method to derive the cs-vulnerability and the test pattern for each domino gate is suggested. we also propose a transistor reordering method to dramatically reduce the cs-vulnerabilities for all domino gates, so that the cs problem can be alleviated. simulation results demonstrate that our transistor reordering method can efficiently reduce the cs-vulnerabilities for most of domino circuits.
fault emulation: a new approach to fault grading. in this paper, we propose a method of using an fpga-based emulation system for fault grading. the real-time simulation capability of a hardware emulator could significantly improve the run-time of fault grading, which is one of the most resource-intensive tasks in the design process. a serial fault emulation algorithm is employed and enhanced by two speed-up techniques. first, a set of independent faults can be emulated in parallel. second, simultaneous injection of multiple dependent faults is also possible by adding extra supporting circuitry. because the reconfiguration time spent on mapping the numerous faulty circuits into the fpga boards could be the bottleneck of the whole process, using extra logic for injecting a large number of faults per configuration can reduce the number of reconfigurations, and thus, significantly improve the efficiency. some modeling issues that are unique in the fault emulation environment are also addressed. the performance estimation indicates that this approach could be several orders of magnitude faster than the existing software approaches for large designs.
an efficient method for hot-spot identification in ulsi circuits. in this paper, we present a method to efficiently identify the onchip hot spots in ulsi circuits. a set of mathematical formulae were derived in analytical forms so that local temperature information can be fetched quickly. these formulae were based on the green's function and error function approximation, and the resulting equations were further simplified to a tractable level by asserting different constraints. experimental result shows that this method is able to accurately locate the hot spots with little time complexity. it is particularly useful for temperature-driven circuit macro placement in early chip design phase, for which a large number of design iterations is needed and simulation efficiency is much required.
circuit partitioning with logic perturbation. traditionally, the circuit partitioning problem is done by first modeling a circuit as a graph and then partitioning is performed on the modeling graph. using the concept of alternative wires, we propose an efficient method that is able to preserve a local optimal solution in the graph domain while a different graph, representing the same circuit, is generated. when a conventional graph partitioning technique reaches a local optimal solution, our proposed technique generates a different graph that is logically equivalent to the original circuit, and that has equal or better partitioning solution. faced with a different graph which is newly generated, together with a currently good partitioning solution, a conventional graph partitioning technique may then escape from the local optimum and continue searching for better solutions in a different graph domain. the proposed technique can be combined with almost any graph partitioner. experiments show encouraging results.
floorplan design for multi-million gate fpgas. modern fpgas have multi-millions of gates and future generations of fpga will be even more complex. this means floorplanning tools will soon be extremely important for the physical design of fpgas. due to the heterogeneous logic and routing resources on an fpga, fpga floorplanning is very different from the traditional floorplanning for asics. this work presents the first fpga floorplanning algorithm targeted for fpgas with heterogeneous resources (e.g., xilinx's spartan3 chips consisting of columns of clbs, ram blocks, and multiplier blocks). our algorithm can generate floor-plans for xilinx's xc3s5000 architecture (largest of the spartan3 family) in a few minutes.
fame: a fault-pattern based memory failure analysis framework. a memory failure analysis framework is developed-the failureanalyzer for memories (fame). the fame integrates the memoryerror catch and analysis (meca) system and the memory defect diagnostics(mdd) system. the fault-type based diagnostics approachused by meca can improve the efficiency of the test and diagnosticalgorithms. the fault-pattern based diagnostics approach used bymdd further improves the defect identification capability. the famealso comes with a powerful viewer for inspecting the failure patternsand fault patterns. it provides an easy way to narrow down the potentialcause of failures and identify possible defects more accuratelyduring the memory product development and yield ramp-up stage.an experiment has been done on an industrial case, demonstratingvery accurate results in a much shorter time as compared with theconventional way.
stable multiway circuit partitioning for eco. we propose a new stable multiway partitioning algorithm,where stability is defined as an additional quality of a partitioningsolution. the stability of a partitioning algorithm isan important criterion for a partitioning based placement toachieve timing closure through the repetition of the placementprocedure [invited talk: important placement considerations for modern vlsi chips]. given a previous partitioning result p*on an original netlist hypergraph h* and a partially modifiednetlist hypergraph h, a new cost function with similarityfactor is defined to produce a new partition p on hwhich is similar to the original partition p*. the proposedalgorithm is the first approach that quantifies the degree ofsimilarity of a current partition to the original partition usingsimilarity cost. our goal is to build a new partition ina relatively short run time, whose cut quality is not muchdegraded from that of the original partition p* while it preservesas much of the previous groupings in p* as possible.the proposed partitioner is especially beneficial to engineeringchange order (eco) applications, where partial modificationsof a netlist are handled by the incremental methodologyin a design iteration cycle. our approach helps ecoplacers maximize the incremental capability since the portionsto be re-placed are minimized. experimental resultsshow that the proposed algorithm achieves a high qualitypartition comparable to a state-of-the-art multilevel partitionerhmetis [multilevel k-way hypergraph partitioning], while many portions of the groupings in the previous partition are preserved in the current partition.the tradeoff between similarity and cut quality with respectto a varying similarity coefficient is also shown.
diagnosis of realistic bridging faults with single stuck-at information. abstract: precise failure analysis requires accurate fault diagnosis. a previously proposed method for diagnosing bridging faults using single stuck-at dictionaries was applied only to small circuits, produced large and imprecise diagnoses, and did not take into account the byzantine generals problem for bridging faults. we analyze the original technique and improve it by introducing the concepts of match restriction, match requirement, and failure recovery. our new technique, which requires no information other than that used by standard stuck-at methods, produces diagnoses that are an order of magnitude smaller than those produced by the original technique and produces many fewer misleading diagnoses than that of traditional stuck-at diagnosis.
inside: instruction selection/identification & design exploration for extensible processors. this paper presents the inside system that rapidly searchesthe design space for extensible processors, given area and performance constraints of an embedded application, while minimizing the design turn-around-time. our system consists ofa) a methodology to determine which code segments are mostsuited for implementation as a set of extensible instructions,b) a heuristic algorithm to select pre-configured extensibleprocessors as well as extensible instructions (library), and c)an estimation tool which rapidly estimates the performance ofan application on a generated extensible processor. by selecting the right combination of a processor core plus extensible instructions, we achieve a performance increase on average of 2.03x (up to 7x) compared to the base processor core at aminimum hardware overhead of 25% on average.
a quantitative study and estimation models for extensible instructions in embedded processors. designing extensible instructions is a computationally complex task, due to the large design space each instruction is exposed to. one method of speeding up the design cycle is to characterize instructions and estimate their peculiarities during a design exploration. in this paper, we study and derive three estimation models for extensible instructions: area overhead, latency, and power consumption under a wide range of customization parameters. system decomposition and regression analysis are used as the underlying methods to characterize and analyze extensible instructions. we verify our estimation models using automatically and manually generated extensible instructions, plus extensible instructions used in large real-world applications. the mean absolute error of our estimation models arc as small as: 3.4% (6.7% max.) for area overhead, 5.9% (9.4% max.) for latency, and 4.2% (7.2% max.) for power consumption, compared to estimation through the time consuming synthesis and simulation steps using commercial tools. our estimation models achieve an average speedup of three orders of magnitude over the commercial tools and thus enable us to conduct a fast and extensive design space exploration that would otherwise not be possible. the estimation models are integrated into our extensible processor tool suite.
compact modeling and spice-based simulation for electrothermal analysis of multilevel ulsi interconnects. this paper presents both compact analytical models and fast spice based 3-d electro-thermal simulation methodology to characterize thermal effects due to joule heating in high performance cu/low-k interconnects under steady-state and transient stress conditions. the results demonstrate excellent agreement with experimental data and those using finite element (fe) thermal simulations (ansys). the effect of vias, as additional heat sinking paths to alleviate the temp erature rise in the metal wires, is included in our analysis to provide more accurate and realistic thermal diagnosis. it shows that the effectiveness of vias in reducing the temperature rise in interconnects is highly dependent on the via separation and the dielectric materials used. the analytical model is then applied to estimate the temperature distribution in multi-level interconnects. in addition, we discuss the possibility that, under the impact of thermal effects, the performance improvement expected from the use of low-k dielectric materials may be degraded. furthermore, thermal coupling between wires is evaluated and found to be significant. finally, the impact of metal wire aspect ratio on interconnect thermal characteristics is discussed.
random pattern testable logic synthesis. previous procedures for synthesis of testable logic guarantee that all faults in the synthesized circuits are detectable. however, the detectability of many faults in these circuits can be very low leading to poor random pattern testability. a new procedure to perform logic synthesis that synthesizes random pattern testable multilevel circuits is proposed. experimental results show that the circuits synthesized by the proposed procedure tstfx are significantly more random pattern testable and smaller than those synthesized using its counterpart fast_extract (fx) in sis. the proposed synthesis procedure design circuits that require only simple random pattern generators in built-in self-test, thereby obviating the need for complex bist circuitry.
bist tpg for faults in system backplanes. a built-in self-test (bist) methodology to test system backplanes by using bist functionality in each of its constituent boards is presented. since the configurations of systems change frequently, at the system level, the proposed methodology employs a simple test schedule which can be easily changed whenever the system configuration is changed. since the boards used in such systems are designed for use in a wide variety of systems, the proposed methodology defines the test objectives to be achieved by a board's bist circuit in terms of the board's edge pin connections, independent of the configurations of the systems in which the board may be used. it is shown that the combination of the proposed test schedule and the availability, on each board in the system, of any bist circuit that satisfies the proposed test objectives, guarantees safe testing of faults in backplanes. a programmable test architecture and an algorithm to program the architecture to obtain bist that satisfies the test objectives is also presented. finally, the applicability and effectiveness of the methodology is demonstrated via its application to multiple configurations of an example system that uses a vme backplane.
fast and efficient phase conflict detection and correction in standard-cell layouts. alternating-aperture phase shift masking (aapsm), a form of strong resolution enhancement technology (ret) is used to image critical features on the polysilicon layer at smaller technology nodes. this technology imposes additional constraints on the layouts beyond traditional design rules. of particular note is the requirement that all critical features be flanked by opposite-phase shifters, while the shifters obey minimum width and spacing requirements. a layout is called phase-assignable if it satisfies this requirement. phase conflicts between shifters have to be removed to enable the use of aapsm for layouts that air not phase-assignable. previous work has sought to detect a suitable set of phase conflicts to be removed, as well as correct them as well as correct them. this paper has two key contributions: (1) a new computationally efficient approach to detect a minimal set of phase conflicts, which when corrected produces a phase-assignable layout; (2) a novel layout modification scheme for correcting these phase conflicts in standard-cell blocks. unlike previous formulations of this problem, the proposed solution for the conflict detection problem does not frame it as a graph bipartization problem. instead, a simpler and more computationally efficient reduction is proposed. this simplification greatly improves the runtime, while maintaining the same improvements ill the quality of results. an average runtime speedup of 5.9/spl times/ is achieved using the new flow. a new layout modification scheme for correcting phase conflicts in large standard-cell blocks is also proposed. the proposed layout modification scheme can handle all phase conflicts in large standard-cell blocks with small increases in area. our experiments show that the percentage area increase for making typical standard-cell blocks phase-assignable ranges from 3.4-9.1%.
a comparative study of design for testability methods using high-level and gate-level descriptions. a comparative study of a gate-level test generator and a high-level test generator by benchmarking them on a common suite of circuits is presented. based on the examination of the results dft techniques that use high-level circuit information are proposed. the results obtained after partial scan selection by a high-level dft tool are compared with results obtained by a gate-level partial scan tool. this detailed comparative study demonstrates that a dft tool can make a more effective selection of partial scan flip-flops by exploiting the high-level circuit information, and by accurately predicting the hard-to-test areas of a circuit
automatic compositional minimization in ctl model checking. a method for reducing the complexity of ctl model checking on a system of interacting finite state machines is described. the method consists essentially of reducing each component machine with respect to the property to be verified, and then verifying the property on the composition of the reduced components. the procedure is fully automatic and produces an exact result. the potential of the approach is assessed on real-world examples, and the method is demonstrated on a circuit
fast flip-chip power grid analysis via locality and grid shells. full-chip power grid analysis is time consuming. several techniques have been proposed to tackle the problem but typically they deal with the power grid as a whole or partition at unnatural boundaries. using a locality effect under flip-chip packaging, we propose a natural partitioning approach based on overlapping power grid "shells". the technique makes more efficient any previous simulation techniques that are polynomial in grid size. it is also parallelizable and therefore extremely fast. using complete partitions gives no loss of accuracy compared to a full matrix solution, while lesser partitions are conservative for droop and current. results on a recent pentium/spl reg/ microprocessor design show excellent speed and accuracy.