Three-Dimensional Cylindrical Model for Single-Row Dynamic Routing

Abstract

Single-row routing is a technique to route pairs of pins aligned in a single axis into non-crossing nets to form a least congested network. The technique has its main application in the printed circuit board design where the nets between the pins are drawn statically, that is, in a fixed manner. In the dynamic single-row routing, the nets from the pairs of pins in the network are allowed to change according to the requirement. This paper proposes a new dynamic single-row routing model for the switching of pins based on the cylindrical design. In the model, a cylinder has unlimited number of planes that are formed by traversing its circular cross-section. Each plane houses a network of single-row pins that share the same pins. As the planes do not overlap, the nets in the networks do not cross as they are placed in different planes. This makes it possible to allow the configuration of the nets to change according to pin connection requirements for forming the dynamic model. The single-row routings in each network are produced optimally using our earlier model called ESSR (Enhanced Simulated annealing for Single-row Routing). This suggests that the cylindrical model is optimal and suitable for adoption into problems requiring massive pin connections such as in switching. Keywords: Single-row Routing; Dynamic Configuration; ESSR; Induction formula. 2010 Mathematics Subject Classification: