（計算機軟件與理論專業(yè)論文）并行遺傳算法在熱傳導反問題中的應(yīng)用.pdf

摘要 隨著科技的發(fā)展，新一代的計算機，無論計算能力和計算速度都比舊的計 算機優(yōu)越。但人類對高性能計算的需求，也不斷提高。除了增強處理器本身的 計算能力外，并行處理是一種提高計算能力的有效手段。以前并行處理要采用 昂貴的專用計算機，隨著個人計算機及網(wǎng)絡(luò)成本的下降，現(xiàn)已廣泛用分布式網(wǎng) 絡(luò)計算機系統(tǒng)進行并行處理。本文是在m p i 網(wǎng)絡(luò)并行環(huán)境中，將二維熱傳導方 程參數(shù)反演問題用并行遺傳算法進行數(shù)值求解。 本文首先介紹本課題研究的背景與意義，然后介紹并行計算的基本理論、 計算機機群系統(tǒng)和m p i 消息傳遞機制。在此基礎(chǔ)上，建立了基于l i n u x 和m p i 的p c 機群實驗環(huán)境。然后基于網(wǎng)絡(luò)并行環(huán)境中并行算法的設(shè)計原則，結(jié)合遺傳 算法的并行性，對陶瓷金屬材料熱物性反問題用并行遺傳算法進行求解。由于 并行遺傳算法將并行計算機的高速并行性和遺傳算法固有的并行性相結(jié)合，極 大地提升了遺傳算法的求解速度和質(zhì)量。在主從式、細粒度和粗粒度這三類遺 傳算法并行化模型中，粗粒度模型以其較小的通訊開銷和對種群多樣化，獲得 了最廣泛的應(yīng)用。本文研究了并行遺傳算法中不同遷移間隔和交叉點數(shù)對并行 算法的性能影響，并對實驗結(jié)果進行了比較和分析。最后總結(jié)了本文所做的j ： 作，并指出本領(lǐng)域有待于進一步研究的問題。 本文總共分為六章，其內(nèi)容如下： 第一章，主要介紹本課題研究的背景與意義及本文所做的主要工作。 第二章，主要介紹并行計算機的發(fā)展及分類，并行計算的基本理論。 第三章，討論了遺傳算法及其并行性，介紹了它的理論背景及算法描述。 第四章，介紹了m p i 系統(tǒng)，詳細的給出了在實際計算中所使用的m p i 機群系 統(tǒng)的配置。同時介紹了一些基于m p i 的并行程序設(shè)計技巧。 第五章，給出了本文研究的熱物性參數(shù)反問題模型的數(shù)值求解過程，對并 行遺傳算法的幾種不同交叉點數(shù)及遷移間隔進行分析比較。 第六章，給出了本文的結(jié)論，并對下一步的工作做了展望。 本文得到了國家自然科學基金項目( 批準號：6 0 1 7 3 0 4 6 ) 的資助。 關(guān)鍵詞：熱傳導，反問題，并行計算，并行遺傳算法，m p i a b s t r a c t w i t h d e v e l o p m e n t s o f t e c h n o l o g y ，c o m p u t i n gp o w e r a n d s p e e d o fn e w g e n e r a t i o nc o m p u t e r s a r em u c hb e t t e rt h a nt h ef o r m e ro n e s h o w e v e r p e o p l e s d e m a n d sf o rh i g hp e r f o r m a n c ec o m p u t i n ga r ei n c r e a s i n ga n di n f i n i t ei ns o m es e n s e ， s ot h a ti na d d i t i o nt o e n h a n c i n gt h ec o m p u t i n gp o w e ro fap r o c e s s o r ，p a r a l l e l p r o c e s s i n gi sa l s oa ne f f i c i e n tw a y t oe n h a n c et h ec o m p u t i n gp o w e ro fas y s t e m i n t h ep a s t ，t h ep a r a l l e lp r o c e s s i n gc a n o n l yb ep e r f o r m e do nt h ee x p e n s i v ea n ds p e c i a l c o m p u t e r s a l o n gw i t h t h ec o s to fp c sa n dn e t w o r kd e s c e n d i n g ，t h ed i s t r i b u t e d p a r a l l e lc o m p u t i n gc o n c e p t i s w i d e l yu s e di n t h e p a r a l l e lc o m p u t i n g t h i st h e s i s f o c u s e so nd e t e r m i n a t i o no f p a r a m e t e r si nat w od i m e n s i o n h e a tc o n d u c t i o ne q u a t i o n o nt h em p in e t w o r kp a r a l l e le n v i r o n m e n t ，b ys o l v i n ga ni n v e r s ep r o b l e mu s i n gt h e p a r a l l e lg e n e t i ca l g o r i t h m f i r s t l yt h i st h e s i si n t r o d u c e sr e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e sr e l a t e dw i t h t h es u b j e c t ，t h e ns h o w sb a s i ct h e o r yo ft h ep a r a l l e lc o m p u t i n g ，i n t r o d u c e st h ec l u s t e r c o n c e p t a n dt h e m e s s a g ep a s s i n gs y s t e m o fm p i ，a f t e rt h a t ，d i s c u s s e sh o wt o e s t a b l i s h e sap a r a l l e lc o m p u t i n ge n v i r o n m e n tb a s e do nt h em p ia n dl i n u x ；a n dt h e n b a s e do nn e t w o r kb a c k g r o u n d ，i n t e g r a t e sp r i n c i p l eo f p a r a l l e la l g o r i t h mw i t hp a r a l l e l c h a r a c t e r i s t i co fp a r a l l e l g e n e t i ca l g o r i t h m ( p g a ) ，u s i n gt h e p g at os o l v et h e t h e r m o p h y s i c a lp r o p e r t i e si n v e r s ep r o b l e mo f c e r a m i c m e t a lc o m b i n em a t e r i a l ，t h e p g ac o m b i n e sh i g h - s p e e dp a r a l l e l - - a b i l i t yo fs u p e r c o m p u t e r sw i t h t h ei n h e r e n t p a r a l l e l i t yo fg a ，a n di m p r o v e sg r e a t l yt h ee f f i c i e n c ya n da c c u r a c y o fg a s a m o n g m a s t e r - s l a v e ，f i n e g r a i n e da n dc o a r s eg r a i n e dp a r a l l e la p p r o a c h e s ，t h ec o a r s e g r a i n e d m o d e li sm o s t w i d e l yu s e df o ri t sl i t t l ec o m m u n i c a t i o n o v e r h e a da n di t sd i v e r s i l y i n g o ft h e p o p u l a t i o n t h i s t h e s i ss t u d i e st h ei n f l u e n c et o p e r f o r m a n c e o fp a r a l l e l a l g o r i t h mo fd i f f e r e n c em i g r a t i o ns t e pa n dc r o s s o v e rp o i n t so fp g a ，a n a l y z e sa n d c o m p a r e ss o m ee x p e r i m e n tr e s u l t s f i n a l l y , c o n c l u s i o n so f t h i st h e s i sa n ds u g g e s t i o n s f o rf u r t h e rr e s e a r c ha r eg i v e n t h i st h e s i sh a ss i xc h a p t e r s c h a p t e r 1i n t r o d u c e sr e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e sr e l a t e dw i t ht h e 1 1 t s u b j e c ta n dm a m w o r kw h i c hh a sb e e nd o n e c h a p t e r 2i n t r o d u c e sd e v e l o p m e n ta n dt h ec l a s s i f i c a t i o no ft h ep a r a l l e lc o m p u t e r ， d i s c u s s e st h eb a s i ct h e o r y o f p a r a l l e lc o m p u t i n g c h a p t e r 3d i s c u s s e st h eg aa n di t sp a r a l l e l i t y , i n t r o d u c e si t st h e o r yb a c k g r o u n d a n d a l g o r i t h md e s c r i p t i o n c h a p t e r4 i n t r o d u c e st h em p is y s t e m ；ad e t a i lc o n f i g u r a t i o no fm p ic l u s t e r s y s t e m w h i c ht h i st h e s i sh a su s e di s g i v e n t h et e c h n i q u e s o fm p ip a r a l l e l p r o g r a m m i n g a l s oh a v e b e e na d d r e s s e d c h a p t e r5g i v e st h ed e t a i ls o l u t i o np r o c e s so ft h e r m o p h y s i c a lp r o p e r t i e si n v e r s e p r o b l e m t h ei n f l u e n c et op e r f o r m a n c e o f p a r a l l e la l g o r i t h mo f d i f f e r e n c em i g r a t i o n s t e pa n d c r o s s o v e r p o i n t so f p g a h a sb e e na n a l y z e d c h a p t e r 6s u m m a r i z e st h i st h e s i s ，a n ds u g g e s t i o n sf o rf u t u r er e s e a r c ha r eg i v e n t h i ss u b j e c ti ss u p p o r t e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ( n s f c g r a n tn o 6 0 1 7 3 0 4 6 ) k e yw o r d s ：h e a tc o n d u c t i o n ，i n v e r s ep r o b l e m ，p a r a l l e lc o m p u t i n g ，p a r a l l e lg e n e t i c a l g o r i t h m ，m p i 武漢理工大學碩士學位論文 第1 章緒論 1 1 本課題研究的背景與意義 高溫材料反問題方法的研究始于上世紀5 0 年代，近幾十年來，它發(fā)展很快， 各國研究者根據(jù)不同對象的特點，采取各自的方法和技巧進行分析研究，但與 正問題相比，畢竟是年輕的，還沒有成熟到可以系統(tǒng)化為完整學科的地步【1 ，”。 反問題的求解有廣泛的應(yīng)用價值。在大型航天器、新型核反應(yīng)堆、大型超導發(fā) 電機等許多無法測量從而要求逆推相應(yīng)物性參數(shù)的工程問題中，在研究新材料 時，往往需要考慮反問題。例如，c o r n e l l 大學力學與空間機械學院的一組科學 家討論了合金定向固化過程的反問題并指出了一種反問題求解的面向?qū)ο缶幹?程序的思路 3 ”。對于實際工程問題，很難得到反問題的精確解，一般用數(shù)值方 法進行求解。j o n a s ( 1 9 9 9 ) ，a b d u l l a h ( 1 9 9 9 ) ，d e l a u n a y ( 1 9 9 8 ) 分析了反問題， 他們認為無論是線性反問題或非性線反問題，其計算量遠大于正問題的計算量， 研究計算速度快的算法是有實際意義的。 并行計算能縮短計算時間，但并行計算機價格昂貴，一般單位很少購買并 行計算機。以局域網(wǎng)為依托的機群計算，可以利用各單位已有的計算資源，使 局域網(wǎng)增加新的功能，一網(wǎng)兩用。一方面作為通常意義的網(wǎng)絡(luò)，用于信息交換 和資源共享；另一方面又可以用作并行計算【5 。 分布式并行處理系統(tǒng)的實質(zhì)是在邏輯關(guān)系上采用消息傳遞( m e s s a g e p a s s i n g ) 方式進行并行計算；在物理結(jié)構(gòu)上經(jīng)過相應(yīng)的通信接口把許多自治的 處理器相連。它與計算機網(wǎng)絡(luò)有許多相似相通之處。因此，這類系統(tǒng)上的并行 算法易與實施機群計算的并行算法相互移植。近年來，隨著計算機網(wǎng)絡(luò)技術(shù)的 發(fā)展，在局域網(wǎng)上開發(fā)并行系統(tǒng)進行機群計算有著巨大的潛在價值?；跈C群 計算的分布式并行算法將為大規(guī)模工程與科學計算開辟一個新的領(lǐng)域。 1 2 本文所做的主要工作 本文研究了在p c 機群環(huán)境中實現(xiàn)并行遺傳算法解熱傳導反問題的相關(guān)問 武漢理工大學碩士學位論文 題。 論文首先研究利用現(xiàn)有計算機資源，構(gòu)建小型的機群系統(tǒng)，建立基于l i n u x 和m p i 的實驗環(huán)境。在此基礎(chǔ)上，介紹了開發(fā)m p i 并行程序的過程，并且在實 驗環(huán)境中測試了并行程序的性能。 本文對機群環(huán)境作的研究和探索，主要包括以下工作： 第一，對并行計算體系結(jié)構(gòu)進行討論，通過建立基于l j n u x 和m p i 的并行 機群實驗環(huán)境，探索可擴展p c 機群系統(tǒng)的構(gòu)建和實現(xiàn)方法。 第二，研究了消息傳遞模式下機群系統(tǒng)并行程序模型以及影響并行程序性 能的因素：討論了m p i 程序設(shè)計的基本模式和方法，以及在m p i 機群環(huán)境下開 發(fā)并行程序的框架和過程。 第三，給出了機群m p i 環(huán)境下遺傳算法的并行程序?qū)崿F(xiàn)。 第四，在建立的并行實驗平臺上，對并行遺傳算法的幾種不同影響因素做 了實驗和比較。 最后，根據(jù)理論研究和實際實驗的結(jié)果，總結(jié)了在機群系統(tǒng)中利用并行遺 傳算法求解熱傳導反問題的可行性，以及分析并行遺傳算法進行改進的思路。 2 武漢理工大學碩士學位論文 第2 章并行計算基礎(chǔ) 2 1 并行計算的意義和發(fā)展前景 并行計算( p a r a l l e c o m p u t i n g ) ，簡單的講，就是在并行訓。算機系統(tǒng)上 所作的計算，它和常說的高性能計算( h i g hp e r f o r m a n c ec o m p u t i n g ) 、超級 計算( s u p e rc o m p u t i n g ) 含義基本相同，因為任何高性能計算和超級計算總要 使用并行技術(shù)。 并行計算機的發(fā)展基于人們在兩方面的認識：第一，單機性能不可能滿足 大規(guī)?？茖W與工程問題的計算需求，而并行計算機是實現(xiàn)高性能計算、解決挑 戰(zhàn)性計算問題的唯一途徑：第二，同時性和并行性是物質(zhì)世界的一種普遍屬性， 具有實際物理背景的計算問題在許多情況下都可以劃分成能夠并行計算的多個 子任務(wù)。針對某一具體應(yīng)用問題，我們可以利用它們內(nèi)部的并行性，設(shè)計并行 算法，將其分解成為互相獨立但彼此又有一定聯(lián)系的若干個子問題，分別交給 各臺處理機，而所有的處理機按并行算法完成初始應(yīng)用問題的求解 7 l 。例如，根 據(jù)幾十個常用應(yīng)用軟件的統(tǒng)計，6 0 - - 8 0 的標量計算可以被向量化，而9 0 左右 的串行計算可以并行化【8 】。 當今，計算科學已經(jīng)和傳統(tǒng)的兩種科學，即理論科學和實驗科學，并列成 為第三門科學，它們彼此相輔相成的推動科學發(fā)展與社會進步。在許多情況下， 或者是理論模型復(fù)雜甚至理論尚未建立、或者實驗費用昂貴甚至實驗無法進行， 此時計算科學就成為求解問題的唯一或主要手段。計算科學極大的增強了人們 從事科學研究的能力，大大地加速了把科技轉(zhuǎn)化為生產(chǎn)力的過程，深刻地改變 著人類認識世界和改變世界的方法和途徑。計算科學的理論和方法，作為新的 研究手段和新的設(shè)計與制造技術(shù)的理論基礎(chǔ)，正推動著當代科學與技術(shù)向縱深 發(fā)展。 人類對計算機性能的要求是無止境的，在諸如預(yù)測模型的構(gòu)造和模擬、工 程設(shè)計和自動化、能源勘探、醫(yī)學、軍事以及基礎(chǔ)理論研究等領(lǐng)域中都對計算 機提出了極高的具有挑戰(zhàn)性的要求。例如，在制造業(yè)領(lǐng)域，工程計算和模擬如 果可能的話必須在幾秒或幾分鐘內(nèi)完成。在設(shè)計環(huán)境中，如果進行一次模擬需 武漢理工大學碩士學位論文 要兩星期才能得到結(jié)果，這通常是不可能接受的。因為只有模擬完成時間足夠 短時，設(shè)計者方可高效地工作【9 】。當系統(tǒng)變得更復(fù)雜時，就需要增加更多時間對 系統(tǒng)進行模擬。有一些應(yīng)用問題的計算對時間有特定的期限( 最著名的要數(shù)氣 象預(yù)報) ，花兩天時間來獲得當?shù)氐诙炀_的天氣預(yù)報將使得這種預(yù)報毫無 意義。某些研究領(lǐng)域，如對大型d n a 結(jié)構(gòu)建模以及進行全球天氣預(yù)報均具有巨 大挑戰(zhàn)性問題。所謂巨大挑戰(zhàn)性問題是指無法用當今計算機在合理的時間內(nèi)完 成求解的那些問題。 另一個需要巨大計算量的應(yīng)用問題是預(yù)測太空中天體運動。每個天體由于 萬有引力而相互吸引，這些遠距離的力可用簡單公式加以計算，而每個天體的 運動可以通過計算天體所受合力的計算加以預(yù)測。如果共有n 個天體，則每個 天體將總共需計算n 1 個力，約n 2 次計算。例如，銀河系可能有l(wèi) o “個星體， 此時就需重復(fù)計算1 0 2 2 次，即使使用一個僅需l o g 。n 次計算的高效的近似算法( 但 每次計算中含有更多的計算量) ，計算的總量仍異常巨大( i 0 “l(fā) o g 。i 0 “) 。若在 單處理器系統(tǒng)上運算將需要很長時間，即使每次計算僅需1 微妙( i 0 “秒，這是 非常樂觀的估計，因為次計算中含有多次乘法和除法) ，則使用n 2 算法是，迭 代就需要1 0 9 年，兩用n l o g ；n 算法時，一次迭代也需幾乎是一年的時間。 最后，計算機運算處理速度的提高和存儲容量的增大主要靠電子工程學的 元件技術(shù)成果。隨著處理器系統(tǒng)規(guī)模日益龐大、技術(shù)日益復(fù)雜，其運算處理速 度的提高不論在理論上還是技術(shù)上都會受到限制。一是計算機電路中信息傳輸 是由電子運動實現(xiàn)，傳輸速度約為光速的一半；二是元器件的物理尺寸受氫原 子直徑d h 的限制不可能無限變小，使用硅材料的v l s i 器件，其特征尺寸以o 1 1 1i f ! 為極限；三是器件的發(fā)熱和冷卻問題，如1 億次的c r a y l 超級計算機用了 幾噸的液態(tài)氟進行冷卻。據(jù)資料估計，單處理機的極限速度為每秒1 0 9 l o “浮 點運算，目前的技術(shù)水平已趨近這個極限。即使微電子技術(shù)的進步還有很大的 潛力，如采用量子效應(yīng)集成電路工藝生成的芯片，可比現(xiàn)在的硅芯片的速度快 幾百倍，但一個c p u 滿足不了多個i 0 設(shè)備的處理速度要求，出現(xiàn)了信號的擁 擠堵塞現(xiàn)象，即所謂的“馮諾依曼隘口”，使得整個系統(tǒng)的性能降低。因此， 并行計算就成為提高計算機系統(tǒng)速度的一個新思路f l 。 總之，并行計算是具有戰(zhàn)略意義、影響深遠的研究領(lǐng)域，將成為一個國家 綜合實力的重要指標之，無論是科技、經(jīng)濟、社會的發(fā)展都越來越離不開高 性能計算。它不僅是一種產(chǎn)業(yè)能力，更是國家尊嚴和國力的表現(xiàn)。正因為如此， 4 武漢理工大學碩士學位論文 世界各國都爭相發(fā)展高性能計算機技術(shù)，以圖在科技和經(jīng)濟發(fā)展的較量中占得 先機。 2 2 當代主要的并行計算機系統(tǒng)及其結(jié)構(gòu)模型 大型并行機系統(tǒng)一般可分為6 類：單指令多數(shù)據(jù)流機s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l e - d a t a ) ；并行向量處理機p v p ( p a r a l l e lv e c t o r p r o c e s s o r ) ；對稱多處理機s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) ；大規(guī)模并行 處理機m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) ；工作站機群c o w ( c l u s t e ro f w o r k s t a t i o n ) 和分布共享存儲d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 多處理機“。 s i m d 計算機多為專用，其余的5 種均屬于多指令多數(shù)據(jù)流m i m d ( m u l t i p l e i n s t r u c t i o nm u l t i p l e d a t a ) 計算機。但隨著計算機的發(fā)展，曾 經(jīng)風行一時的向量機和s i m d 計算機已退出歷史舞臺，而m i m d 類型的并行機卻 占了主導地位。當代主流的并行機是可擴放的并行機，包括共享內(nèi)存的對稱多 處理機( s m p ) 和分布存儲的大規(guī)模并行處理機( m p p ) 和工作站機群( c o w ) 。 對稱多處理機的結(jié)構(gòu)示于圖2 1 。s m p ( s y m m e t r i cm u l t i p r o c e s s o r s ) 系統(tǒng)使 用商品微處理器( 具有片上或外置高速緩存) ，它們經(jīng)由高速總線( 或交叉開關(guān)) 連向共享存儲器。這種機器主要應(yīng)用于商務(wù)，例如數(shù)據(jù)庫、在線事務(wù)處理系統(tǒng) 和數(shù)據(jù)倉庫等。其結(jié)構(gòu)具有如下特征：( 1 ) 對稱性：系統(tǒng)中任何處理器均可訪 問任何存儲單元和1 7 0 設(shè)備；( 2 ) 單地址空間：單地址空間有很多好處，例如因 為只有一個o s 和d b 等副本駐留在共享存儲器中，所以o s 可按工作負載情況 在多個處理器上調(diào)度進程從而易達到動態(tài)負載平衡，又如因為所有數(shù)據(jù)均駐留 在同一共享存儲器中，所以用戶不必擔心數(shù)據(jù)的分配和再分配；( 3 ) 高速緩存 及其一致性：多極高速緩存可支持數(shù)據(jù)的局部性，而其一致性可有硬件來增強； ( 4 ) 低通信延遲：處理器間的通信可用簡單的讀寫指令來完成( 而多計算機系 統(tǒng)中處理器間的通信要多條指令刁能完成發(fā)送接收操作) 【l “。 目前大多數(shù)商用s m p 系統(tǒng)都是基于總線連接的，占了并行計算機很大市場， 但是s m p 也具有如下問題：( 1 ) 欠可靠：總線、存儲器或o s 失效均會造成系 武漢理工大學碩士學位論文 統(tǒng)崩潰，這是s m p 系統(tǒng)最大的問題；( 2 ) 可觀的延遲：盡管s m p 比m p p 通信 延遲要小，但相對處理器速度而言仍然相當可觀( 競爭會加劇延遲) ，一般為數(shù) 百個處理器周期，長者可達千個指令周期；( 3 ) 慢速增加帶寬：有人估計，主 存和磁盤容量為每3 年增加4 倍，而s m p 存儲器總線帶寬每3 年只增加2 倍， i o 總線帶寬增加速率則疆慢，這樣存儲器帶寬的增長跟不上處理器速度或存儲 容量的步伐；( 4 ) 不可擴放性：總線是不可擴放的，這就限制最大的處理器數(shù) 一般不能超過1 0 。為了增大系統(tǒng)的規(guī)模，可改用交叉開關(guān)連接，或改用c c n u m a ( 高速緩存的一致性的非均勻存儲器訪問) 或機群結(jié)構(gòu)【1 2 】。 l 卜 ， 系統(tǒng)互連 ， l ( 總線、交叉井關(guān)，多極網(wǎng)絡(luò)) 圖2 - 1s m p 并行機結(jié)構(gòu)模型 m p p ( m a s s i v e l y p a r a l l e lp r o c e s s o r ) 一般是指由成百上千處理器組成超大型 ( v e r yl a r g e s c a l e ) 計算機系統(tǒng)。所有的m p p 均使用物理上分布的存儲器，且 使用分布的i o 也變多。它的結(jié)構(gòu)示于圖2 2 。其中每個節(jié)點有一個或多個處理 器和高速緩存( p c ) 、一個局部存儲器、有或沒有磁盤和網(wǎng)絡(luò)結(jié)構(gòu)電路( n i c ： n e t w o r ki n t e r f a c ec i r c u i t r y ) ，它們均連向本地互連網(wǎng)絡(luò)，而節(jié)點間通過高速網(wǎng)絡(luò) ( h s n ：h i 曲s p e e dn e t w o r k ) 相連。它具有如下特征：( 1 ) 處理器節(jié)點采用商 用微處理器；( 2 ) 系統(tǒng)中有物理上的分布式存儲器；( 3 ) 采用高通信帶寬和低 延遲的互連網(wǎng)絡(luò)( 專門設(shè)計和定制的) ；( 4 ) 能擴放至成百上千個處理器；( 5 ) 它是一種異步的m i m d 機器，程序系有多個進程組成，每個都有其私有地址空 間，進程間采用傳遞消息相互作用。m p p 的主要應(yīng)用是科學計算、工程模擬和 武漢理丁大學碩士學位論文 信號處理等以計算為主的領(lǐng)域。 2 2 3 聊槲刪 圖2 2m p p 并行機結(jié)構(gòu)模型 隨著工作站性能迅速提高和價格日益下降以及高速網(wǎng)絡(luò)產(chǎn)品陸續(xù)問世，一 種新型的并行計算系統(tǒng)便應(yīng)運而生。這種系統(tǒng)將一群工作站用某種結(jié)構(gòu)的網(wǎng)絡(luò) 互連起來，充分利用各工作站的資源，統(tǒng)一調(diào)度、協(xié)調(diào)處理，以實現(xiàn)高效并行 計算。如圖2 3 所示。它由工作站和互連網(wǎng)絡(luò)兩部分組成，互連網(wǎng)絡(luò)可以是普 通的l a n ( 如以太網(wǎng)、令牌環(huán)和f d d i 等) ，也可以是高速開關(guān)網(wǎng)絡(luò)( 如a t m ， 交換式高速以太網(wǎng)等) 。工作站是個廣義的稱呼，它可以是高檔微機，甚至也可 以是個對稱多處理機s m p 。一個實用的c o w ( c l u s t e ro fw o r k s t a t i o n ) 還應(yīng) 有一個高效的軟件環(huán)境，包括操作系統(tǒng)、可由用戶調(diào)用的通信原語庫以及并行 程序設(shè)計環(huán)境與工具等【1 4 , 1 5 , 1 6 。從用戶、程序員和系統(tǒng)管理員的角度看，c o w 相當于單一并行系統(tǒng)，感覺不到多個工作站的實際存在；從程序設(shè)計模式的角 度看，它與m p p 一樣可采用面向消息傳遞的s p m d ( s i n g l ep r o g r a mm u l t i p l e d a t a ) 編程方式，各個工作站均運行一個程序，但分別加載不同的數(shù)據(jù)，從而支 持粗粒度的并行應(yīng)用程序。 和前面所介紹的對稱多處理機s m p 和大規(guī)模并行處理機m p p 相比，c o w 在實用上具有一些明顯的優(yōu)點： ( 1 ) 投資風險小：用戶在購置傳統(tǒng)巨型機或m p p 系統(tǒng)時，總是擔心使用效率 不高或性能發(fā)揮得不好，如果購置后在一定程度上確實出現(xiàn)此問題，就相當于 浪費了大批資金，但c o w 不存在此問題，因為即使c o w 在技術(shù)上不夠先進， 7 武漢理工大學碩士學位論文 但每臺高性能的工作站仍可照舊使用，不浪費資金；( 2 ) 編程方便：用戶無需 學用新的并行程序設(shè)計( 如并行c 、c + + 和f o r t r a n 等) ，只需利用所提供的并行 程序設(shè)計環(huán)境，在常規(guī)的c ，c + + 和f o r t r a n 等程序中相應(yīng)的地方插入少量的幾 條原語，即可使這些程序在c o w 上運行，這一點最受用戶歡迎；( 3 ) 系統(tǒng)結(jié)構(gòu) 靈活：用戶將不同性能的工作站使用不同的體系結(jié)構(gòu)和互連網(wǎng)絡(luò)構(gòu)成同構(gòu)或異 構(gòu)的工作站機群系統(tǒng)，從而可彌補單體系結(jié)構(gòu)使用面窄的弱點，可更充分的 滿足各類應(yīng)用的需求：( 4 ) 性能價格比高：一般一臺巨型機或m p p 都很昂貴， 而一臺高性能工作站相對便宜，一個c o w 系統(tǒng)從浮點運算能力來看雖然有限， 但一群工作站的總體運算性能可接近些巨型機的性能，但價格卻低了很多。 ( 5 ) 能充分利用分散的計算資源：當個人工作站處于空閑狀態(tài)時，c o w 可在 空閑時間內(nèi)給這些工作站加載并行計算任務(wù)，從而工作站資源可得到充分利用； ( 6 ) 可擴放性好：用戶可根據(jù)需要增加工作站的數(shù)目，以高帶寬和低延遲的網(wǎng) 絡(luò)技術(shù)支持獲得高的加速比，從而獲得應(yīng)用問題的高可擴性。 實現(xiàn)工作站機群需要解決的主要問題是通信性能和并行編程環(huán)境。因為組 成c o w 的硬件環(huán)境中工作站的性能已相當高，且還在不斷的提高，相對而言工 作站性能不是關(guān)鍵問題；相反，負責數(shù)據(jù)通信的互連網(wǎng)絡(luò)卻是一項關(guān)鍵技術(shù)， 因為c o w 系統(tǒng)中并行計算時各工作站之間需要經(jīng)過互連網(wǎng)絡(luò)交換數(shù)據(jù)，某些工 作站上的程序所需要的數(shù)據(jù)也往往要通過網(wǎng)絡(luò)獲取或提交。如果網(wǎng)絡(luò)通信延遲 時間很長，再加上用于通信的軟件開銷( 此部分不可忽略) 可能就限制了c o w 技術(shù)對某些問題的適用性。近幾年來網(wǎng)絡(luò)技術(shù)發(fā)展很快，從而很好的支持理論 工作站的互連j 。 圖2 - 3c o w 并行機結(jié)構(gòu)模型 武漢理工大學碩士學位論文 伴隨高速網(wǎng)絡(luò)而產(chǎn)生的另關(guān)鍵技術(shù)就是工作站到網(wǎng)絡(luò)的主機接口網(wǎng)絡(luò)接 口的設(shè)計，它應(yīng)盡量保持網(wǎng)絡(luò)的傳輸速度與主機數(shù)據(jù)收發(fā)速度相匹配，其中增 加高速緩存或采用d m a 是可供選擇的兩種技術(shù)。網(wǎng)絡(luò)接口使工作站可以利用網(wǎng) 絡(luò)傳輸數(shù)據(jù)，但也增加了通信延遲，它占用了工作站c p u 時間，從而影響了c o w 的性能。一般一次通信時間延遲可如圖2 4 所示，其中d 為操作系統(tǒng)調(diào)度時間， a 用于分配緩沖，c 用于拷貝數(shù)據(jù)到緩沖區(qū)，s 為啟動發(fā)送接收時間，t 為鏈路 傳輸時間，f 用于定位中斷源，x 用于從接收隊列獲取數(shù)據(jù)。一般減少延遲的方 法有：( 1 ) 設(shè)計精簡通信協(xié)議以減少數(shù)據(jù)移動的次數(shù)和協(xié)議處理時間：( 2 ) 采 用主動消息( a c t i v em e s s a g e ) 攜帶數(shù)據(jù)處理命令以重疊計算和通信；( 3 ) 定制 通信處理單元以消除通信對工作站c p u 的依賴。 發(fā)送方物理連接接收方 發(fā)送方延遲 接收方延遲 1 協(xié)議處理 鏈路傳輸 協(xié)議處理 r 1 一 d a | ci stf i s i x l c 圖2 4 一次通信的時間延遲 另外，c o w 要走向?qū)嵱帽仨殲橛脩籼峁┮粋€良好的使用環(huán)境和一套完整的 工具系統(tǒng)，主要包括：( 1 ) 并行編程環(huán)境，如一些通信原語庫、多種編程語言 ( e x p r e s s 、p v m 、l i n d a 、p 4 、m p i ) 的支持以及并行編譯器等；( 2 ) 可視化監(jiān) 視調(diào)試器( 典型的斷點調(diào)試工具如c r a y 的m t d b x 和t o t a l v i e w 等) ；( 3 ) 并行 圖形庫( 如基于e x p r e s s 的p l o t i x 等) ；( 4 ) 并行文件系統(tǒng)和數(shù)據(jù)庫，以適用分 布式事務(wù)處理的研究與開發(fā)1 1 “。 前面我們多處提到機群這個概念，在本節(jié)中，我們將對有關(guān)計算機機群的 基本概念作進一步的詳細描述。 武漢理工大學碩士學位論文 機群是全體計算機( 節(jié)點) 的集合，這些計算機由高性能網(wǎng)絡(luò)或局域網(wǎng)( l a n ) 物理地互連。典型情況下，每個計算機節(jié)點是一臺s m p 服務(wù)器、一臺工作站或 是一臺p c 計算機。更重要的是，所有機群節(jié)點必須能一起集體工作，如同一個 單一集成資源，除了滿足由交互用戶單獨地使用每個節(jié)點的協(xié)定任務(wù)之外。 下面描述有關(guān)機群的五個系統(tǒng)結(jié)構(gòu)概念。 機群節(jié)點：每個節(jié)點是臺完整計算機。這就意味著每個節(jié)點有自己的 處理器、高速緩存、磁盤以及某些i o 適配器。此外在每個節(jié)點上駐留 有完整、標準的操作系統(tǒng)。一個節(jié)點可擁有多臺處理器，但只有一份 o s ( 操作系統(tǒng)) 映像拷貝。 單一系統(tǒng)映像：一個機群是一個單一計算資源。與此相反的是分布式系 統(tǒng)( 例如一個局域計算機網(wǎng)) ，在那里將節(jié)點作為單獨資源。機群借助 若干單一系統(tǒng)映像( s s i ：s i n g l es y s t e mi m a g e ) 技術(shù)，實現(xiàn)單資源概 念。s s i 使機群變得更易使用和管理。目前大多數(shù)商品化可用機群還沒 到可完全實現(xiàn)s s i 操作的程度。 節(jié)點間連接：機群中的節(jié)點，通常用商品化網(wǎng)絡(luò)，如以太網(wǎng)、f d d i 、光 纖通道以及a t m 開關(guān)進行連接。此外使用標準協(xié)議以平滑節(jié)點間通信。 增強的可用性：機群化提供了一個成本有效方法以增強一個系統(tǒng)的可用 性，這是指一個系統(tǒng)可為用戶使用的時間百分比。 更好的性能：在若干服務(wù)領(lǐng)域中，機群應(yīng)能提供更高性能。其中一個服 務(wù)領(lǐng)域是將機群作為超級服務(wù)器使用。如果一個具有n 個節(jié)點的機群中 的每個節(jié)點能為m 個客戶服務(wù)，則該機群就能同時為m n 個客戶服務(wù)。 另一個服務(wù)領(lǐng)域是機群通過分布式并行處理方法，用最短時間去完成一 個大型作業(yè)的執(zhí)行。 機群概念帶來了許多好處，同時也帶來了挑戰(zhàn)。其中最重要的是能用性 ( u s a b i l i t y ) 、可用性、可擴張性、可用利用率( a v a i f a b l eu t i l i z a t i o n ) 和 性能價格比。 武漢理工大學碩士學位論文 將一批工作站用以太網(wǎng)簡單的互連起來，并稱其為機群，幾乎不可能形成 一個高可用性和高性能系統(tǒng)。必須要采用一些技術(shù)( 大部分軟件) 以獲得這些 潛能。這些技術(shù)涉及到的方面有： ( 1 ) 能用性由于機群中每個節(jié)點均是傳統(tǒng)平臺，故用戶能在熟悉和成熟 環(huán)境中開發(fā)和運行他們的應(yīng)用程序。平臺提供了所有功能很強的工作站編程環(huán) 境工具，并允許幾千個現(xiàn)有的( 順序) 應(yīng)用程序無需修改便可運行。因此一個 機群可視為一個巨型工作站，它能為多個順序用戶作業(yè)運行提供大為增加的吞 吐率并減少響應(yīng)時間。 ( 2 ) 可用性術(shù)語可用性是指一個系統(tǒng)從事生產(chǎn)性使用的時間百分比。傳 統(tǒng)的整體系統(tǒng)，如主機和容錯系統(tǒng)依靠昂貴的定制設(shè)計來獲取高可用性。機群 不使用定制組件，而使用廉價的商品化組件以提供含有大量冗余的較高可用性： 處理器和存儲器：機群有多個存儲器和處理器部件，當某個部件失效時， 其它的仍可使用，因此機群仍能運行。與此相反，s m p 機的共享存儲器 失效時，整個系統(tǒng)將崩潰。 磁盤陣列：一個機群有多個局部磁盤。因此如果其中一個損壞，不會使 整個系統(tǒng)崩潰。事實上，具有失效磁盤的節(jié)點可使用遠程磁盤，因而可 繼續(xù)工作。 操作系統(tǒng)：一個機群有多個操作系統(tǒng)映像，每個駐留在分離節(jié)點上。當 一個系統(tǒng)映像崩潰時，其他節(jié)點仍能工作。與此相反，s m p 只有一個操 作系統(tǒng)映像，駐留在共享存儲器，若該映像被毀，則整個系統(tǒng)便將崩潰。 實現(xiàn)機群潛在可用性的關(guān)鍵在于有關(guān)軟件技術(shù)。此外也需要使共享部件( 如 互連) 具有高可用性的技術(shù)，否則它們將成為單失效點( s i n g l ep o i n t o f f a i l u r e ) 。 ( 3 ) 可擴展性能一個機群的計算能力隨節(jié)點增加而增加。其次，機群的 可擴展性是群體可擴展性。關(guān)于這一點，通過機群和s m p 的比較可得到最好的 了解。s m p 是處理器可擴展系統(tǒng)，而機群擴展是多組件的，包括處理器、存儲器、 磁盤，甚至i o 部件。因為是松耦合，機群能擴展至幾百個節(jié)點，而對于s m p 來講，要超過幾十個節(jié)點就非常困難。 在s m p 中，共享存儲器( 以及存儲器總線) 是瓶頸。當幾個順序程序運行 于一個s m p 上時，它們不得不競爭使用存儲器，盡管這些程序是完全獨立的。 相同的程序集運行于機群時，不存在存儲器瓶頸。每個程序可在一個節(jié)點上執(zhí) 武漢理工大學碩士學位論文 行，使用局部存儲器。 對于這類應(yīng)用，機群可提供更高的總體存儲器帶寬和減少存儲器時延。機 群的局部磁盤也聚集為大磁盤空間，可容易地超過集中式r a i d 磁盤空間。增強 的處理、存儲和；o 能力使得機群只需使用良好開發(fā)的，如p v m 或m p i 那樣的 并行軟件包，就可求解大型應(yīng)用問題。 ( 4 ) 性能成本比機群能成本有效的獲取上述優(yōu)點。傳統(tǒng)的p v p ( p a r a j l e l v e c t o rp r o c e s s o r ) 超級計算機以及m p p 的成本很易達到幾千萬美元。與此相 比，具有相同峰值性能的機群價格則要低1 到2 個數(shù)量級。機群大量的采用商 品化部件，它們的性能和價格遵循m o o r e 定律，從而使機群的性能成本比的增 長速率遠快于p v p 和m p p 。 2 4 并行算法基礎(chǔ)知識 2 4 1 并行算法定義與分類 算法是解題的精確描述，是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型 問題的一系列運算。并行計算是可同時求解的諸進程的集合，這些進程相互作 用和協(xié)調(diào)動作，并最終獲得問題的求解。并行算法就是對并行計算過程的精確 描述【1 9 。 并行算法可以從不同的角度分類為數(shù)值計算并行算法和非數(shù)值計算并行算 法：同步并行算法和異步并行算法；共享存儲并行算法和分布存儲并行算法。 數(shù)值計算是指基于代數(shù)關(guān)系運算的計算問題，如矩陣運算、多項式求值、 線性代數(shù)方程組求解等。求解數(shù)值計算問題的算法稱為數(shù)值算法( n u m e r i c a l a l g o r i t h m ) ?？茖W與工程中的計算問題如計算力學、計算物理、計算化學等 般是數(shù)值計算問題。非數(shù)值計算是指基于比較關(guān)系運算的一類諸如排序、選擇、 搜索、匹配等符號處理，相應(yīng)的算法也稱為非數(shù)值算法( n o n n u m e r i c a l a l g o r i t h m ) 。非數(shù)值計算在符號類信息處理中獲得廣泛應(yīng)用，如數(shù)據(jù)庫領(lǐng)域的 計算問題、海量數(shù)據(jù)挖掘等，近年來廣泛關(guān)注的生物信息學主要也是非數(shù)值計 算。 武漢理工大學碩士學位論文 2 4 2 并 亍算法的復(fù)雜性 對于并行算法，除了研究所需的運行時間之外還需要研究其算法所需處理 器數(shù)目以及研究兩者在最壞情形下與問題規(guī)模n 的變化關(guān)系。 運行時間t ( n ) ：它通常包含兩部分的時間，一是數(shù)據(jù)從一個處理器經(jīng) 由互連網(wǎng)絡(luò)或共享存儲器到達另一個處理器所需要的選路時間t r ( r o u t i n gt i m e ，即通信時間) ；二是數(shù)據(jù)在一個處理器內(nèi)作算術(shù)、邏 輯運算所需的計算時間t c 。 處理器數(shù)目p ( r 1 ) ：求解給定問題所需的處理器數(shù)目，可以固定大小，也 可以隨問題規(guī)模n 變化而變化。在實際應(yīng)用中，通常將處理器數(shù)目限制 為p ( n ) = n “，其中o ( e l 。 2 4 3 并行算法陛能評測 那么如何評價一個并行算法的優(yōu)劣呢? 顯然，單純考慮其所需的時間或者 其所使用的處理器數(shù)目都是不全面的。般地，需要綜合考慮以下各項指標： ( 1 ) 并行算法的代價c ( n ) ：將其定義為并行算法所需的運行時間t ( n ) 和所需處理器數(shù)目p ( n ) 的乘積，即：c ( n ) = t ( n ) 掌p ( n ) 。如果求解一 個問題的并行算法的執(zhí)行代價在階的意義上等于最壞情形下串行求解此問題所 需的運行時間( 步數(shù)) ，則稱這樣的并行算法是代價最佳的并行算法。 ( 2 ) 加速比s d ( n ) ：設(shè)t 。( n ) 是求解某個問題的最快速的串行算法在最 壞情形下所需的運行時間；t 。( 1 3 ) 是求解同一個問題的并行算法在最壞情形下 所需的運行時間，則s p ( n ) 定義為：s p ( n ) = t ：( n ) t 。( n ) ，s p ( n ) 的意 義是度量算法并行性對求解問題所需運行時間的改進程度。顯然，若s p ( n ) 越 大，并行算法就越好。在理想的情形下，s p ( n ) = p ( n ) ，即p ( n ) 臺處理器 去并行求解某個問題要比只用一個處理器去求解同一個問題快p ( n ) 倍。但在 絕大多數(shù)情況下，一方面所求解的原始問題不可能分解成n 個子任務(wù)且每個子任 務(wù)運行在一個處理器上所需時間為1 n ；另一方面并行計算機在并行求解過程 中，還需要進行數(shù)據(jù)交換或通信等方面的額外開銷，因此實際上s p ( n ) = p ( n ) 是不可能的。事實上，由于任何一個并行算法都能在一臺串行計算機上進行模 擬，所以：t 。( n ) p ( n ) t 。( n ) ，從而有：l s p ( n ) p ( n ) 。 武漢理工大學碩士學位論文 ( 3 ) 并行算法效率e p ( n ) ：雖然某個并行算法能獲得好的加速，但是有 時候其處理器利用率卻可能很低，特別對于處理器數(shù)目不固定的情形更是如此。