An analysis of the single row transformation (SRT) approach to VLSI channel routing

Venguswamy, Kumar (1990) An analysis of the single row transformation (SRT) approach to VLSI channel routing. Masters thesis, Memorial University of Newfoundland.

[English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (21MB) [English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. (Original Version)

Abstract

This thesis addresses the problem of detailed routing of Very Large Scale Integrated (VLSI) circuits using channel routing. Recently, a novel approach to detailed VLSI routing has been proposed by Wong and Kwok [Wong88]. This method, called the Single Row Transformation (SRT) approach, requires three steps, namely, Forward Transformation (FT), Single Row Routing (SRR) and finally Backward Transformation (BT). When this apparently simple approach was looked at more closely, it was realised that this approach has many hidden problems, the most important being those posed by the crossovers in the SRR layout while carrying out the BT step. Thus, although SRT based routing appeared to be a potential approach, further research was required. The goal of this thesis is to make a study and analysis of the SRT approach as it applies to channel routing, and to use the results of the analysis to design a channel router. -- Although different FT-BT pairs are possible, only straightforward pairs are practical, and even for simple FT-BT pairs the problems posed by crossovers in the SRR solution necessitate a minimum crossover routing, calling for the design of new algorithms, because most of the existing SRR algorithms have been designed with the goal of track optimisation, not crossover minimisation. To facilitate the design of these algorithms, a taxonomy of SRR problems is useful. A proposed taxonomy classifies SRR problems into bipartite and non-bipartite problems, and further into permutation and mixed SRR problems. Based on this taxonomy, various algorithms for the different classes of SRR problems have been developed. Since some crossovers may he inevitable, effective crossover handling techniques are necessary. To this end different crossover handling techniques are discussed and a generalised crossover handling technique is proposed. The application of the analysis to the software design of a channel router and implementation of this software is also addressed.

Actions (login required)

View Item