An efficient submesh allocation strategy for mesh computer systems

A processor allocation strategy is proposed which can apply to any mesh system and recognize submeshes with arbitrary sizes at any location in a mesh system. The proposed strategy allocates a submesh of exactly the size requested by an incoming task, completely avoiding internal fragmentation. Because of its efficient allocation, this strategy exhibits better performance than an earlier allocation strategy based on the buddy principle. An efficient implementation of this strategy is presented. Extensive simulation runs were carried out to collect experimental performance measures of interest under different allocation schemes for comparison