臺灣博碩士論文加值系統

本研究在探討數值積分程式之平行化，所使用的演算法為林聰悟與林佳慧[1997]一書所提出的「Romberg樹自動佈點數值積分」架構(以下簡稱ARTint)，此一數值積分方法能以適應被積函數值變化情形方式自動安排積分點來進行數值求積計算，在提高階數以獲得更高精度積分值的過程中，此一方法只須再計算新增加積分點的函數值，搭配先前已計算過的函數值的重覆運用即可獲得更精確的數值積分估計值，如此將能減少昇階過程中函數求值計算的次數，有效率地完成單重積分的數值計算。
研究中以Romberg樹積分架構用於單重積分所實作的程式ARTint1D(李洋傑[1997])進行平行化，改寫完成PARTint1D程式。在PARTint1D程式中，ARTint數值積分方法的流程由一部主控電腦執行，平行化的策略則是經由網路透過MPI架構將被積函數值計算工作分散給個人電腦叢集中眾多工作者電腦來完成。
PARTint1D程式經測試後發現，分散給各個工作者的被積函數計算量必須足夠龐大，才能夠展現明顯的平行化效能，因此本研究進一步將Romberg樹積分架構應用到迭代進行之雙重積分數值分析。在迭代進行之雙重積分數值分析中，內層積分值被視為外層積分之被積函數值，其數值是經由在工作者執行的ARTint1D程式計算，如此便能充分增加工作者的運算量，而提昇整體的平行化效能。如此，內、外兩層積分的數值計算是以迭代方式分別利用一維ARTint演算法完成，最後實作成為「平行化自動佈點Romberg樹雙重積分數值計算程式：PARTint2D」。
PARTint2D應用於實際雙重積分案例的數值分析結果中，在精度控制方面，誤差估計值都能確實地貼近控制誤差的要求，而實際誤差則在絕大多數情況下皆達到控制誤差的要求，少數有很接近控制誤差的情況，實際誤差與控制誤差間相差之不準確度皆在不到一位十進位數的範圍內。在平行化效能的表現方面，當工作者數量為16時，平行化加速比平均值可達到9倍，顯示PARTint2D所呈現的平行化加速作用顯著，而換算為平行化加速效率平均值也有0.55的表現，顯示PARTint2D所呈現的可擴充性很高。

The objective of this study is aimed at the implementation of parallelized numerical quadrature routines. The algorithm we choose for numerical quadrature routines is the so called “Adaptive Romberg Tree integration scheme” (abbr. “ARTint”) proposed by Lin et. al.[1997]. This numerical quadrature scheme can arrange the function evaluation points adaptively in accordance with characteristic of the trend of variation in integrand function values. When the accuracy of the numerical quadrature value is requested to be increased, a newer and larger set of function evaluation points must be incurred. The main advantage of ARTint method is the inclusion of all function evaluation points used in previous stages. It is this feature of ARTint method that makes it a quadratue scheme with prominent computation efficiency.
Based of an implementation, called “ARTint1D”, of ARTint method by Y.J. Lee[1997], a new parallelized program, called “PARTint1D”, is developed in this study. In PARTint1D program, main procedures of ARTint method are executed in a controller computer, and the strategy for parallelization is to distribute all tasks of evaluations for integrand function to every worker computers in a PC-cluster.
Numerical experimentations on PARTint1D program show that: in order to obtained seasonable efficiency of PARTint1D program, the computational efforts for each evaluation of integrand function must be sufficiently complex. This situation occurs in the numerical quadratue of a double integral. When the inner integral values are treated as integrand function values for the outer integral, then ARTint scheme for the numeric quadrature of outer integral will have a integrand function demanding complex enough computational efforts. Numeric quadratue of all inner integrals may be calculated by ARTint algorithm too. Thus the iterative applications of ARTint algorithm for the numeric quadratue of a double integral lead to a parallelized adaptive Romberg tree double integration program, which can be named with “PARTint2D”.
PARTint2D program is tested in numeric calculation of a series of double integrals which quadratue values can be expressed in terms of closed-form expressions. Concerning the control on the accuracy of numeric quadrature values, both the estimated errors and actual errors obtained by PARTint2D program can be a controlled within the requested tolerance of errors. Concerning the efficiency of parallelization, when 16 workers are used in the execution of PARTint2D program, the average speedup indices of parallelization can reach some values around 9 and the average efficiency indices of parallelization can reach some values around 0.55. These results indicate that both the efficiency and scalability of PARTint2D program are all quite promising.

