Broadcasting multiple messages in the multiport model

被引：6
作者：
Bar-Noy, A [1 ]
Ho, CT
机构：
[1] Tel Aviv Univ, IL-69978 Tel Aviv, Israel
[2] IBM Corp, Almaden Res Ctr, San Jose, CA 95120 USA
来源：
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1999年 / 10卷 / 05期
关键词：
broadcast; one-to-all broadcast; multiport model; message-passing system; collective communication;
D O I：
10.1109/71.770196
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider the problem of broadcasting multiple messages from one processor to many processors in the k-port model for message-passing systems. In such systems, processors communicate in rounds, where in every round, each processor can send k messages to k processors and receive k messages from k processors. In this paper, we first present a simple and practical algorithm based on variations of k complete k-ary trees. We then present an optimal algorithm up to an additive term of one for this problem for any number of processors, any number of messages, and any value for k.
引用
收藏
页码：500 / 508
页数：9
相关论文
共 18 条
  • [1] THE IBM EXTERNAL USER-INTERFACE FOR SCALABLE PARALLEL SYSTEMS
    BALA, V
    BRUCK, J
    BRYANT, R
    CYPHER, R
    DEJONG, P
    ELUSTONDO, P
    FRYE, D
    HO, A
    HO, CT
    IRWIN, G
    KIPNIS, S
    LAWRENCE, R
    SNIR, M
    [J]. PARALLEL COMPUTING, 1994, 20 (04) : 445 - 462
  • [2] BALA V, 1994, 8 INT PAR PROC S APR, P835
  • [3] Bar-Noy A., 1994, Proceedings. Sixth IEEE Symposium on Parallel and Distributed Processing (Cat. No.94TH0675-9), P216, DOI 10.1109/SPDP.1994.346164
  • [4] DESIGNING BROADCASTING ALGORITHMS IN THE POSTAL MODEL FOR MESSAGE-PASSING SYSTEMS
    BARNOY, A
    KIPNIS, S
    [J]. MATHEMATICAL SYSTEMS THEORY, 1994, 27 (05): : 431 - 452
  • [5] BarNoy A, 1997, NETWORKS, V29, P1, DOI 10.1002/(SICI)1097-0037(199701)29:1<1::AID-NET1>3.0.CO
  • [6] 2-P
  • [7] Cidon I., 1988, International Journal of Digital and Analog Cabled Systems, V1, P77, DOI 10.1002/dac.4520010208
  • [8] Cockayne E. J., 1980, P 11 SE C COMB GRAPH, P181
  • [9] DONGARRA J, 1993, MESS PASS INT FOR NO
  • [10] BROADCAST TIME IN COMMUNICATION-NETWORKS
    FARLEY, AM
    [J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1980, 39 (02) : 385 - 390
12