碩士論文

碩士論文摘要
題目: Parallel K-th Selection and Sorting Algorithms on Hypercube. 指導教授: 唐傳義教授 (清華大學) 在本論文中，我們討論超立方體（Hypercube）系統上解決一系列問題之方法。第K選擇問題(K-th selection problem)：平行第K 選擇問題之定義如下：每一處理器皆擁有d 個已排序好之資料，並給定一K 值，則由分布於各處理器之N個資料中找到值為第K 大之資料。本文利用刪剪與尋找（Prune-and-Search）策略來解決此一問題。本文提出一略中點（Rough-median）尋找演算法，使我們能在較短之時間中找到一個刪剪元（Pruner），再在每一處理器中找到此一刪剪元之排行(Ranking) 而得知其總排行。依此，便可在 log d 個循環後找到第K 大之資料。平均問題(Balancing problem) 與區分問題(Partition problem)：若每一處理器上所擁有之資料量不相等，則會降低整個系統之效率。將系統中之所有資料重新安排，使得在各處理器中之資料數量相等，此即為平均問題。而區分問題則是給定一m 值，然後將此一超立方體切分成兩個次立方體，使得小於m 值之資料集中於一個次立方體，而大於m 值之資料集中於另一次立方體中。本論文對此二問題皆有提出解決方法。本論文利用上述三問題之解法加以整合, 成平行系統之排序方法。

碩士論文摘要

題目: Parallel K-th Selection and Sorting Algorithms on Hypercube.
指導教授: 唐傳義教授 (清華大學)

在本論文中，我們討論超立方體（Hypercube）系統上解決一系列問題之方法。

第K選擇問題(K-th selection problem)：
平行第K 選擇問題之定義如下：每一處理器皆擁有d 個已排序好之資料，並給定一K 值，則由分布於各處理器之N個資料中找到值為第K 大之資料。本文利用刪剪與尋找（Prune-and-Search）策略來解決此一問題。本文提出一略中點（Rough-median）尋找演算法，使我們能在較短之時間中找到一個刪剪元（Pruner），再在每一處理器中找到此一刪剪元之排行(Ranking) 而得知其總排行。依此，便可在 log d 個循環後找到第K 大之資料。

平均問題(Balancing problem) 與區分問題(Partition problem)：
若每一處理器上所擁有之資料量不相等，則會降低整個系統之效率。將系統中之所有資料重新安排，使得在各處理器中之資料數量相等，此即為平均問題。而區分問題則是給定一m 值，然後將此一超立方體切分成兩個次立方體，使得小於m 值之資料集中於一個次立方體，而大於m 值之資料集中於另一次立方體中。

本論文對此二問題皆有提出解決方法。本論文利用上述三問題之解法加以整合, 成平行系統之排序方法。

回主畫面