网格多处理机的一种改进的子网分配算法  

An Improved Submesh Allocation Scheme for Mesh Multicomputers

作　　者：张艳[1] 孙世新[1] 彭文钦[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都610054

出　　处：《软件学报》2001年第8期1250-1257,共8页Journal of Software

基　　金：国家"九五"国防预研基金资助项目 (16 .1.4.1)&&

摘　　要：子网分配问题是指识别并分配一个空闲的、满足指定大小要求的节点机 .首先 ,提出了网格结构中一种新的具有 O(N2a· log2 Na)时间复杂度的空闲子网搜索算法 ,它优于现有的 O(N3a)时间复杂度的搜索算法 .然后 ,用该算法对基于保留因子的最佳匹配类子网分配算法—— RF(reservation factor)算法进行了改进 。The submesh allocation problem is to recognize and allocate a free submesh that can accommodate a request for a submesh of a specified size. Firstly, a new algorithm of searching free submesh for mesh multicomputers is proposed, which time complexity is O(N 2 a·log 2N a), better than those existed algorithms whose time complexity are O(N 3 a) . Then this new algorithm is used to improve the best fit allocation scheme which is based on reservation factor--RF scheme, and the result is better than it.

关 键 词：空闲子网 子网分配算法 网格多处理机 计算机网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]