An algorithm for Boolean matching based on binary decision diagrams using a level-first search strategy is presented. This algorithm is generally not restricted to circuits with just a few inputs and can be used for both technology mapping and logic verification. Unlike depth-first and breadth-first strategies, a level-first strategy permits significant pruning of the search space. A set of filters that further improve the performance of the matching algorithm is described. A method of analyzing the effectiveness of a filter is presented, and the various filters are ranked on the basis of their effect/cost ratio. Experimental results on a number of benchmark circuits are presented, comparing the basic matching algorithm with and without the use of various filters. It is shown how the matching algorithm and the filters can be extended to Boolean functions with don't cares.>

This paper describes a new layout style called the Flexible Transistor Matrix (FTM) for large scale CMOS module generation.FTM uses two layers of metal.Compared to Gate Matrix, FTM can generate significantly better results.In addition, the algorithm can control the aspect ratio, 1/0 pin positions and different transistor sizes.

Article A branching process model for observability analysis of combinational circuits Share on Authors: Sarma Sastry Electrical Engineering Systems Department, University of Southern California, Los Angeles, CA Electrical Engineering Systems Department, University of Southern California, Los Angeles, CAView Profile , Amitava Majumdar Electrical Engineering Systems Department, University of Southern California, Los Angeles, CA Electrical Engineering Systems Department, University of Southern California, Los Angeles, CAView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 452–457https://doi.org/10.1145/127601.127711Online:01 June 1991Publication History 4citation121DownloadsMetricsTotal Citations4Total Downloads121Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors consider topological via minimization (TVM) and topological routing (TR) of a two-point nets on two layers. They present a graph coloring technique for via minimization and also use it to derive bounds on the number of vias. The bounds are net intersection dependent. The complexity of coloring procedure is O(n/sup 2/). The coloring procedure shows an abrupt drop in complexity, when intersection density is about 20%. For TR an O(n/sup 4/) algorithm is presented which guarantees at most one via per net. Using the authors' TVM and TR procedures, constraints such as assignment of nets to a particular layer, assignment of via to a particular net, and via density control can be implemented.>

Motivated by the work of K. Kim et al. (1988) and A. Krasniewski and S. Pilarski (1989), the problem of test efficiency in random testing of sequential circuits using built-in self-test (BIST) techniques is addressed. It is shown that, given a circuit with n primary inputs and the goal of maximizing expected pattern coverage, different pattern-sampling distributions for its 2/sup n/ possible patterns can be partially ordered. The exact distributions for pattern coverage for both equiprobable and nonequiprobable pattern-sampling distributions are derived. Approximations for pattern-coverage distributions under equiprobable pattern-sampling conditions and corresponding numerical results are presented. A limiting distribution function for pattern-coverage distribution is derived. The authors also present numerical results on confidence levels for obtaining a specified pattern coverage. The distribution for the number of test cycles (R) required to achieve a specified pattern coverage is also derived. The authors derive and use the expression for the expected value of R to illustrate the increase in the effect of achieving a specified coverage j as j increases.>

The statistical properties of two combinatorial optimization problems that arise in the physical design of circuits, circuit partitioning, and floorplanning, are discussed. For the partitioning problem, the solutions generated by the Kernighan-Lin (1970) procedure and those generated by a random search are examined. It is shown that in both cases, the Type 3 (Weibull) extreme value distribution provides an excellent model for the distribution of local minima generated. The location parameter of the Weibull provides an estimate of the minimum cost. Various techniques that were used to estimate the parameters of the Weibull are discussed, and ample empirical evidence to support the hypothesis is provided. For the floorplanning problem, a number of test problems whose optimal value are known are constructed. By using a representation of slicing floorplans developed by D.F. Wong and C.L. Liu (1986), the solution space is randomly sampled and a number of local minima are generated. As with the partitioning problem, it is found that the Weibull distribution provides an excellent model for estimating the minimum cost.>

In this paper we examine some statistical properties exhibited by combinatorial optimization problems. Although the paper focuses on two particular problems that arise in chip design, namely circuit partitioning and floorplanning, the results seem valid for a much larger set of such problems. For the partitioning problem, we examine the solutions generated by the well known Kernighan-Lin procedure [5,10] and solutions generated by random search. We find that in both cases, the Type 3 (Weibull) extreme-value distribution provides an excellent model for the distribution of local minima generated. The location parameter of the Weibull provides an estimate of the minimum cost. For the floorplanning problem, we construct a number of test problems, whose optimal value is known. As with the partitioning problem, we find that the Weibull distribution provides an excellent model for estimating the minimum cost.

An analysis is presented of CMOS stuck-open faults tested with a pseudorandom test sequence, i.e. a test sequence consisting of some or all of the 2/sup N/ test patterns generated by a modified N-bit linear-feedback shift register (LFSR). Such a scheme is viewed as testing without replacement. When all 2/sup N/ test patterns are applied, then such a test sequence is called a pseudorandom exhaustive test sequence (PRETS). The alternative scheme is called random testing, which corresponds to sampling the population of test vectors with replacement. It is shown that some stuck-open faults require a single test vector of their detection, while most require an ordered pair of test vectors. A PRETS will detect all stuck-open faults that require a single test vector, but may not necessarily detect all faults that require an ordered pair of test vectors. The results obtained under pseudorandom testing are compared with results obtained under random testing.>

A stochastic model for estimating measures of placement and routing on gate arrays is presented. Three important problems are addressed: estimating the dimensions of the routing channels, estimating the routability of a channel given the number of tracks, and determining the distribution and moments of wire lengths. In the context of wiring space estimation, exact and asymptotic formulas for the dimensions of routing channels are presented. Next, an expression for the probability that a routing channel with a given number of tracks will be routable is derived, and its asymptotic properties are examined. Finally, a model that characterizes the relationship between wire length distributions and partitioning of logic is developed. The model provides a firm mathematical basis for Rent's rule from which the distribution of wire lengths can be determined. That is, Rent's rule, or in general any similar relation, contains all the information about wire lengths. Based on this, estimates for the average wire length are derived. Numerical results from both simulated and real chips are presented.