Apparatus for wire routing of VLSI

摘要

A wiring route is determined between terminals on an integrated circuit on the basis of information concerning the terminals and areas of the integrated circuit through which a wire can be routed. A mesh memory holds information of mesh points of a wiring area partitioned in a mesh-like pattern. A wavefront memory holds information concerning mesh points constituting the leads of searching point arrays. An expansion point extracting unit selects a source point from the mesh points for a succeeding search from the leading mesh points on the basis of costs. Addresses and costs for mesh points neighboring the source point are calculated. A searching point register holds information concerning the mesh points obtained through the calculation. A determination is made of whether or not the mesh points placed in the searching point register can be searched, and if so they are written to the mesh memory. Duplicate information stored in the searching point register is eliminated. It is then determined whether or not the mesh points corresponding to the terminals to be wired are contained in the searching point register. If so, the wiring route is determined and the process concluded.