分布式環(huán)境下主副版本任務可靠調(diào)度方法研究
發(fā)布時間：2018-10-24 19:23
【摘要】：隨著計算技術(shù)和網(wǎng)絡技術(shù)的發(fā)展,以分布式計算、并行計算為基礎的分布式計算系統(tǒng)所構(gòu)建的數(shù)據(jù)中心和計算中心在工業(yè)、商業(yè)、科技和軍事等領域有著非常廣泛的應用。在這些應用中將大量的復雜計算任務分解成為若干個子任務并行處理,最后將計算結(jié)果進行有效合并得到最終結(jié)果。可以看到在任務的分解和計算過程中,有效的任務調(diào)度機制是影響分布式計算系統(tǒng)性能和效率的關(guān)鍵因素,而不合理的任務調(diào)度方法會嚴重影響系統(tǒng)的計算能力,降低并行效率,甚至達不到并行計算應具有的效果。因此任務的調(diào)度問題一直是分布式系統(tǒng)、網(wǎng)格系統(tǒng)、云計算系統(tǒng)的核心內(nèi)容,也是人們一直研究的熱點。但是,隨著分布式系統(tǒng)規(guī)模的不斷增加、計算能力不斷提高的同時,系統(tǒng)的穩(wěn)定性和可靠性已成為影響并行應用能否順利執(zhí)行的關(guān)鍵。例如在天河二號、Google數(shù)據(jù)中心等超級計算機或是大規(guī)模集群中,由于復雜的上層應用以及系統(tǒng)超高的功耗導致了系統(tǒng)極容易出現(xiàn)故障,因此設計一套完整的可靠性保障機制顯得尤為重要,而在系統(tǒng)的調(diào)度階段設計高可靠的調(diào)度算法是其中重要的手段之一。本文從“保障性能,提高可靠性”這一目標出發(fā),深入研究如何保障分布式計算系統(tǒng)可靠性與計算資源高效利用問題。論文將任務的類型分為實時周期任務和非實時任務兩種任務類型,通過主副版本調(diào)度技術(shù),實現(xiàn)了高可靠、高性能的調(diào)度策略。具體工作為:(1)針對分布式計算系統(tǒng)的實時任務的可靠調(diào)度問題,提出了一種依據(jù)計算節(jié)點和通信鏈路可靠性代價的調(diào)度算法(DRCAMD)。該方法能通過設置權(quán)值的方法來調(diào)整系統(tǒng)的目標權(quán)重函數(shù),平衡用戶在系統(tǒng)的調(diào)度性能和可靠性的不同需求,另外,針對具有依賴關(guān)系的實時任務的調(diào)度問題,本文提出了一種不考慮主版本任務與副版本任務各種重疊狀態(tài)的可調(diào)度分析方法,實驗結(jié)果表明了在一定的計算節(jié)點和通信鏈路的故障概率條件下,算法的可靠性和性能方面具有一定的優(yōu)勢。(2)針對混合關(guān)鍵任務可靠性調(diào)度的問題,基于主副版本調(diào)度策略,結(jié)合任務關(guān)鍵性等級的處理方法,提出了一種二階段可靠調(diào)度算法(MCRSS)及可調(diào)度分析方法。該算法的第一階段主要是對需要調(diào)度的混合關(guān)鍵性任務按照優(yōu)先級高低進行調(diào)度,調(diào)度過程中,使用副本重疊的方法減少由于副版本任務的復制所帶來的系統(tǒng)開銷,第二個階段是對調(diào)度到目標處理機上的任務進行可調(diào)度分析,對于不能滿足可調(diào)度需求的任務進行升級處理,直到能滿足任務對截止期的要求。仿真實驗表明了MCRSS算法能有效的處理混合關(guān)鍵任務中不同關(guān)鍵等級任務的可靠調(diào)度問題,同時保證了分布式計算系統(tǒng)具有良好的靈活性和性能。(3)針對具有優(yōu)先級依賴關(guān)系的DAG任務的調(diào)度問題,本文提出了一種基于副版本任務最早完成時間的調(diào)度算法(EFTBT),該方法通過分析主版本任務調(diào)度的狀態(tài)以此得到不同情況下副版本任務調(diào)度的最早為完成時間以及調(diào)度的目標處理機的約束,并證明了該約束的合理性,該方法能夠在保障可靠調(diào)度前提下獲得較好的調(diào)度性能,另外,針對科學工作流應用中存在的多個DAG任務同時調(diào)度的問題,為了解決不公平導致的多個后續(xù)DAG任務無法調(diào)度問題,提出了基于分層思想的多DAG調(diào)度策略(MDDL),實驗結(jié)果表明上述兩種算法與經(jīng)典算法相比能有效提高調(diào)度的性能。(4)針對大規(guī)模分布式計算系統(tǒng)的異構(gòu)性、動態(tài)性的特點,提出基于節(jié)點和鏈路故障特征分析的具有依賴關(guān)系DAG任務可靠調(diào)度策略,該策略以副版本任務最早完成時間算法EFTBT為基礎,給出了更符合實際應用需求的通信模型以及副版本執(zhí)行策略,建立了分布式計算系統(tǒng)的故障特點分析方法,在此基礎上提出了基于通信競爭模型的容錯調(diào)度算法(RAPA),實驗結(jié)果表明與HEFT和EFTBT相比,RAPA算法具有較好的性能和可靠性。
[Abstract]:With the development of computing technology and network technology, the data center and computing center constructed by distributed computing and parallel computing are widely used in the fields of industry, commerce, science and technology and military. In these applications, a large number of complex computational tasks are decomposed into several sub-task parallel processing, and the calculation results are effectively combined to obtain the final result. it can be seen that the effective task scheduling mechanism is the key factor that affects the performance and efficiency of distributed computing system during the decomposition and calculation process of the task, and the unreasonable task scheduling method can seriously affect the computing power of the system, reduce the parallel efficiency, Even failing to reach parallel computing should have the effect. Therefore, the task scheduling problem has been the core content of distributed system, grid system and cloud computing system. However, with the increasing scale of distributed system and increasing computing power, the stability and reliability of the system have become the key to the successful implementation of parallel application. For example, in a supercomputer or a large-scale cluster such as Chrome No. 2 and Google data center, due to the complex upper application and the ultra-high power consumption of the system, the system is extremely prone to malfunction, so it is particularly important to design a complete set of reliability guarantee mechanisms. It is one of the most important means to design a highly reliable scheduling algorithm at the scheduling stage of the system. Based on the objective of guaranteeing performance and improving reliability, this paper studies how to guarantee the efficient utilization of distributed computing system reliability and computing resources. The paper divides the types of tasks into real-time periodic task and non-real-time task type, and realizes high-reliability and high-performance scheduling strategy through main sub-version scheduling technology. The specific work is as follows: (1) In order to solve the problem of reliable scheduling of distributed computing system, a scheduling algorithm (DRCAMD) based on calculating node and communication link reliability cost is proposed. The method can adjust the target weight function of the system by the method of setting the weight value, balance the different requirements of the scheduling performance and the reliability of the user in the system, and additionally, aiming at the scheduling problem of the real-time task with the dependency relationship, This paper presents a schedulable analysis method which does not take into account the overlapping states of the main version task and the sub-version task, and the experimental results show that the algorithm has some advantages in the reliability and performance of the algorithm under the failure probability condition of certain computing nodes and communication links. (2) A two-stage reliable scheduling algorithm (MCRSS) and schedulable analysis method are proposed based on the main sub-version scheduling policy and the processing method of task criticality. the first phase of the algorithm is mainly to schedule the mixed key tasks needing to be scheduled according to the priority level, The second stage is to perform schedulable analysis on tasks scheduled to the target processor, and upgrade the tasks that can not meet the scheduling requirements until the deadline requirements for tasks can be met. The simulation experiment shows that the MCRSS algorithm can effectively deal with the reliable scheduling problem of different key-level tasks in hybrid critical tasks, and also ensures that the distributed computing system has good flexibility and performance. (3) Aiming at the scheduling problem of DAG task with priority dependence, a scheduling algorithm (EFTBT) based on the earliest completion time of sub-version task is proposed in this paper. The method obtains the earliest completion time of the sub-version task scheduling and the constraint of the scheduled target processor by analyzing the state of the main version task scheduling, and proves the rationality of the constraint, The method can obtain better scheduling performance under the premise of guaranteeing reliable scheduling, and in addition, aiming at the problem that a plurality of DAG tasks existing in the scientific workflow application are simultaneously scheduled, in order to solve the problem that a plurality of subsequent DAG tasks caused by unfair scheduling cannot be scheduled, A multi-DAG scheduling strategy (MDDL) based on layered thought is proposed. The experimental results show that the two algorithms can effectively improve the performance of scheduling compared with classical algorithms. (4) aiming at the characteristics of heterogeneous and dynamic characteristics of the large-scale distributed computing system, a reliable scheduling strategy with dependency relation DAG task based on the node and link fault characteristics is proposed, and the strategy is based on the earliest completion time algorithm EFTBT of the sub-version task, In this paper, the communication model and the sub-version execution strategy are given. The fault characteristic analysis method of distributed computing system is established. Based on this, a fault-tolerant scheduling algorithm (RAPA) based on communication contention model is proposed. The experimental results show that compared with HEFT and EFTBT, RAPA algorithm has better performance and reliability.
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP338.8
本文編號：2292323
[Abstract]:With the development of computing technology and network technology, the data center and computing center constructed by distributed computing and parallel computing are widely used in the fields of industry, commerce, science and technology and military. In these applications, a large number of complex computational tasks are decomposed into several sub-task parallel processing, and the calculation results are effectively combined to obtain the final result. it can be seen that the effective task scheduling mechanism is the key factor that affects the performance and efficiency of distributed computing system during the decomposition and calculation process of the task, and the unreasonable task scheduling method can seriously affect the computing power of the system, reduce the parallel efficiency, Even failing to reach parallel computing should have the effect. Therefore, the task scheduling problem has been the core content of distributed system, grid system and cloud computing system. However, with the increasing scale of distributed system and increasing computing power, the stability and reliability of the system have become the key to the successful implementation of parallel application. For example, in a supercomputer or a large-scale cluster such as Chrome No. 2 and Google data center, due to the complex upper application and the ultra-high power consumption of the system, the system is extremely prone to malfunction, so it is particularly important to design a complete set of reliability guarantee mechanisms. It is one of the most important means to design a highly reliable scheduling algorithm at the scheduling stage of the system. Based on the objective of guaranteeing performance and improving reliability, this paper studies how to guarantee the efficient utilization of distributed computing system reliability and computing resources. The paper divides the types of tasks into real-time periodic task and non-real-time task type, and realizes high-reliability and high-performance scheduling strategy through main sub-version scheduling technology. The specific work is as follows: (1) In order to solve the problem of reliable scheduling of distributed computing system, a scheduling algorithm (DRCAMD) based on calculating node and communication link reliability cost is proposed. The method can adjust the target weight function of the system by the method of setting the weight value, balance the different requirements of the scheduling performance and the reliability of the user in the system, and additionally, aiming at the scheduling problem of the real-time task with the dependency relationship, This paper presents a schedulable analysis method which does not take into account the overlapping states of the main version task and the sub-version task, and the experimental results show that the algorithm has some advantages in the reliability and performance of the algorithm under the failure probability condition of certain computing nodes and communication links. (2) A two-stage reliable scheduling algorithm (MCRSS) and schedulable analysis method are proposed based on the main sub-version scheduling policy and the processing method of task criticality. the first phase of the algorithm is mainly to schedule the mixed key tasks needing to be scheduled according to the priority level, The second stage is to perform schedulable analysis on tasks scheduled to the target processor, and upgrade the tasks that can not meet the scheduling requirements until the deadline requirements for tasks can be met. The simulation experiment shows that the MCRSS algorithm can effectively deal with the reliable scheduling problem of different key-level tasks in hybrid critical tasks, and also ensures that the distributed computing system has good flexibility and performance. (3) Aiming at the scheduling problem of DAG task with priority dependence, a scheduling algorithm (EFTBT) based on the earliest completion time of sub-version task is proposed in this paper. The method obtains the earliest completion time of the sub-version task scheduling and the constraint of the scheduled target processor by analyzing the state of the main version task scheduling, and proves the rationality of the constraint, The method can obtain better scheduling performance under the premise of guaranteeing reliable scheduling, and in addition, aiming at the problem that a plurality of DAG tasks existing in the scientific workflow application are simultaneously scheduled, in order to solve the problem that a plurality of subsequent DAG tasks caused by unfair scheduling cannot be scheduled, A multi-DAG scheduling strategy (MDDL) based on layered thought is proposed. The experimental results show that the two algorithms can effectively improve the performance of scheduling compared with classical algorithms. (4) aiming at the characteristics of heterogeneous and dynamic characteristics of the large-scale distributed computing system, a reliable scheduling strategy with dependency relation DAG task based on the node and link fault characteristics is proposed, and the strategy is based on the earliest completion time algorithm EFTBT of the sub-version task, In this paper, the communication model and the sub-version execution strategy are given. The fault characteristic analysis method of distributed computing system is established. Based on this, a fault-tolerant scheduling algorithm (RAPA) based on communication contention model is proposed. The experimental results show that compared with HEFT and EFTBT, RAPA algorithm has better performance and reliability.
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP338.8
【相似文獻】
相關(guān)期刊論文 前4條
1 彭日光;李仁發(fā);劉彥;陳宇;李浪;;動態(tài)可重構(gòu)片上系統(tǒng)的任務在線調(diào)度算法[J];計算機工程;2010年05期
2 廖雷;如何在Windows下由一個任務啟動和中止另一個任務[J];現(xiàn)代計算機;1996年04期
3 李濤;楊愚魯;;可重構(gòu)資源管理及硬件任務布局的算法研究[J];計算機研究與發(fā)展;2008年02期
4 ;[J];;年期
相關(guān)博士學位論文 前1條
1 景維鵬;分布式環(huán)境下主副版本任務可靠調(diào)度方法研究[D];哈爾濱工業(yè)大學;2016年
相關(guān)碩士學位論文 前4條
1 李橙;嵌入式MPSoC系統(tǒng)中的任務調(diào)度管理研究[D];浙江大學;2010年
2 王宇;基于DVS的多核周期任務節(jié)能調(diào)度策略研究[D];武漢理工大學;2013年
3 張鐵軍;基于多核CPU的任務級數(shù)據(jù)處理研究及其在集群平臺下的性能測試[D];重慶大學;2011年
4 李俊;基于塊聚集的MapReduce性能研究與優(yōu)化[D];北京交通大學;2014年
，本文編號：2292323
本文鏈接：http://sikaile.net/shoufeilunwen/xxkjbs/2292323.html
最近更新
教材專著
