More Web Proxy on the site http://driver.im/

research-article

Robust partitioning for hardware-accelerated functional verification

Authors:

Michael D. Moffitt,

Mátyás A. Sustik,

Paul G. VillarrubiaAuthors Info & Claims

DAC '11: Proceedings of the 48th Design Automation Conference

Pages 854 - 859

https://doi.org/10.1145/2024724.2024915

Published: 05 June 2011 Publication History

Abstract

We introduce a method of partitioning for massively-parallel hardware accelerated functional verification. Our approach augments classical hypergraph partitioning to model temporal dependencies that maximize parallelization within the instruction memories of the machine. Simulation depth is further reduced by optimizing path criticality and cut directionality. Our techniques are demonstrated on an industrial accelerator containing 262,144 parallel processors, and benchmarked across designs containing up to 200 million gates.

References

[1]

C. J. Alpert, J.-H. Huang, and A. B. Kahng. Multilevel circuit partitioning. In Proceedings of DAC 1997, pages 530--533, 1997.

Digital Library

[2]

C. J. Alpert and A. B. Kahng. Recent directions in netlist partitioning: A survey. Integration, 19:1--81, 1995.

Digital Library

[3]

T. Blank. A survey of hardware accelerators used in computer-aided design. IEEE Design and Test of Computers, 1(3):21--39, 1984.

Digital Library

[4]

A. E. Caldwell, A. B. Kahng, A. A. Kennings, and I. L. Markov. Hypergraph partitioning for VLSI CAD: Methodology for heuristic development, experimentation and reporting. In Proceedings of DAC 1999, pages 349--354, 1999.

Digital Library

[5]

R. D. Chamberlain. Parallel logic simulation of VLSI systems. In Proceedings of DAC 1995, pages 139--143, 1995.

Digital Library

[6]

J. A. Darringer, E. E. Davidson, D. J. Hathaway, B. Koenemann, M. A. Lavin, J. K. Morrell, K. Rahmat, W. Roesner, E. C. Schanzenbach, G. Tellez, and L. Trevillyan. EDA in IBM: past, present, and future. IEEE Trans. on CAD, 19(12):1476--1497, 2000.

Digital Library

[7]

C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proceedings of DAC 1982, pages 175--181, 1982.

Digital Library

[8]

F. M. Johannes. Partitioning of VLSI circuits and systems. In Proceedings of DAC 1996, pages 83--87, 1996.

Digital Library

[9]

A. B. Kahng, J. Lienig, I. L. Markov, and J. Hu. VLSI Physical Design: from Graph Partitioning to Timing Closure. Springer, 2010.

Digital Library

[10]

G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of DAC 1997, pages 526--529, 1997.

Digital Library

[11]

B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2):291--307, 1970.

[12]

Y. Levendel, P. Menon, and S. Patel. Special purpose computer for logic simulation using distributed processing. Bell System Technical Journal, 61(10):2873--2909, 1982.

[13]

M. Marek-Sadowska and S.-P. Lin. Timing driven placement. In Proceedings of ICCAD 1989, pages 94--97, 1989.

[14]

D. McGrath. Cadence teams with Wind River, rolls verification platform. EE Times, April 28th, 2010, April 2010.

[15]

M. D. Moffitt and G. E. Günther. Scalable scheduling for hardware-accelerated functional verification. In Proceedings of ICAPS 2011 (to appear), 2011.

[16]

G. Moretti. Mentor quadruples Veloce hardware emulation capacity. EE Times, December 16th, 2008, December 2008.

[17]

D. A. Papa and I. L. Markov. Hypergraph partitioning and clustering. In Approximation Algorithms and Metaheuristics, 2007.

[18]

S. Patil, P. Banerjee, and C. Polychronopoulos. Efficient circuit partitioning algorithms for parallel logic simulation. In Proceedings of the 1989 Conference on Supercomputing, pages 361--370, 1989.

Digital Library

[19]

J. A. Roy and I. L. Markov. Partitioning-driven techniques for VLSI placement. In C. Alpert, D. Mehta, and S. Sapatnekar, editors, Handbook of Algorithms for VLSI Physical Design Automation, 2008.

[20]

S. Sapatnekar. Timing. Springer-Verlag, New York, NY, USA, 2004.

Digital Library

[21]

K.-D. Schubert. POWER7 - verification challenge of a multi-core processor. In Proceedings of ICCAD 2009, pages 809--812, 2009.

Digital Library

[22]

R. J. Smith. Fundamentals of parallel logic simulation. In Proceedings of DAC 1986, pages 2--12, 1986.

Digital Library

[23]

S. P. Smith, B. Underwood, and M. R. Mercer. An analysis of several approaches to circuit partitioning for parallel logic simulation. In Proceedings of ICCD 1987, pages 664--667, 1987.

[24]

