臺灣博碩士論文加值系統

(44.200.95.157) 您好！臺灣時間：2024/08/08 12:49

:::

詳目顯示

:

• 被引用:0
• 點閱:230
• 評分:
• 下載:0
• 書目收藏:0
 稀疏矩陣的重排列對矩陣分解的效能影響至鉅．一個好的重排列演算法不 僅僅是對循序計算機極為重要，同時也會導致較佳的負載分配，進而提高 平行計算機的效能．儘管長久以來，較少的插入元素一直是評斷循序排列 方法的優劣的標準；然而至今仍無一致的標準來評斷平行排列方法．回顧 過去關於平行排列的研究，大都以消去樹的高度作為衡量的標準．換言之 ，較矮的樹優於較高的樹．然而隨著平行架構的日趨複雜及各種平行矩陣 分解法的相繼出現，要取得一適合各式情況的衡量標準似乎是極為困難． 任意使用消去樹的高度作為各種情況下的衡量標準是極危險的．由一些特 殊的例子顯示，消去樹的高度不僅無法反應真正的平行計算時間且忽略了 通訊所需的額外負擔．此外，它所獲致的速率增加比也遠低於所期望的值 ．在這個論文中我們提出一個重排列衡量標準的組織架構．根據一些平行 架構考慮的因素，我們希望將各種平行稀疏矩陣分解法所需要花的時間降 至最低．因此我們提出一個適合各種衡量標準的重排列方法．其所產生的 重排列能保証平行矩陣分解所需的時間是所有重排列中最短的．從一些稀 疏矩陣的實驗結果進一步証明此重排列方法的可行性．
 Reordering of sparse matrices is essential for good performance on Cholesky factorizations. A good reordering algorithm not only is crucial on a sequential computer, but also can lead to a much better load balance on a parallel computer, and thus to a dramatic increase in performance compared to a "naive" ordering. Though low fill has been long served as an appropriate criterion for measuring the quality of sequential ordering methods, either in space or time, there is not yet an agreed upon objective function for the parallel ordering problem. Reviewing the previous works on parallel ordering problem, most have used elimination tree height as the criterion for comparing orderings; that is, with shorter trees assumed to be superior to taller trees. But with more complicated the parallel architectures have been evolving into and quite a variety of parallel factorization algorithms have been developed, it seems hardly to achieve a well agreed upon criterion suitable for all situations. The discrepancy of simply using elimination tree height as the criterion for different situations is comprehensively illustrated with some contrived examples. As the results shown, the height of elimination tree not only inept to indicate the actual parallel computing time, but also neglect the underlying communication overhead. Additionally, the speedup it can achieve is far less than the expected. The underlying idea in this dissertation is that we propose a framework of reordering criteria aiming to minimize the completion time of various parallel sparse Cholesky factorizations with respect to some architecture issues. Under the framework we have presented a general reordering scheme which yields an equivalent reordering that always guarantees minimum completion time among all equivalent reorderings of the filled graph. Empirical results on a careful selection from the Harwell-Boeing sparse matrices collection further assent the attraction of this reordering scheme.
 CoverContentsAcknowledgmentsAbstractAbstract in ChineseChapter 1 Introduction1.1 Direct Solution of Sparse Linear Systems1.1.1 Symbolic Factorization1.1.2 Task Scheduling1.1.3 Triangular Solution1.2 Some Graph Theory Notations1.3 Cholesky Factorization1.4 Organization of this DisserationChapter 2 Overview of Ordering Problem2.1 Perfect Ordering and Equivalent Reordering2.2 Ordering for Sequential Factorization2.3 Ordering for Parallel Factorization2.4 Previous Related WorkChapter 3 Criteria for Reorderings3.1 A Reordering Framework3.2 Evaluation Functions of Ordering Criteria3.3 Parallel Completion Time Criterion3.4 Consideration on Insufficient Bankwidth3.5 Comparative Analysis of Parallel Sparse Cholesky Factorizations3.5.1 Theoretical Results3.5.2 An example3.6 Deficiencies of Elimination Tree Height Criterion3.6.1 Contrived Examples3.6.3 Comparison with Minimum Height CriterionChapter 4 A Generic Algorithm for Optimal Reorderings4.1 General Description4.2 Minimum Completion Time Property4.3 Combination of Criteria4.4 Detailed Discussions4.4.1 Representation of the Filled Graph4.4.2 Implementation of the Simplicial Set4.4.3 Calculation of the Completion Time4.4.4 Detailed Description and Complexity Analysis4.4.5 Improvement by Simplicial Clique ConceptChapter 5 Implementation and Experimental Results5.1 Test Data Statistics5.2 Comparison and Analysis5.2.1 Computation Issue5.2.2 Communication Issue5.3 SummaryChapter 6 Conclusions6.1 Effects of Task Granularity6.2 More on the Two-Phase Ordering ApproachBibliography
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 在共享記憶體系統的快速平行隨機梯度下降法矩陣分解 2 使用多子矩陣法結合中央處理器和圖形處理器解決大型稀疏線性系統

 無相關期刊

 1 自動迴圈重排列以增加階層式記憶體的資料再使用率 2 笛卡爾通訊問題的研究 3 異質分散式執行系統的設計及實作 4 稀疏多鋒Cholesky分解之處理器配置與工作排程 5 應用無人機低空偵測之研究 6 互動式多媒體融入語文教材與教學之研究 7 混合實境於藝術教材之設計與製作 8 不同種類手機遊戲與學習成就關係之研究 9 應用大數據分析學生網路成癮之研究 10 互動式APP遊戲設計與教學應用之分析 11 應用微電腦控制一體式懸吊點焊機之研究 12 無線射頻辨識庫房管理系統之建置 13 製藥用超純水處理系統設計與應用驗證 14 無線充電系統設計與應用 15 網頁式介面為基礎之維修大數據系統

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室