| 姓名 |
陳威勝(Wei-Sheng Chen)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
Sparse PCG Solver之物件導向設計在叢集電腦上的應用
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
在本篇論文中，我們採C++物件導向程式設計的方式，並利用最常使用的數值方法conjugate gradient method (CG)和preconjugate gradient method (PCG)，來解 Ax = b 的問題，並且加以比較。
通常在數值分析處理問題時，經由Finite Difference Method或者是Finite Element Method所產生的矩陣，都是Sparse Matrix。本論文採用Finite Difference Method作數值模擬，並列兩種sparse matrix的儲存方式來處理問題，達到節省儲存空間的成效；但是，在利用CG或PCG分析問題時，我們發現，需要耗費相當多的時間在做矩陣乘向量的乘法上，當矩陣愈大時，所花的時間相對增加。因此，我們將利用叢集電腦系統(PC Cluster)，並使用MPI函式庫，對CG和PCG此兩種方法做平行化；在此，我們將兩種稀疏矩陣的儲存格式平行化，並且舉出兩個數值範例，在平行化之後，分別用CG和PCG去模擬分析，然後加以比較，是否在效能上有所提升。 |
| 關鍵字(中) |
★ 平行化
★ 物件導向程式語言
★ 叢集電腦 |
關鍵字(英) |
★ Parallel
★ MPI
★ PC Cluster
★ Object-Oriented
★ C++
★ Prec |
| 論文目次 |
摘要 I
致謝 II
圖目錄 V
表目錄 VIII
第一章 序論 1
第二章 Conjugate gradient method ＆
Preconditioned Conjugate gradient method 3
第2.1節 Conjugate gradient method 3
第2.2節 Preconditioned Conjugate gradient method 8
第2.3節 Preconditioner with Jacobian Method 12
第三章 物件導向＆Sparse Matrix 之文獻回顧 15
第3.1節 物件導向程式設計 15
第3.2節 Sparse Matrix 簡介 16
第3.3節 基本類別設計 22
第四章 平行處理 25
第4.1節 平行函式庫(MPI)簡介 26
第4.2節 PCG平行程式設計 27
第五章 數值範例（數據） 35
第5.1節 系統架構 35
第5.2節 效能評估 38
第5.3節 數值範例1 39
第5.4節 數值範例2 50
第六章 結論 （ 未來展望 ） 62
參考文獻 63
圖目錄
圖3-1 程式的類別繼承圖1 23
圖3-2 程式的類別繼承圖2 23
圖3-3 程式的類別繼承圖3 24
圖4-1 平行程式Space-time圖 29
圖5-1 網路架構圖 37
圖5-2 範例1不同儲存方法的時間曲線
with CG (Single Processor) 40
圖5-3 範例1不同儲存方法的時間曲線
with PCG (Single Processor) 41
圖5-4 範例1不同儲存方法的時間曲線
with CG&PCG (Single Processor) 41
圖5-5 範例1採用CDS格式的總時間曲線
with CG (Multiple Processors) 42
圖5-6 範例1採用CDS格式的總時間曲線
with PCG (Multiple Processors) 43
圖5-7 範例1採用CDS格式的Speedup曲線
with CG (Multiple Processors) 43
圖5-8 範例1採用CDS格式的Speedup曲線
with PCG (Multiple Processors) 43
圖5-9 範例1採用CDS格式的Efficiency曲線
with CG (Multiple Processors) 44
圖5-10 範例1採用CDS格式的Efficiency曲線
with PCG (Multiple Processors) 44
圖5-11 範例1採用SBR格式的總時間曲線
with CG (Multiple Processors) 46
圖5-12 範例1採用SBR格式的總時間曲線
with PCG (Multiple Processors) 46
圖5-13 範例1採用SBR格式的Speedup曲線
with CG (Multiple Processors) 47
圖5-14 範例1採用SBR格式的Speedup曲線
with PCG (Multiple Processors) 47
圖5-15 範例1採用SBR格式的Efficiency曲線
with CG (Multiple Processors) 48
圖5-16 範例1採用SBR格式的Efficiency曲線
with PCG (Multiple Processors) 48
圖5-17 範例2不同儲存方法的時間曲線
with CG (Single Processor) 51
圖5-18 範例2不同儲存方法的時間曲線
with PCG (Single Processor) 51
圖5-19 範例2不同儲存方法的時間曲線
with CG&PCG (Single Processor) 52
圖5-20 範例2採用CDS格式的總時間曲線
with CG (Multiple Processors) 53
圖5-21 範例2採用CDS格式的總時間曲線
with PCG (Multiple Processors) 53
圖5-22 範例2採用CDS格式的Speedup曲線
with CG (Multiple Processors) 54
圖5-23 範例2採用CDS格式的Speedup曲線
with PCG (Multiple Processors) 54
圖5-24 範例2採用CDS格式的Efficiency曲線
with CG (Multiple Processors) 55
圖5-25 範例2採用CDS格式的Efficiency曲線
with PCG (Multiple Processors) 55
圖5-26 範例2採用SBR格式的總時間曲線
with CG (Multiple Processors) 57
圖5-27 範例2採用SBR格式的總時間曲線
with PCG (Multiple Processors) 57
圖5-28 範例2採用SBR格式的Speedup曲線
with CG (Multiple Processors) 58
圖5-29 範例2採用SBR格式的Speedup曲線
with PCG (Multiple Processors) 58
圖5-30 範例2採用SBR格式的Efficiency曲線
with CG (Multiple Processors) 59
圖5-31 範例2採用SBR格式的Efficiency曲線
with PCG (Multiple Processors) 59
表目錄
表5-1 Server Node 硬體設備 36
表5-2 Slave Node 硬體設備 37
表5-3 軟體環境 37
表5-4 範例1比較CDS和SBR兩種儲存格式的計算時間
with CG(Single Processor) 41
表5-5 範例1比較CDS和SBR兩種儲存格式的計算時間
with PCG(Single Processor) 42
表5-6 範例1採用Compressed_Diagonal Storage Mode 在CPU個數上的
效能比(CG) 45
表5-7 範例1採用Compressed_Diagonal Storage Mode 在CPU個數上的
效能比(PCG) 45
表5-8 範例1採用Storage_by_Rows 在CPU個數上的效能比(CG) 49
表5-9 範例1採用Storage_by_Rows 在CPU個數上的效能比(PCG) 49
表5-10 範例2比較CDS和SBR兩種儲存格式的計算時間
with CG(Single Processor) 52
表5-11 範例2比較CDS和SBR兩種儲存格式的計算時間
with PCG(Single Processor) 52
表5-12 範例2採用Compressed_Diagonal Storage Mode 在CPU個數上的 效能比(CG) 56
表5-13 範例2採用Compressed_Diagonal Storage Mode 在CPU個數上的 效能比(PCG) 57
表5-14 範例2採用Storage_by_Rows 在CPU個數上的效能比(CG) 60
表5-15 範例2採用Storage_by_Rows 在CPU個數上的效能比(PCG) 60 |
| 參考文獻 |
[1] 蔡佳璋、張西亞、黃國展、李先知、周朝宜、鄭守成、陳敏、沈
澄宇，科學計算應用之新寵；個人電腦叢集，高速計算世界，卷7，
期4，頁17-25，1994
[2] 鄭守成，MPI平行計算程式設計<1>，
http://www.nchc.gov.tw/chinese/07_publication/nchcs/Other/V6N3/P24-38.html
[3] 紀良育，物件導向複合區域網格生成系統在叢集電腦系統的應
用，中央大學數學系碩士論文，2001
[4] Bjarne Stroustrup 著，葉秉哲譯，C++程式語言經典本(The C++
Programing Language,3rd ed.) 儒林發行，1999
[5] MGCG Method: A Robust And Highly Parallel Iterative Method (Make
Corrections) , By Osamu Tatebe. ... ,December 1996
[6]CGCODE: SOFTWARE FOR SOLVING LINEAR SYSTEMS WITH CONJUGATE GRADIENT METHODS
http://scicomp.ucsd.edu/~mholst/pubs/dist/Hols90.pdf
[7] Preconditioned Conjugate Gradient-Like Methods for Nonsymmetric Linear
Systems , By Ulrike Meier Yang , July 19 , 1994
[8] THE MULTIGRADE PRECONDITIONED CONJUGATE GRADIENT
METHOD (Department of InformATION Science University of Tokyo ,Japan)
[9] Message Passing Interface Forum, MPI: A Message Passing Interface
Standard, Version 1.1, June 1998
[10] Parallelization of a Preconditioned Conjugate Gradient Method
Algorithm using the Message-Passing Paradigm (Matt Newman ,1999/11/29)
[11] G.D.SMITH : Numerical Solution of Partial Differential Equations：Finite
Difference Methods, Third Edition, 1985
[12] Jonathan Richard Shewchuk , An Introduction to the Conjugate Gradient
Method Without the Agonizing Pain , March 7 , 1994
http://www.maths.uq.edu.au/~kb/mn475_320/mn475/CG_notes.ps
[13] Performance of Parallel Conjugate Gradient Solvers in Meshfree Analysis
http://css.engineering.uiowa.edu/~swan/inreview/iccg_040703.pdf
[14] Barry Wilkinson, C. Michael Allen, Parallel Programming: Techniques and
Applications Using Networked Workstations and Parallel Computers,
Prentice Hall, August 1998
[15] Parallel Methods in Numerical Analysis
Introduction to Sparse Direct Solver(Symmetric Positive Definite Systems) Kincho H. Law Professor of Civil and Environmental Engineering…November 10, 2003 Page 2. ... |
| 指導教授 |
吳維漢(Wei-Han Wu)
|
審核日期 |
2005-7-24 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
