DocumentCode :
29839
Title :
Algorithms for Maze Routing With Exact Matching Constraints
Author :
Ozdal, Muhammet Mustafa ; Hentschke, Renato Fernandes
Author_Institution :
Intel Corp., Hillsboro, OR, USA
Volume :
33
Issue :
1
fYear :
2014
fDate :
Jan. 2014
Firstpage :
101
Lastpage :
112
Abstract :
Exact route matching is an important constraint for analog and mixed signal designs with nonuniform metal stacks. In this paper, we propose a constrained-path-based maze routing algorithm that can handle exact matching constraints for multiple nets. We also propose a scalable framework that utilizes the proposed maze routing algorithm for realistic problem sizes. Compared to the pattern routing algorithms proposed recently , our algorithms allow a more thorough exploration of the solution space by allowing bends to be inserted to avoid congested regions. Furthermore, we propose an ILP-based model to explore the impact of the initial routing topologies on the final solutions. Our experimental study demonstrates that the proposed algorithm leads to significant reductions in congestion costs compared to the previous algorithm.
Keywords :
circuit optimisation; integer programming; integrated circuit design; linear programming; mixed analogue-digital integrated circuits; network routing; pattern matching; ILP-based model; analog-mixed signal designs; congestion costs; constrained-path-based maze routing algorithm; exact matching constraints; exact route matching; integer linear programming; nonuniform metal stacks; pattern routing algorithms; routing topology; Algorithm design and analysis; Complexity theory; Heuristic algorithms; Metals; Receivers; Routing; Runtime; Dynamic programming; integer linear programming; matching; routing;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/TCAD.2013.2279516
Filename :
6685898
Link To Document :
بازگشت