Title :
A Clustering-Based Optimization Algorithm in Zero-Skew Routings
Author_Institution :
Department of Computer Science, Princeton University, Princeton, NJ, USA and C&C Systems Research Laboratories, NEC Corporation, Kawasaki, Japan
Abstract :
A zero-skew routing algorithm with clustering and improvement methods is proposed. This algorithm generates a zero-skew routing in O(n log n) time for n pins, and it is proven that the order of the total wire length is best possible. Our algorithm achieves 20% reduction of the total wire length on benchmark data compared with the best known algorithm.
Keywords :
Circuits; Clocks; Clustering algorithms; Computer science; Laboratories; National electric code; Nearest neighbor searches; Pins; Routing; Wire;
Conference_Titel :
Design Automation, 1993. 30th Conference on
Print_ISBN :
0-89791-577-1
DOI :
10.1109/DAC.1993.204020
