Task migration in all-port wormhole-routed 2D mesh multicomputers

In a mesh multicomputer, submeshes are scheduled to perform jobs according to some processor allocation schemes, each job assigned to occupy processors of one submesh with an appropriate size. In order to assign the region for the incoming jobs, a task compaction is needed to produce a larger contiguous free region. The overhead of task compaction is primarily relied on designing an efficient task migration scheme. In this paper, we aim at the 2D mesh multicomputers with supporting wormhole routing in all-port communication model as the target machine. First, a certain and a relieved constraints between two submeshes for task migration are proposed. We next propose two task migration schemes following one of the constraints in 2D mesh multicomputers. We also analyze and discuss the routing phases for task migration. Finally, we compare the proposed task migration schemes via performance analysis.