Topological global routing for automated IC package interconnect

A system for determining interconnect routing solution comprising:

• means for determining a global topological solution, said means for determining a global topological solution comprising;
• means for generating a matrix graph and a ring graph;
• means for initializing the matrix graph and ring graph;
• means for graphing pre-routed electrical routing segments to corresponding nodes in the matrix graph and linking the corresponding nodes to neighboring nodes in the ring graph;
• means for sequentially graphing un-routed electrical routing segments to corresponding nodes located in an innermost ring to outermost ring in the matrix graph and linking the corresponding nodes generated to neighboring nodes for each ring in the ring graph;
• means for balancing the nodes within each ring of the ring graph after each graphing of electrical routing segments to corresponding nodes;
• means for determining a geometric routing solution based on the global topological solution, said means for determining a geometric solution based on the global topological solution comprising;
• means for determining whether an overload condition exists;
• means for correcting overload conditions using techniques such as pin swapping and unused ball pad jumping;
• means for recording the location of each node as a guide point;
• and
• means for plotting electrical routing segments in accordance with the geometric solution.

A computer usable medium on which is embodied a set of programmed instructions that cause one or more processors to perform a sequence of steps, said steps comprising:

• determining a global topological solution, said step of determining a global topological solution comprising the steps of;
• generating a matrix graph and a ring graph;
• initializing the matrix graph and ring graph;
• graphing pre-routed electrical routing segments to corresponding nodes in the matrix graph and linking the corresponding nodes to neighboring nodes in the ring graph;
• sequentially graphing un-routed electrical routing segments to corresponding nodes located in an innermost ring to outermost ring in the matrix graph and linking the corresponding nodes generated to neighboring nodes for each ring in the ring graph;
• balancing the nodes within each ring of the ring graph after each graphing of electrical routing segments to corresponding nodes;
• determining a geometric routing solution based on the global topological solution, said step of determining a geometric solution based on the global topological solution comprising the steps of;
• determining whether an overload condition exists;
• correcting overload conditions using techniques such as pin swapping and unused ball pad jumping;
• recording the location of each node as a guide point;
• and
• plotting electrical routing segments in accordance with the geometric solution.

A method of determining interconnect routing solution comprising the steps of:

• determining a global topological solution;
• determining a geometric routing solution based on the global topological solution;
• and
• plotting electrical routing segments in accordance with the geometric solution.

A system for determining interconnect routing solution comprising:

• means for determining a global topological solution;
• means for determining a geometric routing solution based on the global topological solution;
• and
• means for plotting electrical routing segments in accordance with the geometric solution.

A computer usable medium on which is embodied a set of programmed instructions that cause one or more processors to perform a sequence of steps, said steps comprising:

• determining a global topological solution;
• determining a geometric routing solution based on the global topological solution;
• and
• plotting electrical routing segments in accordance with the geometric solution.