Due to the rapid development of manufacturing process technology and tight marketing schedules, chip design and manufacturing always work towards an integrated solution to achieve an enhanced product ...for fast time-to-market and higher niche profit. For high-end "high-volume" products, one good option for further improving chip performance is to add extra metal layers based on an existing design after all easy circuit fixes and process tricks have been applied. This strategy has been applied by the main integrated device manufacturers. In contrast to most low volume ASIC, the additional metal layer cost is low due to cost averaging over huge volumes. We address the NLM (new layer migration) problem which eliminates coupling capacitance violations for speed push in a given routing solution by migrating some wire segments to a metal layer newly inserted under the commonly used metal filling post process for manufacturability and coupling control. We first propose an exact linear-time algorithm to judge whether a feasible solution exists or not. Then we present a provably optimal algorithm to eliminate as many coupling violations as possible. At the same time, the total coupling capacitance on both metal layers is minimized. For n wire segments, the time complexity of the algorithm is O(n/sup 3/2/log(n)). Finally, an LP approach is presented as post processing to adjust segment positions when the two layers have layer-dependent design spacing rules.
We define some new matroids on the edge set of a graph. We show that minimal disconnecting edge sets and minimal edge sets which cover all the odd cycles are cocircuits of a binary matroid. We give a ...polynomial algorithm for finding a minimum weight circuit in our matroids. A necessary and sufficient condition for an edge set to be the minimum weight odd cycle cover is derived in terms of the family of cut sets of the graph.
This is a survey of a recent methodology to solve systems of polynomial equations and inequalities for problems arising in combinatorial optimization. The techniques we discuss use the algebra of ...multivariate polynomials with coefficients over a field to create large-scale linear algebra or semidefinite programming relaxations of many kinds of feasibility or optimization questions.
Mincut partitioning aims to minimize the total cuts of edges by partitioning nodes into two sets. Two-way mincut partitioning is NP-complete. Previous methods only use node information and can only ...yield heuristic solutions. The paper proposes energy level diagram model and indicate that the minimum cut plane characteristics significantly affect the circuit partitioning problems. Under a similar cut plane position, if a circuit has fewer cuts on the plane, and means the higher flows pass the edge, we have higher probability to hit the mincut. If the "normal vector" of the minimum cut plane is identical with the front-end to back-end direction, we also have higher probability to hit the mincut. And the work also finds that regarding the sequential circuit or other time-sensitive circuits as an indivisible element, recording the level is even or odd, and recording the level number of every node or edge, is useful for modern circuit partitioning.
In this paper, we find the relationship between mincut circuit partitioning and the initial (V, E) pairs distributed condition/entropy on the V-E plain. If a circuit has higher initial ...potential/entropy, under a nearly max-cut reservation, we have a higher probability to aim the mincut. The proposed new method is called Interleaved Cutting-Edge-Node Interleaved Sort for Leaching and Envelop (IC-ENISLE) algorithm. It not only uses node and edge information, but also uses the max-min dual property. This new method is simple, but works effectively. Hundreds of netlist experiments have ever been processed. It shows that we can soon get an intuitive heuristic nearly optimal solution for the mincut and the ratio mincut partitioning at the same time. Also the method can display every process step by data compression techniques, is very suitable for IC CAD industrial usage.
PDF
