Efficient circuit partitioning is becoming more and more important as the size of modern circuits keeps increasing. Conventionally, circuit partitioning is solved without altering the circuit by modeling the circuit as a hypergraph for the ease of applying graph algorithms. However, there is room for further improvement on even optimal hypergraph partitioning results, if logic information can be applied for circuit perturbation. Such logic transformation based partitioning techniques are relatively less addressed. In this paper, we present a powerful multiway partitioning technique which applies efficient logic rewiring techniques for further improvement over already superior hypergraph partitioning results. The approach can integrate with any graph partitioner. We perform experiments on two-, three-, and four-way partitionings for MCNC benchmark circuits whose physical and logical information are both available. Our experimental results show that this partitioning approach is very powerful. For example, it can achieve a further 12.3% reduction in cut size upon already excellent pure graph partitioner (hMetis) results on two-way partitioning with an area penalty of only 0.34%. The outperforming results demonstrate the usefulness of this new partitioning technique.

Efficient circuit partitioning is gaining more importance with the increasing size of modern circuits. Conventionally, circuit partitioning is solved by modeling a circuit as a hypergraph for the ease of applying graph algorithms. However there exists room for further improvement on even optimum hypergraph partitioning results, if logic information can be applied for perturbation. In this paper we present a multi-way partitioning framework which can couple any excellent hypergraph partitioner and a noval logic perturbation based technique (GBAW) for further improvement over very excellent partitioning results. Our approach can integrate with any graph partitioner. We performed experiments on 2-, 3-, 4-, and 5-way partitionings for various circuits of different sizes from MCNC benchmarks. We have chosen the state-of-the-art hMetis-Kway to obtain high quality initial solutions for the experiments. Our experiments showed that this partitioning approach can achieve a further 15% reduction in cut size for 2-way partitioning with an area penalty of only 0.33%. The good results demonstrated the effectiveness of this new partitioning technique.

Article Free Access Share on Circuit partitioning with coupled logic restructuring techniques Authors: Yu-Liang Wu Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong Kong Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong KongView Profile , Xiao-Long Yuan Dept. Computer Sci. & Eng., The Northwest Polytechnical University, Xi'an, 710072, China Dept. Computer Sci. & Eng., The Northwest Polytechnical University, Xi'an, 710072, ChinaView Profile , David Ihsin Cheng Ultima Interconnect Technology, Sunnyvale, CA Ultima Interconnect Technology, Sunnyvale, CAView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 655–660https://doi.org/10.1145/368434.368862Online:28 January 2000Publication History 4citation102DownloadsMetricsTotal Citations4Total Downloads102Last 12 Months0Last 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 SiteeReaderPDF

Boolean division, and hence Boolean substitution, produces better result than algebraic division and substitution. However, due to the lack of an efficient Boolean division algorithm, Boolean substitution has rarely been used. We present an efficient Boolean division and Boolean substitution algorithm. Our technique is based on the philosophy of redundancy addition and removal. By adding multiple wires/gates in a specialized way, we tailor the philosophy onto the Boolean division and substitution problem. From the viewpoint of traditional division/substitution, our algorithm can perform substitution not only in sum-of-product form but also in product-of-sum form. Our algorithm can also naturally take all types of internal don't cares into consideration. As far as substitution is concerned, we also discuss the case where we are allowed to decompose not only the dividend but also the divisor. Experiments are presented and the result is promising.

Bo ole andivision, and henc eBo ole ansubstitution, produc es better result than algebraic division and substitution. However, due to the lack of an efficient Bo ole andivision algorithm, Bo ole ansubstitution has rarely b een used. We present an efficient Bo ole andivision and substitution algorithm. Our technique is based on the philosophy of redundancy addition and removal. By adding multiple wires/gates in a specialized way, we tailor the philosophy onto the Bo ole an division and substitution problem. F rom the viewpoint of traditional division/substitution, our algorithm can perform substitution not only in sum-of-product form for but also in product-of-sum form. Our algorithm can also naturally take all typ es of don't cares into consideration. As far as substitution is conc erne d, we also discuss the case where we are allowed to decompose not only the dividend but also the divisor. Experiments are presente d and the result is pr omising.

Redundancy removal is an important step in combinational logic optimization. After a redundant wire is removed, other originally redundant wires may become irredundant, and some originally irredundant wires may become redundant. When multiple redundancies exist in a circuit, this creates a problem where we need to decide which redundancy to remove first. In this paper, we present an analysis and a very efficient heuristic to deal with multiple redundancies. We associate with each redundant wire a Boolean function that describes how the wire can remain redundant after removing other wires. When multiple redundancies exist, this set of Boolean functions characterizes the global relationship among redundancies.

In this paper, we propose a hybrid approach for estimating the switching activities of the internal nodes in logic circuits. The new approach combines the advantages of the simulation-based techniques and the probability-based techniques. We use the user-specified control sequence for simulation, and treat the weakly correlated data inputs using the probabilistic model. The new approach, on one hand, is more accurate than the probabilistic approaches because the strong temporal and spatial correlations among control inputs are well taken into consideration. On the other hand, the new approach is much more efficient than the simulation-based approaches because the weakly correlated data inputs are not explicitly simulated. We also discuss the situation where BDD's are built in terms of internal nodes so that large circuits can he handled. Extensive experimental results are presented to show the effectiveness and efficiency of our algorithms.

This paper addresses the problem of locating error sources in an erroneous combinational circuit. We use a fault simulation-based technique to approximate each signal's correcting power. The correcting power of a particular signal is measured in terms of the signal's correctable set, namely, the maximum set of erroneous input vectors that can be corrected by re-synthesizing the signal. Only the signals that can correct every erroneous input vector are considered as a potential error source. Our algorithm offers three major advantages over existing methods. First, unlike symbolic approaches, it is applicable for large circuits. Secondly, it delivers more accurate results than other simulation-based approaches because it is based on a more stringent condition for identifying potential error sources. Thirdly, it can be easily generalized to identify multiple errors. Experimental results on diagnosing circuits with one and two random errors are presented to show the effectiveness and efficiency of this new approach.

In this paper, we propose a hybrid approach for estimating the switching activities of the internal nodes in logic circuits.The new approach combines the advantages of the simulation-based t e chniques and the probability-based t e chniques.We use the user-speci ed control sequence for simulation and treat the weakly correlated data inputs using the probabilistic model.The new approach, on one hand, is more a c curate than the probabilistic approaches because the strong temporal and spatial correlations among control inputs are well taken into consideration.On the other hand, the new approach is much more ecient than the simulation-based approaches because the weakly correlated data inputs are not explicitly simulated.In addition, we also propose a heuristic that builds BDDs in terms of internal nodes such that large circuits can be handled.Extensive experimental results are p r esented to show the eectiveness and eciency of our algorithms.

No abstract available.

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 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.

This paper describes a diagnosis technique for locating design errors in circuit implementations which do not match their functional speci cation.The method eciently propagates mismatched p atterns from erroneous outputs backward into the network and calculates circuit regions which most likely contain the error(s).In contrast to previous approaches, the described t e chnique does not depend on a xed set of error models.Therefore, it is more general and especially suitable for transistor-level circuits, which have a broader variety of possible design errors than gate-level implementations.Furthermore, the proposed method is also applicable for incomplete sets of mismatched p atterns and hence c an be used not only as a debugging aid for formal veri cation techniques but also for simulationbased approaches.Experiments with industrial CMOS circuits show that for most design errors the identi ed problem region is less than 3% of the overall circuit.