Accuracy versus Migration Overhead in Multiprocessor Reweighting Algorithms
Aaron Block · 2005
We consider schemes for enacting task share changes—a process called reweighting—on real-time multiprocessor platforms. Our particular focus is reweighting schemes that are deployed in environments in which tasks may frequently request significant share changes. Prior work has shown that fair scheduling algorithms are capable of reweighting tasks with minimal allocation error; this source of error is defined by comparing to an ideal allocation scheme. However, such algorithms do so at the expense of potentially high task-migration overheads. While in theoretical research it is common to ignore migration overheads, they actually constitute an additional source of error. With frequent and significant share changes, task migrations cannot be entirely prevented, if reasonable allocation error is desired. However, partitioning-based schemes that allow occasional reassignments of tasks to processors have the potential of significantly reducing migration costs. On the other hand, such schemes cannot match fair schemes with respect to allocation error, because under partitioning, some share allocations may not be possible. In this paper, we consider the question of whether the lower migration costs of partitioning-based schemes are sufficient to compensate for their greater allocation error. We show that allocation error in such schemes is influenced by several factors. We suggest several approaches for dealing with these factors and compare one of the resulting schemes to a prior fair scheme. Our conclusion is that partitioning-based schemes are capable of providing significantly lower overall error (due to both allocation inaccuracies and migration costs) than fair schemes in the average case. However, partitioning-based schemes are incapable of providing comparable fairness and real-time guarantees. ∗Work supported by NSF grants CCR 0204312, CCR 0309825, and CCR 0408996. The first author was also supported by an NSF fellowship.