一种最佳的Mesh中的空闲子网搜索算法  

A Best Algorithm for Searching Free Submesh on Mesh

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

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

出　　处：《系统工程与电子技术》2001年第4期83-86,共4页Systems Engineering and Electronics

基　　金："九五"国防科技预研项目基金资助课题 !(16 1 4 1)

摘　　要：在并行机系统中为了获得系统的高性能 ,对任务进行处理的有效分配是至关重要的 ,这需要用最小的时间开销识别所有的空闲处理机。针对网格多处理机的子网分配 ,提出了一种新的子网搜索算法 ,该算法实现简单 ,时间复杂度为O(N2 a·log2 Na,Na 为已分配子网数 ) ,优于现有的时间复杂度为O(N3a)Efficient allocation of processors for incoming tasks is very important for achieving high performance in parallel computer system. It requires to recognize free available processors with minimum overhead. In this paper, a new algorithm of searching free submesh for submesh allocation on mesh is proposed, it can be realized easily, its time complexity is O(Na2 · log2Na, Na is defined as the number of allocated submesh), which is better than that of previously proposed algorithms, whose time complexity is O(Na3).

关 键 词：并行处理机 空闭子网搜索算法 并行计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP338.6[自动化与计算机技术—计算机科学与技术]