Title :
A hybrid linear equation solver and its application in quadratic placement
Author :
Qian, Haifeng ; Sapatnekar, Sachin S.
Author_Institution :
Minnesota Univ., Minneapolis, MN, USA
Abstract :
This paper presents a new hybrid linear equation solver for quadratic placement. The new solver is a combination of stochastic solver and iterative solver: it is proven in this paper that an approximate LDL factorization can be obtained from random walks, and used as a preconditioner for conjugate gradient solver. Testing on real-life placement benchmarks shows a speedup of up to 7.1 times over traditional Incomplete Cholesky preconditioned Conjugate Gradient (ICCG).
Keywords :
VLSI; benchmark testing; conjugate gradient methods; integrated circuit design; ICCG; Incomplete Cholesky preconditioned Conjugate Gradient; LDL factorization; conjugate gradient solver; hybrid linear equation solver; iterative solver; placement benchmark testing; quadratic placement; random walks; stochastic solver; Benchmark testing; Computational modeling; Cost function; Equations; Length measurement; Simulated annealing; Stochastic processes; Vectors; Very large scale integration; Wire;
Conference_Titel :
Computer-Aided Design, 2005. ICCAD-2005. IEEE/ACM International Conference on
Print_ISBN :
0-7803-9254-X
DOI :
10.1109/ICCAD.2005.1560190
