Method of routability measure for general area routing problems

One of the vital phases in the design flow of electronic artifacts is the phase called physical design. In this phase--which traditionally involves partitioning, placement and routing problems--circuit designs are transformed into layouts ready for fabrication. Whether designing PCBs, MCMs or even VLSI chips, a problem that frequently arises is that of knowing if the layout will be routable. This is a classical problem of predicting routability/wireability that has been known since the early days of physical design. Unfortunately, quantifying the 'real' routability is a difficult task and hence the average wirelength based on the number of intramodule connections has become a common measure of routability. At the other end of this overly simplified measure, people do the actual place and route steps to determine the routability. In search of a more realistic way of quantifying the routability, a new method for measuring routability/wireability is proposed for use in general area routing problems. It focuses on MCM and dense PCB designs but can be extended to any general area routing problem. The routability is measured by extending the counting method of Pascal's Triangle where the number of potential routes of each net in the design can be obtained precisely. The method has made it possible to evaluate the number of potential routes in the presence of arbitrary obstacles as well as the possible limitations on the number of vias/bends to use. The theoretical development of the new method has resulted in two main algorithms called the EPTM and FEPT. Testing on several MCM benchmarks confirms what was intuitively believed that routes with 4 or less vias/bends are sufficient for general area routing problems in MCMs. It also uncovered the fact that increasing the number of vias/bends in the routes doesn't always increase the potential of routability unless detours are introduced. Further testing on non-minimum rectilinear paths shows that detours do improve the routability when the number of vias/bends between detour points is 3 or greater