IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN, TO APPEAR. 1 Optimal Path Routing in Single and Multiple Clock Domain Systems

) Abstract — Shrinking process geometries and the increasing use of IP components in SoC designs give rise to new problems in routing and buffer insertion. A particular concern is that cross-chip routing will require multiple clock cycles. Another is the integration of independently clocked components. This paper explores simultaneous routing and buffer insertion in the context of single and multiple clock domains. We present two optimal and efficient polynomial algorithms that build upon the dynamic programming Fast Path framework proposed in [17]. The first algorithm solves the problem of finding the minimum latency path for a single clock-domain system. The second considers routing between two components that are locally synchronous yet globally asynchronous to each other. Both algorithms can be used to estimate communication overhead for interconnect and resource planning. Experimental results verify the correctness and practicality of our approach. I