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²_a·log₂N_a), better than those existed algorithms whose time complexity are O(N³_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.