Wire density driven top-down global placement for CMP variation control
2
Citation
19
Reference
10
Related Paper
Citation Trend
Abstract:
In this paper, we present a top-down global placement algorithm considering wire density uniformity for CMP variation control. The proposed algorithm is based on top-down recursive bisection framework. Wire weight balancing constraint is employed into bisection to consider wire density uniformity. A multilevel hypergraph partitioning satisfying balancing constraints on not only cell area but also wire weight is performed to acquire more uniform wire distribution. Empirical wire weight model is used to estimate wire density distribution before each bisection of a placement bin. Experimental results show that our algorithm improves ROOSTER [1] with more uniform wire distribution by 3.1% on average and limited increment of wire length by 3.0%.Keywords:
Bisection
Bisection method
Hypergraph
Bisection method
Bisection
Simplex
Cite
Citations (3)
Bisection
Bisection method
Cite
Citations (4)
Bisection
Bisection method
Cite
Citations (25)
Bisection
Bisection method
Error Analysis
Cite
Citations (19)
Bisection
Bisection method
Similarity (geometry)
Cite
Citations (1)
The bisection method is the basic method of finding a root.As iterations are conducted, the interval gets halved.So method is guaranteed to converge to a root of "f" if "f" is a continuous function at an interval [a,b] andf(a) andf(b) should have opposite sign.In this paper we have explained the role of bisection method in computer science research.we also introduced a new method which is a combination of bisection and other methods to prove that with the help of bisection method we can also develop new methods.It is observed that scientists and engineers are often faced with the task of finding out the roots of equations and the basic method is bisection method but it is comparatively slow.We can use this new method to solve these problems and to improve the speed.
Bisection method
Bisection
Root (linguistics)
Interval arithmetic
Sign function
Root-finding algorithm
Cite
Citations (13)
The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors.
Bisection
Bisection method
Asymptotically optimal algorithm
Cite
Citations (107)
We identify a class of root-searching methods that surprisingly outperform the bisection method on the average performance while retaining minmax optimality. The improvement on the average applies for any continuous distributional hypothesis. We also pinpoint one specific method within the class and show that under mild initial conditions it can attain an order of convergence of up to 1.618, i.e., the same as the secant method. Hence, we attain both an improved average performance and an improved order of convergence with no cost on the minmax optimality of the bisection method. Numerical experiments show that, on regular functions, the proposed method requires a number of function evaluations similar to current state-of-the-art methods, about 24% to 37% of the evaluations required by the bisection procedure. In problems with non-regular functions, the proposed method performs significantly better than the state-of-the-art, requiring on average 82% of the total evaluations required for the bisection method, while the other methods were outperformed by bisection. In the worst case, while current state-of-the-art commercial solvers required two to three times the number of function evaluations of bisection, our proposed method remained within the minmax bounds of the bisection method.
Bisection method
Bisection
Cite
Citations (33)