為網(wǎng)格計(jì)算的可靠工作選擇機(jī)器

1、為網(wǎng)格計(jì)算的可靠工作選擇機(jī)器o credible worker selection mechanism for grid computing摘要摘要o 隨著網(wǎng)絡(luò)的高速發(fā)展，網(wǎng)格計(jì)算的概念開(kāi)始浮現(xiàn)。有效的網(wǎng)格工人選擇機(jī)制是對(duì)有效網(wǎng)格計(jì)算非常重要的，因?yàn)槊總€(gè)網(wǎng)格里面的工作者都是不同種類(lèi)的。在本文中，我們提出了選擇可靠的機(jī)器工作者的方法最大化網(wǎng)格計(jì)算，是利用合理的為每個(gè)計(jì)算者分配任務(wù)。不同的工人能夠被網(wǎng)格計(jì)算軟件有效的利用，通過(guò)工人可信度的過(guò)程隊(duì)列。一開(kāi)始，網(wǎng)格中工人的可信度只由一些靜態(tài)的參數(shù)決定，例如cpu的速度，內(nèi)存大小，存儲(chǔ)能力和網(wǎng)絡(luò)帶寬。后來(lái)，隊(duì)列被動(dòng)態(tài)信息優(yōu)化，例如失敗率，任務(wù)完成后時(shí)間提

2、供，和正確的返回值。在試驗(yàn)中，我們發(fā)現(xiàn)我們所提出的機(jī)制能夠提高網(wǎng)格計(jì)算效率和高可信度。1緒論緒論o應(yīng)用軟件程序要求大規(guī)模計(jì)算和高資源能力這幾年發(fā)展得很快，隨后出現(xiàn)了一個(gè)思想就是利用地理區(qū)域分散的數(shù)量龐大的計(jì)算機(jī)去完成這些任務(wù)。隨著網(wǎng)格中間設(shè)備，高速連接地理上分散計(jì)算機(jī)，已經(jīng)被發(fā)展了?；诰W(wǎng)格概念的使用工具已經(jīng)成為可能。典型的網(wǎng)格計(jì)算中間件是globus toolkit，為了解決網(wǎng)格計(jì)算中的巨大問(wèn)題，網(wǎng)格工人發(fā)現(xiàn)空閑的資源，網(wǎng)格表為每個(gè)網(wǎng)格工人分配任務(wù)，網(wǎng)格安全器負(fù)責(zé)系統(tǒng)的穩(wěn)定，網(wǎng)格使用者計(jì)算所需要使用的必要的資源。o由于實(shí)際中的原因，包括工人失敗，新工人注冊(cè)，在網(wǎng)格計(jì)算中的共存的執(zhí)行工人，網(wǎng)格

3、工人的不斷變化，所以，有效的網(wǎng)格工人選擇機(jī)制對(duì)完成可靠的網(wǎng)格計(jì)算系統(tǒng)是非常重要的因?yàn)槊總€(gè)參與網(wǎng)格計(jì)算的工人都是不同的。這個(gè)選擇機(jī)制就是一種各種形式的適當(dāng)?shù)木W(wǎng)格工人的任務(wù)匹配的方法。首先，很多網(wǎng)格工人被只用靜態(tài)的信息連接起來(lái)，例如硬件能力，隊(duì)列，然后用適當(dāng)?shù)娜蝿?wù)匹配。第二，每個(gè)工人的最初結(jié)果被用來(lái)更新工人隊(duì)列，然后去適合將來(lái)所要分配的任務(wù)。任務(wù)安排表算法必須是能夠被擴(kuò)展的，然后能夠有效的處理個(gè)種類(lèi)型的網(wǎng)格計(jì)算系統(tǒng)的動(dòng)態(tài)學(xué)錯(cuò)誤。在本文中，一個(gè)機(jī)制估計(jì)得到結(jié)果要多少時(shí)間，從信息中傳遞任務(wù)的達(dá)到，用心跳信號(hào)檢測(cè)存活的網(wǎng)格工人被發(fā)展了。2相關(guān)工作相關(guān)工作o 反向向?qū)е鞴と私Y(jié)構(gòu)用歷史信息關(guān)于每個(gè)網(wǎng)格工人的

