Fixed Orientation Interconnection Problems: Theory, Algorithms and Applications

Martin Tvede Zachariasen

Research output: Book / Anthology / Report / Ph.D. thesisPh.D. thesis


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 themain contributions is a linear time algorithmfor 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.
Original languageEnglish
PublisherMuseum Tusculanum
ISBN (Print)9788798127048
Publication statusPublished - 2009
Externally publishedYes

Cite this