臺灣博碩士論文加值系統

如今科技日新月異，具有多核系統架構的硬體已經逐漸普遍。而任務平行處理的機制也隨著硬體發展一同出現，將一個任務切割成多個項目分配給多個核心合力完成，目前已廣泛用於各種應用程序中，以獲得更好的執行效率。大多數以前的論文都嘗試找到最大的平行度（Max DOP），以實現最佳性能。但是，隨著硬體的尺寸的不斷縮小，製程的不斷變化，晶體管的磨損及老化效應（例如負偏壓溫度不穩定性（NBTI））已成為不可避免的威脅，可能會降低系統性能，甚至導致功能故障。除非解決此問題，否則多核心系統將面臨平均故障時間（MTTF）短的問題。我們觀察到，如果始終以最大的DOP執行任務，則系統中的所有核心都會持續受到NBTI的負面影響，並很快就會由於過於老化導致無法負擔任務內容。另一方面，如果我們可以減少DOP而又不會導致違反任何一個任務期限的情況，則某些核心就有機會被Power gating給暫時關閉，並從老化效應NBTI中恢復過來。在本文中，我們為多核系統提出了一種新穎的NBTI感知任務並行框架，以實現這種想法。我們的框架首先根據其重要性對已準備好的任務進行優先級排序，然後確定每個任務的最佳DOP，而不會引起時序衝突。在此之後，提出了一種兼顧IR-drop和核心利用率的任務-核心映射算法。最後，使用恢復決策算法來找到每個內核的合適恢復模式。實驗結果表明，與MAX DOP方法相比，提出的NBTI感知任務並行性框架可以成功地將系統壽命延長到3.7倍。

Task parallelism schemes with a multi-core system are widely used through various applications nowadays to obtain better throughput. Most of previous works will try to find maximum degree of parallelism (DOP) to achieve best performance. However, aging effects have become an unavoidable threat which may degrade system performance and even cause functional failure. We observe that if a task is always executed with maximum DOP, all cores may continuously suffer from the NBTI effect and ware out soon. On the other hand, if we can decrease DOP without causing task deadline violation, some cores may have opportunities to be power-gated and recover from the NBTI effect. In this paper, we propose a novel NBTI-aware task parallelism framework for multi-core systems to realize such an idea. Our framework first prioritizes ready tasks based on its criticality and then decide best DOP of each task without causing timing violation. After that, a task-to-core mapping algorithm which considers both IR-drop and core utilization is proposed. Finally, a recover decision algorithm is used to find the suitable recover mode of each core. Experimental results show that the proposed NBTI-aware task parallelism framework can successfully extend system lifetime to 3.7 times compared with MAX DOP method.

Title Page i
Letter of Approval ii
Abstract in Chinese iv
Abstract in English v
Acknowledgements vi
Table of Contents vii
List of Figures viii

Chapter 1. Introduction 1
1.1 Background 1
1.2 An Example 3
1.3 Main Contributions 4
1.4 Thesis Organization 5

Chapter 2. Related Works 6

Chapter 3. Problem Formulation 9
3.1 Core-level NBTI Stress/Recover Model 9
3.2 Application Model 11
3.3 IR-Drop Constraint 12
3.4 Motivation 13
3.5 Problem Formulation 14

Chapter 4. Algorithm 15
4.1 Task Priority And Slack Analysis 16
4.2 DOP Decision 18
4.3 NBTI Aware Task To Core Assignment 19
4.4 Core Recovery Decision 20

Chapter 5. Experimental Results 23

Chapter 6. Conclusion 27

References 28

[1]Xuanxia Yao, Peng Geng and Xiaojiang Du, A Task Scheduling Algorithm for Multi-core Processors, 2013 International Conference on Parallel and Distributed Computing, Applications and Technologies.
[2]Wei Zheng; Lu Tang and Rizos Sakellariou, A Priority-Based Scheduling Heuristic to Maximize Parallelism of Ready Tasks for DAG Applications, 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing.
[3]Qingqiang He; xu jiang; Nan Guan and Zhishan Guo, Intra-Task Priority Assignment in Real-Time Scheduling of DAG Tasks on Multi-cores, IEEE Transactions on Parallel and Distributed Systems.
[4]Jin Sun, Roman Lysecky, Karthik Shankar, Avinash Kodi, Ahmed Louri and Janet M. Wang, Workload Capacity Considering NBTI Degradation in Multi-core Systems, 2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC).
[5]Jin Sun; Avinash Kodi; Ahmed Louri and Janet M. Wang, NBTI Aware Workload Balancing in Multi-core System, 2009 10th International Symposium on Quality Electronic Design.
[6]Jinbin Tu; Tianhao Yang; Yi Zhang and Jin Sun, Particle Swarm Optimization Based Task Scheduling for Multi-core Systems Under Aging Effect, 2017 International Conference on Progress in Informatics and Computing (PIC).
[7]Tiago Rogerio Mück; Zana Ghaderi; Nikil D. Dutt and Eli Bozorgzadeh, Exploiting Heterogeneity for Aging-Aware Load Balancing in Mobile Platforms, IEEE Transactions on Multi-Scale Computing Systems (Volume:3, Issue:1, Jan.-March 1 2017), 25 – 35.
[8]Alireza Namazi; Meisam Abdollahi; Saeed Safari; Siamak Mohammadi and Masoud Daneshtalab, LRTM: Life-time and Reliability-aware Task Mapping Approach for Heterogeneous Multi-core System, 2018 11th International Workshop on Network on Chip Architectures (NoCArc).
[9]Daniele Rossi; Vasileios Tenentes; Saqib Khursheed and Bashir M. Al-Hashimi NBTI and Leakage Aware Sleep Transistor Design for Reliable and Energy Efficient Power Gating, 2015 20th IEEE European Test Symposium (ETS).
[10]R. Vattikonda; Wenping Wang and Yu Cao, Modeling and Minimization of PMOS NBTI Effect for Robust Nanometer Design, 2006 43rd ACM/IEEE Design Automation Conference.
[11]Yu Wang, Xiaoming Chen, Wenping Wang, Varsha Balakrishnan, Yu Cao, Yuan Xie and Huazhong Yang, On the Efficacy of Input Vector Control to Mitigate NBTI Effects and Leakage Power, 2009 10th International Symposium on Quality Electronic Design.
[12]Farshad Firouzi, Saman Kiamehr and Mehdi B. Tahoori, Power-Aware Minimum NBTI Vector Selection Using a Linear Programming Approach, 2013 IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
[13]Vivek T D, Olivier Sentieys and Steven Derrien, Wakeup Time and Wakeup Energy Estimation in Power-Gated Logic Clusters, 2011 24th Internatioal Conference on VLSI Design.
[14]Song Bian; Michihiro Shintani; Zheng Wang; Masayuki Hiromoto; Anupam Chattopadhyay and Takashi Sato, Runtime NBTI Mitigation for Processor Lifespan Extension via Selective Node Control, 2016 IEEE 25th Asian Test Symposium (ATS)