A new paradigm for general architecture routing

Abstract

The interest in alternatives to traditional Manhattan routing has increased tremendously during recent years. The so-called Y- and X-architectures have been proposed as architectures of the future. Manhattan, Y- and X-architectures are special cases of a general architecture in which a fixed set of uniformly oriented directions is allowed. In this paper we present a new paradigm for routing in this general architecture. The routing algorithm is based on a concept of flexibility polygons for Steiner minimum trees --- a new way of describing the inherent flexibility of Steiner trees in uniform orientation metrics. Flexibility polygons characterize possible routing regions for the nets while keeping their netlength at a minimum. The proposed routing algorithm first routes nets that intersect highly congested areas of the chip --- as given by the flexibility polygons --- and then employs dynamic maze (liquid) routing. Experiments with industrial chips show great promise for this new routing paradigm.