GENERALIZED TOUCH AND CROSS ROUTER

This paper presents two of Fujitsu's general routing algorithms, the T ouch and Cross router and the Generalized Routing Processor (GRP). Tou ch and Cross is a cost-based iterative algorithm. This algorithm route s each net in a way that minimizes the cost function, which is defined by a weighted sum of penalties. Two types of design rule violations, touches and crosses, are counted in the cost function. Routing is done by minimizing the total cost values, thereby minimizing the number of touches and crosses. Unlike conventional routers, the Touch and Cross algorithm is powerful enough to complete a routing even when the rout ing problem has nets which must be considered simultaneously. The algo rithm is implemented on a massively parallel computer called the Routi ng Processor (RP) and is in practical use at Fujitsu. The GRP is based on the Touch and Cross algorithm. It is being developed on engineerin g workstations (EWSs) and general-purpose parallel computers.