A Sub-Quadratic Algorithm on the Crossing Distribution Problem

Abstract

VLSI layout design is typically decomposed into four steps: placement, global routing, routing region definition, and detailed routing. The crossing distribution problem occurs prior to detailed routing[1][2][3][4]. It is much more difficult to rout nets with crossings than not. We will use at least two layers to implement and require some vias. So the crossing distribution problem (CDP) is a very important problem of VLSI layout. In this paper we will firstly solve the simple case: the crossing distribution problem of two regions. In previous research, the best result is an O(n2) algorithm[4]. The previous approach is bounded by crossing numbers. This paper presents an O(nlogn) algorithm. We don’t put our focus on the crossings but on permutation. So the time complexity may get better.