消息传递并行环境中全文换操作的发送接收序

Sending and Receiving Order of Total-Exchange in Message Passing Parallel System

传统的全交换操作实现未考虑消息的发送接收序对进程阻塞数目的影响 .本文通过理论推导 ,证明其将导致单进程平均阻塞数、单进程最大阻塞数、所有进程平均阻塞数、所有进程最大阻塞数的量级分别为O(logN)、O(N)、O(NlogN)、O(N2 ) ;接着按优化程度提出了三种改进的发送接收序 :任意发送层次接收、单一集中控制、层次多集中控制 ,其中层次多集中控制的后三个参数的量级分别减少至O(logN)、O(N)、O(N)

The traditional implementation of total-exchange does not consider the influence of the sending and receiving operation order,so it would produce many process blockings.The sending and receving order of traditional implementation was analyzed to prove that four metrics such as the average blocking number of single process,the maximum blocking number of single process,the average blocking number of total processes and the maximum blocking number of total processes are respectively O(logN),O(N),O(NlogN),O(N 2).According to the degree of optimization,three improved sending and receiving orders were provided which are respectively named Random-Send-Layered-Receive order,Single-Centralized-Conroller order,Layered-Multiple-Controller order.The Layered-Multiple-Controller order improves the latter three metrics to O(logN),O(N),O(N) respectively.