Scheduling multiprocessor tasks on two parallel processors

Jacek Błażewicz; Paolo Dell'Olmo; Maciej Drozdowski

RAIRO - Operations Research - Recherche Opérationnelle (2002)

  • Volume: 36, Issue: 1, page 37-51
  • ISSN: 0399-0559

Abstract

top
In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.

How to cite

top

Błażewicz, Jacek, Dell'Olmo, Paolo, and Drozdowski, Maciej. "Scheduling multiprocessor tasks on two parallel processors." RAIRO - Operations Research - Recherche Opérationnelle 36.1 (2002): 37-51. <http://eudml.org/doc/244654>.

@article{Błażewicz2002,
abstract = {In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.},
author = {Błażewicz, Jacek, Dell'Olmo, Paolo, Drozdowski, Maciej},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {parallel processing; deterministic scheduling; multiprocessor tasks; coscheduling; gang scheduling; concurrent task systems; scheduling multiprocessor tasks},
language = {eng},
number = {1},
pages = {37-51},
publisher = {EDP-Sciences},
title = {Scheduling multiprocessor tasks on two parallel processors},
url = {http://eudml.org/doc/244654},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Błażewicz, Jacek
AU - Dell'Olmo, Paolo
AU - Drozdowski, Maciej
TI - Scheduling multiprocessor tasks on two parallel processors
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 1
SP - 37
EP - 51
AB - In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.
LA - eng
KW - parallel processing; deterministic scheduling; multiprocessor tasks; coscheduling; gang scheduling; concurrent task systems; scheduling multiprocessor tasks
UR - http://eudml.org/doc/244654
ER -

References

top
  1. [1] P. Baptiste and B. Schieber, Scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness, in Proc. of the VIII Int. Workshop On Project Management and Scheduling (2002) 55-58. Zbl1027.90027
  2. [2] J. Błażewicz, P. Dell’Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors. Inform. Process. Lett. 41 (1992) 275-280. Corrigendum: Inform. Process. Lett. 49 (1994) 269-270. Zbl0788.68011
  3. [3] J. Błażewicz, M. Drabowski and J. Węglarz, Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput. 35 (1986) 389-393. Zbl0604.68040
  4. [4] J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. Węglarz, Scheduling Computer and Manufacturing Processes. Springer-Verlag, Heidelberg (1996). Zbl0911.90201
  5. [5] J. Błażewicz and Z. Liu, Scheduling multiprocessor tasks with chain constraints. Eur. J. Oper. Res. 94 (1996) 231-241. Zbl0949.68505
  6. [6] P. Brucker and A. Krämer, Shop scheduling problems with multiprocessor tasks and dedicated processors. Ann. Oper. Res. 57 (1995) 13-27. Zbl0831.90071MR1344961
  7. [7] P. Brucker, S. Knust, D. Roper and Y. Zinder, Scheduling UET task systems with concurrency on two parallel identical processors. Math. Meth. Oper. Res. 52, 369-387. Zbl1023.90023MR1810421
  8. [8] E.G. Coffman Jr. and R.L. Graham, Optimal scheduling for two-processor systems. Acta Informatica 1 (1972) 200-213. Zbl0248.68023MR334913
  9. [9] E.G. Coffman Jr., M.R. Garey, D.S. Johnson and A.S. Lapaugh, Scheduling file transfers. SIAM J. Comput. 14 (1985) 744-780. Zbl0604.68039MR795943
  10. [10] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9 (1990) 251-280. Zbl0702.65046MR1056627
  11. [11] M. Drozdowski, Scheduling multiprocessor tasks – An overview. Eur. J. Oper. Res. 94 (1996) 215-230. Zbl0949.68506
  12. [12] M. Drozdowski, Selected problems of scheduling tasks in multiprocessor computer systems. Poznań University of Technology Press, Series: Rozprawy, No. 321, Poznań (1997). See also: http://www.cs.put.poznan.pl/~maciejd/txt/h.ps 
  13. [13] J. Du and J.Y-T. Leung, Complexity of scheduling parallel task systems. SIAM J. Discrete Math. 2 (1989) 473-487. Zbl0676.90029MR1018532
  14. [14] M.R. Garey and D.S. Johnson, Scheduling tasks with nonuniform deadlies on two processors. J. ACM 23 (1976) 461-467. Zbl0338.68048MR418894
  15. [15] E.F. Gehringer, D.P. Siewiorek and Z. Segall, Parallel Processing: The Cm * Experience. Digital Press, Bedford (1987). 
  16. [16] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnoy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5 (1979) 287-326. Zbl0411.90044MR558574
  17. [17] J.A. Hoogeveen, S.L. van de Velde and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processors allocations. Discrete Appl. Math. 55 (1994) 259-272. Zbl0938.68671MR1308882
  18. [18] T.C. Hu, Parallel sequencing and assembly line problems. Oper. Res. 9 (1961) 841-848. MR135614
  19. [19] R.M. Karp, Reducibility among combinatorial problems, edited by R.E. Miller and J.W. Thatcher, Complexity of Computer Computation. Plenum Press, New York (1972) 85-104. MR378476
  20. [20] H. Krawczyk and M. Kubale, An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comput. 34 (1985) 869-872. 
  21. [21] M. Kubale, The complexity of scheduling independent two-processor tasks on dedicated processors. Inform. Process. Lett. 24 (1987) 141-147. Zbl0653.68015MR882219
  22. [22] C.Y. Lee and X. Cai, Scheduling multiprocessor tasks without prespecified processor allocations. Private communication (1998). 
  23. [23] E.L. Lloyd, Concurrent task systems. Oper. Res. 29 (1981) 189-201. Zbl0463.68053MR606866
  24. [24] R. McNaughton, Scheduling with deadlines and loss functions. Management Sci. 6 (1959) 1-12. Zbl1047.90504MR110585
  25. [25] R. Muntz and E.G. Coffman Jr., Preemptive scheduling of real time tasks on multiprocessor systems. J. Assoc. Comput. Machinery 17 (1970) 324-338. Zbl0216.49702MR282644
  26. [26] B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communications delays. Parallel Comput. 16 (1990) 173-182. Zbl0711.68017
  27. [27] J. Zahorjan, E.D. Lazowska and D.L. Eager, The effect of scheduling discipline on spin overhead in shared memory parallel systems. IEEE Trans. Parallel Distributed Systems 2 (1991) 180-199. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.