Source: {"pile_set_name": "USPTO Backgrounds"}

1. Field of the Invention
The present invention relates to an automatic trace determination method for determining a trace route on a substrate, that does not intersect with other traces on the substrate, automatically and by computer computation.
2. Description of the Related Art
For example, in semiconductor integrated circuits such as an LSI, on a PCB and the like, as a typical example of an automatic wiring method for automatically providing traces without intersecting with obstacles existing on a substrate, a method called a labyrinth search method is described, for example, in Japanese Unexamined Patent Publication No. 11-161694, Japanese Unexamined Patent Publication No. 2001-350813, Japanese Unexamined Patent Publication No. 2001-044288, and Japanese Unexamined Patent Publication No. 10-209288.
In the labyrinth search method, trace routes on a substrate are set so as to secure clearance from obstacles and so as not to intersect with the obstacles by bypassing such obstacles by changing direction by 90 degrees or, in some cases, by 45 degrees. Such a setting technique can be implemented, in particular, in an LSI, a PCB and the like, which have peculiar pattern characteristics in that the disposed positions and shapes of the obstacles in the LSI, the PCB and the like have a certain regularity.
On substrates of semiconductor packages such as PBGA, EBGA and the like, there exist a large number of elements, such as planes, gates, marks, internal components or other traces in the packages, that may obstruct the traces and shapes and the disposed positions or angles of such obstacles may vary significantly. Further, vias, balls, bonding pads (B/P), flip chip pads (F/C) or the like, which are to be starting or end points of the traces, may be positioned variously. Therefore, in trace design for the semiconductor packages, when the obstacles on the substrate are bypassed, the trace routes have to bypass the obstacles by changing direction by arbitrary angles which are not limited to 90 or 45 degrees. Thus, the labyrinth search method that has been conventionally used for automatic wiring in an LSI, a PCB and the like cannot be applied to the semiconductor packages.
In view of these circumstances, in trace design for the semiconductor packages, a designer typically designs the trace routes of the semiconductor packages on a virtual plane by trial and error depending on the designer's skill, experience and intuition and, for example, by using a CAD system. In such manual trace design by trial and error, as the required traces become more complicated, the effort, time and difficulty for achieving the optimal traces is increased. Further, an unevenness in the quality of finished products is also increased. In reality, because the manual trace design by trial and error requires some days and it is not economical to spend more time on trace designing, the designer has to compromise to provide a certain design quality. As the semiconductor packages are miniaturized and integrated, automatization of trace design of the semiconductor packages will be one of the most important tasks in the future.
In particular, when a trace, the optimal route of which is to be determined, is obstructed by other traces, it is difficult to automate the trace design. For example, in order to secure clearance from other obstructing traces so as to implement an optimal trace route, a position of the trace to be processed may be maintained but positions of the other traces may be moved. In such case, trace positions may be changed significantly over an entire substrate.
Further, in the related-art automatic wiring method, it is possible to determine optimal routes of all traces on a substrate at a time but it is difficult to change wiring conditions such as, for example, trace widths, clearance and the like, of some of the traces.
In view of the above problems, it is an object of the present invention to provide an automatic trace determination method that can determine a trace route, on a substrate, that does not intersect with other traces on the substrate, automatically and in a short time.