research-article

High Performance Graph Convolutional Networks with Applications in Testability Analysis

Authors:

Brucek Khailany,

Harbinder Sikka,

Karthikeyan Natarajan,

Bei YuAuthors Info & Claims

DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

Article No.: 18, Pages 1 - 6

https://doi.org/10.1145/3316781.3317838

Published: 02 June 2019 Publication History

Abstract

Applications of deep learning to electronic design automation (EDA) have recently begun to emerge, although they have mainly been limited to processing of regular structured data such as images. However, many EDA problems require processing irregular structures, and it can be non-trivial to manually extract important features in such cases. In this paper, a high performance graph convolutional network (GCN) model is proposed for the purpose of processing irregular graph representations of logic circuits. A GCN classifier is firstly trained to predict observation point candidates in a netlist. The GCN classifier is then used as part of an iterative process to propose observation point insertion based on the classification results. Experimental results show the proposed GCN model has superior accuracy to classical machine learning models on difficult-to-observation nodes prediction. Compared with commercial testability analysis tools, the proposed observation point insertion flow achieves similar fault coverage with an 11% reduction in observation points and a 6% reduction in test pattern count.

References

[1]

E. Cai, D.-C. Juan, S. Garg, J. Park, and D. Marculescu, "Learning-based power/performance optimization for many-core systems with extended-range voltage/frequency scaling," IEEE TCAD, vol. 35, no. 8, pp. 1318--1331, 2016.

Digital Library

[2]

Y. Ma, S. Roy, J. Miao, J. Chen, and B. Yu, "Cross-layer optimization for high speed adders: A pareto driven machine learning approach," IEEE TCAD, 2018.

[3]

W. Haaswijk, E. Collins, B. Seguin, M. Soeken, F. Kaplan, S. Süsstrunk, and G. De Micheli, "Deep learning for logic optimization algorithms," in Proc. ISCAS, 2018, pp. 1--4.

[4]

Z. Xie, Y.-H. Huang, G.-Q. Fang, H. Ren, S.-Y. Fang, Y. Chen, and J. Hu, "RouteNet: Routability prediction for mixed-size designs using convolutional neural network," in Proc. ICCAD, 2018, pp. 80:1--80:8.

Digital Library

[5]

H. Yang, S. Li, Y. Ma, B. Yu, and E. F. Young, "GAN-OPC: Mask optimization with lithography-guided generative adversarial nets," in Proc. DAC, 2018, pp. 131:1--131:6.

Digital Library

[6]

N. Selvakkumaran and G. Karypis, "Multiobjective hypergraph-partitioning algorithms for cut and maximum subdomain-degree minimization," IEEE TCAD, vol. 25, no. 3, pp. 504--517, 2006.

Digital Library

[7]

T.-H. Lee and T.-C. Wang, "Congestion-constrained layer assignment for via minimization in global routing," IEEE TCAD, vol. 27, no. 9, pp. 1643--1656, 2008.

Digital Library

[8]

A. B. Kahng, C.-H. Park, X. Xu, and H. Yao, "Layout decomposition approaches for double patterning lithography," IEEE TCAD, vol. 29, pp. 939--952, June 2010.

Digital Library

[9]

B. Yu, K. Yuan, D. Ding, and D. Z. Pan, "Layout decomposition for triple patterning lithography," IEEE TCAD, vol. 34, no. 3, pp. 433--446, March 2015.

[10]

K.-T. Cheng and C.-J. Lin, "Timing-driven test point insertion for full-scan and partial-scan BIST," in Proc. ITC, 1995, pp. 506--514.

Digital Library

[11]

T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," Proc. ICLR, 2016.

[12]

W. Hamilton, Z. Ying, and J. Leskovec, "Inductive representation learning on large graphs," in Proc. NIPS, 2017, pp. 1024--1034.

Digital Library

[13]

R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, "Graph convolutional neural networks for web-scale recommender systems," in Proc. KDD, 2018, pp. 974--983.

Digital Library

[14]

H. Cai, V. W. Zheng, and K. Chang, "A comprehensive survey of graph embedding: problems, techniques and applications," IEEE TKDE, vol. 30, no. 9, pp. 1616--1637, 2018.

[15]

S. Bhagat, G. Cormode, and S. Muthukrishnan, "Node classification in social networks," in Social network data analytics. Springer, 2011, pp. 115--148.

[16]

A. Grover and J. Leskovec, "node2vec: Scalable feature learning for networks," in Proc. KDD, 2016, pp. 855--864.

Digital Library

[17]

B. Krishnamurthy, "A dynamic programming approach to the test point insertion problem," in Proc. DAC, 1987, pp. 695--705.

Digital Library

[18]

A. J. Briers and K. A. E. Totton, "Random pattern testability by fast fault simulation," in Proc. ITC, 1986.

[19]

M. Geuzebroek, J. T. Van Der Linden, and A. Van de Goor, "Test point insertion that facilitates atpg in reducing test time and data volume," in Proc. ITC, 2002, pp. 138--147.

Digital Library

[20]

N. Tamarapalli and J. Rajski, "Constructive multi-phase test point insertion for scan-based bist," in Proc. ITC, 1996, pp. 649--658.

Digital Library

[21]

J.-S. Yang, N. A. Touba, B. Nadeau-Dostie et al., "Test point insertion with control points driven by existing functional flip-flops," IEEE TC, vol. 61, no. 10, pp. 1473--1483, 2012.

Digital Library

[22]

N. A. Touba and E. J. McCluskey, "Test point insertion based on path tracing," in Proc. VTS, 1996, pp. 2--8.

Digital Library

[23]

