(18.210.12.229) 您好!臺灣時間:2021/03/03 15:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王友伶
研究生(外文):Yu-Ling Wang
論文名稱:降低預執行最佳化的負面影響於使用者輸入相關的程式
論文名稱(外文):Minimizing Negative Impact from Input-sensitive Profiling Guided Optimization
指導教授:徐慰中
口試日期:2017-07-23
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:27
中文關鍵詞:編譯器優化預執行優化輸入靈敏度
外文關鍵詞:CompilerOptimizationProfile guided optimizationinput sensitivity
相關次數:
  • 被引用被引用:0
  • 點閱點閱:70
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
預執行優化技巧是編譯器利用程式實際執行的行為來做優化,但前提 是先前收集到的程式特徵要和真實線上情況相近,否則預執行優化技 巧會傷害程式效能。這個研究討論在 LLVM 上的抽樣預執行優化的流 程,舉出了一些預執行優化降低程式效能的例子,並且嘗試以線性合 併靜態分支預測與收集到的程式特徵來做保守的預執行優化。實驗結 果顯示此方法在一些程式之中降低預執行優化的負面影響。
Profile Guided Optimizations (PGO) exploit runtime profile information from sample runs to predict the execution behavior of a program. However, the premise of PGO is that the profile of a sample run could likely represent the behavior of the program execution in general. In some conditions, this premise is not true, and when that happens, profile-guided optimizations may not help. Worse yet, they could significantly degrade the performance of the program. This work discusses the sampling profile guided optimizations adopted in LLVM and shows performance degradation of multiple pro- grams after PGO applied. We propose a conservative approach of using a linear combination of static branch prediction and the gathered branch profile from sample runs to guide optimizations. Such a combination has shown to be effective on reducing the negative impact of the original PGO in LLVM on multiple programs.
口試委員會審定書 iii
摘要 v
Abstract vii
1 Introduction 1
2 Background 5
2.1 Profile guided optimization 5
2.1.1 Instrumentation based 5
2.1.2 Sampling based 6
2.2 AutoFDO 7
2.3 SamplePGO in LLVM 7
2.4 LLVM Sample PGO Related Optimization 8
2.4.1 Function inline 8
2.4.2 Change select instruction to branch 8
2.4.3 Basic block frequency related optimization 8
3 Sampling PGO flow and Problem description 9
3.1 Flow of sampling PGO with perf, AutoFDO and LLVM 9
3.2 An example of performance impact of PGO 11
3.2.1 Original version from tutorial website 12
3.2.2 Modified version 12
3.3 Performance impact of 456.hmmer in SPEC2006 13
3.4 Problem Description 13
4 Experimental Evaluate 15
4.1 Implementation of linear combination of branch probability in LLVM 15
4.2 Experiment configure and benchmark description 16
4.3 Experiment results 16
4.4 Discussion 19
4.4.1 Bubble sort 19
5 Related Work 21
5.1 Sampling PGO and performance monitor unit 21
5.2 Evaluation of PGO 22
5.3 Multiple input handling in PGO 22
5.4 Sampling errors and rectifying 22
6 Conclusion 23
Bibliography 25
[1] Ivan Baev. 2012. Profile-based Indirect Call Promotion. LLVM Developers’ Meeting. (2012). Qualcomm Innovation Center.
[2] Paul Berube and José Nelson Amaral. 2007. Benchmark Design for Robust Profile-Directed Optimization. 2007 SPEC Benchmark Workshop. (2007).
[3] Paul Berube and José Nelson Amaral. 2012. Combined pro ling: A methodology to capture varied program behavior across multiple inputs. In 2012 IEEE International Symposium on Performance Analysis of Systems & Software, New Brunswick, NJ, USA, April 1-3, 2012. 210–220. https://doi.org/10.1109/ISPASS.2012.6189227
[4] Paul Berube, José Nelson Amaral, Rayson Ho, and Raúl Silvera. 2009. Workload Reduction for Multi-input Feedback-Directed Optimization. In Proceedings of the CGO 2009, The Seventh International Symposium on Code Generation and Optimization, Seattle, Washington, USA, March 22-25, 2009. 59–69. https://doi.org/10.1109/ CGO.2009.23
[5] Dehao Chen, David Xinliang Li, and Tipp Moseley. 2016. AutoFDO: automatic feedback-directed optimization for warehouse-scale applications. In Proceedings of the 2016 International Symposium on Code Generation and Optimization, CGO 2016, Barcelona, Spain, March 12-18, 2016. 12–23. https://doi.org/10.1145/2854038.2854044
[6] DehaoChen,Neil Vachharajani,Robert Hundt,Shih-wei Liao,Vinodha Ramasamy, Paul Yuan, Wenguang Chen, and Weimin Zheng. 2010. Taming hardware event samples for FDO compilation. In Proceedings of the CGO 2010, The 8th International Symposium on Code Generation and Optimization, Toronto, Ontario, Canada, April 24-28, 2010. 42–52. https://doi.org/10.1145/1772954.1772963
[7] Wei-Chung Hsu, Howard Chen, Pen-Chung Yew, and Dong-yuan Chen. 2002. On the Predictability of Program Behavior Using Different Input Data Sets. In 6th Annual Workshop on Interaction between Compilers and Computer Architecture (INTERACT-6 2002), 3 February 2002, Boston, MA, USA. 45–53. https://doi.org/10. 1109/INTERA.2002.995842
[8] Andi Kleen. 2013. pmu-tools. (2013). https://github.com/andikleen/pmu-tools
[9] Roy Levin, Ilan Newman, and Gadi Haber. 2008. Complementing Missing and Inaccurate Pro ling Using a Minimum Cost Circulation Algorithm. In High Performance Embedded Architectures and Compilers, Third International Conference, HiPEAC 2008, Göteborg, Sweden, January 27-29, 2008, Proceedings. 291–304. https: //doi.org/10.1007/978-3-540-77560-7_20
[10] David Levinthal and Dehao Chen. 2014. Gooda. (2014). https://github.com/David- Levinthal/gooda
[11] Diego Novillo. 2014. SamplePGO: the power of profile guided optimizations with- out the usability burden. In Proceedings of the 2014 LLVM Compiler Infrastructure in HPC, LLVM 2014, New Orleans, LA, USA, November 17, 2014. 22–28. https: //doi.org/10.1109/LLVM-HPC.2014.8
[12] Vinodha Ramasamy, Paul Yuan, Dehao Chen, and Robert Hundt. 2008. Feedback- Directed Optimizations in GCC with Estimated Edge Profiles from Hardware Event Sampling. In Proceedings of GCC Summit 2008. 87–102. http://www.capsl.udel.edu /conferences/open64/2008/Papers/113.pdf
[13] Baptiste Wicht, Roberto A. Vitillo, Dehao Chen, and David Levinthal. 2014. Hard- ware Counted Profile-Guided Optimization. CoRR abs/1411.6361 (2014). http: //arxiv.org/abs/1411.6361
[14] Bo Wu, Mingzhou Zhou,Xipeng Shen,Yaoqing Gao,Raúl Silvera, and Graham Yiu. 2013. Simple Profile Rectfications Go a Long Way - Statistically Exploring and Alleviating the Effects of Sampling Errors for Program Optimizations. In ECOOP 2013 - Object-Oriented Programming - 27th European Conference, Montpellier, France, July 1-5, 2013. Proceedings. 654–678. https://doi.org/10.1007/978-3-642-39038-8_27
[15] Ahmad Yasin. 2014. A Top-Down method for performance analysis and couters architecture. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2014, Monterey, CA, USA, March 23-25, 2014. 35–44. https://doi.org/10.1109/ISPASS.2014.6844459
[16] Mingzhou Zhou, Bo Wu, Xipeng Shen, Yaoqing Gao, and Graham Yiu. 2016. Examining and Reducing the Influence of Sampling Errors on Feedback-Driven Optimizations. TACO 13, 1 (2016), 6:1–6:24. https://doi.org/10.1145/2851502
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