Touch and cross router

Abstract

A novel general routing algorithm is presented. Each net is routed to minimize the cost function defined by a weighted sum of penalties. Two types of design rule violations, touches and crosses, are factors of the cost function. Using these violations enables the algorithm to achieve 100% completion even when routing problems have nets which must be considered simultaneously. This type of problem could not be routed completely by conventional rip-up routers. The algorithm was implemented on a newly developed massively parallel computer. Experimental results on Burstein's difficult switch box problem and several small printed circuit boards show that the algorithm is as powerful as a human expert designer. >