目 錄

摘 要 I
Abstract II
誌 謝 詞 III
目 錄 IV
表 目 錄 VI
圖 目 錄 VII
第一章 緒 論 1
1.1 個人電腦叢集在科學計算的重要性 1
1.2 重積分數值計算在工程科學計算中的重要性 2
1.3 本文的研究目標 3
1.4 文獻回顧 3
1.5 本文的架構 4
第二章 個人電腦叢集的建構 5
2.1 硬體架構 5
2.2 網路架構 5
2.3 系統架構 6
2.4 訊息傳遞介面 ─ MPI 8
2.5 平行計算的程式架構 8
2.6 個人電腦叢集平行化計算在科學計算上的利基 9
第三章 數值積分的自動佈點演算法 ─ 自動佈點Romberg樹積分方法 11
3.1 Romberg樹積分演算法 11
3.2 自動佈點積分演算法的兩種策略組合 ─ 提高精度與切分區域 12
3.3 自動佈點Romberg樹積分方法ARTint1D 12
3.3.1 Romberg樹的建立 12
3.3.2 Romberg樹積分方法的誤差控制 13
3.3.3 自動佈點的策略與Romberg 樹積分法的演算流程 14
3.3.4 加速數列收斂外插方法在數值積分之應用 16
3.3.5 ARTint1D程式架構 16
3.3.6 實例分析 17
第四章 自動佈點Romberg樹積分程式ARTint1D的平行化 18
4.1 「單程式多執行程序」的平行化實作 18
4.2 「單控制者+多工作者」的MPI實作方法 18
4.3 PARTint1D平行化程式 19
4.3.1 單控制者執行PARTint1D程式主架構 19
4.3.2 多工作者分別執行函數求值 19
4.3.3 PARTint1D程式架構 19
4.4 PARTint1D實例應用的效能分析 20
4.4.1 平行化效能分析的各項指標 20
4.4.2 實例分析 21
4.5 平行化在ARTint1D演算法的使用時機 26
第五章 以PARTint2D程式之迭代處理雙重數值積分及其平行化實作 27
5.1 雙重積分的數值計算與ARTint1D積分程式之迭代 27
5.2 單控制者進行外層積分之PARTint2D程序 28
5.3 多工作者進行內層積分之PARTint1D程序 28
5.4 實例分析 28
5.4.1 DICE1案例之特性 29
5.4.2 DICE1案例之參數分析 30
5.4.3 DICE1案例之精度分析 31
5.4.4 DICE1案例之平行化效能穩定性分析 32
5.4.5 DICE1案例之平行化效能分析 33
5.5 硬體與網路對平行化效能之影響 35
第六章 結論與展望 38
6.1 結論 38
6.2 未來研究展望 38
參 考 文 獻 40


表 目 錄

表2.1 個人電腦硬體規格 A。 43
表2.2 個人電腦硬體規格 B。 43
表2.3 網路卡、線材及集線器。 43
表5.1 不同硬體、網路架構下平行化加速比提升的比值。 43


圖 目 錄

