Techniques For The Synthesis Of Multiprocessor Tasksets
P. Emberson, R. Stafford and R.I. Davis
AbstractThe selection of task attributes for empirical evaluations of multiprocessor scheduling algorithms and associated schedulability analyses can greatly affect the results of experiments. Taskset generation algorithms should meet three requirements: efficiency, parameter independence, and lack of bias. Satisfying these requirements enables tasksets to be generated in a moderate amount of time, allows effects of specific parameters to be explored without the problem of confounding variables, and ensures fairness in comparisons between different schedulability analysis techniques. For the uniprocessor case, they are met by the UUniFast algorithm but for multiprocessor systems, where the total desired utilisation is greater than one, UUniFast can produce invalid tasksets. This paper outlines an algorithm, Randfixedsum, for the underlying mathematical problem of efficiently generating uniformly distributed random points whose components have constant sum. This algorithm has been available via a MatLab forum for a number of years; however, this is the first time it has been formally published. This algorithm has direct application to multiprocessor taskset generation. The importance of period generation to experimental evaluation of schedulability tests is also covered.
BibTex Entry
@inproceedings{Emberson2010a,
author = {P. Emberson and R. Stafford and R.I. Davis},
booktitle = {1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS)},
month = {July},
pages = {6--11},
title = {Techniques For The Synthesis Of Multiprocessor Tasksets},
year = {2010}
}