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

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

作　　者：苗浩[1] 黄刘生[1] 张国义[1] 陈国良[1] 

机构地区：[1]中国科学技术大学高性能计算机中心,安徽合肥230027

出　　处：《电子学报》2004年第12期2109-2112,共4页Acta Electronica Sinica

基　　金：国家 8 63项目 (No .2 0 0 2AA1 0 4 560 );安徽省教育厅重点科研项目 (No .2 0 0 3kj0 4 9zd)

摘　　要：传统的全交换操作实现未考虑消息的发送接收序对进程阻塞数目的影响 .本文通过理论推导 ,证明其将导致单进程平均阻塞数、单进程最大阻塞数、所有进程平均阻塞数、所有进程最大阻塞数的量级分别为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.

关 键 词：消息传递模型 全交换 发送接收序 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]