View Full Document

A Survey on Multi net Global Routing for Integrated Circuits



View the full content.
View Full Document
View Full Document

3 views

Unformatted text preview:

A Survey on Multi net Global Routing for Integrated Circuits Jiang Hu and Sachin S Sapatnekar jhu sachin mail ece umn edu Department of Electrical and Computer Engineering University of Minnesota Minneapolis MN 55455 USA Tel 612 625 0025 Fax 612 625 4583 Abstract This paper presents a comprehensive survey on global routing research over about the last two decades with an emphasis on the problems of simultaneously routing multiple nets in VLSI circuits under various design styles The survey begins with a coverage of traditional approaches such as sequential routing and rip up and reroute and then discusses multicommodity flow based methods which have attracted a good deal of attention recently The family of hierarchical routing techniques and several of its variants are then overviewed in addition to other techniques such as move based heuristics and iterative deletion While many traditional techniques focus on the conventional objective of managing congestion newer objectives have come into play with the advances in VLSI technology Specifically the focus of global routing has shifted so that it is important to augment the congestion objective with metrics for timing and crosstalk In the later part of this paper we summarize the recent progress in these directions Finally the survey concludes with a summary of possible future research directions This work is supported in part by the NSF under contract CCR 9800992 and the SRC under contract 98 DJ 609 Contents 1 Introduction 4 2 Problem background and formulation 6 3 Basic techniques 9 3 1 Maze routing 9 3 2 Steiner tree construction 11 3 3 0 1 integer linear programming 12 3 4 Network flow model 13 4 Sequential routing techniques 14 4 1 Force directed routing 15 4 2 Sequential routing through Steiner min max tree construction 16 4 3 Minimum weighted Steiner tree 17 5 Region wise routing 19 5 1 Unique pattern first and outer rim first routing 19 5 2 Routing in order of wire orientations and in terms of rows 22 6 Move



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view A Survey on Multi net Global Routing for Integrated Circuits and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Survey on Multi net Global Routing for Integrated Circuits and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?