The signal synchronization problem in VLSI design

Abstract

In VLSI design it is necessary sometimes to span a sinks by minimum-cost layout tree, where all paths from the source node to the destinations have the same delays. The kind of tree construction can be effectively used for glitch-minimum interconnection networks and also skew-minimum clock networks. We consider the problem when the source node (root) is located in the origin of the plane, and all sinks are arbitrary placed on the unit length cell grid in the routing plane. For the case where there is no feasible solution of the problem, it is allowed to move destinations at most two units aside. The opportunity of the sinks replacement makes this problem extremely complicated. In the case, when it is forbidden to move the sinks this problem is NP-hard. We present some necessary conditions of the tree existence, the rules how to move the destinations, which does not satisfy the necessary conditions, and a novel polynomial algorithm to construct an approximation solution.