Interconnect Optimization in Chip Design

Abstract

In this thesis, we take a closer look at the buffering problem. We review the literature on the buffering problem and examine how different algorithms try to solve it. We present an overview over the different aspects that are relevant for buffering, explain how they can be modelled and what decisions we made in modelling. Based on these considerations, we present a new problem formulation that captures more aspects and allows more degrees of freedom than all the previous algorithms and formulations. We present an (exponential time) algorithm that is able to solve this problem either approximately, or even optimally, with higher running time. Both variants depend on a slew accuracy function. We prove that the algorithm finds an optimum solution if it starts with a certain set of initial slews. Then, we show how to guess slews that allow us to find an optimum solution. In this way, we solve the inherent problem of including slew in buffering algorithms. Then, we demonstrate that the algorithm can be modified to include higher order delay models or increase the degrees of freedom at the cost of ignoring the slew. <br /> We also present multiple new speed up techniques. Among them are a data structure that efficiently maintains the labels in our algorithm, a construction of a sparse graph representing the routing space and buffering positions that retains helpful properties for finding good solutions and a practical (almost) feasible lower bound function. Then we develop as additional speedups a fast way to restrict the topology of solutions and present a new iterative clustering heuristic that is timing aware. It uses the Capacitated Tree Cover Problem with Edge Loads as a black box. <br /> We present a new 3-approximation algorithm for this problem that runs in O(mlog n) time. An underlying LP-relaxation can be solved optimally using a greedy algorithm, despite its exponential number of inequalities. We round this LP and apply a wellknown splitting technique to get to a feasible solution. In a final step, we prove that the integrality gap of our LP-relaxation is 3, which means that our analysis was optimal. <br /> Finally, we test our algorithm both in a benchmark setting and a practical setting. We show that we gain significant speedups by augmenting our algorithm with heuristic speedup techniques that do not lead to a notable loss in result quality. Then we examine how the fastest variants of our algorithm perform in a practical setting and see that it can give us significant improvements at a high runtime cost. Unfortunately, it is too slow to use it as a default tool in a design flow, but it can be used to optimize a few hard instances that otherwise would have to be optimized manually by a designer. <br /> Our algorithm allows us for the first time to benchmark existing buffering algorithms and heuristics. We can find out if solutions are good or how to improve them by comparing to our results. BonnRouteBuffer has been improved this way multiple times.