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

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

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