并行分布計算中的調(diào)度問題研究.pdf

1、 本文就并行分布式環(huán)境下的調(diào)度問題進行了研究，有中斷時間代價的一致并行調(diào)度問題的研究：證明了這是一個NP-hard問題，給出了一個時間復雜度為O(nlogn+m)的脫線近似算法，其近似比小于等于1.40825；分析了該問題的在線特性，給出一個線性時間復雜度的在線近似算法，其競爭比為2。　　 針對一種已有的分布式計算模型(單位長度的任務由處理器獨立產(chǎn)生，沒有全局控制，彼此通信需要花費時間)，研究了在線性網(wǎng)絡上的任務有效調(diào)度問題

2、。通過考慮算法中任務處理時間和通信時間之間的平衡，給出了一個近似比為5.88的分布式算法，該算法無需全局信息，且處理策略簡單。提出了相應的理論模型來描述其中的任務調(diào)度問題。在此基礎上，評估現(xiàn)有的幾種不同的調(diào)度策略，設計了新的根據(jù)具體的網(wǎng)絡環(huán)境和計算資源進行選擇的調(diào)度策略，通過理論分析和實驗分析說明該策略較之現(xiàn)有策略有更好的性能，并將該調(diào)度策略應用于實際系統(tǒng)中。 本文的主要貢獻和創(chuàng)新針對線性網(wǎng)絡和環(huán)狀網(wǎng)絡，研究了分布式計算環(huán)境下的任