research-article

A metric for layout-friendly microarchitecture optimization in high-level synthesis

Authors:

Bin LiuAuthors Info & Claims

DAC '12: Proceedings of the 49th Annual Design Automation Conference

Pages 1239 - 1244

https://doi.org/10.1145/2228360.2228587

Published: 03 June 2012 Publication History

Abstract

In this work we address the problem of managing interconnect timing in high-level synthesis by generating a layout-friendly microarchitecture. A metric called spreading score is proposed to evaluate the layout-friendliness of microarchitectural netlist structures. For a piece of connected netlist, spreading score measures how far the components can be spread from each other with bounded length for every wire. The intuition is that components in a layout-friendly netlist (e.g., a mesh) can spread over the layout region without introducing long interconnects. We propose a semidefinite programming relaxation to allow efficient estimation of spreading score, and use it in a high-level synthesis tool. On a number of test cases, a normalized spreading score shows a stronger bias in favor of interconnect structures that have better timing after layout, compared to the widely used metric of total multiplexer inputs. We also justify our metric and motivate further study by relating spreading score to other metrics and problems for layout-friendly synthesis.

References

[1]

Agility Design Solutions Inc. Handel-C Language Reference Manual, 2007.

[2]

B. Borchers. CSDP, a C library for semidefinite programming. Optimization Methods and Software, 11(1):613--623, 1999.

[3]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, 2004.

Digital Library

[4]

D. Chen and J. Cong. Register binding and port assignment for multiplexer optimization. In Proc. Asia and South Pacific Design Automation Conf., pages 68--73, 2004.

Digital Library

[5]

J. Cong, Y. Fan, G. Han, W. Jiang, and Z. Zhang. Platform-based behavior-level and system-level synthesis. In Proc. IEEE Int. SOC Conf., pages 199--202, 2006.

[6]

J. Cong, Y. Fan, G. Han, X. Yang, and Z. Zhang. Architecture and synthesis for on-chip multicycle communication. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 23(4):550--564, April 2004.

Digital Library

[7]

J. Cong, Y. Fan, and W. Jiang. Platform-based resource binding using a distributed register-file microarchitecture. In Proc. Int. Conf. on Computer-Aided Design, pages 709--715, 2006.

Digital Library

[8]

J. Cong, B. Liu, G. Luo, and R. Prabhakar. Towards layout-friendly high-level synthesis. In Proc. Int. Symp. on Physical Design, pages 165--172, 2012.

Digital Library

[9]

W. Dougherty and D. Thomas. Unifying behavioral synthesis and physical design. In Proc. Design Automation Conf., pages 756--761, 2000.

Digital Library

[10]

Y.-M. Fang and D. F. Wong. Simultaneous functional-unit binding and floorplanning. In Proc. Int. Conf. on Computer-Aided Design, pages 317--321, 1994.

Digital Library

[11]

M. Fiedler. Laplacian of graphs and algebraic connectivity. Combinatorics and Graph Theory, 25:57--70, 1989.

[12]

F. Göring, C. Helmberg, and M. Wappler. The rotational dimension of a graph. Journal of Graph Theory, 66(4):283--302, 2011.

Digital Library

[13]

Z. Gu, J. Wang, R. Dick, and H. Zhou. Unified incremental physical-level and high-level synthesis. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 26(9):1576--1588, 2007.

Digital Library

[14]

C.-Y. Huang, Y.-S. Chen, Y.-L. Lin, and Y.-C. Hsu. Data path allocation based on bipartite weighted matching. In Proc. Design Automation Conf., pages 499--504, 1990.

Digital Library

[15]

T. Kim and X. Liu. Compatibility path based binding algorithm for interconnect reduction in high level synthesis. In Proc. Int. Conf. on Computer-Aided Design, pages 435--441, 2007.

Digital Library

[16]

M. Kistler, M. Perrone, and F. Petrini. Cell multiprocessor communication network: Built for speed. IEEE Micro, 26(3):10--23, May 2006.

Digital Library

[17]

P. Kudva, A. Sullivan, and W. Dougherty. Measurements for structural logic synthesis optimizations. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22(6):665--674, June 2003.

Digital Library

[18]

A. Kuehlmann and R. A. Bergamaschi. Timing analysis in high-level synthesis. In Proc. Int. Conf. on Computer-Aided Design, pages 349--354, 1992.

Digital Library

[19]

H. Kung. Why systolic architectures? Computer, 15(1):37--46, Jan. 1982.

Digital Library

[20]

M. C. McFarland. Reevaluating the design space for register transfer hardware synthesis. In Proc. Int. Conf. on Computer-Aided Design, pages 262--265, 1987.

[21]

B. M. Pangre. Splicer: a heuristic approach to connectivity binding. In Proc. Design Automation Conf., pages 536--541, 1988.

Digital Library

[22]

