We have seen dramatic advances in the IC technology in the past several years. The shrinkage of die sizes and the increase in functional complexities made the circuits more and more dense. Furthermore, the number of timing critical nets in a typical high-end design has increased considerably due to increasing clock frequencies. These factors have brought significant routing challenges that cannot be handled by traditional board routing algorithms. In this dissertation, we propose novel routing algorithms targeted at handling the challenges due to increasing package densities, and increasing clock frequencies.Routing nets within minimum and maximum length bounds is an important requirement for high-speed VLSI packages. For this problem, we first propose a Lagrangian relaxation based length matching routing algorithm, where the objective of satisfying min-max length constraints is effectively incorporated into the actual routing problem. Our experiments demonstrate that our algorithm outperforms a commonly used ad hoc methodology, especially when the length constraints are tight. Although this algorithm can be used for more general routing problems, we also consider more restricted yet common problem instances, and propose more effective routing algorithms for them. Specifically, we first focus on the problem of two-layer bus routing between component boundaries. We model this problem as a job scheduling problem, and propose algorithms to solve it effectively. After that, we focus on the problem of routing bus structures between component boundaries on a single layer. For this, we propose algorithms that are proven to give close-to-optimal solutions.As the package densities are increasing, routing nets from individual pins within dense components to the component boundaries (escape routing) is becoming the main bottleneck in terms of overall routability. Furthermore, solving the escape routing problem in each component independently is not an effective methodology for high-end board designs, since it ignores the wiring requirements between different components. For this, we propose novel models and algorithms to solve the escape routing problem in multiple components simultaneously, such that the number of crossings in the intermediate area (between components) is minimized. Our experiments demonstrate that these algorithms can reduce via requirements substantially, compared to a net-by-net methodology. We also consider practical generalizations of these models, and discuss how to incorporate several high-speed design constraints into the framework of these algorithms. Finally, we focus on the problem of escape routing within dense pin clusters, which can have arbitrary convex boundaries. We propose a set of sufficient and necessary conditions that guarantee routability outside the escape boundaries. We also discuss how these conditions can be incorporated effectively into an escape routing algorithm.
展开▼
