计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2002年
10期
1307-1313
,共7页
串行算法并行化%并行算法%并行归并%并行排序%Bitonic排序
串行算法併行化%併行算法%併行歸併%併行排序%Bitonic排序
천행산법병행화%병행산법%병행귀병%병행배서%Bitonic배서
串行算法并行化是发挥各种巨型机的效率的关键技术之一."并行优化-串行"归并向量算法(POSVM),是一种串行算法并行化的优化方法.它用O(N/p)时间把总长为N的两个有序序列归并或把总长为N的一个Bitonic序列排序."并行优化-串行"排序向量算法(POSVS)用O((NlogN)/p)时间在实际SIMD机上把N个数排序.这些是第1个满足以下两个条件的向量Optimal算法(加速比=O(p)).①它能在实际SIMD计算机上实现.处理机的台数p的范围很宽1≤p≤N1-ε,这里,ε是任意的小的正数.②它统一了3种不同类的合并算法:Batcher的Bitonic算法(最快但效率随参数变大而趋向于0)、优化(Optimal)算法(效率为常数的算法)和最佳的串行算法.而且也综合了3个算法的优点."并行优化串行"(POS)方法是一个通用方法,它还可以应用到其它类型问题上.
串行算法併行化是髮揮各種巨型機的效率的關鍵技術之一."併行優化-串行"歸併嚮量算法(POSVM),是一種串行算法併行化的優化方法.它用O(N/p)時間把總長為N的兩箇有序序列歸併或把總長為N的一箇Bitonic序列排序."併行優化-串行"排序嚮量算法(POSVS)用O((NlogN)/p)時間在實際SIMD機上把N箇數排序.這些是第1箇滿足以下兩箇條件的嚮量Optimal算法(加速比=O(p)).①它能在實際SIMD計算機上實現.處理機的檯數p的範圍很寬1≤p≤N1-ε,這裏,ε是任意的小的正數.②它統一瞭3種不同類的閤併算法:Batcher的Bitonic算法(最快但效率隨參數變大而趨嚮于0)、優化(Optimal)算法(效率為常數的算法)和最佳的串行算法.而且也綜閤瞭3箇算法的優點."併行優化串行"(POS)方法是一箇通用方法,它還可以應用到其它類型問題上.
천행산법병행화시발휘각충거형궤적효솔적관건기술지일."병행우화-천행"귀병향량산법(POSVM),시일충천행산법병행화적우화방법.타용O(N/p)시간파총장위N적량개유서서렬귀병혹파총장위N적일개Bitonic서렬배서."병행우화-천행"배서향량산법(POSVS)용O((NlogN)/p)시간재실제SIMD궤상파N개수배서.저사시제1개만족이하량개조건적향량Optimal산법(가속비=O(p)).①타능재실제SIMD계산궤상실현.처리궤적태수p적범위흔관1≤p≤N1-ε,저리,ε시임의적소적정수.②타통일료3충불동류적합병산법:Batcher적Bitonic산법(최쾌단효솔수삼수변대이추향우0)、우화(Optimal)산법(효솔위상수적산법)화최가적천행산법.이차야종합료3개산법적우점."병행우화천행"(POS)방법시일개통용방법,타환가이응용도기타류형문제상.
