Automatic trace determination apparatus and computer program thereof

An automatic trace determination apparatus for automatically determining optimal trace positions from pads to corresponding vias on a substrate by computation, comprising:

• means for generating tentative traces connecting said pads and said corresponding vias by straight lines;
• first intersection resolving means for resolving all intersections formed between tentative traces sequentially from the intersection nearest to said pads, wherein resolving one intersection is performed by determining distances from said intersection to corresponding vias of the tentative traces that form said intersection, retracing the tentative trace associated with the longer distance to said intersection to bypass corresponding via of the other tentative trace associated with the shorter distance to said intersection, and defining this retraced tentative trace as an interim trace;
• second intersection resolving means for resolving all intersections formed between said interim traces themselves and intersections formed between said interim and tentative traces sequentially from the intersection nearest to said pads, wherein resolving one intersection is performed by determining distances from said intersection to corresponding vias of the traces that form said intersection, retracing the trace associated with the longer distance to said intersection to bypass corresponding via of the trace associated with the shorter distance to said intersection and defining this retraced trace as a new interim trace;
• and
• means for defining all tentative or interim traces as optimal traces after the resolving of all intersections by the second intersection resolving means.

A computer program stored on a storage medium for allowing a computer to perform an automatic trace determination process for automatically determining optimal trace positions from pads to corresponding vias, the automatic trace determination process comprising:

• a step for generating tentative traces connecting said pads and said corresponding vias by straight lines;
• a first intersection resolving step for resolving all intersections formed between tentative traces sequentially from the intersection nearest to said pads, wherein resolving one intersection is performed by retracing one of tentative traces that form said intersection to bypass the corresponding via of the other tentative trace that forms said intersection, and defining this retraced trace as an interim trace;
• a second intersection resolving step for resolving all intersections formed between said interim traces themselves and intersections formed between said interim and tentative traces sequentially from the intersection nearest to said pads, wherein resolving one intersection is performed by retracing one of the traces that form said intersection to bypass the corresponding via of the other trace that forms said intersection, and defining this retraced trace as an optimal trace;
• and
• a step for defining all tentative or interim traces as optimal traces after the resolving of all intersections by the second intersection resolving means.