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

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