Performance modelling of three parallel sorting algorithms on a pipelined transputer network

被引:0
|
作者
Narasimhan, VL [1 ]
Armstrong, J [1 ]
机构
[1] DEF SCI & TECHNOL ORG,DIV INFORMAT TECHNOL,SALISBURY,SA 5708,AUSTRALIA
来源
CONCURRENCY-PRACTICE AND EXPERIENCE | 1996年 / 8卷 / 05期
关键词
D O I
10.1002/(SICI)1096-9128(199606)8:5<335::AID-CPE202>3.0.CO;2-Y
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The implementation of three parallel sorting algorithms, namely binary sort, odd-even transposition sort and bitonic sort, on a network of transputers is analysed in the paper. The variation in the performance of these algorithms as the number of processors and sort size are changed is investigated, Experimental results show that when up to eight transputers are used, connected as a linear pipeline configuration, all three algorithms can achieve reasonable speedup ratios, The bitonic sort, binary sort and odd-even transposition sort achieve speedup ratios of 5, 4.4 and 4, respectively, when eight processors are used to sort 100,000 integers. Analytical models are derived which can be used to predict the performance of the three algorithms when a linear pipeline configuration is used. The predicted performance of the algorithms is compared with the experimental performance in order to validate the model, When the models are used to predict the performance using 16 transputers, it is found that the speedup does not significantly improve compared to the performance achieved with eight transputers, This shows that interprocessor communication has a significant effect on the algorithmic performance when a larger number of processors are used. The conclusions reinforce the fact that the binary and bitonic sorting algorithms are not well-suited to a linear pipeline configuration and that they may perform better if a different topology were used, for example a mesh or a cube connection scheme. Further, the analytical technique used for performance modelling as elaborated in the paper can be employed profitably for other multiprocessor systems as well.
引用
收藏
页码:335 / 355
页数:21
相关论文
共 50 条
  • [21] An Experimental Analysis of Parallel Sorting Algorithms
    G. E. Blelloch
    C. E. Leiserson
    B. M. Maggs
    C. G. Plaxton
    S. J. Smith
    M. Zagha
    Theory of Computing Systems, 1998, 31 : 135 - 167
  • [22] OPTIMAL SORTING ALGORITHMS FOR PARALLEL COMPUTERS
    BAUDET, G
    STEVENSON, D
    IEEE TRANSACTIONS ON COMPUTERS, 1978, 27 (01) : 84 - 87
  • [23] An experimental analysis of parallel sorting algorithms
    Blelloch, GE
    Leiserson, CE
    Maggs, BM
    Plaxton, CG
    Smith, SJ
    Zagha, M
    THEORY OF COMPUTING SYSTEMS, 1998, 31 (02) : 135 - 167
  • [24] PROBABILISTIC PARALLEL ALGORITHMS FOR SORTING AND SELECTION
    REISCHUK, R
    SIAM JOURNAL ON COMPUTING, 1985, 14 (02) : 396 - 409
  • [25] Parallel probabilistic searching and sorting algorithms
    Kramosil, Ivan
    Kybernetika, 1990, 26 (02) : 17 - 40
  • [26] Performance modelling of a parallel neural network simulator
    Tollenaere, T.
    Roose, D.
    Proceedings of the World Transputer User Group (WOTUG) Conference, 1992, 25
  • [27] PIPELINED RING ALGORITHM FOR MATRIX MULTIPLICATION ON TRANSPUTER NETWORKS - PERFORMANCE ANALYSIS AND ESTIMATION
    SRINIVAS, S
    BASU, A
    KUMAR, KG
    PAULRAJ, A
    PATNAIK, LM
    COMPUTING SYSTEMS, 1992, 7 (01): : 42 - 51
  • [28] PERFORMANCE OF A PIPELINED RING ALGORITHM FOR FAST FOURIER-TRANSFORM ON TRANSPUTER ARRAYS
    PURUSHOTHAM, J
    BASU, A
    KULKARNI, D
    PATNAIK, LM
    COMPUTERS & ELECTRICAL ENGINEERING, 1994, 20 (04) : 319 - 326
  • [29] PARALLEL ALGORITHMS AND ARCHITECTURES BASED ON PIPELINED OPTICAL BUSES
    GUO, ZC
    CAULFIELD, HJ
    APPLIED OPTICS, 1995, 34 (35): : 8116 - 8124
  • [30] Parallel sorting on the biswapped network
    Wei, Wenhong
    Xiao, Wenjun
    Zhang, Zhen
    7TH IEEE/ACIS INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCE IN CONJUNCTION WITH 2ND IEEE/ACIS INTERNATIONAL WORKSHOP ON E-ACTIVITY, PROCEEDINGS, 2008, : 439 - 443