Polynomial-time DP-fair scheduling of Gang Tasks upon m identical processors : LP-based and greedy algorithms.
The project defines a DP-Fair scheduling of Periodic Parallel Tasks. We consider identical processors and Gang Tasks that use simultaneously several processors. The schedule is defined by a pattern that will be used in every slice in the schedule that is delimited by two subsequent task deadlines. Two polynomial-time methods are proposed to define the pattern : an optimal linear programming based approach and an heuristic with a performance guarantee of (2-1/m) on resource augmentation (i.e., processor speedup factor). Both methods are implemented in MATLAB and compared through intensive numerical experiments. All source codes and results are provided.
MATLAB Source codes¶
LP-based optimal method¶
File: GangOPT.zipThree methods have been implemented for defining feasible task subsets (feasible slices in the schedule):
- BruteForce: binary encoding of subsets and brute force enumeration. Computation times are reasonable until n=20.
Related files: BruteForce.m
- Depth First Search: binary encoding of subsets and Depth First Search enumeration. The binary encoding over 64 bits integers of subset limits this approach to n=64.
Related files: binary2vector.m genchild.m DFSbin.m
- Depth First Search2: binary encoding using VPI package (variable precision arithmetic) of subsets and Depth First Search enumeration. No limitation on the number of tasks, but these computations take lot of time. VPI must be installed (to download from MathWork).
Related Files: vpibinary2vector.m genchild2.m DFSvpi.m
Gready heuristic method¶
The heuristic sort the task in non increasing number of required processor and then assign tasks to processors in a gready manner. Related file: GangHeuristic.m
Task utilizations are defined by the Stafford's algorithm (copy included, comes from MathWork). The numnber of used processor for every task is randomly generated using a discrete uniform law.
Experiment.m is the main file for launching all numerical experiments. Depending on the used platform for the numerical experiments, around fo one week of computations is required. These programs use the parallel toolbox for performing parallel computations upon a multicore platform. The other files are PlotXX.m are dedicated to draw figures and ComputeXX.m perform the computations for the XX performance metric.
- Programming Languages: MATLAB