（水文學(xué)及水資源專業(yè)論文）機(jī)群環(huán)境下水環(huán)境并行數(shù)值模擬系統(tǒng)建立及應(yīng)用研究.pdf

摘要 當(dāng)前主流農(nóng)業(yè)非點(diǎn)源商業(yè)模型與g i s 的結(jié)合大都是采用e s r i 公司可編程控 件系列中功能最為簡(jiǎn)單的a t c v i e w 而功能最強(qiáng)的a r c e n g i n e 仍未有與模型結(jié)合 的成果 本文基于e s r i 公司功能強(qiáng)大的3 d 空間分析控件a r c e n g i n e 采用經(jīng)緯 式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)方法及c o m 技術(shù) 研發(fā)了水環(huán)境并行數(shù)值模擬系統(tǒng) 當(dāng)前主流并行平臺(tái)m p i p v m 尚未實(shí)現(xiàn)進(jìn)程遷移功能 當(dāng)進(jìn)行并行計(jì)算時(shí) 網(wǎng) 絡(luò)中某客戶端異常退出計(jì)算將導(dǎo)致臟數(shù)據(jù)的產(chǎn)生 本文自主開發(fā)了并行模型計(jì) 算平臺(tái) 采用c s 方式 服務(wù)器端對(duì)網(wǎng)絡(luò)環(huán)境進(jìn)行監(jiān)控和控制 為模型計(jì)算提供 數(shù)據(jù)交換及進(jìn)程遷移等功能 網(wǎng)絡(luò)發(fā)生故障時(shí)實(shí)時(shí)將未完成計(jì)算的河道轉(zhuǎn)移到其 它客戶端繼續(xù)計(jì)算 同時(shí) 為使資源達(dá)到最大的利用效率 本文提出了應(yīng)用螞蟻 算法進(jìn)行任務(wù)調(diào)度的新方法 提高了整個(gè)調(diào)度器的負(fù)載均衡能力 河道一維圣維南方程組采用p r e i s s m a n n 四點(diǎn)隱格式有限差分方法求解 采用 任務(wù)主從型并行編程模型 將迭代求解節(jié)點(diǎn)水位方程組系數(shù)進(jìn)行并行求解 在求 解節(jié)點(diǎn)水位方程組時(shí) 結(jié)合 上海浦東新區(qū)調(diào)水改善水環(huán)境 項(xiàng)目 根據(jù)機(jī)群負(fù) 載平衡的調(diào)度方案 制定了針對(duì)一維水量水質(zhì)模型的通訊協(xié)議 將河道按權(quán)重分 配到各客戶端進(jìn)行節(jié)點(diǎn)水位求解 河道二維淺水方程通過有限體積方法顯式求 解 采用任務(wù)s p m d 型并行編程模型 將求解區(qū)域網(wǎng)格分成若干部分 對(duì)每部 分進(jìn)行單獨(dú)求解 模型成功應(yīng)用于鎮(zhèn)江內(nèi)江水流數(shù)值模擬 并得到較高的加速比 和并行效率 對(duì)一 二維分別進(jìn)行并行數(shù)值模擬 結(jié)果表明當(dāng)河道 網(wǎng)格 數(shù)一定時(shí) 存在 一最優(yōu)客戶端數(shù) 當(dāng)客戶端數(shù)小于最優(yōu)客戶端數(shù)時(shí) 并行算法所需時(shí)間小于串行 算法時(shí)間 并隨著客戶端數(shù)增加 所需時(shí)間也逐漸減少 反之 所需時(shí)間則逐漸 增大 關(guān)鍵詞 a r c e n g i n e 并行計(jì)算 螞蟻算法 任務(wù)調(diào)度 有限體積法 a b s t r a c t m o s to fn o np o i n ts o u r c ep o l l u t i o nm o d e lh a si n t e g r a t e dw i t ha r e v i e w b u ta r c v i e wi st h e l o w e s t p l a t f o r m o f t h es e r i e s p r o d u c t s o f e s r i c o r p o r a t i o n u s i n g e s r ic o m p a n y s p o w e r f u l3 d a c t i v e xc o n t r 0 1 a r c e n g i n e d e s i g na n di m p l e m e n tw a t e re n v i r o n m e n ti n f o r m a t i o np a r a l l e l s y s t e mo l lc o mc o m p o n e n tt e c h n o l o g ya n dl o n g i t u d e l a t i t u d es t r u c t u r ed e s i g nm e t h o d f o rm p ia n dp v mh a sn o ti m p l e m e n t e dp r o c e s s 仃a n s f e r e n c ef u n c t i o n s ow h e nt h e c o m p u t i n gi sp r o c e s s i n g i fo n ec o m p u t e r sn e t w o r kc o r r u p ta l l a to r l c c t h er e s u l tw i l lb ew r o n g t h i sa r t i c l ed e v e l o p e sm e s s a g ep a r a l l e lp l a t f o r m t h ep l a t f o r mu s e sc l i e n t s 4 l v e rs t r u c t u r e s e r v e r c o n t r o lt h en e te n v i r o n m e n ta n dp r o v i d e sd a t ae x c h a n g ef u n c t i o ni ne a c hc o m p u t e r i ft h en e t w o r k h a st r o u b l e s o r v a rc o u l dt r a n s f e rc o m p u t e rt a s kf r o mo u to fo r d e rc o m p u t e rt oi no r d e rc o m p u t e r a tt h es a m ct i m e i no r d e rt og e tt h em i n i m u mc o m p u t e rt i m e t h i sa r t i c l eu s o o n tc o l o n y a l g o r i t h mt od i s p a t c ht a s k st oa c h i e v ew e a ll e v e l i n g b a s e do nt h es a i n t v e n a n te q u a t i o n s ao n e d i m e n s i o n a lm a t h e m a t i c a lm o d e lh a v eb e e n s o l u t i o n e db yp r e i s s m a n4 p o i n ts c h e m e t h em o d e lu s e st a s km a s t e r s l a v e rp r o g r a m m ef o r m e r i t a d o p t sp a r a l l e lm e t h o dt os o l u t ec o e f f i c i e n to fn o d e w a t e re q u a t i o na n da p p l i e s t op u d o n g r i v e m e t w o r k i no r d e rt oi m p l e m e n tp a r a l l e l i t y t h em o d e ld i v i d e sf r o mr i v e r sb ya n tc o l o n y a l g o r i t h ma n de s t a b l i s h e sc o r r e s p o n d i n gm e s s a g ep r o t o c 0 1 b a s e do nt h es a i n t v e n a n te q u a t i o n s 2 ds h a l l o ww a t e re q u a t i o n su s o ss i n g l ep r o g r a mm u l t i p l ed a t af o r m e r t h em o d e ld i v i d e sf r o m t r i a n g l e sb ya n tc o l o n ya l g o r i t h ma n ds o l u t i o n se a c hr e g i o n si n d e p e n d e n t l y i ta p p l i e st on e i j i a n g f i v e ra n dt h en u m e r i c a ls i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tv e r yh i g ha c c u r a c yc a nb ea c q u i r e d f e wt i m e so fi t e r a t i o n s ot h a tb e t t e rp a r a l l e ls p e e d u pi so b t a i n e d w h e na p p l y i n go n ea n dt w od i m e n s i o n a lf l o wm o d e lt oc h a n g j i a n gf i v e ro fn e i j i a n ga n d p u d o n gf i v e rn e t w o r kc o m p u t a t i o n t h er e s u l t ai n d i c a t e t h a ti fm a c h i n e sc o u n ti sl e s st h a nt h e o r i e n t a lc o n n t t h ec o n s u m et i m ei si n c r e a s i n ga c c o r dw i t ha d d i n gm a c h i n ec o u n t v i c ew f f r s a k e y w o r d s a r c e n g i n e p a r a l l e lc o m p u t i n g a n ta l g o r i t h m t a s ks c h e d u l i n g f i n i t ev o l u m e m e t h o d 刖吾 隨著社會(huì)經(jīng)濟(jì)的高速發(fā)展 水多 水少 水臟 等問題已經(jīng)引起了全社會(huì) 的廣泛重視 實(shí)現(xiàn)水資源可持續(xù)利用 已成為努力改善人類生存和經(jīng)濟(jì)社會(huì)條件 的關(guān)鍵因素 當(dāng)前 太湖流域水環(huán)境污染問題己日益嚴(yán)重 為改善水環(huán)境 通過 調(diào)水來解決水臟問題是一種行之有效的手段 如引江濟(jì)太 南水北調(diào) 博斯騰湖 調(diào)水及黑河調(diào)水等都是意義重大的工程 為了確定調(diào)水水量與河網(wǎng)內(nèi)水質(zhì)之問的關(guān)系 需要根據(jù)河網(wǎng)水體特征及其水 文 水質(zhì)同步監(jiān)測(cè)資料 采用數(shù)值計(jì)算方法 建立河網(wǎng)水力水質(zhì)數(shù)學(xué)模型 當(dāng)前 對(duì)于河道水流和水質(zhì)預(yù)測(cè) 為了減小數(shù)值計(jì)算誤差 需要將計(jì)算網(wǎng)格劃分得很細(xì) 同時(shí)由于河道流域規(guī)模一般都比較大 對(duì)于比較大的計(jì)算域進(jìn)行模擬需要布置的 網(wǎng)格節(jié)點(diǎn)也比較多 如果網(wǎng)格節(jié)點(diǎn)過多 計(jì)算工作量將成倍甚至成指數(shù)增長(zhǎng) 對(duì)于 計(jì)算機(jī)的計(jì)算速度要求比較高 近幾年來 隨著微機(jī)運(yùn)算速度大幅提高 價(jià)格低廉 同時(shí)局域網(wǎng)技術(shù)已十分成 熟 高性能互聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)和處理器之間的距離已不再是影響并行機(jī)系統(tǒng)性能 的關(guān)鍵因素 為利用微機(jī)組建并行計(jì)算集群提供了高性價(jià)比條件 從而被各階層 用戶所接受 正逐步成為并行編程的主要平臺(tái) 本文針對(duì)以上需求 自主研制了基于a r c e n g i n e 組件的并行水動(dòng)力數(shù)值模擬 系統(tǒng) 論文主要的創(chuàng)新成果有 l 分別對(duì)一 二維水量水質(zhì)模型顯 隱式求解方式進(jìn)行并行化改造 自主開發(fā) 了與模型配套的并行通信平臺(tái) 并制定了相關(guān)通訊協(xié)議 并行模型采用c s c l i e n t s e r v e r 結(jié)構(gòu) 服務(wù)器端對(duì)計(jì)算區(qū)域的劃分采用螞蟻智能算法對(duì)機(jī)群 中的作業(yè)進(jìn)行智能調(diào)度 并能實(shí)時(shí)監(jiān)測(cè)網(wǎng)絡(luò)狀況 對(duì)已分配任務(wù)計(jì)算機(jī)網(wǎng)絡(luò) 突然中斷 能迅速將所分配的任務(wù)轉(zhuǎn)移到其它空閑計(jì)算機(jī)上 實(shí)現(xiàn)進(jìn)程遷移 功能 將并行模型與a r c g i s 進(jìn)行無縫集成 開發(fā)了水環(huán)境并行數(shù)值模擬系統(tǒng) 2 一維水動(dòng)力模型采用p r e i s s m a n n 四點(diǎn)隱格式求解圣維南方程組 針對(duì)每個(gè)時(shí) 刻需要求解節(jié)點(diǎn)水位方程組來求出節(jié)點(diǎn)水位 進(jìn)而推求節(jié)點(diǎn)流量的特點(diǎn) 采 用任務(wù)主從型并行編程模型 將迭代求解節(jié)點(diǎn)水位方程組系數(shù)進(jìn)行并行求解 服務(wù)器端將河道分成若干部分 發(fā)往各客戶端 客戶端求解完畢后將結(jié)果返 回服務(wù)器端 服務(wù)器端再進(jìn)行下一時(shí)段的計(jì)算 3 二維水動(dòng)力模型采用有限體積顯式求解潛水方程 求解每個(gè)單元水位 流量 等信息時(shí)需要用到相鄰單元的水位 流量的數(shù)據(jù) 顯式求解方式是采用上一 個(gè)時(shí)刻相鄰單元的水位 流量值來求解本時(shí)刻單元的水位和流量 這樣就避 免了求解方程組 針對(duì)顯示求解的特點(diǎn) 采用任務(wù)s p m d 型并行編程模型 將求解區(qū)域網(wǎng)格分成若干部分 對(duì)每部分進(jìn)行單獨(dú)求解 服務(wù)器端負(fù)責(zé)將每 部分邊界單元的數(shù)據(jù)在相應(yīng)客戶端進(jìn)行交換 客戶端接收到數(shù)據(jù)后進(jìn)行本區(qū) 域本時(shí)段的計(jì)算并且在每個(gè)時(shí)段末 交換一次邊界上的計(jì)算數(shù)據(jù)直至計(jì)算完 畢 學(xué)位論文獨(dú)創(chuàng)性聲明 本人所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取 得的研究成果 盡我所知 除了文中特別加以標(biāo)注和致謝的地方外 論 文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果 與我一同工作的同事 對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意 如不實(shí) 本人負(fù)全部責(zé)任 論文作者c 簽孫 之蘭 盞 和7 年 7 月加 學(xué)位論文使用授權(quán)說明 河海大學(xué) 中國(guó)科學(xué)技術(shù)信息研究所 含萬方數(shù)據(jù)庫(kù) 國(guó)家圖書 館 中國(guó)學(xué)術(shù)期刊 光盤版 電子雜志社有權(quán)保留本人所送交學(xué)位論文 的復(fù)印件或電子文檔 可以采用影印 縮印或其他復(fù)制手段保存論文 本人電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致 除在保密期內(nèi)的保密論 文外 允許論文被查閱和借閱 論文全部或部分內(nèi)容的公布 包括刊登 授權(quán)河海大學(xué)研究生院辦理 論文作者 簽名 虛二蘭復(fù) 7 年7 月a 甲日 1 1 選題的背景及目標(biāo) 1 1 1 選題的背景 第一章緒論 我國(guó)水資源總量大 人均占有量小 水資源時(shí)間 空間上分布不均衡 同時(shí) 隨著我國(guó)經(jīng)濟(jì)的持續(xù)發(fā)展 水環(huán)境污染問題日益嚴(yán)重 使我國(guó)水問題日趨嚴(yán)唆 目前 通過調(diào)水來解決水問題是一種行之有效的手段 如引江濟(jì)太 南水北調(diào) 博斯騰湖調(diào)水及黑河調(diào)水等都是意義重大的工程 但是 通過這些工程可以緩解 環(huán)境壓力 工農(nóng)業(yè)用水及人畜飲用水等問題到何種程度 需要根據(jù)數(shù)學(xué)模型來模 擬 當(dāng)前 對(duì)于河道水流和水質(zhì)預(yù)測(cè) 為了減小數(shù)值計(jì)算誤差 需要將計(jì)算網(wǎng)格劃 分得很細(xì) 同時(shí)由于河道流域規(guī)模一般都比較大 對(duì)于比較大的計(jì)算域進(jìn)行模擬 需要布置的網(wǎng)格節(jié)點(diǎn)也比較多 如果網(wǎng)格節(jié)點(diǎn)過多 計(jì)算工作量將成倍甚至成指 數(shù)增長(zhǎng) 對(duì)于計(jì)算機(jī)的計(jì)算速度要求比較高 為了追求計(jì)算能力的提高 從元器 件到工藝 從大型高性能計(jì)算機(jī)到個(gè)人p c 機(jī) 硬件的性能一直在高速發(fā)展著 但 是同時(shí)由于受計(jì)算機(jī)元器件物理性能的限制 單機(jī)速度的提高也是具有其極限的 l o 現(xiàn)階段 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的改進(jìn)主要圍繞著并行處理技術(shù)展開 高性能并行 計(jì)算機(jī)的出現(xiàn)和發(fā)展使得大型科學(xué)與工程計(jì)算 特別是高維復(fù)雜問題的計(jì)算成為 可能 當(dāng)前高性能并行計(jì)算技術(shù)水平已經(jīng)成為一個(gè)國(guó)家經(jīng)濟(jì)和科技實(shí)力的綜合體 現(xiàn) 為此一些國(guó)家都制定了相應(yīng)的戰(zhàn)略計(jì)劃 其中最為著名的就是美國(guó)的 高性 能計(jì)算和通信 h i g h p e r f o r m a n c ec o m p u t i n ga n dc o m m u n i c a t i o n 簡(jiǎn)稱h p c c 和 加速戰(zhàn)略計(jì)算創(chuàng)新 a c c e l e r a t e ds t r a t e g i cc o m p u t i n gi n i t i a t i v e 簡(jiǎn)稱a s c i 口 我國(guó)在8 6 3 高科技研究發(fā)展計(jì)劃和國(guó)家9 7 3 基礎(chǔ)研究計(jì)劃重大項(xiàng)目中也有對(duì) 應(yīng)項(xiàng)目 并設(shè)立有專門的國(guó)家高性能計(jì)算基金 并且近幾年來 隨著微機(jī)運(yùn)算速 度大幅提高 價(jià)格低廉 同時(shí)局域網(wǎng)技術(shù)已十分成熟 高性能互聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)和 處理器之間的距離已不再是影響并行機(jī)系統(tǒng)性能的關(guān)鍵因素 為利用微機(jī)組建并 行計(jì)算集群提供了高性價(jià)比條件 從而被各階層用戶所接受 工f 逐步成為并行編 程的主要平臺(tái) 1 3 并行計(jì)算所要解決的問題通常包括大量的復(fù)雜計(jì)算和數(shù)據(jù)通訊與處理 此類 需求主要有 1 計(jì)算密集 c o m p u t ei n t e n s i v e 型應(yīng)用 如大型科學(xué)工程計(jì)算與數(shù)值模 擬 2 數(shù)據(jù)密集 d a t ei n t e n s i v e 型應(yīng)用 如數(shù)字圖書館 數(shù)據(jù)倉(cāng)庫(kù) 數(shù)據(jù) 挖掘和計(jì)算可視化等 3 網(wǎng)絡(luò)密集 n e t w o r ki n t e n s i v e 型應(yīng)用 如協(xié)同工作 遙控和遠(yuǎn)程醫(yī)療 診斷等 對(duì)于河道二維水動(dòng)力及水質(zhì)模擬屬于計(jì)算密集應(yīng)用問題 有限體積模型網(wǎng)格 經(jīng)常達(dá)到幾萬甚至幾百萬 但是采用單個(gè)p c 機(jī)需要的時(shí)間長(zhǎng) 內(nèi)存容量易受限 制 一般模型運(yùn)行是在設(shè)定工況的條件下進(jìn)行 運(yùn)行過程中基本資料不能修改 在率定計(jì)算中 是在計(jì)算完成后整合計(jì)算結(jié)果 通過與實(shí)測(cè)資料的對(duì)比 進(jìn)行修 改參數(shù) 參數(shù)一但修改 再進(jìn)行計(jì)算 如此往復(fù) 但一些大的計(jì)算模型運(yùn)行一次 就需要幾天甚至幾周時(shí)間 這樣就給模型的率定帶來了巨大的困難 從而使得分 析人員不得不減小計(jì)算規(guī)模 將網(wǎng)格劃分更粗 但這樣將導(dǎo)致計(jì)算結(jié)果可靠性降 低 當(dāng)前黃河下游計(jì)算區(qū)域從花園e l 至利津 長(zhǎng)約6 6 0 k m 若含灘區(qū)及滯洪區(qū) 則計(jì)算區(qū)域面積達(dá)4 0 0 0 k i n 2 左右 按主槽 灘地平均單元邊長(zhǎng)5 0 m 計(jì)算 網(wǎng)格 量達(dá)2 0 0 萬個(gè)以上 即使采用顯格式計(jì)算方法 單機(jī)計(jì)算下游洪水的演進(jìn)過程 所需時(shí)間也遠(yuǎn)大于天然洪水的實(shí)際傳播時(shí)間 也就是說 針對(duì)黃河下游的大區(qū)域 平面一維計(jì)算 從洪水預(yù)報(bào)的角度來講 單機(jī)計(jì)算是沒有意義的 并行計(jì)算系統(tǒng) 的大容量 高速度己經(jīng)逐步成為多傳質(zhì) 大尺度 多維模型研究和應(yīng)用的 助推 器 眾所周知 水動(dòng)力模型計(jì)算所需要的參數(shù)是眾多的 如每條河道的大斷面資 料 河道編號(hào) 首末節(jié)點(diǎn)號(hào) 糙率等 傳統(tǒng)的數(shù)值模型是將這些數(shù)據(jù)存儲(chǔ)于文本 文件中 文件每行每個(gè)數(shù)據(jù)對(duì)應(yīng)一個(gè)參數(shù) 這個(gè)文件一般人是看不懂的 因?yàn)槔?面只有一大堆的數(shù)據(jù) 也不知道每個(gè)數(shù)據(jù)的具體含義 因此 通常需要專門人員 才能對(duì)這個(gè)文件進(jìn)行編輯 而且由于沒有數(shù)據(jù)檢驗(yàn)功能 如果輸錯(cuò)參數(shù) 計(jì)算結(jié) 果全部無用 耗時(shí)耗力 出于傳統(tǒng)數(shù)值模型的眾多缺陷 當(dāng)前國(guó)外的商業(yè)模型已 2 將模型與g i s 緊密結(jié)合在一起 可以通過系統(tǒng)界面方便的進(jìn)行參數(shù)設(shè)置 計(jì)算結(jié) 果也能直觀的在地圖上顯示出來 大大提高了模型的易用性 l 1 2 選題的目標(biāo) 當(dāng)前環(huán)境水力學(xué)數(shù)值模擬差分求解格式可以分為顯格式 隱格式 顯隱交替 格式等 本文以一 二維水力水質(zhì)數(shù)值模擬為例 分別根據(jù)顯格式 隱格式求解 特點(diǎn) 探索各自并行求解思路及方法 為提高數(shù)值模擬計(jì)算速度提供技術(shù)支持 同時(shí) 將模型與a r c g i s 緊密結(jié)合 并構(gòu)建水環(huán)境數(shù)值模擬系統(tǒng) 由系統(tǒng)提供模 型所需的參數(shù) 并將計(jì)算結(jié)果通過系統(tǒng)直觀的表達(dá)出來 1 2 國(guó)內(nèi)外研究進(jìn)展 1 2 1 并行平臺(tái)應(yīng)用現(xiàn)狀 j 1 并行計(jì)算與并行計(jì)算體系結(jié)構(gòu) 并行計(jì)算口 p a r a l l e l c o m p u t i n g 就是在并行計(jì)算機(jī)上所作的計(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 是將一項(xiàng)大的數(shù)據(jù)處理與數(shù)值計(jì)算任務(wù) 或任務(wù)的局部 分裂成為多個(gè)可相互獨(dú) 謄 立 同時(shí)進(jìn)行的子任務(wù) 并通過對(duì)這些子任務(wù)相互協(xié)調(diào)的運(yùn)行和實(shí)現(xiàn) 從而達(dá)到 快速 高效的對(duì)給定問題求解的處理方法t 因?yàn)槿魏胃咝阅苡?jì)算和超級(jí)計(jì)算總 離不開使用并行技術(shù) 隨著計(jì)算機(jī)和計(jì)算方法的飛速發(fā)展 幾乎所有的學(xué)科都走 向了定量化和精確化 從而產(chǎn)生了一系列諸如計(jì)算物理 計(jì)算化學(xué) 計(jì)算生物學(xué) 計(jì)算地質(zhì)學(xué)等計(jì)算類科學(xué) 逐漸形成了一門計(jì)算性的學(xué)科分支 即計(jì)算科學(xué) i o i i 如今 計(jì)算科學(xué)已經(jīng)成為繼理論科學(xué)及實(shí)驗(yàn)科學(xué)之后的第三門科學(xué) 計(jì)算科學(xué)的 理論和方法 作為新的研究手段和新的設(shè)計(jì)與制造技術(shù)的理論基礎(chǔ) 正推動(dòng)著當(dāng) 代科學(xué)與技術(shù)向縱深發(fā)展 通常 針對(duì)計(jì)算科學(xué)中的復(fù)雜問題 傳統(tǒng)的單機(jī)模式 往往在完成時(shí)間和運(yùn)行效果上無能為力 而并行計(jì)算則被認(rèn)為是解決此類問題的 唯一可行途徑 并行計(jì)算機(jī)的發(fā)展歷程 并行計(jì)算機(jī)的發(fā)展 可分為四個(gè)階段 1 2 i 同步并行計(jì)算技術(shù)的預(yù)研期 并行機(jī)的研究大多屬于概念性的范疇 1 9 7 2 年以前 i i 同步并行計(jì)算實(shí)踐期 異步并行計(jì)算預(yù)研期 2 0 世紀(jì)7 0 年代 1 9 7 4 年c d c s t a r 1 0 0 向量機(jī)在美國(guó)的l a w r e n c el i v e m o r e 國(guó)家實(shí)驗(yàn)室投入使用 1 9 7 6 年c r a y 研究公司推出的向量式并行處理機(jī)在l o sa l m o s 實(shí)驗(yàn)室運(yùn) 1 轉(zhuǎn) 1 9 7 6 年后 控制數(shù)據(jù)公司的s t a r 1 0 0 改進(jìn)為c y b e r 2 0 5 c r a y 一1 改 進(jìn)為c r a y 1 s 并投入批量生產(chǎn) 一批功能強(qiáng)大的并行機(jī)相繼投入使用 使并行機(jī)的研究從初期就呈現(xiàn)出一副欣欣向榮的局面 n i 同步并行計(jì)算成熟期 異步并行計(jì)算實(shí)踐期 2 0 世紀(jì)8 0 年代 各種規(guī)模 的巨型機(jī) 超立體機(jī)和脈動(dòng)機(jī)迅速問世 并相繼投入使用 例如 日立 公司的s 8 2 0 1 8 0 巨型機(jī) i n t e l 公司的 p s c 簇超立體機(jī) h t k u n g 研制 的w a r p 脈動(dòng)陣列機(jī) i v 異步并行計(jì)算技術(shù)成熟期 2 0 世紀(jì)9 0 年代以后 n e c 研制出第一臺(tái)日本 生產(chǎn)的超級(jí)并行向量處理機(jī)s x 3 其每臺(tái)機(jī)器含有4 個(gè)處理器 每個(gè)處 理器含有4 條數(shù)據(jù)流水線 共有4 g 內(nèi)存 并行計(jì)算機(jī)結(jié)構(gòu) 大型并行機(jī)系統(tǒng)的結(jié)構(gòu)模型一般可分為5 類 8 n 單指令多數(shù)據(jù)流機(jī)s 珊 s i n g l e h l 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 枷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 汾布共享存儲(chǔ)多處理機(jī) d i s t r i b u t e ds h a r e d m e m o r y 工作站機(jī)群 c l u s t e r o fw o r k s t a t i o n i s i m d 這種結(jié)構(gòu)并行系統(tǒng)中 處理機(jī)同步執(zhí)行相同的指令流 而同時(shí)執(zhí) 行不同的數(shù)據(jù)流 i i p v p 系統(tǒng)由專門設(shè)計(jì)的高帶寬網(wǎng)絡(luò)及定制的處理器組成 一般采用共 享存儲(chǔ)方式 1 1 1 m p p 大型計(jì)算機(jī)系統(tǒng) 處理節(jié)點(diǎn)采用商品微處理器 采用分布式存儲(chǔ) 方式及專門設(shè)計(jì)的高帶寬 低延遲網(wǎng)絡(luò) i v s m p 與m p p 不同的是采用共享式存儲(chǔ)方式 每個(gè)處理機(jī)可等同的訪問共 享存儲(chǔ)器和i o 設(shè)備 v d s m 采用d i r 用以支持分布在各結(jié)點(diǎn)中的局部存儲(chǔ)器 從而形成一個(gè)共 4 享的存儲(chǔ)器 v i c o w 是近年來發(fā)展勢(shì)頭很好的一種體系結(jié)構(gòu) 這類機(jī)型的技術(shù)起點(diǎn)比 較低 用戶甚至可以自己將一些服務(wù)器或微機(jī)通過以太網(wǎng)連接起來 配 以相應(yīng)的管理 通訊軟件來搭建c l u s t e r 但是如果要構(gòu)造高性能 結(jié) 構(gòu)合理并具有好的r a s 特性的c l u s t e r 卻不是一件容易的事情 它使用的 是常見的硬件設(shè)備 象普通p c 以太網(wǎng)卡和集線器 很少使用特別定 制的硬件和特殊的設(shè)備 幾乎所有的國(guó)內(nèi) 外計(jì)算機(jī)廠商都有自己的 c l u s t e r 集群產(chǎn)品 如i b m 的c l u s t e r l 3 5 0 聯(lián)想的深騰系列及曙光的天 潮系列等 c l u s t e r 系統(tǒng)通常具有以下特點(diǎn) 系統(tǒng)由多個(gè)獨(dú)立的服務(wù)器 在c l u s t e r 概念下稱為節(jié)點(diǎn) 通過交換 杌連接在一起 每個(gè)節(jié)點(diǎn)擁有各自的內(nèi)存 某個(gè)節(jié)點(diǎn)的c p u 不能直接訪 問另外一個(gè)節(jié)點(diǎn)的內(nèi)存 每個(gè)節(jié)點(diǎn)擁有獨(dú)立的操作系統(tǒng) 需要一系列的集群軟件來完成整個(gè)系統(tǒng)的管理與運(yùn)行 包括 c l u s t e r 系統(tǒng)管理軟件 如i b m 的c s m x c a t 等 消息傳遞庫(kù) 如m p i p m 等 作業(yè)管理與調(diào)度系統(tǒng) 如l s f p b s l o a d l e v e l e r 等 并行文件系統(tǒng) 如p v f s g p f s 等 支持消息傳遞方式的并行模式 如m p i p v m 等 只能在單個(gè)節(jié)點(diǎn)內(nèi)部支持共享內(nèi)存方式的并行模式 如o p e n m p p t h r e a d s 等 性能價(jià)格比好 2 并行編程環(huán)境簡(jiǎn)介 要進(jìn)行并行計(jì)算 軟件支撐平臺(tái)是重要組成部分之一 廉價(jià)并行計(jì)算機(jī)的支 撐環(huán)境按并行計(jì)算支撐平臺(tái)可分為m p i m e s s a g ep a s s i n gi n t e r f a c e 一消息傳遞 接口 和p v m p a r a l l e lv i r t u a lm a c h i n e 并行虛擬機(jī) 以及l(fā) i n d a 等 l i n d a m f 5 1 9 世紀(jì)8 0 年代中期l i n d a 平臺(tái)是美國(guó)y a l e 大學(xué)的d a v i dg e l e r n t e r 開發(fā)的 是 第一個(gè)商業(yè)產(chǎn)品應(yīng)用于v s m 作為超級(jí)計(jì)算機(jī)和大規(guī)模工作站機(jī)群平行計(jì)算 與機(jī) 器無關(guān)的編程環(huán)境 它是一個(gè)關(guān)聯(lián)的 虛擬的共享存儲(chǔ)系統(tǒng) 新版的l i n d a 丌發(fā) 語(yǔ)言支持c 和f o r t r a n 能支持共享內(nèi)存多指令多數(shù)據(jù)流 m i 帥 系統(tǒng)和分布式內(nèi) 存 m i m d 系統(tǒng) 網(wǎng)絡(luò)機(jī)群等 有較強(qiáng)的穩(wěn)定性和可擴(kuò)張性 主要適合于一節(jié)點(diǎn) 上具有多個(gè)處理進(jìn)程 且進(jìn)程間同步點(diǎn)較多和全局通信較頻繁的應(yīng)用場(chǎng)合1 6 j m p i m p i 是消息傳遞接口的簡(jiǎn)稱 它實(shí)際上是一個(gè)消息傳遞函數(shù)庫(kù)的標(biāo)準(zhǔn)說明 提 供了一種與語(yǔ)言平臺(tái)無關(guān) 可以被廣泛使用的編寫消息傳遞程序的標(biāo)準(zhǔn) r 丌 其標(biāo) 準(zhǔn)化開始于1 9 9 2 年4 月2 9 日至3 0 e l 在威吉尼亞的威廉姆斯堡召開的分布存儲(chǔ)環(huán)境 中消息傳遞標(biāo)準(zhǔn)的討論會(huì)由d o n g a r r a h c m p e l h c y 和w a l k e r 建議的初始草案于 1 9 9 2 年1 1 月推出 并在1 9 9 3 年2 月完成了修訂版這就是m p i1 0 1 9 9 5 年6 月推出 了m p i 的新版本m p l l 1 對(duì)原來的i v i p i 作了進(jìn)一步的修改完善和擴(kuò)充 但是當(dāng)初推 出m p i 標(biāo)準(zhǔn)時(shí)為了能夠使它盡快實(shí)現(xiàn)并迅速被接受許多其它方面的重要但實(shí)現(xiàn) 起來比較復(fù)雜的功能都沒有定義比如并行i o 當(dāng)m 口i 被廣為接受之后擴(kuò)充并提高 m p i 功能的要求就越來越迫切了 于是在1 9 9 7 年的7 f l 在對(duì)原來的m p i 作了重大擴(kuò) 充的基礎(chǔ)上又推出了m p i 的擴(kuò)充部分m p i 2 而把原來的m p i 各種版本稱為 m p i 1 m p i 2 的擴(kuò)充很多但主要是三個(gè)方面并行f o 遠(yuǎn)程存儲(chǔ)訪問和動(dòng)態(tài)進(jìn)程管 理 1 8 2 1 m p i 以語(yǔ)言獨(dú)立的形式來定義這個(gè)接口庫(kù) 提供了與c f o r t r a n 和c 語(yǔ) 言的綁定 p v m p v m f 雒刀是并行虛擬機(jī) 由美國(guó)田納西大學(xué) o a k r i d g e 觥等研制的 并行程序開發(fā)環(huán)境 它可以把多個(gè)異構(gòu)的計(jì)算機(jī)組織起來成為一個(gè)易于管理的 可擴(kuò)展的 易編程使用的并行計(jì)算資源 它圍繞 虛擬機(jī) 的中心思想展開 即 通過網(wǎng)絡(luò)互聯(lián)的一系列異構(gòu)的主機(jī)在邏輯上對(duì)用戶呈現(xiàn)為單一的并行計(jì)算機(jī) 由 于p v m 強(qiáng)調(diào)虛擬機(jī)的擴(kuò)展性 異構(gòu)性和容錯(cuò)能力 因此它把可移植性看得比性能更 重要 它支持在異構(gòu)網(wǎng)絡(luò)中應(yīng)用程序問的通信 含有動(dòng)態(tài)的資源管理和進(jìn)程控制 功能 提供了容錯(cuò)的基本機(jī)制 當(dāng)發(fā)生錯(cuò)誤時(shí) 可以重新分配任務(wù) 3 冰hm p i 由于m p l 只支持c f o r t r a n 和c 語(yǔ)言的網(wǎng)絡(luò)分布并行計(jì)算編程環(huán)境 這就存 在m p i 應(yīng)用程序在不同系統(tǒng)間的二進(jìn)制兼容的問題 將j a v a 語(yǔ)言與m p i 結(jié)合起來 提供m p i 對(duì)j a v a 語(yǔ)言的支持 使用j a v a 語(yǔ)言編寫的并行程序?qū)⒕哂锌缙脚_(tái)的功能 矗 張曉軍 刀等人通過j a v a 語(yǔ)言調(diào)用m p i 的c 語(yǔ)言函數(shù)庫(kù) 將c 語(yǔ)言的參數(shù)數(shù)據(jù)類型轉(zhuǎn) 換戍j a v a 支持的數(shù)據(jù)類型 調(diào)用m p i 的庫(kù)函數(shù) 從而將j a v a 與m p i 結(jié)合起來 m p i 與嗍的比較 目前較為常用的并行編程環(huán)境為m p i 與p v m i 移植性 基于m p l 的并行應(yīng)用程序可以幾乎不作修改在不同型號(hào)的并行 機(jī)之間轉(zhuǎn)移 或轉(zhuǎn)移到網(wǎng)絡(luò)環(huán)境中運(yùn)行 1 6 1 p v m 的應(yīng)用程序可以在兩組 不同的計(jì)算機(jī)群之間移植 而不可能把并行應(yīng)用程序完全移植到單個(gè)的 并行機(jī)上去運(yùn)行 所以說 從可移植性上m p i 相對(duì)于p v m 有著無可比擬 的優(yōu)勢(shì) i i 通信模式 m p i 提供了點(diǎn)到點(diǎn)通信和集合通信 在點(diǎn)到點(diǎn)通信中 發(fā)送 只有阻塞式發(fā)送 接收有阻塞和非阻塞兩種 非阻塞通信機(jī)制可以在硬 件設(shè)備的支持下 實(shí)現(xiàn)通信和計(jì)算的并行 而p v m 沒有這種功能 在 集合通信中 m p i 提供了更多的全局操作函數(shù) 支持廣播 分散 收集 多收集 多對(duì)多等過程組內(nèi)多進(jìn)程數(shù)據(jù)通信操作 此外m p i 還支持進(jìn)程 組內(nèi)多進(jìn)程數(shù)據(jù)運(yùn)算操作 矧 相比較而言 p v m 雖然也提供了一些集 體通信操作函數(shù) 但是在集體通信函數(shù)數(shù)量 功能以及對(duì)數(shù)據(jù)處理的復(fù) 雜程度等方面遠(yuǎn)不如m p i i i i 安全通信 啪p i 中提供了通信子 c o m m u n i c a t o r 的概念 所謂通信子 就是點(diǎn)對(duì)點(diǎn)通信只能在屬于同一通信子的節(jié)點(diǎn)機(jī)間進(jìn)行 通信子對(duì)其起 屏蔽作用 即使形式上完全相同的通信操作 只要其所屬的通信子不同 m p i 就視其為截然不同的兩次操作 通信子的存在 保證了可靠安全的 通信環(huán)境 避免了通信空間的出錯(cuò) 提供了可靠的通信接e l 2 4 2 q p v m 類似于m p i 也提供了使一組任務(wù)獲得唯一的上下文標(biāo)簽的函數(shù) 在 p v m 中 當(dāng)屬于一個(gè)任務(wù)組 具有唯一的上下文標(biāo)簽 的一個(gè)任務(wù)失 敗后 容許一個(gè)新的任務(wù)使用這個(gè)唯一的上下文 從而提供了容錯(cuò)的功 能 但也引入了沖突的可能 例如當(dāng)一個(gè)任務(wù)的失敗導(dǎo)致了整個(gè)任務(wù)組 失敗 其擁有的唯一的上下文標(biāo)簽被釋放 此時(shí)如果有一個(gè)具有此上下 文的新任務(wù)生成 則將會(huì)引起沖突 i v 進(jìn)程管理 m p i 一1 完全是靜態(tài)的 認(rèn)為所有進(jìn)程是事先靜態(tài)初始化好了 盡管m p i 2 在此進(jìn)行了改進(jìn) 提供了增加一組進(jìn)程組的函數(shù)及組內(nèi)進(jìn)程 間發(fā)送控制信息的函數(shù) 可是并不支持對(duì)動(dòng)態(tài)進(jìn)程的查詢 但m p i 中對(duì) 任務(wù)分配提供了笛卡爾拓?fù)浜蛨D拓?fù)鋪矸峙滟Y源 有可能充分利用硬件 的特性來達(dá)到簡(jiǎn)化設(shè)計(jì) 提高效率 2 2 1 p v m 建立在虛擬機(jī)的概念上 有 完全的資源管理功能 用戶既可以增加或刪除計(jì)算資源 即計(jì)算機(jī)結(jié) 點(diǎn) 也可以把任務(wù) 通常表現(xiàn)為進(jìn)程 從一個(gè)計(jì)算機(jī)結(jié)點(diǎn)轉(zhuǎn)移到另一 個(gè)計(jì)算機(jī)結(jié)點(diǎn) 同時(shí) p v m 提供了動(dòng)態(tài)查詢和管理虛擬機(jī)中各個(gè)任務(wù) 及計(jì)算機(jī)結(jié)點(diǎn)狀態(tài)的函數(shù) 從而使用戶的應(yīng)用程序可以通過與p v m 虛 擬機(jī)的動(dòng)態(tài)交互 管理自己的計(jì)算環(huán)境 為實(shí)現(xiàn)計(jì)算環(huán)境的負(fù)載平衡 任務(wù)遷移和容錯(cuò)提供了強(qiáng)有力的支持閉 3 調(diào)度算法簡(jiǎn)介 在工作站網(wǎng)絡(luò) n o w 環(huán)境中 由于任務(wù)到達(dá)的隨機(jī)性以及各節(jié)點(diǎn)處理能力上 的差異 會(huì)造成某些節(jié)點(diǎn)分配的任務(wù)過多 重載 而另外一些節(jié)點(diǎn)卻是空閑的 輕載或空載 一方面使重載節(jié)點(diǎn)上的任務(wù)盡可能快地完成是當(dāng)務(wù)之急 另一 方面使某些節(jié)點(diǎn)空閑是一種浪費(fèi) 負(fù)載均衡設(shè)法對(duì)已經(jīng)分配的任務(wù)進(jìn)行重新調(diào) 度 并通過任務(wù)遷移使各節(jié)點(diǎn)負(fù)載大致相等 避免這種空閑和忙等待并存的情況 有效提高網(wǎng)格資源的利用率 減少任務(wù)的平均響應(yīng)時(shí)間 根據(jù)調(diào)度結(jié)點(diǎn)的數(shù)量 調(diào)度策略可分為集中式調(diào)度和分布式調(diào)度 集中式調(diào) 度 9 5 能夠減少通信的開銷 但是其調(diào)度的規(guī)模較大 易產(chǎn)生通訊瓶頸等問題 分 布式調(diào)度即 信息實(shí)時(shí)性強(qiáng) 可靠性好 易擴(kuò)充 但通信開銷搭 算法設(shè)計(jì)復(fù)雜 不易管理 根據(jù)調(diào)度策略執(zhí)行的時(shí)期 生產(chǎn)調(diào)度分為動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度兩大類 j a c k s o n 口刃虧 1 9 5 7 年對(duì)靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度的概念做了區(qū)分 靜態(tài)調(diào)度是在己知 調(diào)度環(huán)境和任務(wù)的前提下的所謂事前調(diào)度方案 動(dòng)態(tài)調(diào)度是指在調(diào)度環(huán)境和任務(wù) 存在著不可預(yù)測(cè)的擾動(dòng)情況下的調(diào)度方案 它不僅依賴于事前調(diào)度環(huán)境和任務(wù) 而且與當(dāng)前狀態(tài)有關(guān) 靜態(tài)任務(wù)調(diào)度算法要求事先知道完整的任務(wù)依賴關(guān)系和準(zhǔn) 確的任務(wù)執(zhí)行時(shí)間 這些要求在實(shí)際應(yīng)用中很難得到滿足 因此 在集群系統(tǒng)的 任務(wù)調(diào)度問題中 大多數(shù)的系統(tǒng)采用的是動(dòng)態(tài)調(diào)度算法 動(dòng)態(tài)調(diào)度的概念出現(xiàn)較早 最初的研究主要采用最優(yōu)化方法 m a t s u u r a 2 9 提 出的重調(diào)度算法 首先用分支定界法產(chǎn)生一個(gè)調(diào)度 當(dāng)工況發(fā)生變化時(shí) 再用調(diào)度 規(guī)則來分配工件 由于絕大多數(shù)調(diào)度問題已被證明是n p 問題 3 4 1 隨著調(diào)度問題規(guī) 模的增大 上述方法的求解難度將急劇增加 因而最優(yōu)化方法往往不能適應(yīng)生產(chǎn) 實(shí)際對(duì)實(shí)時(shí)性的要求 此外 該類方法大多基于某些理想化的假設(shè) 遠(yuǎn)不能充分 反映實(shí)際生產(chǎn)環(huán)境的復(fù)雜性 而且要充分表達(dá)實(shí)際生產(chǎn)環(huán)境的隨機(jī)性和動(dòng)態(tài)性 也極為困難 所以單獨(dú)使用此類方法來解決動(dòng)態(tài)調(diào)度問題是不現(xiàn)實(shí)的 近年來 計(jì)算機(jī)技術(shù)的迅速發(fā)展以及人工智能 神經(jīng)網(wǎng)絡(luò) 遺傳算法和仿真 技術(shù)等新方法的產(chǎn)生和發(fā)展 為動(dòng)態(tài)調(diào)度的研究開辟了新思路 也為生產(chǎn)調(diào)度的 實(shí)用化奠定了基礎(chǔ) 1 9 9 6 年 k w o k 和a h m a d 提出了一個(gè)動(dòng)態(tài)關(guān)鍵路徑 d c p 調(diào)度算 法 1 9 9 9 年 張宏莉等人針對(duì)單并發(fā)任務(wù)簇提出了一個(gè)最優(yōu)分配算法o p t a l 3 1 j 而單并發(fā)任務(wù)簇就等同于f o r k j o i n 任務(wù)圖 o c p 和o p t a 是兩個(gè)較好的調(diào)度算 法 1 9 9 8 年 d a r b h a g 口a g r a w a l 提出了一個(gè)基于任務(wù)復(fù)制 t d s 的調(diào)度算法 3 2 t d s 算法在調(diào)度長(zhǎng)度 s c h e d u l el e n g t h 方面 基本上比在它以前出現(xiàn)的所有算法都 優(yōu)越 因?yàn)樗ㄟ^任務(wù)復(fù)制減少了通信時(shí)間 但是 t d s 算法沒有考慮節(jié)省處理器 個(gè)數(shù)的問題 這會(huì)降低算法的加速比 s i 薛 1 提出一種專家神經(jīng)網(wǎng)絡(luò)方法 該方 法用1 6 個(gè)神經(jīng)網(wǎng)絡(luò)分別從相應(yīng)的訓(xùn)練樣本集中獲取調(diào)度知識(shí) 用專家系統(tǒng)確定各 子網(wǎng)的輸入 由于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練由1 6 個(gè)子網(wǎng)分擔(dān) 并且各子網(wǎng)可以并行訓(xùn)練 從而減少了訓(xùn)練時(shí)間 l e e 等i 搠用遺傳算法和機(jī)器學(xué)習(xí)來解決單件車問的調(diào)度問 題 用機(jī)器學(xué)習(xí)來產(chǎn)生將工件下發(fā)到車間層的知識(shí)庫(kù) 而用遺傳算法在各臺(tái)機(jī)器 上分配工件 螞蟻算法是f h d o r i g o p d 提出的解決組合優(yōu)化問題的一種多a g e n t 方法 其模 擬自然界中螞蟻覓食路徑的搜索過程 螞蟻在尋找食物時(shí) 能在其走過的路徑上 釋放信息素 p h e r o m o n e 螞蟻在覓食過程中能夠感知信息素的存在和強(qiáng)度 并 傾向于朝信息素強(qiáng)度高的方向移動(dòng) 當(dāng)大量螞蟻不斷地從蟻巢通往食物時(shí) 相同 時(shí)間內(nèi)相對(duì)較短路徑上通過的螞蟻較多 該路徑上累積的信息素強(qiáng)度也較大 后 來螞蟻選擇該路徑的概率也相對(duì)較大 最終整個(gè)蟻群會(huì)找到最優(yōu)路徑 許智宏 孫濟(jì)洲 3 8 將螞蟻算法應(yīng)用到網(wǎng)格計(jì)算任務(wù)調(diào)度中 其將一組需調(diào)度的任務(wù)定義為 一只螞蟻 隨機(jī)的分配到網(wǎng)絡(luò)的各節(jié)點(diǎn)上 每只螞蟻根據(jù)當(dāng)前各資源的信息素值 決定自己解域的下一任務(wù)分配給剩余各資源的概率 對(duì)每只螞蟻的分配結(jié)果計(jì)算 目標(biāo)函數(shù) 選當(dāng)前計(jì)算時(shí)間最小值為最佳解 將信息素恢復(fù)至本組任務(wù)調(diào)度前的 值 然后重復(fù)以上過程 到達(dá)終止步時(shí) 選得最優(yōu)解作為本組任務(wù)的分配方案 粒子群優(yōu)化算法 p s o 是由j a m e sk e n n e d y 博士和r c e b e r h a r t 博士于1 9 9 5 年提出的 該算法源于對(duì)鳥群 魚群覓食行為的模擬1 3 9 1 在p s 0 中 首先初始化 一群隨機(jī)粒子 隨機(jī)解 然后通過迭代尋找最優(yōu)解 在每一次迭代中 粒子通過 跟蹤兩個(gè)極值來更新自己的速度和位置 第一個(gè)就是粒子本身所找到的最優(yōu)解 這個(gè)解叫做個(gè)體極值 另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解 這個(gè)極值是全 局極值 另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居 那么在 所有鄰居中的極值就是局部極值 p s 0 算法簡(jiǎn)單易實(shí)現(xiàn) 不需要調(diào)整很多參數(shù) 主要應(yīng)用有神經(jīng)網(wǎng)絡(luò)的訓(xùn)練 函數(shù)的優(yōu)化問題等 劉志雄 王少梅 將港口拖輪 作業(yè)調(diào)度問題描述為一類帶特殊工藝約束的并行多機(jī)調(diào)度問題 采用粒子群算法 求解該類調(diào)度問題 提出了一種2 維粒子表示方法 通過對(duì)粒子位置向量進(jìn)行排序 生成有效調(diào)度 并采用粒子位置向量多次交換的局部搜索方法來提高算法的搜索 效率 1 2 2 流體力學(xué)中常用的數(shù)值離散方法 1 有限差分 f d m 有限差分方法 f i n i t e d i f f e r e n c e m e t h o d 是計(jì)算機(jī)數(shù)值模擬最早采用的方法 至今仍被廣泛運(yùn)用 該方法將求解域劃分為差分網(wǎng)格 用有限個(gè)網(wǎng)格節(jié)點(diǎn)代替連 續(xù)的求解域 有限差分法以t a y l o r 級(jí)數(shù)展開等方法 把控制方程中的導(dǎo)數(shù)用網(wǎng)格 節(jié)點(diǎn)上的函數(shù)值的差商代替進(jìn)行離散 從而建立以網(wǎng)格節(jié)點(diǎn)上的值為未知數(shù)的代 數(shù)方程組 該方法是 種直接將微分問題變?yōu)榇鷶?shù)問題的近似數(shù)值解法 數(shù)學(xué)概 念直觀 表達(dá)簡(jiǎn)單 是發(fā)展較早且比較成熟的數(shù)值方法 對(duì)于有限差分格式 從 格式的精度來劃分 有一階格式 二階格式和高階格式 從差分的空間形式來考 慮 可分為中心格式和逆風(fēng)格式 考慮時(shí)間因子的影響 差分格式還可以分為顯 格式 隱格式 顯隱交替格式等 目前常見的差分格式 主要是上述幾種形式的 組合 不同的組合構(gòu)成不同的差分格式 差分方法主要適用于有結(jié)構(gòu)網(wǎng)格 網(wǎng)格 的步長(zhǎng)一般根據(jù)實(shí)際地形的情況和柯朗穩(wěn)定條件來決定 二維水流模擬時(shí)常采用交替方向隱式法 a d i 6 1 a o i 法是將高維問題的計(jì)算 逐層分解為若干絕對(duì)穩(wěn)定的一維隱格式形式 該方法又包括多種不同的差分格式 如p r 格式 d 格式 d r 格式等 其中 有些格式可以由二維擴(kuò)展到三維 有些 1 0 則不能應(yīng)用于三維計(jì)算 但a d i 法不適用于含有混合偏導(dǎo)數(shù)的情況 差分方法的計(jì)算精度較其它一些方法稍低 從理論上講可以通過提高差分階 數(shù)來提高計(jì)算精度 但又會(huì)帶來一些不便 差分方法的另一個(gè)弱點(diǎn)是 傳統(tǒng)的矩形 網(wǎng)格不能較好的適應(yīng)復(fù)雜的邊界 但近年來提出的梯形和三角形網(wǎng)格等以及邊 界擬合坐標(biāo)法i 間 將會(huì)適當(dāng)彌補(bǔ)差分方法的缺憾 2 有限體積 f i 舊 有限體積法 f i n i t ev o l u m em e t h o d 又稱為控制體積法 鹋啁 其基本思路 是 將計(jì)算區(qū)域劃分為一系列不重復(fù)的控制體積 并使每個(gè)網(wǎng)格點(diǎn)周圍有一個(gè)控 制體積 將待解的微分方程對(duì)每一個(gè)控制體積積分 便得出一組離散方程 其中 的未知數(shù)是網(wǎng)格點(diǎn)上的因變量的數(shù)值 為了求出控制體積的積分 必須假定值在 網(wǎng)格點(diǎn)之間的變化規(guī)律 即假設(shè)值的分段的分布的分布剖面 從積分區(qū)域的選取 方法看來 有限體積法屬于加權(quán)剩余法中的子區(qū)域法 從未知解的近似方法看來 有限體積法屬于采用局部近似的離散方法 簡(jiǎn)言之 子區(qū)域法屬于有限體積發(fā)的 基本方法 7 l 有限體積法的基本思路易于理解 并能得出直接的物理解釋 離散方程的物 理意義 就是因變量在有限大小的控制體積中的守恒原理 如同微分方程表示因 變量在無限小的控制體積中的守恒原理一樣 有限體積法得出的離散方程 要 求因變量的積分守恒對(duì)任意一組控制體積都得到滿足 對(duì)整個(gè)計(jì)算區(qū)域 自然也 得到滿足 這是有限體積法吸引人的優(yōu)點(diǎn) 有一些離散方法 例如有限差分法 僅當(dāng)網(wǎng)格極其細(xì)密時(shí) 離散方程才滿足積分守恒 而有限體積法即使在粗網(wǎng)格情 況下 也顯示出準(zhǔn)確的積分守恒 就離散方法而言 有限體積法可視作有限單元 法和有限差分法的中間物 有限單元法必須假定值在網(wǎng)格點(diǎn)之間的變化規(guī)律 既 插值函數(shù) 并將其作為近似解 有限差分法只考慮網(wǎng)格點(diǎn)上的數(shù)值而不考慮值 在網(wǎng)格點(diǎn)之間如何變化 有限體積法只尋求的結(jié)點(diǎn)值 這與有限差分法相類似 但有限體積法在尋求控制體積的積分時(shí) 必須假定值在網(wǎng)格點(diǎn)之間的分布 這又 與有限單元法相類似 在有限體積法中 插值函數(shù)只用于計(jì)算控制體積的積分 得出離散方程之后 便可忘掉插值函數(shù) 如果需要的話 可以對(duì)微分方程中不同 的項(xiàng)采取不同的插值函數(shù) 針對(duì)采用不同的計(jì)算網(wǎng)格 控制體積法也派生出一些不同的方法 其中 使用 較多的是四邊形正交貼體網(wǎng)格 在采用四邊形網(wǎng)格時(shí) 由于對(duì)控制體積積分時(shí)包 含了相間節(jié)點(diǎn)的壓力差 可能使計(jì)算程序無法辨別均勻的合理壓力場(chǎng)與不符合實(shí) 際的 交錯(cuò)的波狀壓力場(chǎng) 同樣 在離散連續(xù)性方程時(shí) 也可能出現(xiàn)滿足連續(xù)方程 卻不符合實(shí)際的波狀速度場(chǎng) 從而導(dǎo)致不正確的結(jié)果 為此 往往采用交錯(cuò)網(wǎng)格 將不同的物理量布置在不同的節(jié)點(diǎn)上 交錯(cuò)網(wǎng)格可以解決波狀壓力場(chǎng)和速度場(chǎng)的 問題 但采用交錯(cuò)網(wǎng)格時(shí) 要在計(jì)算前插值生成相應(yīng)的副網(wǎng)格 對(duì)計(jì)算的最終結(jié)果 還要進(jìn)行插值轉(zhuǎn)換 才能統(tǒng)一得到主網(wǎng)格上的各種變量值 因此 計(jì)算復(fù)雜程度和 計(jì)算量都有所增加吲 此外 由于生成三維正交網(wǎng)格存在諸多困難 王曉建 張 廷芳采用非正交貼體網(wǎng)格的控制體積法 以及a l b e r t oc a r p i n t e f i k a r u t z h 等人提 出的無結(jié)構(gòu)網(wǎng)格下的控制體積法口4 j 5 1 也得到了一定的應(yīng)用 3 有限元 f e m 有限元方法 f i n i t ee l e m e n t m e t h o a 是于1 9 8 3 年h u 曲船tj r l e v i t j w i n g e rj i 蜘提出的 最初用于熱傳導(dǎo)問題的有限元分析中 其基礎(chǔ)是變分原理和 加權(quán)余量法 其基本求解思想是把計(jì)算域劃分為有限個(gè)互不重疊的單元 在每個(gè) 單元內(nèi) 選擇一些合適的節(jié)點(diǎn)作為求解函數(shù)的插值點(diǎn) 將微分方程中的變量改寫 成由各變量或其導(dǎo)數(shù)的節(jié)點(diǎn)值與所選用的插值函數(shù)組成的線性表達(dá)式 借助于變 分原理或加權(quán)余量法 將微分方程離散求解 采用不同的權(quán)函數(shù)和插值函數(shù)形式 便構(gòu)成不同的有限元方法 根據(jù)所采用的權(quán)函數(shù)和插值函數(shù)的不同 有限元方法 也分為多種計(jì)算格式 從權(quán)函數(shù)的選擇來說 有配置法 矩量法 最小二乘法和 伽遼金法 從計(jì)算單元網(wǎng)格的形狀來劃分 有三角形網(wǎng)格 四邊形網(wǎng)格和多邊形 網(wǎng)格 從插值函數(shù)的精度來劃分 又分為線性插值函數(shù)和高次插值函數(shù)等 不同 的組合同樣構(gòu)成不同的有限元計(jì)算格式 對(duì)于權(quán)函數(shù) 伽遼金 g a l e r