排序方法向量化之研究

Abstract

儘管許多關於計算應用上的平行計算機架構已被探討，然而向量計算機成功地商品化 ，如Cray-1, Cyber-205, 使其成為此一應用領域的主流。欲完全發揮此種高速計算 機的效能，最重要的就是資料的向量化。雖然向量編譯器能夠檢視出程式中可向量化 的部份，但仍需要適當的演算方法相互配合。在這篇論文中，我們對一些排序方法的 向量化進行研究，包括Quicksort, Insertion sort, Shellsort, Straight radix s ort, Radix exchange sort, Odd-even transposition sort, Odd-even merge sort , 和Diamond sort。我們在CONVEX C-1上實際地執行這些排序方法，測量每個方法的 純量和向量的速度比，以評估其適合向量化的程度。從比較之中我們發現，雖然以比 較一交換作為運算基礎的排序方法中具不定性質(contingent)者較不適合向量化，但 運用M-section 方法的Insertion sort卻有很好的表現。至於以基數分配為基礎的排 序的方法，採LSD 方式較MSD 更適合向量化。最後，根據我們的實驗與討論，我們建 議在向量計算機上採用Straight radix sort 。