A new approach to processor allocation and task migration in an N-cube multiprocessor

We propose a new strategy to recognize the maximum subcube in an n-cube multiprocessor. This subcube recognition algorithm can be done in both serial and parallel and analyzed. This strategy will enhance the performance drastically so that our algorithm will outperform the buddy system by a factor nCk, the gray strategy by nCk/2 and Al-Dhelaan [8] by nCk/(k(n-k)+1) in cube recognition. We present a very efficient processor allocation strategy which makes larger contiguous spaces for the new coming job than buddy, gray strategy and Al-Dhelaan [8] do. Furthermore, this new strategy is suitable for static as well as dynamic processors allocation and it results in a less fragmentation and higher fault tolerance. Also we describe an efficient procedure for task migration under the new strategy: 1) goal configuration under the new strategy 2) node-mapping between source and destination node 3) the shortest deadlock-free routing algorithm.