Optimal algorithm for minimizing the number of twists in an on-chip bus

Complementary bus architecture is used to achieve higher speed and lower power in VLSI chips. However, in deep submicron circuit design, the effects of crosstalk become more and more serious, especially in the bus structure where wires are placed close to each other. Complementary bus architecture with twisted wires can reduce the coupling noise. But in current chip design flow, engineering change order (ECO) happens commonly to meet improvement requirement. Layout changes due to ECO introduce obstacles to the twists, which could reduce the number of twists and increase the coupling noise. In this paper, an ECO algorithm for generating twisted complementary architecture is proposed based on the shortest path algorithm. Our algorithm guarantees to give the minimum number of twists along the bus wires under noise constraints. Experimental results show that the twist patterns generated by our algorithm can effectively reduce the capacitive coupling noises.