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

摘要

在并行机系统中为了获得系统的高性能，对任务进行处理的有效分配是至关重要的，这需要用最小的时间开销识别所有的空闲处理机。针对网格多处理机的子网分配，提出了一种新的子网搜索算法，该算法实现简单，时间复杂度为O(N2a.log2Na，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(N2a.log2Na, Na is defined as the number of allocated submesh), which is better than that of previously proposed algorithms, whose time complexity is O(N3a).