waashk/dblp huggingface dataset:
test and diagnosis of fault logic blocks in fpgas. since field programmable gate arrays (fpgas) are reprogrammable, faults in them can be easily tolerated once fault sites are located. in this paper we present a method for the testing and diagnosis of faults in fpgas. the proposed method imposes no hardware overhead, and requires minimal support from external test equipments. test time depends only on the number of faults, and is independent of the chip size. with the help of this technique, chips with faults can still be used. as a result, the chip yield can be improved and chip cost is reduced. experimental results are given to show the feasibility of this method.
communication synthesis for distributed embedded systems. abstract: communication synthesis is an essential step in hardware-software co-synthesis: many embedded systems use custom communication topologies and the communication links are often a significant part of the system cost. this paper describes new techniques for the analysis and synthesis of the communication requirements of embedded systems during co-synthesis. our analysis algorithm derives delay bounds on communication in the system given an allocation of messages to links. this analysis algorithm is used by our synthesis algorithm to choose the required communication links in the system and assign interprocess communication to the links. experimental results show that our algorithm finds good communication architectures in small amounts of cpu time.
a wide frequency range surface integral formulation for 3-d rlc extraction. a new surface integral formulation and discretization approach for computing electromagnetoquasistatic impedance of general conductors is described. the key advantages of the formulation is that it avoids volume discretization of the conductors and the substrate, and a single discretization is accurate over the entire frequency range. computational results from an on-chip inductor, a connector and a transmission line are used to show that the formulation is accurate and is &ldquo;acceleration&rdquo; ready. that is, the results demonstrate that an efficiently computed preconditioner insures rapid iterative method convergence and tests with projection show the required kernels can be approximated easily using a coarse grid.
solution of parallel language equations for logic synthesis. the problem of designing a component that combined with a known part of a system, conforms to a given overall specification arises in several applications ranging from logic synthesis to the design of discrete controllers. we cast the problem as solving abstract equations over languages. language equations can be defined with respect to several language composition operators such as synchronous composition, &bull;, and parallel composition, &diams;; conformity can be checked by language containment. in this paper we address parallel language equations.parallel composition arises in the context of modeling delay-insensitive processes and their environments. the parallel composition operator models an exchange protocol by which an input is followed by an output after a finite exchange of internal signals. it abstracts a system with two components with a single message in transit, such that at each instance either the components exchange messages or one of them communicates with its environment, which submits the next external input to the system only after the system has produced an external output in response to the previous input.we study the most general solutions of the language equation a &diams; x &sube; c, and define the language operators needed to express them. then we specialize such equations to languages associated with important classes of automata used for modeling systems, e.g., regular languages and fsm languages. in particular, for a &diams; x &sube; c, we give algorithms for computing: the largest fsm language solution, the largest complete solution, and the largest solution whose composition with a yields a complete fsm language. we solve also fsm equations under bounded parallel composition.in this paper, we give concrete algorithms for computing such solutions, and state and prove their correctness.
multi-level logic optimization for low power using local logic transformations. in this paper we present an efficient technique to reduce the switching activity in a cmos combinational logic network based on local logic transformations. these transformations consist of adding redundant connections or gates so as to reduce the switching activity. simple and efficient procedures, based on logic implication, for identifying the sources and targets of the redundant connections are presented. additionally, procedures that permit the designer to tradeoff power and delay after the transformations are described. results of experiments on the mcnc benchmark circuits are given. the results indicate that significant reduction of the switching activities of a cmos combinational circuit can be achieved with a very low area overhead and low computational cost.
passive synthesis of compact frequency-dependent interconnect models via quadrature spectral rules. in this paper, we present a reduced order modeling methodology,based on the utilization of optimal non-uniform grids generatedby gaussian spectral rules, for the direct passive synthesis ofspice-compatible modeling of multi-conductor interconnectstructures. the algorithm is based on a padé-chebyshevapproximation of the frequency-dependent input impedancematrix of the passive interconnect system. the synthesized circuitis represented as the concatenation of a number of non-uniformsections of passive lumped coupled circuits. however, contrary tothe popular uniform segmentation-based distributed circuitmodels for interconnects, where 10 to 15 segments per minimumwavelength are needed for multi-ghz accuracy, the proposedmodel is "optimal" in the sense that highly-accurate responses canbe obtained with a number of segments per minimum wavelengthbarely exceeding the nyquist limit of 2. this high accuracy stemsfrom the super-exponential convergence of the padé-chebyshevapproximation of the input impedance of the transmission-linemodel of the interconnect, and results in the synthesis of mnastamps for the interconnect structure with five to ten timesreduction in the number of state variables compared to uniformgrids. moreover, the passivity of the generated spice-compatiblemulti-port models is guaranteed through the use ofpassive equivalent circuits for the representation of the frequency-dependent,per-unit-length series impedance and shunt admittancematrices of the interconnect.
an algorithm for power estimation in switched-capacitor circuits. a number of low-power designs, such as those for mobile communication equipment, contain switched-capacitor circuits. in such designs it is important to be able to estimate the power dissipated by the switched-capacitor portion of the circuit. this paper describes an algorithm for the computation of statistical information about the power dissipated in a switched-capacitor circuit when corresponding statistical information about the inputs to the circuit is known. ordinary circuit simulators are not suited for this task, because they can only compute the power dissipated by the circuit for one specific set of input signals. the algorithm does not require monte-carlo analyses, and it accounts for correlation among the inputs. to demonstrate the algorithm's performance, numerical results obtained on a number of sample switched-capacitor circuits are reported.
dragon2000: standard-cell placement tool for large industry circuits. in this paper, we develop a new standard cell placement tool, dragon2000, to solve large scale placement problem effectively. a top-down hierarchical approach is used in dragon2000. state-of-the-art partitioning tools are tightly integrated with wirelength minimization techniques to achieve superior performance. we argue that net-cut minimization is a good and important shortcut to solve the large scale placement problem. experimental results show that minimizing net-cut is more important than greedily obtain a wirelength optimal placement at intermediate hierarchical levels. we run dragon2000 on recently released large benchmark suite ispd98 as well as mcnc circuits. for circuits which have more than 100k cells, comparing to itools1.4.0, dragon2000 can produce slightly better placement results (1.4%) while spending much less amount of time (2&times; speedup). this is also the first published placement result on the publicly available large industrial circuits.
the maximum set of permissible behaviors for fsm networks. for systems of interacting finite state machines (fsm''s), manual designs sometimes use information derived from the other components to optimize one of them. an associated problem is to find the set of permissible sequential functionalities that can be implemented at a component while preserving the behavior of the total system. most conventional approaches attempt to find such a set using th notion of don''t care sequences, but in general, the complete set of permissible finite state machines are difficult to compute. as a result, only small subsets are derived and used in designing interacting components. however, there is no knowledge of how much optimality is lost using these subsets. this paper proposes a method for computing and representing the complete set of permissible finite state machines. we show that the complete set can be computed and represented by a single non-deterministic finite state machine, called the e-machine. the computation is different from any based on don''t care sequences. the transition relation of the e-machine is obtained by a fixed point computation. the procedure has been implemented and initial experimental results are given.
vlsi timing simulation with selective dynamic regionization. accurate timing simulations are crucial to the design of mos vlsi circuits, but can take prohibitively large amounts of time. this paper describes dynamic regionization techniques applied to an event based simulator for mos timing simulation that have proven to be more efficient and as accurate as the static reorganization method. the mos network is first statically partitioned into groups of strongly coupled nodes called regions. big regions are then incrementally and dynamically partitioned into and replaced by subregions. subregions are treated just like normal regions in the event based simulation process. this simulator has been used to verify the timing and functionality of several large vlsi chips. performance is 3 to 7 times faster than a static regionalization method.
single-layer fanout routing and routability analysis for ball grid arrays. fanout routing for ball grid array(bga) packages becomes non-trivial when the i/o pin count increases. with large number of i/os, the number of i/os we can put on a package is not always limited by the available area but sometimes by the ability to fan them out on the next level of interconnect---the pcb or mcm substrate. this paper is the first to consider this problem and offers an efficient algorithm (evenfanout) to solve it. evenfanout generates the optimal uniform distribution of wires. another important contribution is that we analyzed the relationship between pin pitch and the routability of fanout so that the package designer can choose an optimal pitch for maximum routability. knowing this relationship, we know whether a fanout routing is routable or not before it is routed. this is implemented in the package early analysis and routing tool (peart) for rapid development of ball grid array packages.
an adaptive two-level management for the flash translation layer in embedded systems. while the capacity of flash-memory storage systems keeps increasing significantly, effective and efficient management of flash-memory space has become a critical design issue! different granularities in space management impose different management costs and mapping efficiency. in this paper, we explore an address translation mechanism that can dynamically and adaptively switch between two granularities in the mapping of logical block addresses into physical block addresses in flash memory management. the objective is to provide good performance in address mapping and space utilization and, at the same time, to have the memory space requirements, and the garbage collection overhead under proper management. the experimental results show that the proposed adaptive mechanism could provide significant performance improvement over the well-known coarsegrained management mechanism nftl (nand flash translation layer) over realistic workloads.
interchangeable pin routing with application to package layout. many practical routing problems such as bga, pga, pin redistribution and test fixture routing involve routing with interchangeable pins. these routing problems, especially package layout, is becoming more difficult to do manually due to increasing speed and i/o. currently, no commercial or university router is available for this task. in this paper, we unify these different problems as instances of interchangeable pin routing (ipr) problem. we show that this problem is np-complete. we formulate the problem as flows in a routing network on a triangulation instead of grids and developed a min-cost max-flow heuristic considering only the most important cuts in the design. the heuristic is extended to multiple layers and handles prerouted nets. it can accommodate all-angle, octilinear or rectilinear metric. experiments showed that the heuristic is very effective on most practical examples. it successfully routed an industry design with 4000 interchangeable pins without manual intervention.
on per-test fault diagnosis using the x-fault model. this work proposes a new per-test fault diagnosis method based on the x-fault model. the x-fault model represents all possible behaviors of a physical defect or defects in a gate and/or on its fanout branches by using different x symbols on the fanout branches. a novel technique is proposed for analyzing the relation between observed and simulated responses to extract diagnostic information and to score the results of diagnosis. experimental results show the effectiveness of our method.
approximate symbolic analysis of large analog integrated circuits. this paper describes a unified approach to the approximate symbolic analysis of large linearized analog circuits. it combines two new approximation-during-computation strategies with a variation of the classical two-graph tree enumeration method. the first strategy is to generate common trees of the two-graphs, and therefore the product terms in the symbolic network function, in the decreasing order of magnitude. the second approximation strategy is the sensitivity-based simplification of two-graphs, which excludes from the two-graphs many circuit elements that have little effect on the network function being derived. our approach is therefore able to symbolically analyze much larger analog integrated circuits than previously reported, using complete small signal models for the semiconductor devices. we show accurate yet reasonably sized symbolic network functions for integrated circuits with up to 39 transistors whereas previous approaches were limited to less than 15.
area optimization of multi-functional processing units. functions executed by a multifunctional processing unit (pu) correspond to clusters of operations in the specification, which are represented as signal flow graphs (sfgs). because of high-throughput demands, the operations of each sfg are executed in parallel. since operations for only one of the sfgs are executed at a given time, operations belonging to different sfgs can be executed on the same operator. here, the most important part of the mapping of several sfgs onto one pu, which is the assignment of the sfgs operations to the pu's operators, given a number of allocated operators, is considered. the problem is to find an operator assignment that minimizes the silicon area that is occupied by the pu's interconnection consisting of multiplexers and wires. an approach based on local search algorithms such as iterative improvement and simulated annealing is presented. although these algorithms are known to be generally applicable, it is shown that detailed knowledge of the operator assignment problem is required to obtain good results within acceptable cpu time limits for large problem instances
simplifying boolean constraint solving for random simulation-vector generation. we present an algorithm for simplifying the solution of conjunctive boolean constraints of state and input variables, in the context of constrained random vector generation using bdds. the basis of our approach is extraction of "hold-constraints" from constraint system. hold-constraints are deterministic and trivially resolvable; in addition, they can be used to simplify the original constraints as well as refine the conjunctive partition. experiments demonstrate significant reduction in the time and space needed for constructing the conjunction bdds, and the time spent in vector generation during simulation.
a framework for constrained functional verification. we describe a framework for constrained simulation-vector generationin an industry setting. the framework consists of two keycomponents: the constraint compiler and the vector generator. theconstraint compiler employs various techniques, including prioritization,partitioning, extraction, and decomposition, to minimize theinternal representation of the constraints, and thus the complexityof constraint solving. the vector generator then uses the compileddata together with input biasing to generate random simulation vectors.constraints and input biases are treated in a unified manner inthe vector generator. although there are many alternative ways ofgenerating vectors from constraints, the framework uniquely suits apractical constrained verification environment because of its abilityto handle complicated constraints and its seamless treatment of constraintsand biases. we illustrate the effectiveness of the frameworkwith real examples from commercial designs.
modeling design constraints and biasing in simulation using bdds. constraining and input biasing are frequently used techniques in functional verification methodologies based on randomized simulation generation. constraints confine the simulation to a legal input space, while input biasing, which can be considered as a probabilistic constraint, makes it easier to cover interesting &ldquo;corner&rdquo; cases. in this paper, we propose to use constraints and biasing to form a simulation environment instead of using an explicit testbench in hierarchical functional verification. both constraints and input biasing can depend on the state of the design and thus are very expressive in modeling the environment. we present a novel method that unifies the handling of constraints and biasing via the use of binary decision diagrams (bdds). the distribution of input vectors under the effect of constraints and input biasing are determined by what we refer to as the constrained probabilities. a bdd representing the constraints is first built, then an algorithm is applied to bias the branching probabilities in the bdd. during simulation, this annotated bdd is used to generate input vectors whose distribution match their predetermined constrained probabilities. the simulation generation is a one-pass process, i.e., no backtracking or retry is needed. also, we describe a partitioning method to minimize the size of bdds used in simulation generation. our techniques were used in the verification of a set of commercial designs; experimental results demonstrated their effectiveness.
temporal floorplanning using the t-tree formulation. improving logic capacity by time-sharing, dynamically reconfigurable fpgas are employed to handle designs of high complexity and functionality. we model each task as a 3d-box and deal with the temporal floorplanning/placement problem for dynamically reconfigurable fpga architectures. we present a tree-based data structure, called t-trees, to represent the spatial and temporal relations among tasks. each node in a t-tree has at most three children which represent the dimensional relationship among tasks. for the t-tree, we develop an efficient packing method and derive the condition to ensure the satisfaction of precedence constraints which model the temporal ordering among tasks induced by the execution of dynamically reconfigurable fpgas. experimental results show that our tree-based formulation can achieve significantly better solution quality with less execution time than the most recent state-of-the-art work.
automatic synthesis of 3d asynchronous state machines. an automatic synthesis tool (3d) for designing asynchronous controllers from burst-mode specifications, a class of specifications allowing multiple input change fundamental mode operation, is described. an algorithm for constructing a three-dimensional next-state table, a heuristic for encoding states, and a procedure for generating necessary constraints for exact logic minimization are presented. the effectiveness of the 3d implementation and the synthesis procedure on numerous designs including a large realistic example (asynchronous data transfer protocol of the scsi bus controller) is demonstrated. the latency (input to output delay) and the cycle time (time required for the circuit to stabilize after the excitation) for all benchmark designs using a 0.8-&mu;m cmos standard cell library are estimated
an enhanced flow model for constraint handling in hierarchical multi-view design environments. in this paper we present an enhanced design flow model that increases the capabilities of a cad framework to support design activities on hierarchical multi-view design descriptions. this flow model offers new constructs for the configuration of complex design constraints in terms of conditions on the hierarchical multi-view structure of a design. the design flow management system enforces these constraints and uses them to inform the designer more effectively about the validity of verification results and the executability of tools. this helps to make the design process less error prone and to improve productivity. our solution is original in that we introduce the notions of design hierarchy and equivalence in a design flow model. we thereby bridge a gap between the areas of data management and design flow management. strong points of our solution are its simplicity and the seamless integration with existing flow management concepts.
fast balanced stochastic truncation via a quadratic extension of the alternating direction implicit iteration. balanced truncation (bt) model order reduction (mor) is known for its superior accuracy and computable error bounds. balanced stochastic truncation (bst) is a particular bt procedure that provides a general, structure-independent mor framework to preserve both passivity and stability of original models. its application toward large scale systems, however, has been limited by the complexity of solving large size continuous time algebraic riccati equations (cares). this paper introduces a novel quadratic extension of the alternating direction implicit (adi) iteration, called qadi, that efficiently solves a care. a cholesky factor variant of qadi, called cfqadi, further exploits low rank matrices and and produces solution in factor form that greatly accelerates bst. remarkable efficiency of the proposed bst/(cf)qadi integration is demonstrated with numerical examples.