Partitionable multistage interconnection networks. Part 2: Task migration schemes

A new subcube migration scheme for maximally utilizing system resources is proposed for multiprocessor systems based on multistage interconnection networks (MINs). The objective is to migrate tasks to create larger free subcubes; this is referred to as subcube migration. After the migration, we can then apply the more conventional subcube compaction schemes. First, the problem formulation is presented and the goals are set for the solution. It is shown that the migration problem is, in fact, not just a one subcube to one subcube migration problem (as treated in the previous work), but rather a many subcubes to many subcubes migration problem. This problem analysis and formulation lead us to a sophisticated subcube migration scheme. This scheme, thus, successfully handles many-to-many subcube migrations. It is not only near-optimal but also scalable for different sizes of the multiprocessors. Extensive experiments were performed over a wide range of load distributions and problem sizes; the results show that for problems sizes of all practical purposes, the proposed scheme achieves very high system utilization, while requiring little computing time.