Abstract
在本論文中，我們將在超立方體(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)，再跟據此中間值，利用第三章中之區分演算法，可以將所有資料平分成兩部分，且平均地分布於兩個次立方體中。如此便會使一次立方體中之資料大於另一個次立方體中之資料。我們再對這兩個次立方體執行上述之步驟，如此不斷重覆直到每一次立方體都只有一個處理器為止。如此便可完成排序。