On VLSI interconnect optimization and linear ordering problem

On VLSI interconnect optimization and linear ordering problem

0.00 Avg rating0 Votes
Article ID: iaor201110220
Volume: 12
Issue: 4
Start Page Number: 603
End Page Number: 609
Publication Date: Dec 2011
Journal: Optimization and Engineering
Authors: , ,
Keywords: engineering
Abstract:

Some well‐known VLSI interconnect optimizations problems for timing, power and cross‐coupling noise immunity share a property that enables mapping them into a specialized Linear Ordering Problem (LOP). Unlike the general LOP problem which is NP‐complete, this paper proves that the specialized one has a closed‐form solution. Let f(x,y):ℝ2→ℝ be symmetric, non‐negative, defined for x≥0 and y≥0, and let f(x,y) be twice differentiable, satisfying 2 f(x,y)/∂x∂y<0. Let π be a permutation of {1,…,n}. The specialized LOP comprises n objects, each associated with a real value parameter r i , 1≤in, and a cost f(r i ,r j ) associated to any two objects if |π(i)−π(j)|=1,1≤i,jn, and f(r i ,r j )=0 otherwise. We show that the permutation π which minimizes Σ i = 1 n 1 f ( r π 1 ( i ) , r π 1 ( i + 1 ) ) equ1 , called ‘symmetric hill’, is determined upfront by the relations between the parameter values r i .

Reviews

Required fields are marked *. Your email address will not be published.