H. Ren, M. Kusko, V. Kravets, and R. Yaari, "Low cost test point insertion without using extra registers for high performance design," in Proc. ITC, 2009, pp. 1--8.

[24]

H. F. Li and P. Lam, "A protocol extraction strategy for control point insertion in design for test of transition signaling circuits." in Proc. GLSVLSI, 1995, pp. 178--183.

Digital Library

[25]

Z. Li, S. K. Goel, F. Lee, and K. Chakrabarty, "Efficient observation-point insertion for diagnosability enhancement in digital circuits," in Proc. ITC, 2015, pp. 1--10.

[26]

L. H. Goldstein and E. L. Thigpen, "SCOAP: Sandia controllability/observability analysis program," in Proc. DAC, 1980, pp. 190--196.

Digital Library

[27]

V. Nair and G. E. Hinton, "Rectified linear units improve restricted boltzmann machines," in Proc. ICML, 2010, pp. 807--814.

Digital Library

Cited By

Wu NLi YYang HChen HDai SHao CYu CXie Y(2024)Survey of Machine Learning for Software-assisted Hardware Design Verification: Past, Present, and ProspectACM Transactions on Design Automation of Electronic Systems10.1145/366130829:4(1-42)Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1145/3661308
Mohamed Tvan Santen VAlrahis LSinanoglu OAmrouch H(2024)Graph Attention Networks to Identify the Impact of Transistor Degradation on Circuit ReliabilityIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2024.339746071:7(3269-3281)Online publication date: Jul-2024
https://doi.org/10.1109/TCSI.2024.3397460
Wang HZhang ZXiong HZou DChen YJin H(2024)GRAND: A Graph Neural Network Framework for Improved DiagnosisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333621243:4(1288-1301)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3336212
Show More Cited By

Recommendations

Exploiting node-feature bipartite graph in graph convolutional networks
Abstract
In recent years, Graph Convolutional Networks (GCNs), which extend convolutional neural networks to graph structure, have achieved great success on many graph learning tasks by fusing structure and feature information, such as node ...
Revisiting 2D Convolutional Neural Networks for Graph-Based Applications
Graph convolutional networks (GCNs) are widely used in graph-based applications such as graph classification and segmentation. However, current GCNs have limitations on implementation such as network architectures due to their irregular inputs. In ...
SGCN: A Graph Sparsifier Based on Graph Convolutional Networks
Advances in Knowledge Discovery and Data Mining
Abstract
Graphs are ubiquitous across the globe and within science and engineering. With graphs growing in size, node classification on large graphs can be space and time consuming, even with powerful classifiers such as Graph Convolutional Networks (GCNs)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

June 2019

1378 pages

ISBN:9781450367257

DOI:10.1145/3316781

Copyright © 2019 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

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: 02 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

DAC '19

Sponsor:

SIGDA

DAC '19: The 56th Annual Design Automation Conference 2019

June 2 - 6, 2019

NV, Las Vegas, USA

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

71
Total Citations
View Citations
1,214
Total Downloads

Downloads (Last 12 months)169
Downloads (Last 6 weeks)23

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu NLi YYang HChen HDai SHao CYu CXie Y(2024)Survey of Machine Learning for Software-assisted Hardware Design Verification: Past, Present, and ProspectACM Transactions on Design Automation of Electronic Systems10.1145/366130829:4(1-42)Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1145/3661308
Mohamed Tvan Santen VAlrahis LSinanoglu OAmrouch H(2024)Graph Attention Networks to Identify the Impact of Transistor Degradation on Circuit ReliabilityIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2024.339746071:7(3269-3281)Online publication date: Jul-2024
https://doi.org/10.1109/TCSI.2024.3397460
Wang HZhang ZXiong HZou DChen YJin H(2024)GRAND: A Graph Neural Network Framework for Improved DiagnosisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333621243:4(1288-1301)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3336212
Liu LYang FShang LZeng X(2024)GNN-Cap: Chip-Scale Interconnect Capacitance Extraction Using Graph Neural NetworkIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333194243:4(1206-1217)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3331942
Wang SWei SOkamoto HNishikawa TKai HHigami YYotsuyanagi HMa RNi TTakahashi HWen X(2024)Test Point Selection for Multi-Cycle Logic BIST using Multivariate Temporal-Spatial GCNs2024 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia62534.2024.10661324(1-6)Online publication date: 18-Aug-2024
https://doi.org/10.1109/ITC-Asia62534.2024.10661324
Zeng YCui X(2024)A High Performance PODEM Algorithm with the Improved Backtrace Process2024 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia62534.2024.10661307(1-6)Online publication date: 18-Aug-2024
https://doi.org/10.1109/ITC-Asia62534.2024.10661307
Zhao HYang FShan J(2024)A Graph AutoEncoder Approach for Fault Prediction in Test Pattern Generation2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10618040(462-467)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10618040
Li ZLi TLiu CWang LLiu CGuo YQu W(2024)Towards Evaluating SEU Type Soft Error Effects with Graph Attention Network2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617594(241-246)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617594
Qoutb AKawa JFriedman E(2024)Test Modules for Enhanced Testability of Single Flux Quantum Integrated CircuitsJournal of Electronic Testing10.1007/s10836-024-06141-7Online publication date: 24-Oct-2024
https://doi.org/10.1007/s10836-024-06141-7
Roy SMillican SAgrawal V(2024)A Survey and Recent Advances: Machine Intelligence in Electronic TestingJournal of Electronic Testing10.1007/s10836-024-06117-740:2(139-158)Online publication date: 15-Apr-2024
https://doi.org/10.1007/s10836-024-06117-7
Show More Cited By

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