Process-variation-tolerant clock skew minimization

In this paper, we propose a novel hierarchical multiple-merge zero skew clock routing algorithm. The routing results produced by our approach will have zero skew in the nominal case and minimal skew increase in the presence of worst process variations. In order to construct such a clock routing, we formulate the linear placement with maximum spread problem and provide an O(n min{n, P} log n log P) algorithm for optimally solving this problem, where n is the number of cells to be placed and P is the maximum spread. Experimental results show that our algorithm can indeed reduce the skew in various manufacturing variations effectively.