Maspar 머쉰상의 병렬 분류 알고리즘

• 영문명: Parallel Sorting Algorithm on MasPar Machine
• 발행기관: 호서대학교 중앙도서관
• 저자명: 민용식(Yong sik Min)
• 간행물 정보: 『호서대학교 논문집』제2권, 91~105쪽, 전체 15쪽
• 주제분류: 사회과학 > 무역학
• 파일형태: PDF
• 발행일자: 1994.12.30

영문 초록

This paper presents a parallel sorting algorithm suitable for the SIMD multiprocessor. The algorithm finds pivots for partitioning the data into ordered subsets. The data can be evenly distributed to be sorted since it uses the probability theory. For n data elements to be sorted on p processors, when n ≥ p², the algorithm is shown to be asymptotically optimal. In practice, sorting 8 million data items on 64 processors achieved a 48.43-fold speedup, while the PSRS required a 44.4-fold speedup. On a variety of shared and distributed memory machines, the algorithm achieved better than half-linear speedups.

목차

Abstract

Ⅰ. Introduction

Ⅱ. Parallel Sorting by Median-Median

Ⅲ. Complexity Analysis

Ⅳ. Experimental Results

Ⅴ. Conclusion

References