Patent ID: 11886786
Assignee: FUZHOU UNIVERSITY
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 8:
9. The two-step X-architecture Steiner minimum tree construction method according to claim 1, wherein S2 is specifically as follows:
at most q adjacent edges of each pin are traversed through the local topological optimization strategy and are properly adjusted, wherein 1≤q≤Q, and Q is a maximum degree of pins in the net; meanwhile, the parameter q is adjusted to obtain a better optimization effect or a shorter runtime; the closer q is to Q, the better the optimization effect will be; each pin is endowed with two attributes, one attribute is the degree degree of the pin, which represents the number of adjacent points of the pin, and the other attribute is an adjacent point list adj_list[ ] of the pin, which is used to store the adjacent points; a specific implementation process of this stage is as follows:
SA: recording the degree and adjacent point list of each point in the XST, and for a point with the degree being greater than q, only q adjacent points of this point are recorded;
SB: setting a local topological optimization sequence as follows: from pins with large degrees to pins with small degrees; sorting all the pins in a decreasing order according to the degree, and sorting the adjacent points of each pin in a decreasing order according to the degree, so that topological structures in a dense region are optimized first and then topological structures in a sparse region are optimized;
SC: sequentially optimizing local topological structures of all the points, adjusting PS selections of edges between the pins and the adjacent points, trying to use the other three selections, except the current selection, for connection, and reserving the connection with the minimum fitness; continuously adjusting the PS selections of the q adjacent edges of the pins in the XST to obtain a local optimal structure in a current XST topology; and finally, constructing the X-architecture Steiner tree with the minimum wirelength.