隨著半導體製程持續的縮減，標準元件也變得更小。因此，設計規則的數量大幅增加，讓實體設計流程變得更困難，尤其是標準元件的繞線階段，很多設計規則違反可能會出現在此階段。由於複雜的設計規則和有限的繞線資源，腳位可連接性就是其中一個主要影響設計規則違反的原因。為了要解決這個的問題，很多以前的研究會運用機器學習的方法，並且在訓練的過程中使用全域繞線擁擠程度和局部腳位密度當作主要的特徵來預測一個局部的地方有沒有設計規則違反。但是從經驗上來看，在先進製程中，設計規則的出現其實和這兩個特徵沒有很強烈的直接關聯。在這本論文中的第一個主題，我們提出第一個基於深度學習並且使用腳位圖騰當作主要的特徵的設計規則違反預測模型去直接預測一個給定的局部的區域中，是否存在一個因為不好的腳位可連接性所造成的設計規則違反。和大部分現存的模型只能用於預測設計規則違反，我們提出的模型可以被用來引導設計流程中的詳細布局的腳位可連接性最佳化問題。實驗結果秀出，在所有定量的指標比較，我們提出的模型是比先前的研究出色很多的。而且，再運用我們所提出的基於模型引導下的詳細布局流程，設計規則違反的數量也有戲劇化的減少。
雖然用腳位圖騰訓練出來的基於深度學習的模型在設計規則違反預測問題上已經可以達到很好的成果，但是這樣的模型並不通用，因為這樣的模型是用特定設計內的腳位圖騰所訓練出來的，也因此這個訓練好的模型只能被運用在同樣的設計上做設計規則違反辨認。所以，設計一個可以預測更多設計的設計規則違反模型變得非常重要。幾個最先進的研究中，都是針對同樣的設計使用監督式學習的模型來解決設計規則違反預測問題。然而，那些監督式學習方法會事先準備非常多已經繞線好的設計來萃取所有訓練資料的標籤，這不僅會造成在準備訓練資料上的負擔，而且已經訓練好的模型也不能被用在其他使用不同標準元件資料庫的設計上。在此本論文的第二個主題中，我們提出第一個只拿標準元件資料庫當作輸入資料，基於活動學習的腳位可連接性預測。有別於現存的研究都是針對特定的設計做訓練，我們提出一個和設計無關的模型，而此模型可以被用於使用同一個標準元件資料庫集合的所有設計。實驗結果證實，我們所提出的模型可以被用來預測兩個使用不同標準元件資料庫的設計，而且我們提出的基於標準元件資料庫的訓練模型在設計規則違反的數量和第二層金屬短路的數量上也優於針對設計的訓練模型。
除了標準元件的腳位可連接性，標準元件持續縮小也造成了積體電路中的時序問題、能量問題、電子遷移問題等等…，為了擺平這些問題，一種新架構叫做結構性的事先繞線被提出。這種事先繞線種類具有低電阻和備用的金屬和導通孔，所以時序和良率可以獲得改進。但是這種事先繞線很大，變成了插入事先繞線在設計中的主要問題。在此本論文的最後一個主題，我們提出了一個基於深度學習的方法來在元件合法化步驟預測結構性事先繞線的插入性。更多的是，我們運用了一個模型視覺化的方法叫〝引導式反向傳遞〞來深入探勘我們的模型並且辨識出那些造成結構性事先繞線插入失敗的特徵。實驗結果不只秀出了我們的模型擁有很好的表現，還秀出了在元件合法化過程中避免擺出事先偵測過的特徵可以比商業工具中基於結構性是先繞線插入能力的元件合法化方法提高更多的結構性事先繞線插入率。

With the continuous scaling down of process nodes, standard cells become much smaller. Thus, the number of design rules is dramatically increased. This really increases the difficulty of physical design flow especially for the standard cell routing stage. Lots of design rule violations (DRVs) may emerge in this stage. Pin accessibility is one of the major issues causing DRVs due to the complex design rules and limited routing resources. To tackle this problem, many recent works apply machine learning-based techniques to predict whether a local region has DRV or not by regarding global routing (GR) congestion and local pin density as the main features during the training process. Empirically, however, DRV occurrence is not necessary to be strongly correlated with the two features in advanced nodes. In the first topic in this dissertation, we propose the first work of deep learning-based DRV prediction using pin pattern as our major feature to directly identify whether a DRV will exist or not due to bad pin accessibility of the given pin pattern. Unlike most of existing models that can only be used for DRV prediction, the proposed models can be applied to guide detailed placement for pin accessibility optimization during physical design. Experimental results show that the proposed models are greatly superior than those of previous studies in terms of all quantitative metrics. Additionally, the numbers of DRVs can be dramatically reduced by applying the proposed model-guided detailed placement flow.