4、活動(dòng)信息被提出。結(jié)構(gòu)的完全工人和遞送信息在網(wǎng)格計(jì)算系統(tǒng)中是很有效的。每個(gè)主人分配任務(wù)考慮到每個(gè)工人隊(duì)列或者任務(wù)特點(diǎn)，不斷更新工人隊(duì)列考慮的信息動(dòng)態(tài)，然后用再次使用他們?yōu)閷?lái)任務(wù)做準(zhǔn)備。o 在本文中，有效地處理每個(gè)工人的可信度，我們提出一個(gè)新的分等級(jí)的工人結(jié)構(gòu)，如圖1所示，利用投票和抽樣算法，這2個(gè)是一種分組機(jī)制用來(lái)測(cè)量結(jié)果的正確性，是在同時(shí)間間隔中測(cè)量結(jié)果的正確性和任務(wù)分配之后 o為了避免喚醒工人的壞的信息，這個(gè)方法要求返回的正確的結(jié)果，需要每個(gè)工人都返回正確的結(jié)果，這是必須的。一般的做法是使用容錯(cuò)技術(shù)增加正確性，用奇偶校驗(yàn)或者校驗(yàn)和算法，但是我們用投票和點(diǎn)校驗(yàn)策略因?yàn)榍罢呤枪室夤舻囊粋€(gè)弱點(diǎn)

5、。然而，先前的投票和點(diǎn)校驗(yàn)算法被用來(lái)區(qū)分有錯(cuò)誤的工人，只有當(dāng)工人的表現(xiàn)有壞的信息的時(shí)候。網(wǎng)格計(jì)算系統(tǒng)出現(xiàn)錯(cuò)誤的可能性是一般發(fā)生在特定組合里面的任務(wù)分配，判斷每個(gè)工人的返回值的正確性。o有一個(gè)算法，是要求任務(wù)完成的時(shí)間的，它是隨機(jī)分配任務(wù)去每個(gè)網(wǎng)格工人評(píng)估。然而，因?yàn)樗?qǐng)求的資源有限，很多時(shí)候是不能很好匹配的。同時(shí)，它還有一個(gè)缺點(diǎn)，這個(gè)缺點(diǎn)是不能夠計(jì)算工人們最好的負(fù)荷量因?yàn)樗胁煌瑯?biāo)準(zhǔn)的混合結(jié)構(gòu)，同時(shí)安排表只允許round-robin方法。有一個(gè)智能算法，叫螞蟻算法，它利用歷史信息分配計(jì)算資源，這個(gè)資源叫做信息素。信息素被表示為歷史信息，是一個(gè)中間匹配資源的中間值，它是利用先前資源收集和傳遞的信

6、息。然而，正確或錯(cuò)誤的任務(wù)結(jié)果的判斷機(jī)制是不能用的，而且只考慮更新信息素的正確性，排除動(dòng)態(tài)元素，例如失敗率和翻轉(zhuǎn)時(shí)間。o在本文中，我們?cè)O(shè)計(jì)一個(gè)可靠的工人選擇機(jī)制使網(wǎng)格計(jì)算表現(xiàn)最大化，用合理的任務(wù)分配機(jī)制。換一句話(huà)說(shuō)，這個(gè)提出的機(jī)制考慮隊(duì)列中的每個(gè)網(wǎng)格工人的可信度基于靜態(tài)和動(dòng)態(tài)信息的歷史信息素。首先，網(wǎng)格工人的可靠度只依靠一些靜態(tài)信息，例如cpu頻率，內(nèi)存大小，存儲(chǔ)能力和網(wǎng)絡(luò)帶寬。然后，隊(duì)列被動(dòng)態(tài)因素更新，例如失敗率，任務(wù)完成后的翻轉(zhuǎn)時(shí)間。3網(wǎng)格計(jì)算體系結(jié)構(gòu)網(wǎng)格計(jì)算體系結(jié)構(gòu)o 我們才用分等級(jí)的主控工人結(jié)構(gòu)，這個(gè)比以前的結(jié)構(gòu)先進(jìn)的結(jié)構(gòu)。圖1顯示了主控和工人間的關(guān)系。主控只能分辨比它下一級(jí)的工人任務(wù)

7、分配給第一級(jí)的工人和整合工人收集上來(lái)的結(jié)果，這些工人是完成任務(wù)的工人。工人能夠成為擴(kuò)展后的主控。假定一個(gè)任務(wù)能夠被分成許多小的部分，每個(gè)節(jié)點(diǎn)作為一個(gè)工人一旦傳遞任務(wù)就是給它下一級(jí)的工人。 3.1工人注冊(cè)和可信隊(duì)列管理o 一個(gè)網(wǎng)絡(luò)中愿意加入網(wǎng)格計(jì)算的候選的工人由注冊(cè)過(guò)程連接到主控機(jī)（如圖2所示）。工人必須記錄它自己的靜態(tài)信息連接給主控機(jī)。主控機(jī)利用被控機(jī)的注冊(cè)信息。主控機(jī)用基于排列輸出量分配相同的任務(wù)，和從正確的結(jié)果中刷新工人的可信度。最后，主控機(jī)按照隊(duì)列的可信度為每個(gè)工人分配任務(wù)。當(dāng)相同組的工人分配到任務(wù)以后，給予網(wǎng)格計(jì)算輸出的很小的時(shí)間變化增加了。因此，全部網(wǎng)格工人的利用率增加了。o 圖3顯

8、示了由主控節(jié)點(diǎn)和它的任務(wù)管理，資源管理，資源池和數(shù)據(jù)庫(kù)的組成。o 3.2 工人的靜態(tài)信息o 當(dāng)每個(gè)工人想被注冊(cè)到網(wǎng)格計(jì)算系統(tǒng)中時(shí)，我們要提供他們自己本身的系統(tǒng)信息給主控機(jī)。表1顯示了組中工人的靜態(tài)信息，這些是工人計(jì)算時(shí)的表現(xiàn)和計(jì)算資源更新的后的刷新。每個(gè)組中的工人由等式1表示。當(dāng)一個(gè)工人在群中時(shí)，它能夠被下一級(jí)工人用元素k表示。o 每個(gè)工人可能的5種狀態(tài)由圖4表示出來(lái)，o 第i組中第j個(gè)工人的cpu，內(nèi)存，存儲(chǔ)和網(wǎng)絡(luò)帶寬信息用下面的等式2表示。o 只利用這些靜態(tài)信息的話(huà)，我們能夠決定網(wǎng)格計(jì)算系統(tǒng)中先前一個(gè)工人在網(wǎng)格問(wèn)題中的特征。例如，計(jì)算導(dǎo)向網(wǎng)格任務(wù)把cpu速度放在更高的位置上，和數(shù)據(jù)精度網(wǎng)格

9、任務(wù)把存儲(chǔ)能力放在更重要位置。為了表現(xiàn)以上的情況，我們用等式3定義在第i組中的第j個(gè)工人.3.3 一個(gè)工人的動(dòng)態(tài)信息（dynamic information）o 工人的動(dòng)態(tài)信息被用來(lái)測(cè)量結(jié)果可信度和現(xiàn)場(chǎng)校驗(yàn)算法和歷史信息，例如失敗率far，翻轉(zhuǎn)時(shí)間tat，和正確率crt，用等式4表示。o 平均翻轉(zhuǎn)時(shí)間atat和atat的標(biāo)準(zhǔn)背離用等式5和等式6表示反應(yīng)時(shí)間的小變化網(wǎng)格計(jì)算結(jié)果的可能性由等式6表示。也就是說(shuō)，工人組中最小標(biāo)準(zhǔn)背離是最適合聯(lián)合完成任務(wù)。3.3 失敗率o 失敗率是工人在計(jì)算過(guò)程中可能產(chǎn)生的錯(cuò)誤。我們提出的這個(gè)機(jī)制利用心跳機(jī)制去辨認(rèn)工人的失敗率，和決定失敗率因素由圖5表示。o 任務(wù)管理

10、工具分配為每個(gè)任務(wù)分配資源然后等待結(jié)果。這個(gè)結(jié)果被適用于基于工人的點(diǎn)工作的暫停，工人是第一個(gè)給結(jié)果的工人，和給同組工人發(fā)送心跳。如果其他工人對(duì)確定時(shí)間間隔內(nèi)心跳沒(méi)有回應(yīng)，那么就認(rèn)為工人錯(cuò)誤了。等式7表示了第i組第j個(gè)工人刷新了它先前的失敗率的信息。3.3.2翻轉(zhuǎn)時(shí)間o 反轉(zhuǎn)時(shí)間是消逝時(shí)間的持續(xù)時(shí)間的結(jié)果從一個(gè)工人到另外一個(gè)工人后開(kāi)始它的工作的時(shí)間。為了獲得精確的時(shí)間，網(wǎng)絡(luò)延遲也要考慮到。圖6顯示了翻轉(zhuǎn)時(shí)間模型和它的計(jì)算方法用等式8給出3.3.3正確性o 工人的正確性是由在相同組完成同一個(gè)任務(wù)之后比較返回值決定。由等式9給出3.4工人可信度o 工人的動(dòng)態(tài)信息是由基于失敗率，翻轉(zhuǎn)時(shí)間，和等式10中

