跳到主要內容

臺灣博碩士論文加值系統

(3.238.225.8) 您好!臺灣時間:2022/08/09 00:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:李佳訓
研究生(外文):Jia-Shin Li
論文名稱:Fortran90稀疏矩陣結構的或然率推理方法
論文名稱(外文):Probabilistic Inference Schemes for Sparsity Structures of Fortran 90 Array Intrinsics
指導教授:李政崑
指導教授(外文):Jenq Kuen Lee
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:32
中文關鍵詞:電腦效能分散式處理器多處理器數值程式設計
外文關鍵詞:Computer performanceDistributed processorsMultiprocessorsMathematical programming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:130
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
Fortran 90 提供了相當豐富的矩陣運算函式,對於表示矩陣運算式
和平行運算來說是相當有用的。然而在分散式記憶體的環境中,這些
矩陣運算函式應用在稀疏資料集的方式,並不被Fortran 90 或 HPF
編譯器所支援。在我們一系列的研究中,我們嘗試對於Fortran 90
的矩陣運算提供稀疏矩陣的平行化支援。在我們的設計中,以多載矩
陣運算子和函式來提供稀疏矩陣的模組化支援。
在我們實驗和設計的過程式,我們發現稀疏矩陣的稀疏程度資訊,對
於效能的影響,例如壓縮、散布和傳遞的花費,具有決定性的影響。
對我們的程式來說,如何取得這些稀疏程度資訊就顯得相當地重要。
先前我們提出了以或然率推理的方式,來估計Fortran 90 運算式目
標矩陣的稀疏程度。我們以假設原始矩陣元素平均分布的方式,對於
Fortran 90 矩陣運算函式的目標矩陣推理其稀疏度度。然而,對於
非平均分布的矩陣來說,這個問題仍舊沒有解決。
在這份論文中,提出了這個問題的解決方法。提出了對於Fortran 矩
陣運算和函式運用在非平均分布情形下的推理方式。並且以對
Harwell-Boeing 稀疏矩陣集的實驗來觀察我們的取樣方法。我們並
展示出實驗的結果和分析模型,說明利用我們的或然率推理方法和稀
疏矩陣的分布結構,在選擇 OLAP 的程式上,編譯器有顯而易見的效
能改進。我們的實驗是在 IBM SP2 的平台上,以我們對 Fortran 90
稀疏矩陣的函式支援所完成。

Fortran 90 provides a rich set of array intrinsic functions,
and they are useful to represent array expressions and data
parallel programming. In the case that these intrinsic
functions are applied to sparse data sets on distributed
memory environments, it is however not supported by vendor
Fortran 90 or HPF compilers. In a series of our research
work, we attempt to provide parallel sparse supports for
array intrinsics of Fortran 90.
In our design, we support sparse modules with overloaded
array operations and intrinsics.
In the process of our lab's experiments and design, we found
that the sparsity information of sparse arrays are crucial
for performance issues, such as compression, distribution,
and communication cost. It became crucial how we could
obtain the sparsity information for arrays of our programs.
Previously, we provided probabilistic inference schemes to
estimate sparsity ratio of target arrays operated based on
Fortran 90 array operations and intrinsics.
Our methods gave an inference scheme to estimate the
sparsity ratio of the target array of an expression using
array intrinsic functions of Fortran 90 assuming a uniform
distribution of sparsity among source array elements.
However, it remains open for this problem when the sparse
dataset is with non-uniform distributions.
In this thesis, a solutions was proposed to address the issues
for the non-uniform distribution of sparse elements. This
work gives sparse inference schemes for the complete set of
array operations and array intrinsics of Fortran 90 for
non-uniform distributions of sparse datasets. Experiments
are also done to observe our sampling techniques for sparse
arrays with the Harwell-Boeing sparse matrix collection. We
also demonstrate with our experiments and analytical model
that a compiler can distinguish the performances among
different OLAP programs with the help of the sparsity
structures of the source arrays and our probabilistic
inference schemes. Our experiments are done on IBM SP-2 and
with the support of our sparse array intrinsics of Fortran
90.

