Task Assignment on Uniform Heterogeneous Multiprocessors
Shelby H. Funk, S. Baruah · 2006
The partitioning of periodic task systems upon uniform multiprocessors is considered. In the partitioned approach to scheduling periodic tasks upon multiprocessors, each task is assigned to a specific processor and all jobs generated by a task are required to execute upon the processor to which the task is assigned. A uniform heterogeneous multiprocessor is a multiprocessor in which each processor has an associated speed - a processor of speed s operating for t units of time will perform s /spl times/ t units of work. Partitioning of periodic task systems requires solving the bin-packing problem, which is known to be intractable (NP-hard in the strong sense). This paper presents methods for finding an approximate utilization bound for partitioned scheduling on uniform heterogeneous multiprocessors.