Task allocation

How to partition tasks?

• By information sharing.

• By functionality.

• Minimizing resources: number of cores, frequency, energy, etc.

• and many others (e.g fault-tolerance).

These approaches do not aim at schedulability / real-time performance.

Problem

Partitioning problem (bin packing problem)

Given a set of tasks τ = {τ1 , τ2 , ..., τn }, and a multiprocessor platform with m processors,find an assignment from tasks to processors such that each task is assigned to one and only one processor.

Solutions:

• Select a fitness criteria

  • Example: task utilization or task density

• Decide how to sort the tasks (decreasing, increasing, random).

• Decide what is the fitness evaluation method (assignment rejection rule).

• Use a fitting policy to assign tasks to processors:

  • FirstFit, BestFit, WorstFit, NextFit (there are others).

Bin packing heuristics - definitions

The Bin Packing problem

Pack n objects of different size a1, a2, ..., an into the minimum number of bins (containers) of fixed capacity c.

Definitions

	number of bins used by an algorithm A.
	minimum number of bins used by the optimal algorithm.
	Number of bins required for sure by any algorithm.
	Number of bins that cannot be exceeded for sure by any algorithm.

Simple and immediate bounds

Given a set of n items of volume

• No algorithm can use less than
• No algorithm can use more than

“c” is the capacity of each bin.

Optimality implies clairvoyance for online sequences → heuristics.

Partitioning heuristics (some examples)

First fit (FF)	Place each item in the first bin that can contain it.
Best fit (BF)	Place each item in the bin with the smallest empty space.
Worst fit (WF)	Place each item in the used bin with the largest empty space.
Next fit (NF)	Place each item in the same bin as the last item.

First fit

Place each item in the first bin that can contain it.

Best fit

Place each item in the bin with the smallest empty space.

Worst fit

Places each item in the used bin with the largest empty space, otherwise start a new bin.

Next fit

Place each item in the same bin as the last item. If it does not fit, start a new bin.

The performance of each algorithm strongly depends on the input sequence.

However:

NF	has a poor performance since it does not exploit the empty space in the previous bins.
FF	improves the performance by exploiting the empty space available in all the used bins.
BF	tends to fill the used bins as much as possible.
WF	tends to balance the load among the used bins.

First Fit Decreasing

In this case, sorting tasks by decreasing execution times would allow for minimizing the number of bins.

Some theoretical results

Theoretical results.

• Any online algorithm uses at least 4/3 times the optimal number of bins:
• NF and WF never use more than 2 · M0 bins.

• FF and BF never use more than (1.7 · M0 + 1) bins.

• FFD never uses more than ( 4/3 M0 + 1) bins.

• FFD never uses more than ( 11/9 M0 + 4) bins.

Some utilization bounds

• Any task set with total utilization is schedulable in a multiprocessor made up of m processors using FF allocation and EDF scheduling on each processor.(Lopez-Diaz-Garcia)
• Any task set with total utilization is schedulable in a multiprocessor made up of m processors using FF allocation and RM scheduling on each processor.(Oh and Baker)
• When each task has utilization , the task set is feasible by global RM scheduling if . (Andersson, Baruah, Jonsson)