On Routing Two-Point Nets Across a Three-Dimensional Channel

Abstract: Routing techniques for plain ’flat’ microchips have been developed extensively and will soon reach its limitations. One natural step would be to develop chips which are manufactured in a more cubic type of volume, as oppose to the classical flat design. This thesis proposes a method for routing two-point nets across a three- dimensional channel. The height required by this algorithm is of the order O(n (3/2)), where n is the number of terminals on a square top-layer with the side 2 (n(1/2)). The algorithm proposed here is based on"On Routing Two-Point Nets Across a Channel", by Ron Y. Pinter [9], and the concepts from this paper are explainedin this thesis to familiarise the reader these. It is also shown that the proposed algorithm is more effective in its volume than the two-dimensional counterpart. The algorithm here is of the order O(n(3/2)) with the two-dimensional algorithm of the order O(n2).