多端口模式下的多消息广播算法与分析

Algorithm and Analysis of Multiple Messages Broadcast in the Multiport Model

1引言 网络通信一般可分为五类,单播(Unicast)、组播(Multicast)、汇播(Concast)、群播(MultiPointto MultiPoint)和广播(Broadcast).其中,广播通信是实现一点对所有点通信(oneto-all Broadcast)的简便有效形式,在很多并行计算问题,如神经网络、优化、线性代数等问题中的使用非常频繁.

In this paper,we first make a comparison between two kinds of one-to-all broadcast--one message broadcast and multiple messages broadcast. And through simple introduction to a multiple messages broadcast algorithm presented in [1],called k-tree algorithm,in the multiport model,we sum up its basis and model of theory and provide essential proof for theorems. At last,we make a detailed analysis of its time complexity.