The retiming and routing of VLSI circuits

In this thesis, we explore three problems arising during the logic synthesis and physical design stages of VLSI circuit design. We first present a new formulation for the retiming of single-phase clocked circuits containing latches. Then, we discuss crosstalk optimization in channel-based routings, and finally present a new performance-driven algorithm for the layer assignment of critical global nets.Although single-phase clocked circuits containing latches are in widespread use, there is no existing practical formulation for such circuits that allows retiming-based optimizations. We present a novel, ILP-based formulation for the retiming of such circuits. This formulation can be used to optimize any linearizable objective function. As examples, we discuss the optimization of the clock period and the area of such circuits. Our experiments demonstrate that our approach is efficient and generates ILPs that are easy to solve.We address the increased importance of crosstalk avoidance in deep submicron technologies by presenting a new postprocessing algorithm to minimize the peak crosstalk in the nets routed in a gridless channel. We study the variation of the crosstalk in a net and its neighbors when some trunk belonging to the net is perturbed, proving that this variation is well-behaved. This allows us to determine the optimal location for the trunk without needing to solve any non-linear equations. Our experimental results verify that our approach is very effective.Multi-layer technologies present additional challenges to the routing of the nets because the layer assignment can have a large impact on the net delays. Traditional approaches cause the first few nets to monopolize the "good" layers. Therefore, they perform poorly under the metric of minimizing the maximum net delay. We propose the use of dynamic area quotas to remedy this problem. Our approach is independent of the routing model and the router used, and works very well in practice.