H. Park, K. Fan, S. A. Mahlke, T. Oh, H. Kim, and H.-s. Kim. Edge-centric modulo scheduling for coarse-grained reconfigurable architectures. In Proc. Int. Conf. on Parallel Architecture and Compilation Techniques, pages 166--176, 2008.

Digital Library

[23]

N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309--322, 1986.

[24]

I. E. Sutherland, C. E. Molnar, and R. F. Sproull. Counterflow pipeline processor architecture. Technical Report 94-25, Sun Microsystems Laboratories, 1994.

Digital Library

[25]

L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(1):49--95, 1996.

Digital Library

[26]

J.-P. Weng and A. Parker. 3D scheduling: high-level synthesis with floorplanning. In Proc. Design Automation Conf., pages 668--673, 1991.

Digital Library

[27]

D. R. White and F. Harary. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology, 31(1):305--359, 2001.

[28]

L. Zhong and N. K. Jha. Interconnect-aware low-power high-level synthesis. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 24(3):336--351, 2005.

Digital Library

Cited By

TATSUOKA MKANEKO M(2020)High Level Congestion Detection from C/C++ Source Code for High Level SynthesisIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2020VLP0012E103.A:12(1437-1446)Online publication date: 1-Dec-2020
https://doi.org/10.1587/transfun.2020VLP0012
Tatsuoka MKaneko M(2018)Wire congestion aware high level synthesis flow with source code compiler2018 International Conference on IC Design & Technology (ICICDT)10.1109/ICICDT.2018.8399766(101-104)Online publication date: Jun-2018
https://doi.org/10.1109/ICICDT.2018.8399766
Liu DYu BChowdhury SPan D(2017)Incremental Layer Assignment for Timing OptimizationACM Transactions on Design Automation of Electronic Systems10.1145/308372722:4(1-25)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3083727
Show More Cited By

Index Terms

A metric for layout-friendly microarchitecture optimization in high-level synthesis
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
    2. Logic synthesis
      1. Circuit optimization

Recommendations

Towards layout-friendly high-level synthesis
ISPD '12: Proceedings of the 2012 ACM international symposium on International Symposium on Physical Design

There are two prominent problems with technology scaling: increasing design complexity and more challenges with interconnect design, including routability. High-level synthesis has been proposed to solve the complexity problem by raising the abstraction ...
Resource Sharing Combined with Layout Effects in High-Level Synthesis

In deep-submicron designs, the interconnects are equally as or more important than the logic gates. In particular, to achieve timing closure, it is necessary and critical to consider the interconnect delay at an early stage of the synthesis process. It ...
Post-layout Redundant Via Insertion Approach Considering Multiple Via Configuration

Yield loss caused by via failures is unacceptably high in many semiconductor manufacturing processes. Redundant via insertion (RVI) is a typical approach for improving manufacturing competitiveness. The double-via insertion in concurrent routing or post-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '12: Proceedings of the 49th Annual Design Automation Conference

June 2012

1357 pages

ISBN:9781450311991

DOI:10.1145/2228360

General Chair:
Patrick Groeneveld
Magma Design Automation, Inc., San Jose, CA
,
Program Chairs:
Donatella Sciuto
Politecnico di Milano, Milano, Italy
,
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CEDA

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Semiconductor Research Corporation

Conference

DAC '12

Sponsor:

EDAC
SIGDA

DAC '12: The 49th Annual Design Automation Conference 2012

June 3 - 7, 2012

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
258
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

TATSUOKA MKANEKO M(2020)High Level Congestion Detection from C/C++ Source Code for High Level SynthesisIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2020VLP0012E103.A:12(1437-1446)Online publication date: 1-Dec-2020
https://doi.org/10.1587/transfun.2020VLP0012
Tatsuoka MKaneko M(2018)Wire congestion aware high level synthesis flow with source code compiler2018 International Conference on IC Design & Technology (ICICDT)10.1109/ICICDT.2018.8399766(101-104)Online publication date: Jun-2018
https://doi.org/10.1109/ICICDT.2018.8399766
Liu DYu BChowdhury SPan D(2017)Incremental Layer Assignment for Timing OptimizationACM Transactions on Design Automation of Electronic Systems10.1145/308372722:4(1-25)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3083727
FUJIWARA KKAWAMURA KYANAGISAWA MTOGAWA N(2016)Interconnection-Delay and Clock-Skew Estimate Modelings for Floorplan-Driven High-Level Synthesis Targeting FPGA DesignsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E99.A.1294E99.A:7(1294-1310)Online publication date: 2016
https://doi.org/10.1587/transfun.E99.A.1294
Tatsuoka MWatanabe ROtsuka THasegawa TZhu QOkamura RLi XTakabatake T(2015)Physically aware high level synthesis design flowProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744893(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744893
Cong JLiu BLuo GPrabhakar RHu JKoh C(2012)Towards layout-friendly high-level synthesisProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160952(165-172)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160952

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents