局域網(wǎng)絡(luò)并行計算環(huán)境的建立及并行處理管理策略研究

1、局域網(wǎng)絡(luò)并行計算環(huán)境的建立及并行處理管理策略研究王玲玲 李元香(武漢大學(xué)軟件工程國家重點實驗室,430072(wlingling00 yxli 摘要本文討論了一種在現(xiàn)有局域網(wǎng)上建立并行環(huán)境的方法,提出了半機群系統(tǒng)的概念,并研究了在半機群系統(tǒng)中的并行處理管理策略。關(guān)鍵詞并行環(huán)境,并行處理,策略,資源分配引言我們身處在一個信息爆炸的時代信息爆炸的時代,現(xiàn)實世界越來越多的信息帶來越來越龐大的需要存儲、處理的數(shù)據(jù)。并行處理方法是一種快速處理海量數(shù)據(jù)的有效方法。但是,由于高性能計算機價格昂貴,并不便于普及。近年來,由于個人計算機的性能不斷提高,價格持續(xù)下降,同時網(wǎng)絡(luò)技術(shù)飛速發(fā)展,并行機群系統(tǒng)(NOW,N

2、etwork of Workstation替代高性能計算機,成為并行處理領(lǐng)域的關(guān)注焦點。機群系統(tǒng)是利用通用的高速網(wǎng)絡(luò),將一組高性能工作站或高檔PC機按某種結(jié)構(gòu)連接起來,統(tǒng)一調(diào)度、協(xié)調(diào)處理,實現(xiàn)高效并行處理的系統(tǒng)。并行機群系統(tǒng)具有性價比高,易于組建,無工作站同構(gòu)性要求,可擴展性強等優(yōu)點,得到了越來越廣泛的應(yīng)用。并行機群系統(tǒng)最方便的源泉就是局域網(wǎng),可以說局域網(wǎng)是天然的并行機群系統(tǒng),只需要對于局域網(wǎng)的組網(wǎng)和管理策略,以及相應(yīng)的軟件系統(tǒng)作一些修改,就可以很容易地改造成為一個并行機群系統(tǒng)。這里,我們研究的就是局域網(wǎng)上并行系統(tǒng)的建立,同時提出了一種任務(wù)調(diào)度策略。一、 局域網(wǎng)絡(luò)、機群系統(tǒng)及半機群系統(tǒng)1. 局

3、域網(wǎng)和機群系統(tǒng)通常局域網(wǎng)有以下的特點:為一個單位所有;所有的站點共享較高的總帶寬;較低的時延和較低的誤碼率;各站為平等關(guān)系而不是主從關(guān)系;能進行廣播或多播。機群系統(tǒng)結(jié)構(gòu)通常具有的特點:構(gòu)成系統(tǒng)的所有節(jié)點都是可以獨立使用的計算機;連接各個節(jié)點的互連網(wǎng)絡(luò)提供節(jié)點間高性能、高可靠和可擴展的通信服務(wù);整個系統(tǒng)在所有用戶看來就是一個整體,用戶使用此系統(tǒng)時,就好像是在使用一臺具有高性能配置的單一計算機系統(tǒng)。整個系統(tǒng)具有健壯性。當(dāng)一個或幾個節(jié)點出現(xiàn)故障時,這個系統(tǒng)只是性能降低,不會停機。2. 半機群系統(tǒng)比較局域網(wǎng)和機群系統(tǒng)我們可以看到,兩者在很大程度上具有相似性,將局域網(wǎng)改造成機群系統(tǒng),以適用較大規(guī)模并行計

4、算的需求,是比較方便的。同時我們也應(yīng)該看到局域網(wǎng)和通常意義上的機群系統(tǒng)的區(qū)別:局域網(wǎng)中的節(jié)點機主要還是用來作為個人計算機使用,這是它的最主要功能;而通常機群系統(tǒng)中的節(jié)點機可以沒有顯示器、鍵盤等等外設(shè),主要作為存儲計算節(jié)點來使用。我們改造局域網(wǎng)成為機群系統(tǒng)使其能充分利用空閑資源來處理并行計算問題,很大程度上是為了使現(xiàn)有局域網(wǎng)功能更強大,也更方便用于并行計算,而不是將它徹底改造成一個機群系統(tǒng),因此,這里我們稱它為半機群系統(tǒng)。半機群系統(tǒng)具有以下特點:機群系統(tǒng)從本質(zhì)上來說更傾向于一個局域網(wǎng),因為其主要的功用還是提供給各聯(lián)機用戶聯(lián)網(wǎng)計算機,在通常情況下,與普通的局域網(wǎng)沒有什么區(qū)別。系統(tǒng)應(yīng)提供一套完整而統(tǒng)

5、一的并行處理平臺。當(dāng)要使用此系統(tǒng)進行并行計算時,此平臺會給用戶提供方便的使用界面,并分配網(wǎng)絡(luò)資源,使用戶可以使用幾乎整個系統(tǒng)來進行并行處理。因此,它具有機群系統(tǒng)的特點。系統(tǒng)統(tǒng)一管理所有工作站,工作站資源的使用對用戶透明。用戶請求并行處理后,由系統(tǒng)按用戶需求分配資源,用戶無從知曉自己現(xiàn)在使用的具體是哪里的資源。這一點,對于局域網(wǎng)中信息保密是十分重要的。用戶雖然可以使用其它工作站的CPU及其它有限的資源,但是,不可以從其他工作站獲得私有信息。這樣就保證了聯(lián)機用戶的信息不被泄漏。3. 將局域網(wǎng)改造成半機群系統(tǒng)這里我們以一個實驗室局域網(wǎng)為例,來說明我們需要進行的改造: 現(xiàn)有的局域網(wǎng)很多都有文件服務(wù)器,

6、我們可以直接利用它兼作并行處理服務(wù)器,如果局域網(wǎng)中都是平等的工作站,沒有如圖所示的專用服務(wù)器,那么我們就要選擇一個安全級別最高的工作站,最好性能也是較高,來承擔(dān)服務(wù)器的工作,或者單獨設(shè)置一臺工作站專做服務(wù)器,除此以外,不需要對網(wǎng)絡(luò)結(jié)構(gòu)作任何修改。然后就是軟件和工作站的管理問題了。4. 在半機群系統(tǒng)上進行并行計算系統(tǒng)上的任何一個工作站都可以向服務(wù)器申請并行計算服務(wù),也可以從服務(wù)器直接使用系統(tǒng)進行并行計算。對于并行計算任務(wù)的管理由專門的軟件負(fù)責(zé),系統(tǒng)的并行管理策略在下一小節(jié)具體介紹。二、 并行處理管理策略并行處理管理策略,是整個系統(tǒng)的最重要的部分。軟件平臺就是根據(jù)此策略進行設(shè)計的,其內(nèi)容包括以下幾

7、個部分:1.承擔(dān)并行處理管理的軟件平臺軟件平臺分為服務(wù)器端平臺及工作站端平臺。平臺應(yīng)設(shè)計為可以在多種操作系統(tǒng)下使用的,并可與運行于另一不同操作系統(tǒng)上的平臺通信的通用平臺,可以運行在如WIN9X, WINNT,及LINUX上。軟件平臺分為后臺和前臺兩部分:后臺程序為本機與服務(wù)器及其它工作站的通信服務(wù),并且負(fù)有任務(wù)分配及控制負(fù)載平衡的責(zé)任;前臺則提供一個改進的PVM編譯系統(tǒng),提供友好的用戶界面,供用戶編輯并運行自己的并行程序。服務(wù)器端后臺應(yīng)具有管理所有工作站,并收集相關(guān)信息的功能,同時可以進行資源分配;當(dāng)?shù)玫椒?wù)器授權(quán)后,工作站端后臺就可以使用分配給它的資源,工作站端后臺應(yīng)該有任務(wù)分配及撤銷的功能

8、,另外,后臺還要對前臺屏蔽具體物理信息,存放物理邏輯映射表;當(dāng)本機資源可用狀況發(fā)生一定程度的改變時,主動向服務(wù)器報告。2.系統(tǒng)采用的資源分配及任務(wù)分配策略當(dāng)用戶請求使用系統(tǒng)資源進行并行計算時,要求用戶給出并行任務(wù)的緊急程度,同時每個工作站都有自己所屬的重要級別,系統(tǒng)就是根據(jù)兩者的綜合評估來確定并行任務(wù)的初始優(yōu)先級,一般某個工作站任務(wù)的優(yōu)先級不超過該工作站的優(yōu)先級。系統(tǒng)中還應(yīng)有一個統(tǒng)計器,用來統(tǒng)計在各個時段各工作站本機用戶的利用率,得到統(tǒng)計概率。同時,系統(tǒng)還記錄每一個工作站當(dāng)前的負(fù)載及資源使用狀況。對兩者綜合評價,并打分,按照目前空閑率,及其在未來空閑率大于某個固定值的概率不小于預(yù)先設(shè)定的概率的

9、時間段的長度值,評價工作站參與并行計算的合適程度,并評出等級,排序,作為資源分配的依據(jù)。當(dāng)工作站資源使用狀況改變,則等級也相應(yīng)改變。服務(wù)器的資源分配策略:采用優(yōu)先級高的任務(wù)優(yōu)先處理,同級任務(wù)先到先服務(wù)的原則給并行任務(wù)分配資源。工作站提出的任務(wù)在本站上具有最高優(yōu)先級,即,當(dāng)一個工作站向服務(wù)器提出分配并行資源的請求并獲得所需資源開始并行處理后,此工作站就不再被分配給其他并行任務(wù)使用。當(dāng)一個工作站提出并行處理申請時,除了本站,沒有可分配的其他資源,則任務(wù)申請進入等待隊列,不占用任何系統(tǒng)資源,包括本站資源。服務(wù)器采用資源動態(tài)分配方式。服務(wù)器首先分配最優(yōu)工作站給并行程序使用,當(dāng)沒有其他并行任務(wù)申請資源時

10、,可以將全部資源分配給現(xiàn)有并行程序使用。一旦有新的任務(wù)進入,則根據(jù)該任務(wù)的優(yōu)先級及現(xiàn)正在運行的并行程序的優(yōu)先級重新分配資源,如果要求現(xiàn)運行的程序從某一工作站完全退出,則將該工作站從其可分配節(jié)點集中刪除,并等待其在該工作站上的任務(wù)完成,或者使用轉(zhuǎn)移策略將任務(wù)轉(zhuǎn)移到其他工作站,至于具體是采取轉(zhuǎn)移策略還是等待策略,則要有任務(wù)運行狀態(tài)及轉(zhuǎn)移代價決定。例如任務(wù)剛開始,則可以使用轉(zhuǎn)移策略;任務(wù)即將完成,則不妨等待一下,以免工作浪費。服務(wù)器將資源分配給工作站,就是將系統(tǒng)節(jié)點的使用權(quán)交給了工作站,同一個節(jié)點,在負(fù)載允許的范圍內(nèi)可以分配給多個工作站支配,然后根據(jù)負(fù)載的變化,變更使用權(quán),變更使用權(quán)的依據(jù)同樣是優(yōu)先

11、級。等待隊列中及運行中任務(wù)優(yōu)先級不是固定不變的:運行中任務(wù)的優(yōu)先級高于等待隊列中任務(wù)的優(yōu)先級;運行時間越長,任務(wù)優(yōu)先級越高;等待隊列中任務(wù)等待時間越長,優(yōu)先級越高,但不超過運行任務(wù)優(yōu)先級。工作站的任務(wù)分配策略可以采用現(xiàn)有的任何一種分配策略,如啟發(fā)式分配、貪婪法分配等等,或它們的綜合,具體使用那種策略,要通過實驗,使用統(tǒng)計方法,進行結(jié)果分析來確定。3.軟件平臺的使用工作站啟動時,并行處理后臺程序就開始運行,向服務(wù)器報告初始負(fù)載,以后每當(dāng)工作站資源發(fā)生超過某一范圍的改變時,自動向服務(wù)器報告一次。后臺程序的運行對于用戶是透明的。服務(wù)器接收從工作站發(fā)送過來的資源信息,進行處理,并修改服務(wù)器上系統(tǒng)資源信

12、息,為提供并行處理做準(zhǔn)備。用戶從工作站前臺軟件上提出并行處理要求,后臺程序接收到后,向服務(wù)器提出資源申請,得到服務(wù)器分配給它的資源后,按照一定的任務(wù)分配策略,開始并行處理用戶提交的任務(wù),任務(wù)完成后,向服務(wù)器歸還資源。服務(wù)器收到工作站的資源申請時,檢查是否還有可分配資源,如果有,則分配給工作站使用,否則,將申請加入等待隊列。服務(wù)器在分配資源之后,向工作站確定并行任務(wù)已開始執(zhí)行后,向各工作站要求最新資源狀況,修改資源表后,才可以進行下一次資源分配。三、 進一步的工作和展望本文主要研究了半機群系統(tǒng)的特點及其軟件環(huán)境的實現(xiàn)策略,若要將其發(fā)展成為實用的并行系統(tǒng),還需要進行進一步的開發(fā)工作,而且軟件平臺的

13、策略也還不夠完善,需要進一步的改進。下一步我們要做的就是,研究平臺開發(fā)技術(shù),實現(xiàn)功能較完備的軟件平臺,考慮容錯策略的設(shè)計,然后將其投入實際使用中。半機群系統(tǒng)雖然并行處理能力略遜于機群系統(tǒng),但是實用性卻更強,應(yīng)該更容易為更多的單位接受?？梢栽诓挥脤ζ渚W(wǎng)絡(luò)做大的修改的同時,提供功能強大的并行服務(wù),而且實現(xiàn)價格低廉,尤其適合有并行處理數(shù)據(jù)需要,但并非主要需要并行處理的單位使用。半機群系統(tǒng)因其實現(xiàn)方便,價格低廉會有比較好的應(yīng)用前景。參 考 文 獻王同勝,計算機網(wǎng)絡(luò),機械工業(yè)出版社,2000何炎祥 宋文欣 彭鋒, 高級操作系統(tǒng),科學(xué)出版社,1999鄒 暉 羅省賢,機群并行系統(tǒng)與網(wǎng)絡(luò)并行計算環(huán)境,物探化探計算技術(shù),第23卷 第4期,375-379,2001李仁發(fā) 李方敏,網(wǎng)絡(luò)并行計算軟件環(huán)境的分析與比較,計算機工程與應(yīng)用,第37卷 第22期,73-74 86,2001劉赫男 羅 霄 高曉東,并行計算的現(xiàn)狀與發(fā)展,煤,第10卷 第1期,56-57,2001盧小勇 方 立,局域網(wǎng)上并行計算方法研究,計算技術(shù)與自動化,第2