摘要: We present an optimal NC algorithm for 2-layer channel routing of VLSI designs. Our achieves density and runs in O(logn) time using O(n) processors on EREW P-RAM. The is a parallel version the widely used Left-Edge Algorithm. It can be to solve maximum clique minimum coloring problem interval graphs independent set co-interval with processor-time bounds. give optimizing extension our that resolves column conflicts under certain weak conditions polylog time. easily implemented multi-processor shared-memory machine so solution has considerable practical value.
springer.com
sci-hub.st 参考文章(27)
Dennis V. Heinbuch, CMOS3 cell library Addison-Wesley Pub. Co.. ,(1988)
Richard M Karp, None, A Survey of Parallel Algorithms for Shared-Memory Machines University of California at Berkeley. ,(1988)
A. S. LaPaugh, ALGORITHMS FOR INTEGRATED CIRCUIT LAYOUT: AN ANALYTIC APPROACH Massachusetts Institute of Technology. ,(1980)
Richard Cole, Parallel merge sort SIAM Journal on Computing. ,vol. 17, pp. 770- 785 ,(1988) , 10.1137/0217049
T. Yoshimura, E.S. Kuh, Efficient Algorithms for Channel Routing IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 1, pp. 25- 35 ,(1982) , 10.1109/TCAD.1982.1269993
M. Sarrafzadeh, Channel-Routing Problem in the Knock-Knee Mode Is NP-Complete IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 6, pp. 503- 506 ,(1987) , 10.1109/TCAD.1987.1270298
T.G. Szymanski, Dogleg Channel Routing is NP-Complete IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 4, pp. 31- 41 ,(1985) , 10.1109/TCAD.1985.1270096
Danny Dolev, Kevin Karplus, Alan Siegel, Alex Strong, Jeffrey D. Ullman, Optimal wiring between rectangles Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 312- 317 ,(1981) , 10.1145/800076.802484
David P. Dobkin, Richard J. Lipton, On the complexity of computations under varying sets of primitives Journal of Computer and System Sciences. ,vol. 18, pp. 86- 91 ,(1979) , 10.1016/0022-0000(79)90054-0
Michael Ben-Or, Lower bounds for algebraic computation trees symposium on the theory of computing. pp. 80- 86 ,(1983) , 10.1145/800061.808735