An embodiment method of routing traces of an interconnect structure includes deriving first capacity information of a first plurality of routing nodes in a first area of the interconnect structure and generating a first plurality of predicted traces connecting the first plurality of routing nodes based on the first capacity information. The method of routing traces of the interconnect structure includes deriving second capacity information of a second plurality of routing nodes in a second area of the interconnect structure, and generating a second plurality of predicted traces connecting the second plurality of routing nodes based on the second capacity information. The method of routing traces of the interconnect structure further includes generating a plurality of traces connecting the first plurality of routing nodes and the second plurality of routing nodes based on the first plurality of predicted traces and the second plurality of predicted traces.