A predictive distributed congestion metric with application to technology mapping

Rupesh S. Shelar; Sachin S. Sapatnekar; Prashant Saxena; Xinning Wang

doi:10.1109/TCAD.2005.846368

A predictive distributed congestion metric with application to technology mapping

Rupesh S. Shelar, Sachin S. Sapatnekar, Prashant Saxena, Xinning Wang

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Due to increasing design complexities, routing congestion has become a critical problem in very large scale integration designs. This paper introduces a distributed metric to predict routing congestion and applies it to technology mapping that targets area and delay optimization. Our technology mapping algorithms are guided by a probabilistic congestion map for the subject graph to identify the congested regions, where congestion-optimal matches are favored. Experimental results on a set of benchmark circuits in a 90-nm technology show that congestion-aware mapping results in a reduction of 37%, on an average, in track overflows with marginal gate-area penalty as compared to conventional area-oriented technology mapping. For delay-oriented mapping, our algorithm improves track overflows by 20%, on an average, in addition to preserving or improving the delay, as compared to the conventional method.

Original language	English (US)
Pages (from-to)	696-709
Number of pages	14
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	24
Issue number	5
DOIs	https://doi.org/10.1109/TCAD.2005.846368
State	Published - May 2005

Bibliographical note

Funding Information:
Manuscript received June 3, 2004; revised September 17, 2004. This work was supported in part by the Semiconductor Research Consortium (SRC) under Contract 2002-TJ-1092 and Award NSF CCR-0205227. This paper was recommended by Guest Editor P. Groeneveld. R. S. Shelar was with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. He is now with Intel Corporation, Hillsboro, OR 97124 USA (e-mail: ru-pesh@mail.ece.umn.edu). S. S. Sapatnekar is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. P. Saxena and X. Wang are with Intel Corporation, Hillsboro, OR 97124 USA. Digital Object Identifier 10.1109/TCAD.2005.846368

Keywords

Congestion estimation
Logic synthesis
Physical design
Placement
Routing congestion
Technology mapping

Access

10.1109/TCAD.2005.846368

OpenUrl availability

Full text

Cite this

@article{16aad9a584e54d4eaa73776bf5764c4a,

title = "A predictive distributed congestion metric with application to technology mapping",

abstract = "Due to increasing design complexities, routing congestion has become a critical problem in very large scale integration designs. This paper introduces a distributed metric to predict routing congestion and applies it to technology mapping that targets area and delay optimization. Our technology mapping algorithms are guided by a probabilistic congestion map for the subject graph to identify the congested regions, where congestion-optimal matches are favored. Experimental results on a set of benchmark circuits in a 90-nm technology show that congestion-aware mapping results in a reduction of 37%, on an average, in track overflows with marginal gate-area penalty as compared to conventional area-oriented technology mapping. For delay-oriented mapping, our algorithm improves track overflows by 20%, on an average, in addition to preserving or improving the delay, as compared to the conventional method.",

keywords = "Congestion estimation, Logic synthesis, Physical design, Placement, Routing congestion, Technology mapping",

author = "Shelar, {Rupesh S.} and Sapatnekar, {Sachin S.} and Prashant Saxena and Xinning Wang",

note = "Funding Information: Manuscript received June 3, 2004; revised September 17, 2004. This work was supported in part by the Semiconductor Research Consortium (SRC) under Contract 2002-TJ-1092 and Award NSF CCR-0205227. This paper was recommended by Guest Editor P. Groeneveld. R. S. Shelar was with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. He is now with Intel Corporation, Hillsboro, OR 97124 USA (e-mail: ru-pesh@mail.ece.umn.edu). S. S. Sapatnekar is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. P. Saxena and X. Wang are with Intel Corporation, Hillsboro, OR 97124 USA. Digital Object Identifier 10.1109/TCAD.2005.846368",

year = "2005",

month = may,

doi = "10.1109/TCAD.2005.846368",

language = "English (US)",

volume = "24",

pages = "696--709",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - A predictive distributed congestion metric with application to technology mapping

AU - Shelar, Rupesh S.

AU - Sapatnekar, Sachin S.

AU - Saxena, Prashant

AU - Wang, Xinning

N1 - Funding Information: Manuscript received June 3, 2004; revised September 17, 2004. This work was supported in part by the Semiconductor Research Consortium (SRC) under Contract 2002-TJ-1092 and Award NSF CCR-0205227. This paper was recommended by Guest Editor P. Groeneveld. R. S. Shelar was with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. He is now with Intel Corporation, Hillsboro, OR 97124 USA (e-mail: ru-pesh@mail.ece.umn.edu). S. S. Sapatnekar is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. P. Saxena and X. Wang are with Intel Corporation, Hillsboro, OR 97124 USA. Digital Object Identifier 10.1109/TCAD.2005.846368

PY - 2005/5

Y1 - 2005/5

N2 - Due to increasing design complexities, routing congestion has become a critical problem in very large scale integration designs. This paper introduces a distributed metric to predict routing congestion and applies it to technology mapping that targets area and delay optimization. Our technology mapping algorithms are guided by a probabilistic congestion map for the subject graph to identify the congested regions, where congestion-optimal matches are favored. Experimental results on a set of benchmark circuits in a 90-nm technology show that congestion-aware mapping results in a reduction of 37%, on an average, in track overflows with marginal gate-area penalty as compared to conventional area-oriented technology mapping. For delay-oriented mapping, our algorithm improves track overflows by 20%, on an average, in addition to preserving or improving the delay, as compared to the conventional method.

AB - Due to increasing design complexities, routing congestion has become a critical problem in very large scale integration designs. This paper introduces a distributed metric to predict routing congestion and applies it to technology mapping that targets area and delay optimization. Our technology mapping algorithms are guided by a probabilistic congestion map for the subject graph to identify the congested regions, where congestion-optimal matches are favored. Experimental results on a set of benchmark circuits in a 90-nm technology show that congestion-aware mapping results in a reduction of 37%, on an average, in track overflows with marginal gate-area penalty as compared to conventional area-oriented technology mapping. For delay-oriented mapping, our algorithm improves track overflows by 20%, on an average, in addition to preserving or improving the delay, as compared to the conventional method.

KW - Congestion estimation

KW - Logic synthesis

KW - Physical design

KW - Placement

KW - Routing congestion

KW - Technology mapping

UR - http://www.scopus.com/inward/record.url?scp=18744396148&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=18744396148&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2005.846368

DO - 10.1109/TCAD.2005.846368

M3 - Article

AN - SCOPUS:18744396148

SN - 0278-0070

VL - 24

SP - 696

EP - 709

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 5

ER -

A predictive distributed congestion metric with application to technology mapping

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this