Article Free Access Share on Spectral partitioning: the more eigenvectors, the better Authors: Charles J. Alpert UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , So-Zen Yao Cadence Design Systems, San Jose, CA Cadence Design Systems, San Jose, CAView Profile Authors Info & Claims DAC '95: Proceedings of the 32nd annual ACM/IEEE Design Automation ConferenceJanuary 1995 Pages 195–200https://doi.org/10.1145/217474.217529Online:01 January 1995Publication History 84citation1,151DownloadsMetricsTotal Citations84Total Downloads1,151Last 12 Months50Last 6 weeks5 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe a new linear programming (LP)-based hierarchical pitchmatching method. With a simplified treatment of the intercell constraints, the size of the LP problems is significantly reduced as compared to the best known results. In particular, the pitchmatching problem is decomposed into independent subproblems by exploiting the layout slicing structure. Each subproblem is further "folded" to reduce the LP problem size. We prove that the new method generates smaller LP problem than the previously best known approach. Experimental data show that the LP problem size can be 10 times smaller.>

Multi-chip module (MCM) technology has become an important means to package high performance systems. An important task during the packaging process is to check for possible open, short, and high resistance faults in the wiring networks of the bare MCM substrates, which is called substrate testing. After examining several substrate testing methodologies, we find that multi-probe or k-probe testers are cost-effective for substrate testing. However, the testing speed of this method is not high; hence, we focus on improving the throughput by reducing the number of tests and by deriving good probe routes. For test size reduction, we propose a routing tree model to capture the wiring structure of a given net; then by taking advantage of the routing tree, we generate a minimum number of tests while ensuring complete open fault coverage. Our algorithm reduces the number of tests by up to 50% compared to that of previous approaches. Given a routing tree with its node degree bounded by a constant, our test generation algorithm runs in linear time with respect to the number of leaves of the tree. For probe route scheduling, we observe that in order to obtain a balanced and efficient scheduling, the routes of different probes must be considered simultaneously, which motivates our Multi-Dimensional Traveling Salesman Problem (MDTSP) formulation. Our package has been installed on existing substrate testers and has achieved encouraging results.>

We describe a new linear programming (LP)-based hierarchical pitchmatching method.Whh a simplified treatment of the intercell constraints, the size of the LP problems is significantly smaller than the best known methods.In particular, the pitchmatching problem is decomposed into independent subproblems by the natural slicing structure in layout.Each subproblem is folded further to reduce the LP problem size.Experiments show that the LP problem size can be 10 times smaller than the best known result.

The k-probe testing methodology is an effective approach to detect open and short faults in MCM substrates. An algorithm which generates the minimum number of tests for complete open fault coverage is proposed. For k equals two, the algorithm is able to reduce the test size by up to 50% compared with that generated by an ordinary approach. A multidimensional traveling salesman problem formulation is developed to optimize probe routes. The approach has been tested on substrate testers and has achieved excellent results.>

The compaction of IC layouts subjected to conditional spacing rules in multiple-level metal technology is addressed. The constraints imposed by conditional rules make the automatic compaction of layout much more difficult than when the usual minimum separation rules are applied. To solve the problem, each conditional spacing rule is formulated with a set of arcs in the constraint graph representation. It is proven that finding the optimal solution under one bridge rule is NP-complete. A graph-theory method of compaction which, by reducing the problem size, can efficiently obtain an optimal solution is proposed.>

In the layout stage of VLSI and printed circuit board (PCB) design, after all circuit modules (rectangular) are placed, it is possible to flip the modules so as to reduce the total net length. The authors formulate the orientation of modules as a graph problem and prove it to be NP-complete. The orientation problem is shown to be equivalent to finding a minimum cut of a graph with some arcs of negative capacities. In many cases, the graph can be decomposed into subgraphs to reduce the search space for optimum orientation. Experiments with real cases show that module orientation reduces the total net length and improves the routability.>