A GENERAL AND FLEXIBLE SWITCHBOX ROUTER - CARIOCA

In the building block style layout, two-dimensional routers are often necessary. A switchbox router utilizing two layers is presented in this paper. The routing technique we have implemented can roughly be described as follows. Each net is first partitioned into a set of subnets. This decomposition is driven by the minimum Steiner tree. The construction is then carried out on a step by step basis, which allows the system to dynamically take into account new information on the problem. This information is examined by a set of expert systems which decide which subnet should be routed next. This part has been implemented with a blackboard architecture. The router can handle pins that are not on a grid on one set of parallel edges. In order to always provide a solution to a given problem, the router expands the switchbox by adding rows dynamically where they are needed. This point will be justified. The program has been implemented in the Lisp programming language. Many test cases have been run successfully and some results, including Burstein’s difficult switchbox, are presented. © 1990 IEEE