Optimal circuit clustering with variable interconnect delay

[[abstract]]The paper aims at extending the circuit clustering algorithm in [1] to handle a more sophisticated delay model, which practically takes variable interconnect delay into account. Our delay model is particularly applicable in allowing the back-annotation of actual delay information to drive the clustering process. We first show that the algorithm in [1] fails to produce optimal solution for this delay model. In order to solve the problem, a generalized algorithm based on an extension of the algorithm in [1] is proposed such that the problem can be solved optimally while the polynomial time complexity is maintained.[[fileno]]2030229030010[[department]]資訊工程學