Routing based port assignment and buffering

Abstract

In this thesis, we present mathematical and practical progress in BonnPangea for port assignment and in BonnRouteBuffer for global buffering. <br/> We present an approximation algorithm for the uniform cost-distance Steiner tree problem. Our approximation factor is <2.05. <br/> The task of the pangea routing problem is to compute a global routing on a chip partitioned into components ("continents"), such that the routing interfaces of each component (which are also part of the output) are as simple as possible. We provide the first written account of the standard pangea flow as well as pangea replay. We then consider the completely new problem of reusing a continent multiple times. This happens for example when there are several cores on a processor chip. We then need to compute equivalent interfaces on all instances of the continent. Pangea ReUse is the first tool in the industry able to deal with this case. We present a new collection of algorithms for Pangea ReUse that was developed and implemented at part of this thesis. <br/> Pangea ReUse was a huge success in practice. Compared to the previous workflow, it saves one week in going from netlist to port creation. Pangea ReUse also enables the use of BonnPangea on designs that would not have been eligible without it. Afterwards, we explore necessary conditions for eligible solutions. This leads to an advanced algorithm for Pangea ReUse. We show that this algorithm is able to solve much more general instances correctly. <br/> BonnRouteBuffer is a tool for simultaneously routing and buffering large designs. Doing so, BonnRouteBuffer can optimize routing congestion, timing properties, power consumption and placement density. <br/> We uncover a major inaccuracy in the slew computations and present the improvements that were devised and implemented as part of this thesis. The computation of both the backwards propagation of slew limits and the forwards propagation of slews were rewritten. The new slew model allows us to reduce the pessimism in the slew calculations, leading to improvements in almost all metrics. <br/> From the experimental results, we draw several conclusions. Firstly, the inaccuracy in the slew calculations was a main reason why very sub-optimal buffering solutions were computed. A refinement of these computations already leads to significant improvements in many metrics. Secondly, both slew and load violations play a major role for the buffering quality. This is not reflected well in the model. Finally, further speed-ups of BonnRouteBuffer are necessary to make it suitable to replace industrial buffering flows.