waashk/dblp huggingface dataset:
ilp models for the synthesis of asynchronous control circuits. a new technique for the logic synthesis of asynchronous circuits is presented. it is based on the structural theory of petri nets and integer linear programming. the techniqueis capable of checking implementability conditions, such as,complete state coding, and deriving a gate netlist to implement the specified behavior. this technique can synthesize specifications with few thousands of transitions in the petrinet, providing a speed-up of several orders of magnitudewith regard to other existing techniques.
phdd: an efficient graph representation for floating point circuit verification. data structures such as *bmds, hdds, and k*bmds provide compact representations for functions which map boolean vectors into integer values, but not floating point values. in this paper, we propose a new data structure, called multiplicative power hybrid decision diagrams (*phdds), to provide a compact representation for functions that map boolean vectors into integer or floating point values. the size of the graph to represent the ieee floating point encoding is linear with the word size. the complexity of floating point multiplication grows linearly with the word size. the complexity of floating point addition grows exponentially with the size of the exponent part, but linearly with the size of the mantissa part. we applied *phdds to verify integer multipliers and floating point multipliers before the rounding stage, based on a hierarchical verification approach. for integer multipliers, our results are at least 6 times faster than *bmds. previous attempts at verifying floating point multipliers required manual intervention. we verified floating point multipliers before the rounding stage automatically.
daomap: a depth-optimal area optimization mapping algorithm for fpga designs. in this work we study the technology mapping problem for fpga architectures to minimize chip area, or the total number of lookup tables (luts) of the mapped design, under the chip performance constraint. this is a well-studied topic and a very difficult task (np-hard). the contributions of this work are as follows: (i) we consider the potential node duplications during the cut enumeration/generation procedure so the mapping costs encoded in the cuts drive the area-optimization objective more effectively; (ii) after the timing constraint is determined, we will relax the non-critical paths by searching the solution space considering both local and global optimality information to minimize mapping area; (iii) an iterative cut selection procedure is carried out that further explores and perturbs the solution space to improve solution quality. we guarantee optimal mapping depth under the unit delay model. experimental results show that our mapping algorithm, named daomap, produces significant quality and runtime improvements. compared to the state-of-the-art depth-optimal, area minimization mapping algorithm cutmap (cong and hwan, 1995), daomap is 16.02% better on area and runs 24.2x faster on average when both algorithms are mapping to fpgas using luts of five inputs. luts of other inputs are also used for comparisons.
the y-architecture for on-chip interconnect: analysis and methodology. the y-architecture for on-chip interconnect is based on pervasiveuse of 0-, 120-, and 240-degree oriented semi-global and globalwiring. its use of three uniform directions exploits on-chip routingresources more efficiently than traditional manhattan wiring architecture.this paper gives in-depth analysis of deployment issues associatedwith the y-architecture. our contributions are as follows:(1) we analyze communication capability (throughput of meshes)for different interconnect architectures using a multi-commodityflow approach and a rentian communication model. throughput ofthe y-architecture is largely improved compared to the manhattanarchitecture, and is close to the throughput of the x-architecture.(2) we propose a symmetrical y clock tree structure with bettertotal wire length compared to both h and x clock tree structures,and better path length compared to the h tree. (3) we discuss powerdistribution under the y-architecture, and give analytical and spicesimulation results showing that the power network in y-architecturecan achieve 8.5% less ir drop than an equally-resourced power networkin manhattan architecture. (4) we propose the use of via tunnelsand banks of via tunnels as a technique for improving routabilityfor manhattan and y-architectures.
a general dispersive multiconductor transmission line model for interconnect simulation in spice. although numerous methods have been proposed for interconnect simulation, no single model exists for all kind of transmission line problems. this paper presents a new, single, general dispersive coupled uniform/nonuniform transmission line model which can be used for interconnect simulation in spice. the mathematical model is based on the use of chebyshev polynomials for the representation of the spatial variation of the transmission-line voltages and currents. a simple collocation procedure is used to obtain a matrix representation of the transmission line equations with matrix coefficients that are first polynomials in s, and in which terminal transmission-line voltages and currents appear explicitly. thus, the model is compatible with both the spice's numerical integration algorithm and the modified nodal analysis formalism.
imf: interconnect-driven multilevel floorplanning for large-scale building-module designs. we present in this paper, a new interconnect-driven multilevel floorplanning, called imf, to handle large-scale building-module designs. unlike the traditional multilevel framework that adopts the "v-cycle" framework: bottom-up coarsening followed by top-down uncoarsening, in contrast, imf works in the "/spl lambda/-cycle" manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). the top-down partitioning stage iteratively partitions the floorplan region based on mm-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and thus the total wirelength. then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. we also propose an accelerative fixed-outline floorplanning (aff) to speed up wirelength minimization under the outline constraint. experimental results show that imf consistently obtains the best floorplanning results with the smallest wirelength for large-scale building-module designs, compared with all publicly available floorplanners. in particular, imf scales very well as the circuit size increases. the /spl lambda/-cycle multilevel framework outperforms the v-cycle one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the /spl lambda/-cycle framework considers the global configuration first and then processes down to local ones level by level and thus the global effects can be handled at earlier stages. the /spl lambda/-cycle multilevel framework is general and thus can be readily applied to other problems.
partial simulation-driven atpg for detection and diagnosis of faults in analog circuits. in this paper, we propose a novel fault-oriented test generation methodology for detection and isolation of faults in analog circuits. given the description of the circuit-under-test, the proposed test generator computes the optimal transient test stimuli in order to detect and isolate a given set of faults. it also computes the optimal set of test nodes to probe at, and the time instants to make measurements. the test generation program accommodates the effects introduced by component tolerances and measurement inaccuracy, and can be tailored to fit the signal generation capabilities of a hardware tester. experimental results show that the proposed technique can be applied to generate transient tests for both linear and non-linear analog circuits of moderate complexity in reasonably less cpu time. this will significantly impact the test development costs for an analog circuit and will decrease the time-to-market of a product. finally, the short duration and the easy-to-apply feature of the test stimuli will lead to significant reduction in production test costs.
fast and exact simultaneous gate and wire sizing by lagrangian relaxation. this paper considers simultaneous gate and wire sizing for general vlsi circuits under the elmore delay model. we present a fast and exact algorithm which can minimize total area subject to maximum delay bound. the algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g. minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). no previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. it is based on lagrangian relaxation and "one-gate/wire-at-a-time" local optimizations, and is extremely economical and fast. for example, we can optimize a circuit with 13824 gates and wires in about 13 minutes using under 12 mb memory on an ibm rs/6000 workstation.
test scheduling for core-based systems. we present optimal solutions to the test scheduling problem for core-based systems. we show that test scheduling is equivalent to the m-processor open-shop scheduling problem and is therefore np-complete. however, a commonly-encountered instance of this problem (m = 2) can be solved in polynomial time. for the general case (m > 2), we present a mixed-integer linear programming (milp) model for optimal scheduling and apply it to a representative core-based system using an milp solver. we also extend the milp model to allow optimal test set selection from a set of alternatives. finally, we present an efficient heuristic algorithm for handling larger systems for which the milp model may be infeasible.
reducing structural bias in technology mapping. technology mapping based on dag-covering suffers from the problem of structural bias: the structure of the mapped netlist depends strongly on the subject graph. in this paper we present a new mapper aimed at mitigating structural bias. it is based on a simplified cut-based boolean matching algorithm, and using the speed afforded by this simplification we explore two ideas to reduce structural bias. the first, called lossless synthesis, leverages recent advances in structure-based combinational equivalence checking to combine the different networks seen during technology independent synthesis into a single network with choices in a scalable manner. we show how cut based mapping extends naturally to handle such networks with choices. the second idea is to combine several library gates into a single gate (called a supergate) in order to make the matching process less local. we show how supergates help address the structural bias problem, and how they fit naturally into the cut-based boolean matching scheme. an implementation based on these ideas significantly outperforms state-of-the-art mappers in terms of delay, area and run-time on academic and industrial benchmarks.
a cocktail approach on random access scan toward low power and high efficiency test. scan design, providing a good test solution to sequential circuits, suffers large data volume, long test time and high test power problem. recently, the random access scan (ras) scheme offers a solution to alleviate the above problems (baik et al., 2004). in this paper, based on ras, a cocktail scan scheme is proposed and demonstrated to improve the test efficiency significantly. the scheme adopts a two-phase approach, firstly by using a cycle random scan test with a few random seed patterns to test the dut and secondly, by using the ras mechanism to test the circuit. due to employment of a revised process and several strategies, namely, test response abundant, constrained static compaction, and bit propagation before test vector dropping, it is very effective in reducing bit flipping and test data volume, consequently, the test application time and power. experimental results show that the scheme can achieve 86% reduction in test data volume and 10 times of speedup in test application time.
eliminating wire crossings for molecular quantum-dot cellular automata implementation. when exploring computing elements made from technologies other than cmos, it is imperative to investigate the effects of physical implementation constraints. this paper focuses on molecular quantum-dot cellular automata circuits. for these circuits, it is very difficult for chemists to fabricate wire crossings (at least in the near future). a novel technique is introduced to remove wire crossings in a given circuit to facilitate the self assembly of real circuits - thus providing meaningful and functional design targets for both physical and computer scientists. the technique eliminates all wire crossings with minimal logic gate/node duplications. experimental results based on existing qca circuits and other benchmarks are quite encouraging, and suggest that further investigation is needed.
approximate algorithms for time separation of events. we describe a polynomial-time approximate algorithm for computing minimum and maximum time separations between all pairs of events in systems specified by acyclic timing constraint graphs. even for acyclic graphs, the problem is np-complete. we propose finding an approximate solution by first approximating the non-convex feasible space with a suitable convex ``envelope'', and then solving the problem efficiently in the approximate convex space. unlike previous works, our algorithm can handle both min and max-type timing constraints in the same system, and has a computational complexity that is polynomial in the number of events. although the computed separations are conservative in the worst-case, experiments indicate that our results are highly accurate in practice.
validation coverage analysis for complex digital designs. in interactive behavioral synthesis, the designer can control the design process at every stage, including modifying the schedule of the design to improve its performance. in this paper, we present a methodology for performance optimization in interactive behavioral synthesis. also proposed are several quality metrics and hints that can assist the user in utilizing the proposed methodology. when the user is optimizing the performance of the design, one important decision is the selection of a clock period. to facilitate clock selection by the user, we have developed an algorithm to estimate the effect of different clock periods on the execution time of the design. we have tested our methodology on several benchmarks. the experimental results support the proposed methodology by demonstrating an average improvement of 46.2% in design performance.
an efficient, bus-layout based method for early diagnosis of bussed driver shorts in printed circuit boards. this paper presents a new, layout-based approach to board-level shorts diagnosis for bussed drivers, with the goal of early repair of interconnect shorts so as to minimize (a) fault masking during opens testing and (b) driver abuse. this approach leads to an early diagnosis of more than 96% of shorts and simplifies the subsequent rest for opens considerably. besides, this approach improves the production yield and field survivability of boards.
multilevel optimization for large-scale circuit placement. we have designed and implemented a new class of fast and highly scalable placement algorithms that directly handle complex constraints and achieve total wirelengths comparable to the state of the art. our approach exploits recent advances in (i) multilevel methods for hierarchical computation, (ii) interior-point methods for nonconvex nonlinear programming, and (iii) the fast multipole method for the order n evaluation of sums over the n (n - 1)/2 pairwise interactions of n components. significant adaptation of these methods for the placement problem is required, and we have therefore developed a set of customized discrete algorithms for clustering, declustering, slot assignment, and local refinement with which the continuous algorithms are naturally combined. preliminary test runs on benchmark circuits with up to 184,000 cells produce total wirelengths within approximately 5-10% of those of gordian-l [1] in less than one tenth the run time. such an ultra-fast placement engine is badly needed for timing convergence of the synthesis and layout phases of integrated circuit design.
characteristic faults and spectral information for logic bist. we present a new method of built-in-self-test (bist) for sequential circuits and system-on-a-chip (soc) using characteristic faults and circuitspecific spectral information in the form of one or more hadamard coefficients. the hadamard coefficients are extracted from the test sequences for a small set of characteristic faults of the circuit. by extracting a few characteristic faults from the circuit, we show that detection of these characteristic faults is sufficient in detecting a vast majority of the remaining faults in the circuit. the small number of characteristic faults allows us to reduce the coefficients necessary for bist. state relaxation is performed on the compacted test sequences to reduce the spectral noise further. since we are targeting only a very small number of characteristic faults, the execution times for computing the spectra are greatly reduced. our experimental results show that our new method can achieve high bist coverage with both lower computational efforts and storage, with very few characteristic faults.
an enhanced multilevel algorithm for circuit placement. this paper presents several important enhancements to therecently published multilevel placement package mpl.the improvements include (i) unconstrained quadratic relaxation on small, noncontiguous subproblems at every level of the hierarchy; (ii) improved interpolation (declustering)based on techniques from algebraic multigrid (amg), and(iii) iterated v-cycles with additional geometric informationfor aggregation in subsequent v-cycles. the enhanced version of mpl, named mpl2, improves the total wirelength result by about 12% compared to the original version. the attractive scalability properties of the mpl run time have beenlargely retained, and the overall run time remains very competitive. compared to gordian-l-domino on uniform-cell-size ibm/ispd98 benchmarks, a speed-up of well over8x on large circuits (¿ 100,000 cells or nets) is obtainedalong with an average improvement in total wirelength ofabout 2%. compared to dragon [32] on the same benchmarks, a speed-up of about 5x is obtained at the cost ofabout 4% increased wirelength. on the recently publishedpeko synthetic benchmarks, mpl2 generates surprisinglyhigh-quality placements - roughly 60% closer to the optimal than those produced by capo 8.5 and dragon - inrun time about twice as long as capo's and about 1/10th of dragon's.
goldengate: a fast and accurate bridging fault simulator under a hybrid logic/iddq testing environment. in this paper we describe goldengate-a bridging fault simulator for cell-based digital vlsi circuits with the following features: 1. it targets both combinational and sequential circuits. 2. it simulates general (routing, adjacency, and intra-cell) realistic bridging faults efficiently through a table-based scheme. the pre-computed table contains accurate cell output voltage and i/sub ddq/ values obtained through electrical-level simulations. 3. it simulates both feedback and nonfeedback bridging faults (bfs) efficiently through a cycling event-driven technique. 4. it allows mixed voltage and i/sub ddq/ simulation to support a fully hybrid test scheme where mixed logic and i/sub ddq/ sensings are allowed. the experimental results show that goldengate is both accurate and fast.
hierarchical partitioning for field-programmable systems. this paper presents a new recursive bipartitioning algorithm for a hierarchical field-programmable system. it draws new insights into relating the quality of the bipartitioning algorithm to circuit structures by the use of the partitioning tree (hagen et al., 1994). the final algorithm proposed not only forms the basis for the partitioning solution of a 1-million gate field programmable system (lewis et al., 1997) but can also be applied to general vlsi or multiple-fpga partitioning problems.
nocee: energy macro-model extraction methodology for network on chip routers. in this paper we present nocee, a fast and accurate method for extracting energy models for packet-switched network on chip (noc) routers. linear regression is used to model the relationship between events occurring in the noc and energy consumption. the resulting models are cycle accurate and can be applied to different technology libraries. we verify the individual router estimation models with many different synthetically generated traffic patterns and data inputs. characterization of a small library takes about two hours. the mean absolute energy estimation error of the resultant models is 5% (10% max) against a complete gate level simulation. we also apply this method to a number of complete nocs with inputs extracted from synthetic application traces and compare our estimated results to the gate level power simulations (mean absolute error is 5%). our estimation methodology has been integrated with commercial logic synthesis flow and power estimation tools (synopsys design compiler and primepower), allowing application across different designs. the extracted models show the different trends across various parameterizations of network on chip routers and have been integrated into an architecture exploration framework.
simultaneous gate sizing and fanout optimization. this paper describes an algorithm for simultaneous gate sizing and fanout optimization along the timing-critical paths in a circuit. first, a continuous-variable delay model that captures both sizing and buffering effects is presented. next, the optimization problem is formulated as a non-convex mathematical program. to manage the problem size, only a small number of critical paths are considered simultaneously. the mathematical program is solved by a non-linear programming package. finally, a design flow based on iterative selection and optimization of the k most critical paths in the circuit is proposed. experimental results show that the proposed flow reduces the circuit delay by an average of 9.2% compared to conventional flows that separate gate sizing from fanout optimization.
practical considerations in rlck crosstalk analysis for digital integrated circuits. inductance and inductive crosstalk has become an important new concern for on-chip wires in deep-submicron integrated circuits. recent advances in extractors to include inductance make possible the extraction of coupled rlck interconnect networks from large, complex on-chip layouts. in this paper, we describe the techniques we use in a commercial static noise analysis tool to analyze crosstalk noise due to fully-coupled rlck networks extracted from layout. notable are the approaches we use to filter and lump aggressor couplings, as well as the techniques used to handle degeneracies in the modified nodel analysis (mna) formulation. furthermore, the nonmonotonicity of interconnect responses in the presence of inductance require additional "sensitizations" in searching the possible switching events inducing the worst-case noise. comparisons with silicon indicate the need to include the substrate in the extracted models in certain cases.