網(wǎng)絡(luò)并行計(jì)算環(huán)境中基于多處理機(jī)任務(wù)的調(diào)度研究

《網(wǎng)絡(luò)并行計(jì)算環(huán)境中基于多處理機(jī)任務(wù)的調(diào)度研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、摘要網(wǎng)絡(luò)計(jì)算技術(shù)與并行計(jì)算技術(shù)的高速發(fā)展，導(dǎo)致了網(wǎng)絡(luò)并行計(jì)算系統(tǒng)的產(chǎn)生，并以其范圍之廣泛、性能之高超、造價(jià)之低廉等卓越特性迅速發(fā)展壯大起來。目前最為典型的實(shí)例有基于局域網(wǎng)的集群(Cluster)和基于廣域網(wǎng)的網(wǎng)格(Grid)，它們把分布在不同地理位置的計(jì)算資源包括CPU、存儲(chǔ)器、數(shù)據(jù)庫等，通過高速網(wǎng)絡(luò)組成充分共享的資源集成，從而提供一種高性能計(jì)算、管理及服務(wù)的資源能力。網(wǎng)絡(luò)并行計(jì)算(Networkparallelcomputing，本文簡(jiǎn)稱NPC)已成為并行計(jì)算領(lǐng)域的一個(gè)重要發(fā)展方向，隨著NPC系統(tǒng)的應(yīng)用和推廣，人們不斷增長(zhǎng)的需求

2、和異構(gòu)環(huán)境的復(fù)雜性，為科研工作者提出了一系列新的挑戰(zhàn)課題。本文就NPC系統(tǒng)的任務(wù)調(diào)度策略與調(diào)度算法進(jìn)行了較為深入的研究。首先介紹了ⅣPc系統(tǒng)中的基于多處理機(jī)任務(wù)的調(diào)度模型，并在已有工作的基礎(chǔ)上進(jìn)行了探索和創(chuàng)新，并取得了一定的成果。具體內(nèi)容體現(xiàn)在如下幾個(gè)方面：(1)在全局調(diào)度上把NPC系統(tǒng)當(dāng)成一個(gè)異構(gòu)的多處理機(jī)系統(tǒng)來考慮。根據(jù)處理機(jī)本身的處理能力、處理機(jī)之間的通信能力及任務(wù)對(duì)處理機(jī)的不同需求，定義具有多模式的多處理機(jī)任務(wù)，從而建立ⅣPc系統(tǒng)中的多處理機(jī)任務(wù)調(diào)度模型B。Isetlck。。。并從理論上探討了該調(diào)度模型的近似優(yōu)化問題的難度

3、，在強(qiáng)NP．難的基礎(chǔ)上證明了不存在一個(gè)多項(xiàng)式時(shí)間的常數(shù)近似比的調(diào)度算法。同時(shí)，通過對(duì)多處理機(jī)任務(wù)之間的并行關(guān)系的分析，得到了一般最優(yōu)調(diào)度的下界。(2)研究了3，處理機(jī)系統(tǒng)中的規(guī)則調(diào)度(Normalschedule)，通過比較6個(gè)規(guī)則任務(wù)之間的時(shí)間長(zhǎng)度關(guān)系，構(gòu)造了一個(gè)最簡(jiǎn)單的調(diào)度算法，使得其調(diào)度時(shí)間跨度不超過最優(yōu)調(diào)度的5／4倍，并通過一個(gè)實(shí)例說明該算法得到的是最優(yōu)規(guī)則調(diào)度。然后在規(guī)則調(diào)度的基礎(chǔ)上進(jìn)行改進(jìn)，利用拆分(Partition)和半規(guī)則調(diào)度(Semi—normalschedule)方法，將3一處理機(jī)系統(tǒng)中由Goemans，保持

4、了數(shù)年之久的II世界最好結(jié)果7／6改進(jìn)到了9／8。(3)研究了4．處理機(jī)系統(tǒng)中的規(guī)則調(diào)度。在組調(diào)度(GroupSchedule)的基礎(chǔ)上，改善各處理機(jī)的間隙搭配方式，并引入部分調(diào)度(Partialschedule)以便充分利用間隙，構(gòu)造了一系列線性算法。先后得到了近似比為2、5／3、3／2直至4／3的近似調(diào)度，而且4／3是規(guī)則調(diào)度中最優(yōu)的，這些結(jié)果都經(jīng)過了嚴(yán)格的證明。(4)研究了多處理機(jī)(≥5)的NPC系統(tǒng)中的基于多處理機(jī)任務(wù)的調(diào)度問題。首次改進(jìn)表調(diào)度算法并給出了簡(jiǎn)單可行的處理機(jī)指派方法和3種O(n2)時(shí)間的調(diào)度算法：最大長(zhǎng)度優(yōu)先

5、調(diào)度(LLF)方法、最大寬度優(yōu)先調(diào)度(三聊宇)方法和最大面積優(yōu)先調(diào)度(朋F)方法，并通過實(shí)驗(yàn)?zāi)M，驗(yàn)證了它們的算法效率和近似調(diào)度性能，分析了這些算法的優(yōu)勢(shì)和不足。關(guān)鍵詞網(wǎng)絡(luò)并行計(jì)算，調(diào)度模型，多處理機(jī)任務(wù)調(diào)度，近似算法，規(guī)則調(diào)度lIIABSTRACTAstheadvanceofthenetworktechnologyandparallelcomputingtechnology,thenetworkparallelcomputingtechnologyhasbeenfounded，andhasbeendevelopedrapidly

6、foritsmoreeminentproperitiessuchasintensivescope，highperformanceandcheappriceetc．Atpresent．thetypicalexampleistheclusterbasedonthelocalareanetworkandgridbasedonthewideareanetwork．Throughthespeedynetwork，theyintegratedallsharedresourcesincludingCPUstorageanddatabaseetc

7、．10catedindifferentgeographicplaces，andastheresultthehighperformancecomputing，managementandservicehavebeenprovided．Networkparallelcomputing州PC)hasbecomeanimportantdevelopmentdirectioninthefieldofparallelcomputing．WiththeapplicationandpopularizationoftheNPCsystem、andth

8、eincreasinIgrequirementandcomplexityofheterogeneousenvironment，aseriesofchallengeshasbeenraisedfortheworkersinthefield，Thisp