跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.172) 您好!臺灣時間:2025/02/18 03:59
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳育威
論文名稱:超立方體多處理機上具容錯能力之前置針算、排序及嵌入演算法之設計與分析
論文名稱(外文):The Design and Analysis of Fault-Tolerant Prefix Computation, Sorting and Embedding Algorithms on Hypercubes
指導教授:鍾國亮鍾國亮引用關係
學位類別:博士
校院名稱:國立臺灣科技大學
系所名稱:管理研究所
學門:商業及管理學門
學類:企業管理學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:78
中文關鍵詞:容錯演算法前置計算排序嵌入有處理故障的超立方體多處理機被佔較少之維度
相關次數:
  • 被引用被引用:0
  • 點閱點閱:314
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
In parallel processing, prefix computation, sorting, and embeddings are three of the most important and kernel research issues. Based on the concept of the light-occupied dimension (LOD) [60, 62], this thesis first proposes some new partition schemes to partition a hypercube into subcubes. According to the proposed schemes and the derived properties, this thesis presents two algorithms for prefix computation and sorting on faulty hypercubes. Without using the LOD concept, we present some embedding methods to map complete binary trees into faulty hypercubes.
Given 2n = N operands and an n-dimensional hypercube Hn with [3n/2] - 1 faulty nodes, employing a newly proposed delay-update technique, the proposed algorithm for prefix computation takes n + 5logn + 7 steps and it tolerates more [n/2] faulty nodes than Raghavendra and Sridhar''s algorithm [46], although 11 extra steps are needed.
Consider M unsorted elements and the same faulty Hn, where M ≧ N. With O((M/N) log(M/N) + (M/N) log2 N) time as in Sheu et al.'' algorithm [53], the proposed sorting algorithm tolerates more [n/2] faulty nodes than Sheu et al.''s algorithm [53]. Finally, we present some embedding methods to map complete binary trees (CBTs) into hypercubes. With dilation 1 and expansion 1, we first present an embedding algorithm to map two (n-1)-CBTs, where each is a CBT with n-1 levels and 2n-1 nodes, (one (n-1) -CBT and two (n-2)-CBTs) into Hn tolerating two (three) connected faulty nodes. With dilation 1 and expansion 2, the proposed fault-tolerant embedding algorithm maps an (n - 1)-CBT into an Hn with 2n - 2[log2 (n-2)]-5 faulty nodes distributed on a half of the Hn. Under the same dilation, expansion, and distribution of faulty nodes, our result has twice the capacity of fault tolerance of the previous known result [9] asymtotically.
cover
Conternts
Chapter 1. Introduction
1.1. Background
1.2. Motivations and purposes
1.3. Contributions
1.4. Organization of the thesis
Chapter 2. Degree of Occupancy
Chapter 3. Partitioning Strategy and Fault-Distribution Analyses
3.1 Partitioning a Faulty H into SH''s
3.2 Analyses of Fault-Distribution for SH''s
Chapter 4. Prefix Computations
4.1. Preliminaries
4.2. Data Allocation
4.3. The Proposed Algorithm
Chapter 5. Sorting
5.1. The Sketch of Sheu it al.''s Sorting Algorithm
5.2. New Partition Strategy Based on LOD concept
5.3. Case 1 and Case 2
5.4. Case 3a
5.5. Case 3b
Chapter 6. Embedding Complete Binary Trees into Hypercubes
6.1. Definitions and Terminologies
6.2. Embedding Multiple CBTs into Hypercube
6.3. Embedding (n-1)-CBT into Hn
Chapter 7 . Conclusions and Future Works
References
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top