11、的每個(gè)工人的正確性計(jì)算的。o 最后，工人的可信度由等式11定義o 可信性是由最初的靜態(tài)和動(dòng)態(tài)信息和以后的工人不斷更新增加任務(wù)所得到的結(jié)果的隊(duì)列計(jì)算出的。在等式12中，新的可信性是由分解舊的總和可信度和完成所有分配任務(wù)的可信性獲得。o 圖7是全部網(wǎng)格結(jié)構(gòu)開(kāi)始由任務(wù)接受者插入任務(wù)過(guò)程開(kāi)始，為每個(gè)工人分配任務(wù)，確認(rèn)結(jié)果，和產(chǎn)生隊(duì)列和用結(jié)果重新排列工人隊(duì)列。4 執(zhí)行評(píng)估執(zhí)行評(píng)估o 表2是每個(gè)工人的靜態(tài)信息和被使用的最初分組。o pri信息是由定義的所有權(quán)重計(jì)算的。表3是一個(gè)動(dòng)態(tài)信息的例子（參照等式10中的i/o流）利用上面提到的靜態(tài)。每個(gè)權(quán)值設(shè)定為： 自從i/o流比f(wàn)ar和crt大受網(wǎng)絡(luò)條件影響之后，

12、所以tat就故意設(shè)成2倍大小。表4顯示了工人隊(duì)列考慮了全部的動(dòng)態(tài)和靜態(tài)信息。o 首先，觀測(cè)lan環(huán)境中的i/o流，和表4中第3組工人排除他們不屬于同一個(gè)組因素。圖8是估計(jì)i/o流時(shí)間在不同大小從100到600兆用5個(gè)工人有5到9個(gè)隊(duì)列的不同可信度。文件i/o流時(shí)間對(duì)系統(tǒng)可信度并沒(méi)有太大的影響。沒(méi)有太大的背離當(dāng)分配任務(wù)給每個(gè)同組工人之后。反而，低容量的工人需要的時(shí)間更短。考慮到接受和發(fā)送的網(wǎng)絡(luò)條件，狀態(tài)正確性比系統(tǒng)容量更好。o 圖9顯示了可信度的反應(yīng)時(shí)間和工人數(shù)量。o 當(dāng)有一定數(shù)量的參與者參與到網(wǎng)格計(jì)算系統(tǒng)和可信度提高時(shí)，有可能縮短反應(yīng)時(shí)間。這個(gè)結(jié)果暗示有很多工人的投票，失敗率下降和返回值的正確

13、性增加。很難合適目標(biāo)正確率在任務(wù)大小和工人系統(tǒng)能力之間在分配任務(wù)給獲得好的回應(yīng)時(shí)間，但是匹配資源用最好的能力給最大任務(wù)將能夠成為最合適的匹配標(biāo)準(zhǔn)。o 失敗率的影響對(duì)反應(yīng)時(shí)間由圖10給出。o 反應(yīng)時(shí)間的在圖中的變化依照不同的失敗率和園羅賓算法（round-robin）。這里，失敗率給出了工人匹配任務(wù)的正確性，10%的失敗率意思是能夠正確匹配到工人的任務(wù)是90%。當(dāng)失敗率到30%的時(shí)候，它顯示了更好的表現(xiàn)，比匹配工人用園羅賓算法，和縮短反應(yīng)時(shí)間是獲得當(dāng)更小失敗率的時(shí)候?？紤]可信信息例如失敗率，最少比2倍于有效反應(yīng)時(shí)間表現(xiàn)能夠被達(dá)到，盡管接受失敗率只有10%。o 圖11顯示了正確性依照失敗率和同組工

14、人數(shù)量。o 它利用投票算法，和度量正確性在假設(shè)大量工人返回同一個(gè)值的情況下。例如，有一個(gè)組有3個(gè)工人，失敗率是40%，那么有可能得到正確結(jié)果的可能性是60%。因此，增加更多工人和降低失敗率，能夠增加正確性。o 圖12是一個(gè)表顯示監(jiān)視圈t依照高架m和系統(tǒng)可能改變能力p，它表示了最好的t假設(shè)，這個(gè)是m是由監(jiān)視系統(tǒng)m發(fā)生能力改變和p是信息可能改變，在工作過(guò)程t中?？赡苄愿蟮墓と诵畔⒏淖儼l(fā)生，一個(gè)更短的得到正確工人信息的圈。所以工人的正確性能夠被t增加。o 在圖13中，deadline sort and first-come first-serverd算法被考慮來(lái)比較網(wǎng)格計(jì)算系統(tǒng)的表現(xiàn)用我們提出的機(jī)制。o 在這次試驗(yàn)中，我們采用試驗(yàn)參數(shù)。任務(wù)相應(yīng)時(shí)間從5到11秒被平均使用，和給出5個(gè)不同的先決條件。工人們被分為31組依照任務(wù)的不同性和每組由3個(gè)工人組成。這個(gè)反應(yīng)時(shí)間被評(píng)估作