Contents
Abstract i
Contents iii
List of Figures iv
List of Tables v
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Sparse Supports for Array Operations 5
2.1 Motivating Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Sparse Supports for Fortran 90 Array Intrinsic Functions . . . . . . . 7
2.3 Concern on Irregularly Shaped Sparse Arrays . . . . . . . . . . . . . 9
3 Probabilistic Inference Scheme 11
3.1 Inference Schemes with Non-Uniform Distributions . . . . . . . . . . 11
3.1.1 Dense Subarray Extraction/Sampling . . . . . . . . . . . . . . 11
3.1.2 Segmented Inference Algorithm . . . . . . . . . . . . . . . . . 16
3.1.3 Transformational Functions . . . . . . . . . . . . . . . . . . . 18
iii
4 Experimental Results 20
4.1 Expremental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Conclusion and Future Work 29
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Bibliography 30
iv

Bibliography
[Adams 92] Jeanne C. Adams, Walter S. Brainerd, Jeanne T. Martin, Brian T.
Smith, and Jerrold L. Wagener, Fortran 90 handbook complete
ansi/iso reference, Intertext Publications McGraw-Hill Book Company, 1992.
[Alok 98] Sanjay Goil and Alok Choudhary. High Performance OLAP and Data
Mining on Parallel Computers, In Proceedings of IPPS/SPDP '98,
Orlando, April, 1998.
[Bodin 93] F. Bodin, P. Beckman, D. Gannon, S. Narayana, and S. Yang, "Dis-
tributed pC++: Basic ideas for an object parallel language,"
Scientific Programming, Vol. 2, No. 3, 1993.
[Chang 97] Rong-Guey Chang, Cheng-Wei Chen, Tyng-Ruey Chuang, and
Jenq Kuen Lee. Towards automatic supports of parallel sparse
computation in Java with continuous compilation. Concurrency: Practice
and Experience, 9(11):1101-1111, November 1997. This special journal
issue is dedicated to the 1997 ACM Workshop on Java for Science
and Engineering Computation, Las Vegas, Nevada, USA, June 1997.
[Chang 98] Rong Guey Chang, Tyng Ruey Chuang, and Jenq Kuen Lee, "Efficient
Support of Parallel Sparse Computation for Array Intrinsic
Functions of Fortran 90," ACM International Conference on Supercomputing,
Melbourne, July 13-17, 1998.
[Chang 99] Rong Guey Chang, Tyng Ruey Chuang, and Jenq Kuen Lee,
"Compiler Optimizations for Parallel Sparse Programs with Array Intrinsics
of Fortran 90," International Conference on Parallel Processing,
September 1999.
[Chang 00] Rong-Guey Chang, Tyng-Ruey Chuang, and Jenq Kuen Lee.
Parallel Sparse Supports for Array Intrinsic Functions of Fortran 90,
accepted by The Journal of Supercomputing.
[Cytron 97] Michael P. Plezbert and Ron K. Cytron. Does "just in time" =
"better late then never". In 24th Annual SIGPLAN{SIGACT Symposium
on Principle of Programming Languages. Paris, France, 1997.
12 pages. ACM Press.
[Garey] M. Garey and D. Johnson. Computers and Intractability: A Guide to
the Theory of NP-Completeness.
[Hwang 95] Gwan-Hwan Hwang, Jenq Kuen Lee, and Dz ching Ju, "An array
operation synthesis scheme to optimize Fortran 90 programs,
"Proceedings of the Fifth ACM SIGPLAN Symposium on Principles &
Practice of Parallel Programming, July 1995.
[Iain 89] Iain S. Duff, Roger G. Grimes, and John G Lewis, Sparse Matrix Test
Problems, ACM Trans. Math. Softw. pp.1-14, 15, 1, Mar. 1989.
[Koelbel 94] Charles H. Koelbel, David B. Loveman, Robert S. Schreiber, Guy
L. Steele Jr, and Mary E. Zosel, The high performance fortran handbook,
Scientic and Engineering Computation Series, The MIT Press, 1994.
[Kumar 98] Mahesh V. Joshi, George Karypis, and Vipin Kumar, "ScalParC:
A New Scalable and Efficient Parallel Classification Algorithm for
Mining Large Datasets", Proceedings of IPPS/SPDP '98, Orlando,
April, 1998.
[Press 96] William H. Press, Saul A. Teukolsky, William T. Vetterling, and
Brian P. Flannery, Numerical Recipes in Fortran 90: The Art of
Scientic Computing, Cambridge University Press, 1996.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top