圖1.1 電腦叢集架構在TOP500的佔有率(TOP500, 2005)。 44
圖1.2 電腦叢集架構在TOP500的成長情形(TOP500, 2005)。 44
圖2.1 電腦叢集的網路架構。 45
圖2.2 軟硬體整合架構。 45
圖2.3 序列化的程式架構。 46
圖2.4 平行化的程式架構。 46
圖3.1 Romberg 樹積分法多重區間處理示意圖(階數=3)。 47
圖3.2 Romberg 樹積分法的昇階計算：第2階昇為第3階。 47
圖3.4 Romberg 樹積分法各區間昇階的情形。 49
圖3.5 Romberg 樹積分法各區間昇階的先後次序。 49
圖3.6 實例分析之被積函數 圖形。 50
圖3.7 實例分析之誤差控制。 50
圖3.8 實例分析之函數值計算次數。 51
圖4.1 案例一之被積函數 圖形。 52
圖4.2 案例一之(實際絕對誤差對數值－容許絕對誤差對數值)之比較。(上)ltmax=6, lcmin=3、(中) ltmax=7, lcmin=4、(下) ltmax=8, lcmin=5。 53
圖4.3 案例一之函數值計算次數針對不同(容許絕對誤差對數值, 參數對數值）組合之比較。(上)ltmax=6, lcmin=3、(中) ltmax=7, lcmin=4、(下) ltmax=8, lcmin=5。 54
圖4.4 案例一之絕對誤差估計對數值vs. (容許絕對誤差對數值, 參數對數值) 之立體關係圖。 55
圖4.5 案例一之絕對誤差估計對數值vs. 容許絕對誤差對數值之比較。 55
圖4.6 案例一之(絕對誤差估計對數值－容許絕對誤差對數值)之比較。 56
圖4.7 案例一之(絕對誤差估計對數值－容許絕對誤差對數值)針對不同(容許絕對誤差對數值, 參數對數值)組合之比較。 56
圖4.8 案例一之實際絕對誤差對數值vs. (容許絕對誤差對數值, 參數對數值) 之立體關係圖。 57
圖4.9 案例一之實際絕對誤差對數值vs. 容許絕對誤差對數值之比較。 57
圖4.10 案例一之(實際絕對誤差對數值－容許絕對誤差對數值)之比較。 58
圖4.11 案例一之(實際絕對誤差對數值－容許絕對誤差對數值)針對不同(容許相對誤差對數值, 參數對數值)組合之比較。 58
圖4.12 案例一在不同函數重複計算次數下的工作者數量與平行化加速比之比較。 59
圖4.13 案例一在不同函數重複計算次數下的工作者數量與平行化加速效率之比較。 59
圖4.14 案例二之被積函數 圖形( )。 60
圖4.15 案例二之被積函數 圖形( ) 。 60
圖4.16 案例二之(實際絕對誤差對數值－容許絕對誤差對數值)之比較。(上)ltmax=6, lcmin=3、(中) ltmax=7, lcmin=4、(下) ltmax=8, lcmin=5。 61
圖4.17 案例二之函數值計算次數針對不同(容許絕對誤差對數值, 參數對數值)組合之比較。(上)ltmax=6, lcmin=3、(中) ltmax=7, lcmin=4、(下) ltmax=8, lcmin=5。 62
圖4.18 案例二之絕對誤差估計對數值vs. (容許絕對誤差對數值， 參數對數值) 之立體關係圖。 63
圖4.19 案例二之絕對誤差估計對數值vs. 容許絕對誤差對數值之比較。 63
圖4.20 案例二之(絕對誤差估計對數值－容許絕對誤差對數值)之比較。 64
圖4.21 案例二之(絕對誤差估計對數值－容許絕對誤差對數值)針對不同(容許絕對誤差對數值, 參數對數值)組合之比較。 64
圖4.22 案例二之實際絕對誤差對數值vs. (容許絕對誤差對數值， 參數對數值) 之立體關係圖。 65
圖4.23 案例二之實際絕對誤差對數值vs. 容許絕對誤差對數值之比較。 65
圖4.24 案例二之(實際絕對誤差對數值－容許絕對誤差對數值)之比較。 66
圖4.25 案例二之(實際絕對誤差對數值－容許絕對誤差對數值)針對不同(容許絕對誤差對數值, 參數對數值)組合之比較。 66
圖4.26 案例二在不同函數重複計算次數下的工作者數量與平行化加速比之比較。 67
圖4.27 案例二在不同函數重複計算次數下的工作者數量與平行化加速效率之比較。 67
圖5.1 DICE1之被積函數 圖形( )。 68
圖5.2 DICE1之內層被積函數 圖形( )。 68
圖5.3 DICE1之被積函數 圖形( )。 69
圖5.4 DICE1之內層被積函數 圖形( )。 69
圖5.5 (實際相對誤差對數值－容許相對誤差對數值)之比較。(上)ltmax=6, lcmin=3, erry=1e-3、(中) ltmax=7, lcmin=4, erry=1e-3、 (下) ltmax=8, lcmin=5, erry=1e-2。 70
圖5.6 內層函數值計算次數針對不同(容許相對誤差對數值, 參數對數值)組合之比較。(上)ltmax=6, lcmin=3, erry=1e-3、(中) ltmax=7, lcmin=4, erry=1e-3、 (下) ltmax=8, lcmin=5, erry=1e-2。 71
圖5.7 相對誤差估計對數值vs. 容許相對誤差對數值與 參數對數值之立體關係圖。 72
圖5.8 相對誤差估計對數值vs. 容許相對誤差對數值之比較。 72
圖5.9 (相對誤差估計對數值－容許相對誤差對數值)之比較。 73
圖5.10 (相對誤差估計對數值－容許相對誤差對數值)針對不同 (容許相對誤差對數值, 參數對數值)組合之比較。 73
圖5.11 實際相對誤差對數值vs. 容許相對誤差對數值與 參數對數值 之立體關係圖。 74
圖5.12 實際相對誤差對數值vs. 容許相對誤差對數值之比較。 74
圖5.13 (實際相對誤差對數值－容許相對誤差對數值)之比較。 75
圖5.14 (實際相對誤差對數值－容許相對誤差對數值)針對不同(容許相對誤差對數值, 參數對數值)組合之比較。 75
圖5.15 單機、4工作者、8工作者與16工作者以同一參數執行50次之執行時間。 76
圖5.16 (上)單機版、1工作者~16工作者以同一參數執行50次之執行時間(平均值、平均值±標準差、最小值、最大值)(下)將上圖之數據除以平均值之結果。 76
圖5.17 平行處理加速比針對不同(容許相對誤差對數值, 參數對數值) 組合之比較。(上) (中) (下)三圖皆為8工作者之結果。 77
圖5.18 執行時間之標準差除以平均值針對不同(容許相對誤差對數值, 參數對數值) 組合之比較。(上) 16工作者、(中) 8工作者、(下) 4工作者。 78
圖5.19 平行處理加速比vs. 容許相對誤差對數值與 參數對數值之立體關係圖。 (上) 16工作者、(中) 8工作者、(下) 4工作者。 79
圖5.20 平行處理加速比vs. 參數對數值之比較。 (上) 16工作者、(中) 8工作者、(下) 4工作者。 80
圖5.21 平行處理加速比vs. 容許相對誤差對數值之比較。 (上) 16工作者、(中) 8工作者、(下) 4工作者。 81
圖5.22 平行處理加速比針對不同(容許相對誤差對數值, 參數對數值) 組合之比較。(上) 16工作者、(中) 8工作者、(下) 4工作者。 82
圖5.23 平行處理加速效率vs. 容許相對誤差對數值與 參數對數值之立體關係圖。 (上) 16工作者、(中) 8工作者、(下) 4工作者。 83
圖5.24 平行處理加速效率vs. 參數對數值之比較。(上) 16工作者、(中) 8工作者、(下) 4工作者。 84
圖5.25 平行處理加速效率vs. 容許相對誤差對數值之比較。(上) 16工作者、(中) 8工作者、(下) 4工作者。 85
圖5.26 平行處理加速效率針對不同(容許相對誤差對數值, 參數對數值)組合之比較。(上) 16工作者、(中) 8工作者、(下) 4工作者。 86
圖5.27 Cluster A在Fast Ethernet與Gigabit Ethernet兩種不同網路架構的比較。(上)ClusterA, Fast Ethernet(中)ClusterA, Gigabit Ethernet(下)兩者間之比值。 87
圖5.28 Cluster B在Fast Ethernet與Gigabit Ethernet兩種不同網路架構的比較。 (上)Cluster B, Fast Ethernet(中)Cluster B, Gigabit Ethernet(下)兩者間之比值。 88
圖5.29 Fast Ethernet在Cluster A與Cluster B兩種不同硬體架構的比較。 (上)Cluster A, Fast Ethernet(中)Cluster B, Fast Ethernet(下)兩者間之比值。 89
圖5.30 Gigabit Ethernet在Cluster A與Cluster B兩種不同硬體架構的比較。 (上)Cluster A, Gigabit Ethernet(中)Cluster B, Gigabit Ethernet(下)兩者間之比值。 90

1.Aki, K., and Richards, P. G., [2002], “Quantitative Seismology”, 2nd ed., University Science Books, Sausalito California.
2.Bull, J. M., [1997], “Parallel Algorithms for Globally Adaptive Quadrature”, Ph.D. Thesis, University of Manchester.
3.De Doncker, E., [1978], “An Adaptive Extrapolation Algorithm for Automatic Integration”, SIGNUM Newsl, 13, pp. 12-18.
4.De Doncker, E., Ealy, P., and Gupta, A., [1996], “Two Methods for Load Balanced Distributed Adaptive Integration”, Lecture Notes in Computer Science 1067, High-Performance Computing and Networking, Eds. H. Liddell, A. Colbrook, B. Hertzberger and P. Sloot, Springer Verlag, pp. 562-570.
5.De Doncker, E., Gupta, A., and Greenwood, G., [1996], “Adaptive Integration Using Evolutionary Strategies”, Proceedings of the Third International Conference on High-Performance Computing (HiPC '96), pp. 94-99.
6.De Doncker, E., Kaugras, K., Cucos, L., and Zanny, R., [2002], “Current status of the ParInt package for Parallel multivariate Integration”, In Proceedings of the Second Computational Particle Physics Symposium (CPP'01), pp. 110-119.
7.Grama, A., Gupta, A., Karypis, G., and Kumar, V., [2003],” Introduction to Parallel Computing”, 2nd ed., Addison Wesley.
8.Gropp, W., [1997], “Tutorial on MPI: The Message-Passing Interface”, Mathematics and Computer Science, Argonne National Laboratory, Argonne, IL.
9.Kumar, V., and Grama, A., [1994], “Scalable Load Balancing Techniques for Parallel Computers”, Journal of Parallel and Distributed Computing, 22(1), pp. 60-79.
10.Li, S., De Doncker, E., and Kaugars, K., [2005], “On Iterated Numerical Integration”, Springer Lecture Notes in Computer Science, LNCS 3514, pp. 123-130.
11.Lyness, J. N., and Kaganove, J. J., [1976], “Comments on the Nature of Automatic Quadrature Routines”, ACM Transactions on Mathematical Software, Vol. 2, No. 1, pp. 65-81.
12.McKeeman, W.M., [1962],” Algorithm 145: adaptive numerical integration by Simpson’s rule”, Comm. ACM, v.5, pp. 604.
13.Pacheco, P. S., [1998], “A user's guide to MPI”, Technical report, Department of mathematics, University of San Fransisco, California.
14.Piessens, R., De Donker, E., Uberhuber, C. W., and Kahaner, D. K., [1983], “QUADPACK A Subroutine Package for Automatic Integration”, Springer-Verlag Berlin Heidelberg, Germany.
15.Quinn, M. J., [2004], “Parallel Programming in C with MPI and OpenMP”, McGraw-Hill
16.Rice, J. R., [1975], “A Metalgorithm for Adaptive Quadrature, Journal of the Association for Computing Machinery”, Vol. 22, No. 1, pp. 61-82.
17.Sidi, A., [2003], “Practical Extrapolation Methods: Theory and Applications”, No. 10 in Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press.
18.Sloan, J. D., [2004], “High Performance LINUX CLUSTER with OSCAR, Rocks, openMosix & MPI”, O’Reilly.
19.Universitys of Mannheim and Tennessee, “TOP500 Supercomputer Sites”, http://www.top500.org/.
20.Yazıcı, A., Ergenç ,T., and Altas, İ., [2003], “Romberg integration: A symbolic approach with Mathematica”, Lecture Notes in Computer Science, 2657, pp. 691-700.
21.Zanny, R., [1999], “Efficiency of Distributed Priority Queues in Parallel Adaptive Integration”, Master's thesis, Western Michigan University.
22.林聰悟, 林佳慧, [1997], “數值方法與程式”, 著者自行出版.
23.李洋傑, [1997], “鋼結構實體模型之土壤與結構互制作用研究”, 行政院國家科學委員會專題研究計畫成果報告.
24.冼鏡光, [1990], “FORTRAN程式語言”, 格致圖書.