REDUCING COMMUNICATION COSTS FOR SORTING ON MESH-CONNECTED AND LINEARLY CONNECTED PARALLEL COMPUTERS

被引：9

作者：

PARK, A ^{[1
]}

BALASUBRAMANIAN, K ^{[1
]}

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1990年 / 9卷 / 03期

关键词：

D O I：

10.1016/0743-7315(90)90083-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Most sorting algorithms for linearly connected and mesh-connected parallel computers have been developed assuming that the number of processors equals the number of elements to be sorted. This assumption has simplified analysis of the problem, however, it causes unnecessary communication costs because elements must be permuted across large numbers of processors. It also underutilizes processors because comparison operations involve two data elements for each processor. By modifying parallel sorting algorithms to use fewer processors, we are able to improve processor utilization and decrease communication costs. This leads to constant factor improvements in the best parallel sorting bounds for both mesh-connected and linearly connected SIMD parallel computers. (Previous bounds are within a constant factor of optimal.). © 1990.

引用

页码：318 / 322

页数：5