(3.235.11.178) 您好!臺灣時間:2021/02/26 03:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳明正
研究生(外文):CHEN,MING-ZHENG
論文名稱:在超立方體系統上之平行第k選擇與排序演算法
論文名稱(外文):Parallel K-th selection and sorting algorithms on hypercube
指導教授:唐傳義
指導教授(外文):TANG,CHUAN-YI
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1990
畢業學年度:78
語文別:中文
論文頁數:27
中文關鍵詞:超立方體第k選擇問題刪剪與尋找略中點尋找刪剪元平均問題區分問題排序
外文關鍵詞:(HYPERCUBE)(K-TH-SELECTION-PROBLEM)(PRUNE-AND-SEARCH)(ROUGH-MEDIAN-FINDING)(PRUNER)(BALANCING-PROBLEM)(PARTITION-PROBLEM)(SORTING)
相關次數:
  • 被引用被引用:1
  • 點閱點閱:91
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在本論文中,我們將在超立方體(hypercube) 系統上解決一系列之問題。首先我們解
決第 K選擇問題(k-th selection problem)。我們定義第 k選擇問題如下:設每一處
理器皆擁有 d個已排序好之資料並給定一k 值,我們將在所有分佈於各處理器之n 個
資料中找到其值為第k 大的數字。我們利用刪剪與尋找(prune-and-search)策略來解
決k 選擇問題。首先我們提出略中點尋找(rough-median finding)演算法使我們能在
較短之時間中找到一個刪剪元(pruner)。在每一處理器中找到此一刪剪元之排行(ra-
nking),再利用加法可以獲知其總排行。利用其總排行便可獲知第k 小的數目是大於
或小於此刪剪元,而保留比刪剪元大或小之資料。如此不斷重覆刪除不適用之資料直
到找到第 k小的數目為止。
然後我們再解決平均問題(balancing problem) 與區分問題 (partition problem)。
如果每一處理器所擁有之資料量不相等,則如此可能會降低整個系統之效率。將所有
資料重新安排,使每一處理器都擁有 d個資料,此即為平均問題。區分問題則是給一
定值 m,我們將我們的超立方體切分為兩個次立方體(subcubes),使得小於或等於 m
之資料集中於第一次立方體中,而大於或等於 m之資料集中於第二次立方體。然後再
分別對兩個次立方體之處理器做資料量之平均。解決平均問題之方法是先與一連結 (
link) 之另一端處理器交換其資料量,然後資料較多之處理器將部分資料送給資料較
少之處理器,使得此二處理器擁有相同之資料量。如此對每一連結執行相同步驟,便
可解決平均問題。至於區分問題,首先與分屬不同次立方體之處理器交換不屬於自己
之資料,再利用前述之平均演算法來分別解決兩個次立方體。
在超立方體系統上之排序(sorting) 問題則是將所有之資料依大小順序排好,然後依
處理器編號之大小順序將已排序之資料平均分散於各處理器中。我們利用分割與克服
(divide-and-conquer)策略來解決排序問題。先利用第二章中介紹之第k 選擇演算法
來找出中間值(median),再跟據此中間值,利用第三章中之區分演算法,可以將所有
資料平分成兩部分,且平均地分布於兩個次立方體中。如此便會使一次立方體中之資
料大於另一個次立方體中之資料。我們再對這兩個次立方體執行上述之步驟,如此不
斷重覆直到每一次立方體都只有一個處理器為止。如此便可完成排序。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