Modeling multicomputer task allocation as a vector packing problem

This paper considers the problem of task allocation for embedded, bus–based multicomputers. The problem is shown to be isomorphic to a generalization of vector packing, and heuristic solution techniques are investi-gated. A total of 256 packing algorithms are considered, using a divide–and–conquer experimentation strategy on a set of sixteen real and synthetic test cases. Perfor-mance is compared based on the number of processors, the utilization level of the broadcast bus and run time. This research differs from other approaches in that task allocation is formulated as a “multi–dimensional” problem, and general purpose solution techniques are developed that can accommodate arbitrary models for the schedulable resources.