Abstract:

Symbolic layout often serves as an intermediate form during 
thegeneration of layout for integrated circuits.  We present a 
methodology, borrowed from compiler optimization practice, and 
a specific technique, based on efficient string matching algorithms, 
to improve the quality of symbolic layout.  The method constitutes 
the application of numerous local replacement rules to the
original symbolic layout, thereby producing a new layout with better
performance characteristics and that would facilitate better eventual 
compaction.
The transformations are enabled by the recognition of patterns in the
layout, which is performed efficiently using an almost linear-time 
string matching algorithm.  The ideas have been demonstrated by an 
experimental tool, which was applied to a number of channel routes, 
resulting in noticeable improvements.
Furthermore, this application led to a few observations regarding 
practical string matching techniques which we shall review at the end 
of the talk.

Joint work with Shimon Ben-Yehuda.