An efficient routing database

Routing is an important problem in the process of design creation. In this paper, we focus on the problem of designing a database for the non-partitioned routing problem. New technology libraries describe constraints that are hard to manage in grid-based approaches to the routing database. While general region query based data-structures have been proposed, they typically suffer from speed problems when applied to large blocks. We introduce an interval-based approach. It provides more flexibility than grid-based techniques. It exploits the notion of preferred direction for metal layers to manage the memory efficiently. It supports efficient region queries. We finally present a comparison study for real industrial designs on this database