Although the deep learning-based model trained by pin patterns already achieves a good performance on DRV prediction problem, it is not general since the model is trained by the pin patterns from a specific design, and thus the trained model can only be applied on the same design for DRV identification. Therefore, it is important to design a model which can be applied to predict more designs. The state-of-the-art works address the DRV prediction problem on the same design by the supervised machine learning approach. However, those supervised learning approaches extract all training data labels by preparing a lot of routed designs in advance, giving rise to the large effort on training data preparation and the pre-trained model cannot be applied to predict other designs with different referenced cell libraries. In the second topic of this dissertation, we propose the first work of active learning-based pin accessibility prediction (PAP) by regarding the standard cell libraries as the only input. Unlike most of existing researches aim at design-specific training, we proposed a library-based model which can be applied to those designs referencing to the same standard cell library set. Experimental results show that the proposed model can be applied to predict two different designs with different referenced cell library set. The number of remaining DRVs and M2 shorts of the designs optimized by the proposed model are also superior than the design-specific models.

Besides pin accessibility of standard cells, the shrinking of standard cell size opposes the problem of integrated circuit (IC) such as timing, power and electromigration (EM), etc. To tackle these problems, a new style structural pre-route (SPR) is proposed. Such type of pre-route is composed of redundant parallel metals and vias so that the low resistance and the redundant sub-structures can improve the timing and yield. But the large area cost becomes the major problem of inserting such pre-routes all over a design. In the final topic of this dissertation, we propose a machine learning-based approach to predict the insertability of SPRs during the cell legalization stage. Furthermore, we apply a critical pattern visualization technique based on a guided-backpropagation algorithm to see in depth of our model and identify the problematic features causing SPR insertion failures. The experimental results not only show that the excellent performance of our model but also show that avoiding generating the identified critical features during legalization can improve SPR insertability compared to the build-in SPR-aware placement approach of a commercial tool.

