（水文學(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 公司可編程控 件系列中功能最為簡單的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)前主流并行平臺m p i p v m 尚未實(shí)現(xiàn)進(jìn)程遷移功能 當(dāng)進(jìn)行并行計(jì)算時 網(wǎng) 絡(luò)中某客戶端異常退出計(jì)算將導(dǎo)致臟數(shù)據(jù)的產(chǎn)生 本文自主開發(fā)了并行模型計(jì) 算平臺 采用c s 方式 服務(wù)器端對網(wǎng)絡(luò)環(huán)境進(jìn)行監(jiān)控和控制 為模型計(jì)算提供 數(shù)據(jù)交換及進(jìn)程遷移等功能 網(wǎng)絡(luò)發(fā)生故障時實(shí)時將未完成計(jì)算的河道轉(zhuǎn)移到其 它客戶端繼續(xù)計(jì)算 同時 為使資源達(dá)到最大的利用效率 本文提出了應(yīng)用螞蟻 算法進(jìn)行任務(wù)調(diào)度的新方法 提高了整個調(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)水位方程組時 結(jié)合 上海浦東新區(qū)調(diào)水改善水環(huán)境 項(xiàng)目 根據(jù)機(jī)群負(fù) 載平衡的調(diào)度方案 制定了針對一維水量水質(zhì)模型的通訊協(xié)議 將河道按權(quán)重分 配到各客戶端進(jìn)行節(jié)點(diǎn)水位求解 河道二維淺水方程通過有限體積方法顯式求 解 采用任務(wù)s p m d 型并行編程模型 將求解區(qū)域網(wǎng)格分成若干部分 對每部 分進(jìn)行單獨(dú)求解 模型成功應(yīng)用于鎮(zhèn)江內(nèi)江水流數(shù)值模擬 并得到較高的加速比 和并行效率 對一 二維分別進(jìn)行并行數(shù)值模擬 結(jié)果表明當(dāng)河道 網(wǎng)格 數(shù)一定時 存在 一最優(yōu)客戶端數(shù) 當(dāng)客戶端數(shù)小于最優(yōu)客戶端數(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 刖吾 隨著社會經(jīng)濟(jì)的高速發(fā)展 水多 水少 水臟 等問題已經(jīng)引起了全社會 的廣泛重視 實(shí)現(xiàn)水資源可持續(xù)利用 已成為努力改善人類生存和經(jīng)濟(jì)社會條件 的關(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)測資料 采用數(shù)值計(jì)算方法 建立河網(wǎng)水力水質(zhì)數(shù)學(xué)模型 當(dāng)前 對于河道水流和水質(zhì)預(yù)測 為了減小數(shù)值計(jì)算誤差 需要將計(jì)算網(wǎng)格劃分得很細(xì) 同時由于河道流域規(guī)模一般都比較大 對于比較大的計(jì)算域進(jìn)行模擬需要布置的 網(wǎng)格節(jié)點(diǎn)也比較多 如果網(wǎng)格節(jié)點(diǎn)過多 計(jì)算工作量將成倍甚至成指數(shù)增長 對于 計(jì)算機(jī)的計(jì)算速度要求比較高 近幾年來 隨著微機(jī)運(yùn)算速度大幅提高 價格低廉 同時局域網(wǎng)技術(shù)已十分成 熟 高性能互聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)和處理器之間的距離已不再是影響并行機(jī)系統(tǒng)性能 的關(guān)鍵因素 為利用微機(jī)組建并行計(jì)算集群提供了高性價比條件 從而被各階層 用戶所接受 正逐步成為并行編程的主要平臺 本文針對以上需求 自主研制了基于a r c e n g i n e 組件的并行水動力數(shù)值模擬 系統(tǒng) 論文主要的創(chuàng)新成果有 l 分別對一 二維水量水質(zhì)模型顯 隱式求解方式進(jìn)行并行化改造 自主開發(fā) 了與模型配套的并行通信平臺 并制定了相關(guān)通訊協(xié)議 并行模型采用c s c l i e n t s e r v e r 結(jié)構(gòu) 服務(wù)器端對計(jì)算區(qū)域的劃分采用螞蟻智能算法對機(jī)群 中的作業(yè)進(jìn)行智能調(diào)度 并能實(shí)時監(jiān)測網(wǎng)絡(luò)狀況 對已分配任務(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 一維水動力模型采用p r e i s s m a n n 四點(diǎn)隱格式求解圣維南方程組 針對每個時 刻需要求解節(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)行下一時段的計(jì)算 3 二維水動力模型采用有限體積顯式求解潛水方程 求解每個單元水位 流量 等信息時需要用到相鄰單元的水位 流量的數(shù)據(jù) 顯式求解方式是采用上一 個時刻相鄰單元的水位 流量值來求解本時刻單元的水位和流量 這樣就避 免了求解方程組 針對顯示求解的特點(diǎn) 采用任務(wù)s p m d 型并行編程模型 將求解區(qū)域網(wǎng)格分成若干部分 對每部分進(jìn)行單獨(dú)求解 服務(wù)器端負(fù)責(zé)將每 部分邊界單元的數(shù)據(jù)在相應(yīng)客戶端進(jìn)行交換 客戶端接收到數(shù)據(jù)后進(jìn)行本區(qū) 域本時段的計(jì)算并且在每個時段末 交換一次邊界上的計(jì)算數(shù)據(jù)直至計(jì)算完 畢 學(xué)位論文獨(dú)創(chuàng)性聲明 本人所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取 得的研究成果 盡我所知 除了文中特別加以標(biāo)注和致謝的地方外 論 文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果 與我一同工作的同事 對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意 如不實(shí) 本人負(fù)全部責(zé)任 論文作者c 簽孫 之蘭 盞 和7 年 7 月加 學(xué)位論文使用授權(quán)說明 河海大學(xué) 中國科學(xué)技術(shù)信息研究所 含萬方數(shù)據(jù)庫 國家圖書 館 中國學(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 選題的背景 第一章緒論 我國水資源總量大 人均占有量小 水資源時間 空間上分布不均衡 同時 隨著我國經(jīng)濟(jì)的持續(xù)發(fā)展 水環(huán)境污染問題日益嚴(yán)重 使我國水問題日趨嚴(yán)唆 目前 通過調(diào)水來解決水問題是一種行之有效的手段 如引江濟(jì)太 南水北調(diào) 博斯騰湖調(diào)水及黑河調(diào)水等都是意義重大的工程 但是 通過這些工程可以緩解 環(huán)境壓力 工農(nóng)業(yè)用水及人畜飲用水等問題到何種程度 需要根據(jù)數(shù)學(xué)模型來模 擬 當(dāng)前 對于河道水流和水質(zhì)預(yù)測 為了減小數(shù)值計(jì)算誤差 需要將計(jì)算網(wǎng)格劃 分得很細(xì) 同時由于河道流域規(guī)模一般都比較大 對于比較大的計(jì)算域進(jìn)行模擬 需要布置的網(wǎng)格節(jié)點(diǎn)也比較多 如果網(wǎng)格節(jié)點(diǎn)過多 計(jì)算工作量將成倍甚至成指 數(shù)增長 對于計(jì)算機(jī)的計(jì)算速度要求比較高 為了追求計(jì)算能力的提高 從元器 件到工藝 從大型高性能計(jì)算機(jī)到個人p c 機(jī) 硬件的性能一直在高速發(fā)展著 但 是同時由于受計(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)成為一個國家經(jīng)濟(jì)和科技實(shí)力的綜合體 現(xiàn) 為此一些國家都制定了相應(yīng)的戰(zhàn)略計(jì)劃 其中最為著名的就是美國的 高性 能計(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 簡稱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 簡稱a s c i 口 我國在8 6 3 高科技研究發(fā)展計(jì)劃和國家9 7 3 基礎(chǔ)研究計(jì)劃重大項(xiàng)目中也有對 應(yīng)項(xiàng)目 并設(shè)立有專門的國家高性能計(jì)算基金 并且近幾年來 隨著微機(jī)運(yùn)算速 度大幅提高 價格低廉 同時局域網(wǎng)技術(shù)已十分成熟 高性能互聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)和 處理器之間的距離已不再是影響并行機(jī)系統(tǒng)性能的關(guān)鍵因素 為利用微機(jī)組建并 行計(jì)算集群提供了高性價比條件 從而被各階層用戶所接受 工f 逐步成為并行編 程的主要平臺 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ù)倉庫 數(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ī)療 診斷等 對于河道二維水動力及水質(zhì)模擬屬于計(jì)算密集應(yīng)用問題 有限體積模型網(wǎng)格 經(jīng)常達(dá)到幾萬甚至幾百萬 但是采用單個p c 機(jī)需要的時間長 內(nèi)存容量易受限 制 一般模型運(yùn)行是在設(shè)定工況的條件下進(jìn)行 運(yùn)行過程中基本資料不能修改 在率定計(jì)算中 是在計(jì)算完成后整合計(jì)算結(jié)果 通過與實(shí)測資料的對比 進(jìn)行修 改參數(shù) 參數(shù)一但修改 再進(jìn)行計(jì)算 如此往復(fù) 但一些大的計(jì)算模型運(yùn)行一次 就需要幾天甚至幾周時間 這樣就給模型的率定帶來了巨大的困難 從而使得分 析人員不得不減小計(jì)算規(guī)模 將網(wǎng)格劃分更粗 但這樣將導(dǎo)致計(jì)算結(jié)果可靠性降 低 當(dāng)前黃河下游計(jì)算區(qū)域從花園e l 至利津 長約6 6 0 k m 若含灘區(qū)及滯洪區(qū) 則計(jì)算區(qū)域面積達(dá)4 0 0 0 k i n 2 左右 按主槽 灘地平均單元邊長5 0 m 計(jì)算 網(wǎng)格 量達(dá)2 0 0 萬個以上 即使采用顯格式計(jì)算方法 單機(jī)計(jì)算下游洪水的演進(jìn)過程 所需時間也遠(yuǎn)大于天然洪水的實(shí)際傳播時間 也就是說 針對黃河下游的大區(qū)域 平面一維計(jì)算 從洪水預(yù)報的角度來講 單機(jī)計(jì)算是沒有意義的 并行計(jì)算系統(tǒng) 的大容量 高速度己經(jīng)逐步成為多傳質(zhì) 大尺度 多維模型研究和應(yīng)用的 助推 器 眾所周知 水動力模型計(jì)算所需要的參數(shù)是眾多的 如每條河道的大斷面資 料 河道編號 首末節(jié)點(diǎn)號 糙率等 傳統(tǒng)的數(shù)值模型是將這些數(shù)據(jù)存儲于文本 文件中 文件每行每個數(shù)據(jù)對應(yīng)一個參數(shù) 這個文件一般人是看不懂的 因?yàn)槔?面只有一大堆的數(shù)據(jù) 也不知道每個數(shù)據(jù)的具體含義 因此 通常需要專門人員 才能對這個文件進(jìn)行編輯 而且由于沒有數(shù)據(jù)檢驗(yàn)功能 如果輸錯參數(shù) 計(jì)算結(jié) 果全部無用 耗時耗力 出于傳統(tǒng)數(shù)值模型的眾多缺陷 當(dāng)前國外的商業(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ù)支持 同時 將模型與a r c g i s 緊密結(jié)合 并構(gòu)建水環(huán)境數(shù)值模擬系統(tǒng) 由系統(tǒng)提供模 型所需的參數(shù) 并將計(jì)算結(jié)果通過系統(tǒng)直觀的表達(dá)出來 1 2 國內(nèi)外研究進(jìn)展 1 2 1 并行平臺應(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ì)算 s u p e rc o m p u t i n g 是將一項(xiàng)大的數(shù)據(jù)處理與數(shù)值計(jì)算任務(wù) 或任務(wù)的局部 分裂成為多個可相互獨(dú) 謄 立 同時進(jìn)行的子任務(wù) 并通過對這些子任務(wù)相互協(xié)調(diào)的運(yùn)行和實(shí)現(xiàn) 從而達(dá)到 快速 高效的對給定問題求解的處理方法t 因?yàn)槿魏胃咝阅苡?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) 代科學(xué)與技術(shù)向縱深發(fā)展 通常 針對計(jì)算科學(xué)中的復(fù)雜問題 傳統(tǒng)的單機(jī)模式 往往在完成時間和運(yùn)行效果上無能為力 而并行計(jì)算則被認(rèn)為是解決此類問題的 唯一可行途徑 并行計(jì)算機(jī)的發(fā)展歷程 并行計(jì)算機(jī)的發(fā)展 可分為四個階段 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ī)在美國的l a w r e n c el i v e m o r e 國家實(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ī)和脈動機(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 脈動陣列機(jī) i v 異步并行計(jì)算技術(shù)成熟期 2 0 世紀(jì)9 0 年代以后 n e c 研制出第一臺日本 生產(chǎn)的超級并行向量處理機(jī)s x 3 其每臺機(jī)器含有4 個處理器 每個處 理器含有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 對稱多處理機(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 汾布共享存儲多處理機(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í)行相同的指令流 而同時執(zhí) 行不同的數(shù)據(jù)流 i i p v p 系統(tǒng)由專門設(shè)計(jì)的高帶寬網(wǎng)絡(luò)及定制的處理器組成 一般采用共 享存儲方式 1 1 1 m p p 大型計(jì)算機(jī)系統(tǒng) 處理節(jié)點(diǎn)采用商品微處理器 采用分布式存儲 方式及專門設(shè)計(jì)的高帶寬 低延遲網(wǎng)絡(luò) i v s m p 與m p p 不同的是采用共享式存儲方式 每個處理機(jī)可等同的訪問共 享存儲器和i o 設(shè)備 v d s m 采用d i r 用以支持分布在各結(jié)點(diǎn)中的局部存儲器 從而形成一個共 4 享的存儲器 v i c o w 是近年來發(fā)展勢頭很好的一種體系結(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è)備 幾乎所有的國內(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)由多個獨(dú)立的服務(wù)器 在c l u s t e r 概念下稱為節(jié)點(diǎn) 通過交換 杌連接在一起 每個節(jié)點(diǎn)擁有各自的內(nèi)存 某個節(jié)點(diǎn)的c p u 不能直接訪 問另外一個節(jié)點(diǎn)的內(nèi)存 每個節(jié)點(diǎn)擁有獨(dú)立的操作系統(tǒng) 需要一系列的集群軟件來完成整個系統(tǒng)的管理與運(yùn)行 包括 c l u s t e r 系統(tǒng)管理軟件 如i b m 的c s m x c a t 等 消息傳遞庫 如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 等 只能在單個節(jié)點(diǎn)內(nèi)部支持共享內(nèi)存方式的并行模式 如o p e n m p p t h r e a d s 等 性能價格比好 2 并行編程環(huán)境簡介 要進(jìn)行并行計(jì)算 軟件支撐平臺是重要組成部分之一 廉價并行計(jì)算機(jī)的支 撐環(huán)境按并行計(jì)算支撐平臺可分為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 平臺是美國y a l e 大學(xué)的d a v i dg e l e r n t e r 開發(fā)的 是 第一個商業(yè)產(chǎn)品應(yīng)用于v s m 作為超級計(jì)算機(jī)和大規(guī)模工作站機(jī)群平行計(jì)算 與機(jī) 器無關(guān)的編程環(huán)境 它是一個關(guān)聯(lián)的 虛擬的共享存儲系統(tǒng) 新版的l i n d a 丌發(fā) 語言支持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) 上具有多個處理進(jìn)程 且進(jìn)程間同步點(diǎn)較多和全局通信較頻繁的應(yīng)用場合1 6 j m p i m p i 是消息傳遞接口的簡稱 它實(shí)際上是一個消息傳遞函數(shù)庫的標(biāo)準(zhǔn)說明 提 供了一種與語言平臺無關(guān) 可以被廣泛使用的編寫消息傳遞程序的標(biāo)準(zhǔn) r 丌 其標(biāo) 準(zhǔn)化開始于1 9 9 2 年4 月2 9 日至3 0 e l 在威吉尼亞的威廉姆斯堡召開的分布存儲環(huán)境 中消息傳遞標(biāo)準(zhǔn)的討論會由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 對原來的i v i p i 作了進(jìn)一步的修改完善和擴(kuò)充 但是當(dāng)初推 出m p i 標(biāo)準(zhǔn)時為了能夠使它盡快實(shí)現(xiàn)并迅速被接受許多其它方面的重要但實(shí)現(xiàn) 起來比較復(fù)雜的功能都沒有定義比如并行i o 當(dāng)m 口i 被廣為接受之后擴(kuò)充并提高 m p i 功能的要求就越來越迫切了 于是在1 9 9 7 年的7 f l 在對原來的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ò)充很多但主要是三個方面并行f o 遠(yuǎn)程存儲訪問和動態(tài)進(jìn)程管 理 1 8 2 1 m p i 以語言獨(dú)立的形式來定義這個接口庫 提供了與c f o r t r a n 和c 語 言的綁定 p v m p v m f 雒刀是并行虛擬機(jī) 由美國田納西大學(xué) o a k r i d g e 觥等研制的 并行程序開發(fā)環(huán)境 它可以把多個異構(gòu)的計(jì)算機(jī)組織起來成為一個易于管理的 可擴(kuò)展的 易編程使用的并行計(jì)算資源 它圍繞 虛擬機(jī) 的中心思想展開 即 通過網(wǎng)絡(luò)互聯(lián)的一系列異構(gòu)的主機(jī)在邏輯上對用戶呈現(xiàn)為單一的并行計(jì)算機(jī) 由 于p v m 強(qiáng)調(diào)虛擬機(jī)的擴(kuò)展性 異構(gòu)性和容錯能力 因此它把可移植性看得比性能更 重要 它支持在異構(gòu)網(wǎng)絡(luò)中應(yīng)用程序問的通信 含有動態(tài)的資源管理和進(jìn)程控制 功能 提供了容錯的基本機(jī)制 當(dāng)發(fā)生錯誤時 可以重新分配任務(wù) 3 冰hm p i 由于m p l 只支持c f o r t r a n 和c 語言的網(wǎng)絡(luò)分布并行計(jì)算編程環(huán)境 這就存 在m p i 應(yīng)用程序在不同系統(tǒng)間的二進(jìn)制兼容的問題 將j a v a 語言與m p i 結(jié)合起來 提供m p i 對j a v a 語言的支持 使用j a v a 語言編寫的并行程序?qū)⒕哂锌缙脚_的功能 矗 張曉軍 刀等人通過j a v a 語言調(diào)用m p i 的c 語言函數(shù)庫 將c 語言的參數(shù)數(shù)據(jù)類型轉(zhuǎn) 換戍j a v a 支持的數(shù)據(jù)類型 調(diào)用m p i 的庫函數(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)用程序可以幾乎不作修改在不同型號的并行 機(jī)之間轉(zhuǎn)移 或轉(zhuǎn)移到網(wǎng)絡(luò)環(huán)境中運(yùn)行 1 6 1 p v m 的應(yīng)用程序可以在兩組 不同的計(jì)算機(jī)群之間移植 而不可能把并行應(yīng)用程序完全移植到單個的 并行機(jī)上去運(yùn)行 所以說 從可移植性上m p i 相對于p v m 有著無可比擬 的優(yōu)勢 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ù) 支持廣播 分散 收集 多收集 多對多等過程組內(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ù)量 功能以及對數(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)對點(diǎn)通信只能在屬于同一通信子的節(jié)點(diǎn)機(jī)間進(jìn)行 通信子對其起 屏蔽作用 即使形式上完全相同的通信操作 只要其所屬的通信子不同 m p i 就視其為截然不同的兩次操作 通信子的存在 保證了可靠安全的 通信環(huán)境 避免了通信空間的出錯 提供了可靠的通信接e l 2 4 2 q p v m 類似于m p i 也提供了使一組任務(wù)獲得唯一的上下文標(biāo)簽的函數(shù) 在 p v m 中 當(dāng)屬于一個任務(wù)組 具有唯一的上下文標(biāo)簽 的一個任務(wù)失 敗后 容許一個新的任務(wù)使用這個唯一的上下文 從而提供了容錯的功 能 但也引入了沖突的可能 例如當(dāng)一個任務(wù)的失敗導(dǎo)致了整個任務(wù)組 失敗 其擁有的唯一的上下文標(biāo)簽被釋放 此時如果有一個具有此上下 文的新任務(wù)生成 則將會引起沖突 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ù) 可是并不支持對動態(tài)進(jìn)程的查詢 但m p i 中對 任務(wù)分配提供了笛卡爾拓?fù)浜蛨D拓?fù)鋪矸峙滟Y源 有可能充分利用硬件 的特性來達(dá)到簡化設(shè)計(jì) 提高效率 2 2 1 p v m 建立在虛擬機(jī)的概念上 有 完全的資源管理功能 用戶既可以增加或刪除計(jì)算資源 即計(jì)算機(jī)結(jié) 點(diǎn) 也可以把任務(wù) 通常表現(xiàn)為進(jìn)程 從一個計(jì)算機(jī)結(jié)點(diǎn)轉(zhuǎn)移到另一 個計(jì)算機(jī)結(jié)點(diǎn) 同時 p v m 提供了動態(tài)查詢和管理虛擬機(jī)中各個任務(wù) 及計(jì)算機(jī)結(jié)點(diǎn)狀態(tài)的函數(shù) 從而使用戶的應(yīng)用程序可以通過與p v m 虛 擬機(jī)的動態(tài)交互 管理自己的計(jì)算環(huán)境 為實(shí)現(xiàn)計(jì)算環(huán)境的負(fù)載平衡 任務(wù)遷移和容錯提供了強(qiáng)有力的支持閉 3 調(diào)度算法簡介 在工作站網(wǎng)絡(luò) n o w 環(huán)境中 由于任務(wù)到達(dá)的隨機(jī)性以及各節(jié)點(diǎn)處理能力上 的差異 會造成某些節(jié)點(diǎn)分配的任務(wù)過多 重載 而另外一些節(jié)點(diǎn)卻是空閑的 輕載或空載 一方面使重載節(jié)點(diǎn)上的任務(wù)盡可能快地完成是當(dāng)務(wù)之急 另一 方面使某些節(jié)點(diǎn)空閑是一種浪費(fèi) 負(fù)載均衡設(shè)法對已經(jīng)分配的任務(wù)進(jìn)行重新調(diào) 度 并通過任務(wù)遷移使各節(jié)點(diǎn)負(fù)載大致相等 避免這種空閑和忙等待并存的情況 有效提高網(wǎng)格資源的利用率 減少任務(wù)的平均響應(yīng)時間 根據(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í)時性強(qiáng) 可靠性好 易擴(kuò)充 但通信開銷搭 算法設(shè)計(jì)復(fù)雜 不易管理 根據(jù)調(diào)度策略執(zhí)行的時期 生產(chǎn)調(diào)度分為動態(tài)調(diào)度和靜態(tài)調(diào)度兩大類 j a c k s o n 口刃虧 1 9 5 7 年對靜態(tài)調(diào)度和動態(tài)調(diào)度的概念做了區(qū)分 靜態(tài)調(diào)度是在己知 調(diào)度環(huán)境和任務(wù)的前提下的所謂事前調(diào)度方案 動態(tài)調(diào)度是指在調(diào)度環(huán)境和任務(wù) 存在著不可預(yù)測的擾動情況下的調(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í)際應(yīng)用中很難得到滿足 因此 在集群系統(tǒng)的 任務(wù)調(diào)度問題中 大多數(shù)的系統(tǒng)采用的是動態(tài)調(diào)度算法 動態(tài)調(diào)度的概念出現(xiàn)較早 最初的研究主要采用最優(yōu)化方法 m a t s u u r a 2 9 提 出的重調(diào)度算法 首先用分支定界法產(chǎn)生一個調(diào)度 當(dāng)工況發(fā)生變化時 再用調(diào)度 規(guī)則來分配工件 由于絕大多數(shù)調(diào)度問題已被證明是n p 問題 3 4 1 隨著調(diào)度問題規(guī) 模的增大 上述方法的求解難度將急劇增加 因而最優(yōu)化方法往往不能適應(yīng)生產(chǎn) 實(shí)際對實(shí)時性的要求 此外 該類方法大多基于某些理想化的假設(shè) 遠(yuǎn)不能充分 反映實(shí)際生產(chǎn)環(huán)境的復(fù)雜性 而且要充分表達(dá)實(shí)際生產(chǎn)環(huán)境的隨機(jī)性和動態(tài)性 也極為困難 所以單獨(dú)使用此類方法來解決動態(tài)調(diào)度問題是不現(xiàn)實(shí)的 近年來 計(jì)算機(jī)技術(shù)的迅速發(fā)展以及人工智能 神經(jīng)網(wǎng)絡(luò) 遺傳算法和仿真 技術(shù)等新方法的產(chǎn)生和發(fā)展 為動態(tài)調(diào)度的研究開辟了新思路 也為生產(chǎn)調(diào)度的 實(shí)用化奠定了基礎(chǔ) 1 9 9 6 年 k w o k 和a h m a d 提出了一個動態(tài)關(guān)鍵路徑 d c p 調(diào)度算 法 1 9 9 9 年 張宏莉等人針對單并發(fā)任務(wù)簇提出了一個最優(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 是兩個較好的調(diào)度算 法 1 9 9 8 年 d a r b h a g 口a g r a w a l 提出了一個基于任務(wù)復(fù)制 t d s 的調(diào)度算法 3 2 t d s 算法在調(diào)度長度 s c h e d u l el e n g t h 方面 基本上比在它以前出現(xiàn)的所有算法都 優(yōu)越 因?yàn)樗ㄟ^任務(wù)復(fù)制減少了通信時間 但是 t d s 算法沒有考慮節(jié)省處理器 個數(shù)的問題 這會降低算法的加速比 s i 薛 1 提出一種專家神經(jīng)網(wǎng)絡(luò)方法 該方 法用1 6 個神經(jīng)網(wǎng)絡(luò)分別從相應(yīng)的訓(xùn)練樣本集中獲取調(diào)度知識 用專家系統(tǒng)確定各 子網(wǎng)的輸入 由于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練由1 6 個子網(wǎng)分擔(dān) 并且各子網(wǎng)可以并行訓(xùn)練 從而減少了訓(xùn)練時間 l e e 等i 搠用遺傳算法和機(jī)器學(xué)習(xí)來解決單件車問的調(diào)度問 題 用機(jī)器學(xué)習(xí)來產(chǎn)生將工件下發(fā)到車間層的知識庫 而用遺傳算法在各臺機(jī)器 上分配工件 螞蟻算法是f h d o r i g o p d 提出的解決組合優(yōu)化問題的一種多a g e n t 方法 其模 擬自然界中螞蟻覓食路徑的搜索過程 螞蟻在尋找食物時 能在其走過的路徑上 釋放信息素 p h e r o m o n e 螞蟻在覓食過程中能夠感知信息素的存在和強(qiáng)度 并 傾向于朝信息素強(qiáng)度高的方向移動 當(dāng)大量螞蟻不斷地從蟻巢通往食物時 相同 時間內(nèi)相對較短路徑上通過的螞蟻較多 該路徑上累積的信息素強(qiáng)度也較大 后 來螞蟻選擇該路徑的概率也相對較大 最終整個蟻群會找到最優(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ù)分配給剩余各資源的概率 對每只螞蟻的分配結(jié)果計(jì)算 目標(biāo)函數(shù) 選當(dāng)前計(jì)算時間最小值為最佳解 將信息素恢復(fù)至本組任務(wù)調(diào)度前的 值 然后重復(fù)以上過程 到達(dá)終止步時 選得最優(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 年提出的 該算法源于對鳥群 魚群覓食行為的模擬1 3 9 1 在p s 0 中 首先初始化 一群隨機(jī)粒子 隨機(jī)解 然后通過迭代尋找最優(yōu)解 在每一次迭代中 粒子通過 跟蹤兩個極值來更新自己的速度和位置 第一個就是粒子本身所找到的最優(yōu)解 這個解叫做個體極值 另一個極值是整個種群目前找到的最優(yōu)解 這個極值是全 局極值 另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居 那么在 所有鄰居中的極值就是局部極值 p s 0 算法簡單易實(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 維粒子表示方法 通過對粒子位置向量進(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)格 用有限個網(wǎng)格節(jié)點(diǎn)代替連 續(xù)的求解域 有限差分法以t a y l o r 級數(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á)簡單 是發(fā)展較早且比較成熟的數(shù)值方法 對于有限差分格式 從 格式的精度來劃分 有一階格式 二階格式和高階格式 從差分的空間形式來考 慮 可分為中心格式和逆風(fēng)格式 考慮時間因子的影響 差分格式還可以分為顯 格式 隱格式 顯隱交替格式等 目前常見的差分格式 主要是上述幾種形式的 組合 不同的組合構(gòu)成不同的差分格式 差分方法主要適用于有結(jié)構(gòu)網(wǎng)格 網(wǎng)格 的步長一般根據(jù)實(shí)際地形的情況和柯朗穩(wěn)定條件來決定 二維水流模擬時常采用交替方向隱式法 a d i 6 1 a o i 法是將高維問題的計(jì)算 逐層分解為若干絕對穩(wěn)定的一維隱格式形式 該方法又包括多種不同的差分格式 如p r 格式 d 格式 d r 格式等 其中 有些格式可以由二維擴(kuò)展到三維 有些 1 0 則不能應(yīng)用于三維計(jì)算 但a d i 法不適用于含有混合偏導(dǎo)數(shù)的情況 差分方法的計(jì)算精度較其它一些方法稍低 從理論上講可以通過提高差分階 數(shù)來提高計(jì)算精度 但又會帶來一些不便 差分方法的另一個弱點(diǎn)是 傳統(tǒng)的矩形 網(wǎng)格不能較好的適應(yīng)復(fù)雜的邊界 但近年來提出的梯形和三角形網(wǎng)格等以及邊 界擬合坐標(biāo)法i 間 將會適當(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ù)的控制體積 并使每個網(wǎng)格點(diǎn)周圍有一個控 制體積 將待解的微分方程對每一個控制體積積分 便得出一組離散方程 其中 的未知數(shù)是網(wǎng)格點(diǎn)上的因變量的數(shù)值 為了求出控制體積的積分 必須假定值在 網(wǎng)格點(diǎn)之間的變化規(guī)律 即假設(shè)值的分段的分布的分布剖面 從積分區(qū)域的選取 方法看來 有限體積法屬于加權(quán)剩余法中的子區(qū)域法 從未知解的近似方法看來 有限體積法屬于采用局部近似的離散方法 簡言之 子區(qū)域法屬于有限體積發(fā)的 基本方法 7 l 有限體積法的基本思路易于理解 并能得出直接的物理解釋 離散方程的物 理意義 就是因變量在有限大小的控制體積中的守恒原理 如同微分方程表示因 變量在無限小的控制體積中的守恒原理一樣 有限體積法得出的離散方程 要 求因變量的積分守恒對任意一組控制體積都得到滿足 對整個計(jì)算區(qū)域 自然也 得到滿足 這是有限體積法吸引人的優(yōu)點(diǎn) 有一些離散方法 例如有限差分法 僅當(dāng)網(wǎng)格極其細(xì)密時 離散方程才滿足積分守恒 而有限體積法即使在粗網(wǎng)格情 況下 也顯示出準(zhǔn)確的積分守恒 就離散方法而言 有限體積法可視作有限單元 法和有限差分法的中間物 有限單元法必須假定值在網(wǎng)格點(diǎn)之間的變化規(guī)律 既 插值函數(shù) 并將其作為近似解 有限差分法只考慮網(wǎng)格點(diǎn)上的數(shù)值而不考慮值 在網(wǎng)格點(diǎn)之間如何變化 有限體積法只尋求的結(jié)點(diǎn)值 這與有限差分法相類似 但有限體積法在尋求控制體積的積分時 必須假定值在網(wǎng)格點(diǎn)之間的分布 這又 與有限單元法相類似 在有限體積法中 插值函數(shù)只用于計(jì)算控制體積的積分 得出離散方程之后 便可忘掉插值函數(shù) 如果需要的話 可以對微分方程中不同 的項(xiàng)采取不同的插值函數(shù) 針對采用不同的計(jì)算網(wǎng)格 控制體積法也派生出一些不同的方法 其中 使用 較多的是四邊形正交貼體網(wǎng)格 在采用四邊形網(wǎng)格時 由于對控制體積積分時包 含了相間節(jié)點(diǎn)的壓力差 可能使計(jì)算程序無法辨別均勻的合理壓力場與不符合實(shí) 際的 交錯的波狀壓力場 同樣 在離散連續(xù)性方程時 也可能出現(xiàn)滿足連續(xù)方程 卻不符合實(shí)際的波狀速度場 從而導(dǎo)致不正確的結(jié)果 為此 往往采用交錯網(wǎng)格 將不同的物理量布置在不同的節(jié)點(diǎn)上 交錯網(wǎng)格可以解決波狀壓力場和速度場的 問題 但采用交錯網(wǎng)格時 要在計(jì)算前插值生成相應(yīng)的副網(wǎng)格 對計(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ì)算域劃分為有限個互不重疊的單元 在每個 單元內(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ì)算格式 對于權(quán)函數(shù) 伽遼金 g a l e r