Multiprocessor scheduling

In computer science, multiprocessor scheduling is an NP-hard optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors m, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?"[1] The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.

Multiprocessor schedulers have to schedule tasks which may or may not be dependent upon one another. For example, take the case of reading user credentials from console, then use it to authenticate, then if authentication is successful display some data on the console. Clearly one task is dependent upon another. This is a clear case of where some kind of ordering exists between the tasks. In fact it is clear that it can be modelled with partial ordering. Then, by definition, the set of tasks constitute a lattice structure.

The general multiprocessor scheduling problem is a generalization of the optimization version of the number partitioning problem, which considers the case of partitioning a set of numbers (jobs) into two equal sets (processors).[2]

Algorithms

A simple, often-used algorithm is the LPT algorithm (Longest Processing Time) which sorts the jobs by their processing time, longest first, and then assigns them to the machine with the earliest end time so far. This algorithm achieves an upper bound of 4/3 - 1/(3m) OPT.[3]

Static versus Dynamic

Multiprocessor scheduling algorithms are static or dynamic. A scheduling algorithm is static if the scheduling decisions as to what computational tasks will be allocated to what processors are made before running the program. An algorithm is dynamic if it is taken at run time. For static scheduling algorithms, a typical approach is to rank the tasks according to their precedence relationships and use a list scheduling technique to schedule them onto the processors.[4]

gollark: It is known.
gollark: Macron is just this plus macros.
gollark: This sounds performant.
gollark: Shouldn't that be a ParserResult or something?
gollark: Nobody will notice.

See also
  • Job shop scheduling, a similar problem for scheduling jobs on machines. Some variants of multiprocessor scheduling and job shop scheduling are equivalent problems.

References
  1. Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. p. 238. ISBN 978-0716710448.
  2. Mertens, Stephan (2006), "The Easiest Hard Problem: Number Partitioning", in Allon Percus; Gabriel Istrate; Cristopher Moore (eds.), Computational complexity and statistical physics, Oxford University Press US, p. 125, arXiv:cond-mat/0310317, Bibcode:2003cond.mat.10317M, ISBN 978-0-19-517737-4
  3. Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131. doi:10.1137/0117039.
  4. Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Static scheduling algorithms for allocating directed task graphs to multiprocessors". ACM Computing Surveys. 31 (4): 406–471. CiteSeerX 10.1.1.322.2295. doi:10.1145/344588.344618. ISSN 0360-0300.
  • A compendium of NP optimization problems. Editors: Pierluigi Crescenzi, and Viggo Kann
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.