[1] C. Yu, and Z. Zhang. \Painting on Placement: Forecasting Routing Congestion
using Conditional Generative Adversarial Nets," In Proc. Design Automation
Conference (DAC), 2019.
[2] Y. Lin, S. Dhar, W. Li, H. Ren, B. Khailany, and D. Z. Pan. \DREAM-
Place: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI
Placement," In Proc. Design Automation Conference (DAC), 2019.
[3] E. C. Barboza, N. Shukla, Y. Chen, and J. Hu. \Machine Learning-Based
Pre-Routing Timing Prediction with Reduced Pessimism," In Proc. Design
Automation Conference (DAC), 2019.
[4] Y. H. Huang, Z. Xie, G. Q. Fang, T. C. Yu, H. Ren, S. Y. Fang, Y. Chen, and
J. Hu. \Routability-Driven Macro Placement with Embedded CNN-Based Pre-
diction Model," In Proc. Design, Automation and Test in Europe Conference
and Exhibition (DATE), 2019.
[5] W. T. J. Chan, P.-H. Ho, A. B. Kahng, and P. Saxena, \Routability Op-
timization for Industrial Designs at Sub-14nm Process Nodes Using Machine
Learning," In Proc. International Symposium on Physical Design (ISPD), 2017.
[6] Q. Zhou, X. Wang, Z. Qi, Z. Chen, Q. Zhou, and Y. Cai. \An accurate detailed
routing routability prediction model in placement." In Proc. Asia Symposium
on Quality Electronic Design (ASQED), 2015.
[7] A. F. Tabrizi, N. K. Darav, S. Xu, L. Rakai, I. Bustany, A. Kennings and L.
Behjat. \A Machine Learning Framework to Identify Detailed Routing Short
Violations from a Placed Netlist." In Proc. Design Automation Conference
(DAC), 2018.
[8] Z. Qi, Y. Cai and Q. Zhou. \Accurate Prediction of Detailed Routing Conges-
tion using Supervised Data Learning." In Proc. International Conference on
Computer Design (ICCD), 2014.
[9] Y. T. Yu, G. H. Lin, I. H. R. Jiang and C. Chiang. \Machine-Learning-Based
Hotspot Detection Using Topological Classication and Critical Feature Extrac-
tion" In IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems (TCAD), vol. 34, no. 3, pp. 460-470, 2015.
[10] A. F. Tabrizi, N. K. Darav, L. Rakai, A. Kennings and L. Behjat. \Detailed
Routing Violation Prediction During Placement Using Machine Learning." In
Proc. VLSI Design, Automation and Test (VLSI-DAT), 2017.
[11] W. T. J. Chan, Y. Du, A. B. Kahng, S. Nath and K. Samadi. \BEOL stack-
aware routability prediction from placement using data mining techniques" In
Proc. International Conference on Computer Design (ICCD), 2016.
[12] Z. Xie, Y. H. Huang, G. C. Fang, H. Ren, S. Y. Fang, Y. Chen and J. Hu.
\RouteNet: Routability Prediction for Mixed-Size Designs Using Convolutional
Neural Network." In Proc. International Conference on Computer-Aided De-
sign (ICCAD), 2018.
[13] T. C. Yu, S. Y. Fang, H. S. Chiu, K. S. Hu, P. H. Y. Tai, C. C. F. Shen,
and H. Sheng. \Pin Accessibility Prediction and Optimization with Deep
Learning-based Pin Pattern Recognition." In Proc. Design Automation Con-
ference (DAC), 2019.
[14] X. Xu, B. Yu, J. R. Gao, C. L. Hsu and D. Z. Pan. \PARR: Pin Access
Planning and Regular Routing for Self-Aligned Double Patterning." In Proc.
Design Automation Conference (DAC), 2015.
[15] X. Xu, B. Yu, J. R. Gao, C. L. Hsu and D. Z. Pan. \PARR: Pin Access Planning
and Regular Routing for Self-Aligned Double Patterning." ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 21, no. 3, article
42, 2016.
[16] X. Xu, Y. Lin, V. Livramento and D. Z. Pan. \Concurrent Pin Access Opti-
mization for Unidirectional Routing." In Proc. Design Automation Conference
(DAC), 2017.
[17] J. Seo, J. Jung, S. Kim and Y. Shin. \Pin Accessibility-Driven Cell Layout Re-
design and Placement Optimization." In Proc. Design Automation Conference
(DAC), 2017.
[18] W. Ye, B. Yu, D. Z. Pan, Y. C. Ban and L. Liebmann. \Standard Cell Layout
Regularity and Pin Access Optimization Considering Middle-of-Line." In Proc.
Great Lakes Symposium on VLSI (GLSVLSI), 2015.
[19] Y. Ding, C. Chu and W. K. Mak. \Pin Accessibility-Driven Detailed Placement
Renement." In Proc. International Symposium on Physical Design (ISPD),
2017.
[20] M. M. Ozdal. \Detailed-Routing Algorithms for Dense Pin Clusters in Inte-
grated Circuits." IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems (TCAD), vol. 28, no. 3, pp. 340-349, 2009.
[21] X. Xu, B. Cline, G. Yeric, B. Yu and D. Z. Pan. \Self-Aligned Double Pattern-
ing Aware Pin Access and Standard Cell Layout Co-Optimization." In Proc.
International Symposium on Physical Design (ISPD), 2014.
[22] X. Xu, B. Cline, G. Yeric, B. Yu and D. Z. Pan. \Self-Aligned Double Pat-
terning Aware Pin Access and Standard Cell Layout Co-Optimization." IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems
(TCAD), vol. 34, no. 5, pp. 699{712, 2015.
[23] M. Pan, N. Viswanathan and C. Chu. \An Ecient and Eective Detailed
Placement Algorithm." IEEE Transactions on Computer-Aided Design of In-
tegrated Circuits and Systems (TCAD), pp. 48{55, 2005.
[24] P. Spindler, U. Schlichtmann, and F. M. Johannes. \Abacus: Fast Legalization
of Standard Cell Circuits with Minimal Movement." In Proc. International
Symposium on Physical Design (ISPD), 2008.
[25] K. H. Tseng, Y. W. Chang and C. C. C. Liu. \Minimum-Implant-Area-Aware
Detailed Placement with Spacing Constraints." In Proc. Design Automation
Conference (DAC), 2016.
[26] Z. W. Lin and Y. W. Chang. \Detailed Placement for Two-Dimensional Di-
rected Self-Assembly Technology." In Proc. Design Automation Conference
(DAC), 2017.
[27] P. Debacker, K. Han, A. B. Kahng, H. Lee, P. Raghavan and L.Wang. \Vertical
M1 Routing-Aware Detailed Placement for Congestion and Wirelength Reduc-
tion in Sub-10nm Nodes." In Proc. Design Automation Conference (DAC),
2017.
[28] D. Vasisht, A. Damianou, M. Varma, and A. Kapoor. \Active learning for
sparse Bayesian multilabel classication." In Proc. Special Interest Group on
Knowledge Discovery and Data Mining (SIGKDD), 2014.
[29] P. Melville and R. J. Mooney. \Diverse ensembles for active learning." In Proc.
21th International Conference on Machine Learning (ICML), 2004.
[30] I. Guyon, G. Cawley, V. Lemaire, and G. Dror. \Results of the active learning
challenge." Journal of Machine Learning Research (JMLR). vol. 16, pp. 19-45,
2011.
[31] M. Wang and X.-S. Hua. \Active learning in multimedia annotation and re-
trieval: A survey." ACM Transactions on Intelligent Systems and Technology
(TIST). vol. 2, no. 2, pp. 1-21, 2011.
[32] Y. Chen and A. Krause. \Near-optimal batch mode active learning and
adaptive submodular optimization." Journal of Machine Learning Research
(JMLR). vol. 28, no. 1, pp. 160-168, 2013.
[33] S. Tong and D. Koller. \Support vector machine active learning with applica-
tions to text classication." Journal of Machine Learning Research (JMLR).
vol. 2, pp. 45-66, 2001.
[34] J. Zhu and M. Ma. \Uncertainty-based active learning with instability es-
timation for text classication." ACM Transactions on Audio, Speech, and
Language Processing. vol. 8, no. 4, pp. 1-21, 2012.
[35] M. Park and J. W. Pillow. \Bayesian active learning with localized priors for
fast receptive eld characterization." In Proc. Neural Information Processing
Systems (NIPS), 2012.
[36] W. Luo, A. Schwing, and R. Urtasun. \Latent structured active learning." In
Proc. Neural Information Processing Systems (NIPS), 2013.
[37] N. V. Cuong, W. S. Lee, N. Ye, K. M. A. Chai, and H. L. Chieu. \Active
learning for probabilistic hypotheses using the maximum Gibbs error criterion."
In Proc. Neural Information Processing Systems (NIPS), 2013.
[38] B. Du, Z. Wang, L. Zhang, L. Zhang, W. Liu, J. Shen, and D. Tao. \Exploring
representativeness and informativeness for active learning." IEEE Transactions
on Cybernetics. vol. 47, no. 1, pp. 14{26, 2017.
[39] X. Li, D. Kuang, and C. X. Ling. \Active learning for hierarchical text classi-
cation." In Proc. Pacic-Asia Conference on Knowledge Discovery and Data
Mining (PAKDD), 2012.
[40] I. Dino, B. Albert, Z. Indre, and P. Bernhard. \Clustering based active learning
for evolving data streams." In Proc. Discovery Science, 2013.
[41] R. Chattopadhyay et al. \Batch mode active sampling based on marginal prob-
ability distribution matching." In Proc. Special Interest Group on Knowledge
Discovery and Data Mining (SIGKDD), 2012.
[42] Y. Fu, B. Li, X. Zhu, and C. Zhang. \Active learning without knowing individ-
ual instance labels." IEEE Transactions on Knowledge and Data Engineering
(TKDE). vol. 26, no. 4, pp. 808-822, Apr. 2014.
[43] T. Reitmaier, A. Calma, and B. Sick. \Transductive active learningA new semi-
supervised learning approach based on iteratively rened generative models to
capture structure in data." Information Sciences. vol. 293, pp. 275-298, Feb.
2015.
[44] K. Simonyan, A. Vedaldi, and A. Zisserman. \Deep inside convolu-
tional networks:Visualising image classication models and saliency maps."
In arXiv:1312.6034, also appeared at ICLR Workshop 2014, 2014. URL
http://arxiv.org/abs/1312.6034.
[45] M. D. Zeiler and R. Fergus. \Visualizing and understanding convolutional
networks." In Proc. European Conference on Computer Vision (ECCV). 2014.
[46] J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller. \Striving for
simplicity: The all convolutional net." arXiv:1412.6806. 2014. 5
[47] Synopsys ICC2 user guide. https://www.synopsys.com
[48] Tensorow C++ Reference. https://www.tensorflow.org/api docs/cc/