连接所有处理结点的互连网络是大规模并行计算机中至关重要的组成部分成百上千的结点之间的通信都依赖于该网络选播是其中最基本的通信方式之一单播和广播都是选播的特殊形式选播/广播在MPI标准中还被定义为实现集体通信的基本操作因此研究高效的选播通信算法对提高并行系统的性能具有非常重要的意义现有的大规模并行计算机绝大多数在硬件上都只支持单播通信此时选播必须以软件方式通过发送多个单播消息来实现本文提出了一个通用的软件选播模型为无通道冲突的软件选播指明了研究方向在此基础上在带环立方体网络hexagonal网络和honeycomb网络上分别提出了一个最小时间的无通道冲突的软件选播算法用硬件来实现选播通信可以极大地减小通信时延本文在虫蚀寻径的二维mesh网络上提出了一个基于树的硬件选播算法通过使用相邻寻径器间的握手协议来控制选播树的各个分支的长度从而保证了算法的无死锁性该算法采用mesh网络中单播消息最普遍使用的XY寻径算法因而更加适合于实际的并行系统此外该算法可以适用于任意长度的消息模拟结果表明该算法具有明显的性能优势基于生成树的选播通常不能充分利用网络中的所有通道本文通过构造多棵生成树的方法在二维mesh网络和k元n-立方体网络上分别提出了一个无死锁的选播算法这两个算法可以充分利用所有通道可以支持任意长度的消息而且不需要虚拟通道的支持与现有算法相比这两个算法的性能都有特别显著的提高在要求高可靠性的应用中通信算法必须具有容错能力本文在构造一个覆盖网络中所有健康结点的伪环的基础上提出了一个有效的无死锁的容错选播算法在每条物理通道至多支持两条虚拟通道的情况下该算法可以应用于任何故障网络只要该网络仍然是保持连通的模拟结果表明即使在故障结点很多的情况下该算法的性能下降仍然是最小的