CAJ | 학술논문

提出了两种新的并行排序算法,在第一部分设计了一种有效的异步并行算法,可应用于多指令和多数据流计算机,且提供了该算法的最小和最大的运算时间.第二部分给出了一种新的并行排序网络,对于n个元素的排序序列,可以使用n(n-1)/2个比较元素和n(n-1)/2个反转换元素及n个转换元素能达到常数数量级的运行时间进行快速排序,同时给出了以{0,1}元素组成的序列的排序过程.
제출료량충신적병행배서산법,재제일부분설계료일충유효적이보병행산법,가응용우다지령화다수거류계산궤,차제공료해산법적최소화최대적운산시간.제이부분급출료일충신적병행배서망락,대우n개원소적배서서렬,가이사용n(n-1)/2개비교원소화n(n-1)/2개반전환원소급n개전환원소능체도상수수량급적운행시간진행쾌속배서,동시급출료이{0,1}원소조성적서렬적배서과정.
We present two new parallel sorting algorithms.In first chapter an efficient asynchronous parallel sorting algorithm on an MIMD computer has been designed.A lower bound and upper bound for running times of the algorithm are provided. In second chapter,a new parallel sorting network has been designed.By using n(n-1)/2 comparison elements,n(n-1)/2 inverters and n transverters which can with it perform the sum of {0,1}elements a fast sorting algorithm with a running time of T(n)=4 for the problem of sorting a sequence of n items has been proposed.