Techniques For The Synthesis Of Multiprocessor Tasksets

P. Emberson, R. Stafford, R.I. Davis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The 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.
Original languageEnglish
Title of host publicationWATERS workshop at the Euromicro Conference on Real-Time Systems
Publication statusPublished - Jul 2010
Event1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems - Brussels, Belgium
Duration: 6 Jul 2010 → …


Conference1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems
Period6/07/10 → …


  • real-time
  • multiprocessor
  • scheduling
  • task set generation
  • unbiased
  • multicore
  • schedulability analysis

Cite this