A Multiple Terminal Net Routing Algorithm using Failure Prediction
E.P. Huijbregtst, J.A.G. Jess · 2005
A new multiple terminul net muze runner is described thut is used in u generic plucement und routing system turgeted towards prefubricuted devices such us gate arrays and Seu-of-Gates gate urrays. Insteud of purtitioning un n-terminul net into several 2-terminul nets to be routed sequentially, we tuckle the routing problem by routing u1l terminals ut once. We show thut the explored routing space diminishes and thus the cpu-time is reduced by doing so. A new mechanism is introduced that partitions the routing spuce into so-culled 'unconnected regions'. The benefit of this is twofold. Firstly, it enubles us to identiD non-routable nets or non-routable purts of nets without uctuully trying to route them. Secondly, udditionul routing spuce restriction is possible. It is shown thut this failure prediction mechunism cun be implemented in uny muze runner scheme without increusing the complexity of the algorithm. Experimental results show an extru reduction of cpu-time up to 35% by using this new mechunism.