TY - THES

T1 - Fixed Orientation Interconnection Problems: Theory, Algorithms and Applications

AU - Zachariasen, Martin

PY - 2009

Y1 - 2009

N2 - Interconnection problems have natural applications in the design of integrated circuits (or chips). A modern chip consists of billions of transistors that are connected by metal wires on the surface of the chip. These metal wires are routed on a (fairly small) number of layers in such a way that electrically independent nets do not intersect each other. Traditional manufacturing technology limits the orientations of the wires to be either horizontal or vertical — and is known as Manhattan architecture.Over the last decade there has been a growing interest in general architectures, where more than two perpendicular orientations can be used for routing. This development has made fixed orientation interconnection problems (where an arbitrary set of fixed orientations can be used) interesting from a research point of view. In particular, the problem of computing minimum length networks with fixed orientations — the so-called fixed orientation Steiner tree problem — has received significant attention.This doctoral dissertation is a collection of twelve research papers and a survey on the fixed orientation Steiner tree problem and some of its generalizations. One of the main contributions is a linear time algorithm for computing a Steiner minimum tree for a given full topology. Also, a linear programming formulation is presented for the problem. For the general problem an exact algorithm that computes optimal solutions to problem instances with thousands of points is described and implemented. A novel paradigm for routing a chip using a general architecture is implemented and tested on a set of benchmark instances; the approach documents the advantages of using more than two fixed orientations in chip design.The last part of the dissertation is concerned with generalizations that are motivated by chip design. Firstly, a catalog of problems that can be solved on the so-called Hanan grid is presented. Next, generalizations related to signal delay and group interconnections are studied, and finally, properties of the rotational Steiner tree problem are given.The results of the dissertation represent a significant step forward, both concerning theory and algorithms, for the fixed orientation Steiner tree problem. In addition, the work maintains a close link to applications and generalizations motivated by chip design.

AB - Interconnection problems have natural applications in the design of integrated circuits (or chips). A modern chip consists of billions of transistors that are connected by metal wires on the surface of the chip. These metal wires are routed on a (fairly small) number of layers in such a way that electrically independent nets do not intersect each other. Traditional manufacturing technology limits the orientations of the wires to be either horizontal or vertical — and is known as Manhattan architecture.Over the last decade there has been a growing interest in general architectures, where more than two perpendicular orientations can be used for routing. This development has made fixed orientation interconnection problems (where an arbitrary set of fixed orientations can be used) interesting from a research point of view. In particular, the problem of computing minimum length networks with fixed orientations — the so-called fixed orientation Steiner tree problem — has received significant attention.This doctoral dissertation is a collection of twelve research papers and a survey on the fixed orientation Steiner tree problem and some of its generalizations. One of the main contributions is a linear time algorithm for computing a Steiner minimum tree for a given full topology. Also, a linear programming formulation is presented for the problem. For the general problem an exact algorithm that computes optimal solutions to problem instances with thousands of points is described and implemented. A novel paradigm for routing a chip using a general architecture is implemented and tested on a set of benchmark instances; the approach documents the advantages of using more than two fixed orientations in chip design.The last part of the dissertation is concerned with generalizations that are motivated by chip design. Firstly, a catalog of problems that can be solved on the so-called Hanan grid is presented. Next, generalizations related to signal delay and group interconnections are studied, and finally, properties of the rotational Steiner tree problem are given.The results of the dissertation represent a significant step forward, both concerning theory and algorithms, for the fixed orientation Steiner tree problem. In addition, the work maintains a close link to applications and generalizations motivated by chip design.

M3 - Doctoral thesis

SN - 978-87-981270-4-8

BT - Fixed Orientation Interconnection Problems: Theory, Algorithms and Applications

PB - Museum Tusculanum

CY - København

ER -