Combinatorial Algorithms in VLSI Routing

OData support
Supervisor:
Dr. Recski András
Department of Computer Science and Information Theory

Since the recent technologies permit a large number of layers, the modern algorithms for the design of very large scale integrated circuits need not distinguish the third dimension from the classical two. We may consider arbitrary rectangular boxes where the terminals to be interconnected are placed on any of the six faces and the routing of the nets should be performed along a cubic grid inside the box.

The first type of results referred to the single active layer case (where all the terminals were situated at a single face) and to the 3D-channel routing problem where two opposite faces contain all the terminals. The theory of the 3D-gamma routing problem (where two adjacent faces contain all the terminals) is less developed.

This thesis work presents theoretical results in the detailed routing of VLSI circuits. It shows how both two and three dimensional routing problems can be handled using combinatorial algorithms. Despite the fact that many problems are NP-hard, a lot of heuristics have been developed.

The main emphasis is put on 3-dimensional gamma routing results. It is shown that if we are allowed to extend width, length and/or height of the routing, the solution always exists. The optimization problem in this case is to use as small spacing as possible.

Furthermore, we present a new routing algorithm which solves any 3D-gamma routing problem if length, width and height are equal.

Downloads

Please sign in to download the files of this thesis.