L. Soulé and T. Blank. Parallel logic simulation on general purpose machines. In Proceedings of DAC 1988, pages 166--171, 1988.

Digital Library

[25]

C. Sporrer and H. Bauer. Corolla partitioning for distributed logic simulation of VLSI-circuits. In Proceedings of PADS 1993, pages 85--92, 1993.

Digital Library

[26]

B. Wile, J. Goss, and W. Roesner. Comprehensive Functional Verification: The Complete Industry Cycle (Systems on Silicon). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005.

Digital Library

[27]

L. Zhu, G. Chen, B. K. Szymanski, C. Tropper, and T. Zhang. Parallel logic simulation of million-gate VLSI circuits. In Proceedings of MASCOTS 2005, pages 521--524, 2005.

Digital Library

Cited By

Lin PLi KXiao ZChen CYu S(2021)Work in Progress: Path-based Graph Partition for Parallel Hardware-accelerated Functional Verification2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00061(497-500)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00061
Moffitt MGünther GPasnik KHenkel J(2013)Place and route for massively parallel hardware-accelerated functional verificationProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561920(466-472)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561920
Lingfeng Wang Yangdong Steve Deng (2013)Logic process merging for conservative parallel simulation of logic circuits2013 IEEE 4th International Conference on Software Engineering and Service Science10.1109/ICSESS.2013.6615484(1037-1040)Online publication date: May-2013
https://doi.org/10.1109/ICSESS.2013.6615484
Show More Cited By

Index Terms

Robust partitioning for hardware-accelerated functional verification

Recommendations

Hardware-accelerated generation of 3D diffusion-limited aggregation structures

The diffusion and aggregation of particles in a medium can result in complex geometric forms with an artistic interpretation, yet these aggregates can represent many natural processes as well. Although the method is quite simple, it takes many particles ...
Implementations of hardware acceleration for MD4-family algorithms based on GPU
ASID'09: Proceedings of the 3rd international conference on Anti-Counterfeiting, security, and identification in communication

The MD4-family algorithms have been widely applied in cryptographic field. Nowadays, it is discovered that MD4- family algorithms are also suitable for random number generators. Since the MD4-family algorithms are computing intensive, they can be ...
A Nested Partitioning Algorithm for Adaptive Meshes on Heterogeneous Clusters
ICS '15: Proceedings of the 29th ACM on International Conference on Supercomputing

In the era of the accelerator, load balancing strategies that are well-understood for traditional homogeneous supercomputers must be re-worked in order to address the problem of distributing work across heterogeneous hardware such that neither the CPU ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '11: Proceedings of the 48th Design Automation Conference

June 2011

1055 pages

ISBN:9781450306362

DOI:10.1145/2024724

General Chair:
Leon Stok
IBM Corp., Hopewell Jct., NY
,
Program Chairs:
Nikil Dutt
Univ. of California, Irvine, CA
,
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2011 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 Council on Electronic Design Automation (CEDA)

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '11

Sponsor:

EDAC
SIGDA

DAC '11: The 48th Annual Design Automation Conference 2011

June 5 - 10, 2011

California, San Diego

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

7
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lin PLi KXiao ZChen CYu S(2021)Work in Progress: Path-based Graph Partition for Parallel Hardware-accelerated Functional Verification2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00061(497-500)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00061
Moffitt MGünther GPasnik KHenkel J(2013)Place and route for massively parallel hardware-accelerated functional verificationProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561920(466-472)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561920
Lingfeng Wang Yangdong Steve Deng (2013)Logic process merging for conservative parallel simulation of logic circuits2013 IEEE 4th International Conference on Software Engineering and Service Science10.1109/ICSESS.2013.6615484(1037-1040)Online publication date: May-2013
https://doi.org/10.1109/ICSESS.2013.6615484
Moffitt MGunther GPasnik K(2013)Place and route for massively parallel hardware-accelerated functional verification2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2013.6691158(466-472)Online publication date: Nov-2013
https://doi.org/10.1109/ICCAD.2013.6691158
Mammo BChatterjee DPidan DNahir AZiv AMorad RBertacco VRosenstiel WMacii E(2012)Approximating checkers for simulation accelerationProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492745(153-158)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2492745
Mammo BChatterjee DPidan DNahir AZiv AMorad RBertacco V(2012)Approximating checkers for simulation acceleration2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.1109/DATE.2012.6176449(153-158)Online publication date: Mar-2012
https://doi.org/10.1109/DATE.2012.6176449
Moffitt MGünther G(2011)Scalable scheduling for hardware-accelerated functional verificationProceedings of the Twenty-First International Conference on International Conference on Automated Planning and Scheduling10.5555/3038485.3038507(162-169)Online publication date: 11-Jun-2011
https://dl.acm.org/doi/10.5555/3038485.3038507

View Options

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