×

zbMATH — the first resource for mathematics

Scheduling multiprocessor tasks – An overview. (English) Zbl 0949.68506
Summary: Multiprocessor tasks require more than one processor at the same moment of time. This relatively new concept in scheduling theory emerged with the advent of parallel computing systems. In this work we present the state of the art for multiprocessor task scheduling. We show the rationale behind the concept of multiprocessor tasks. The standard three-field notation is extended to accommodate multiprocessor tasks. The main part of the work is presentation of the results in multiprocessor tasks scheduling both for parallel and for dedicated processors.

MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, M.; Zhu, Y., An O(n log n) feasibility algorithm for preemptive scheduling of n independent jobs on a hypercube, Information processing letters, 35, 7-11, (1990) · Zbl 0704.68052
[2] Atallah, M.J.; Black, C.L.; Marinescu, D.C.; Siegel, H.J.; Casavant, T.L., Models and algorithms for coscheduling compute-intensive tasks on a network of workstations, Journal of parallel and distributed computing, 16, 319-327, (1992) · Zbl 0786.68010
[3] Avizienis, A.; Gilley, G.C.; Mathur, F.P.; Rennels, D.A.; Rohr, J.A.; Rubin, D.K., The STAR (self-testing and repairing) computer: an investigation of the theory and practice of fault-tolerant computer design, IEEE transactions on computers, 20, 11, 1312-1321, (1971) · Zbl 0227.68028
[4] Bharadwaj, V.; Ghose, D.; Mani, V., Optimal sequencing and arrangement in distributed single-level tree networks with communication delays, IEEE transactions on parallel and distributed systems, 5, 9, 968-976, (1994)
[5] Bianco, L.; Błażewicz, J.; Dell’Olmo, P.; Drozdowski, M., Preemptive scheduling of multiprocessor tasks on the dedicated processors system subject to minimal lateness, Information processing letters, 46, 109-113, (1993) · Zbl 0781.90049
[6] Bianco, L. Błażewicz, J., Dell’Olmo, P., and Drozdowski, M., “Linear algorithms for preemptive scheduling of multiprocessor processor tasks subject to minimal lateness”, to appear in Discrete Applied Mathematics.
[7] Bianco, L.; Błażewicz, J.; Dell’Olmo, P.; Drozdowski, M., Scheduling preemptive multiprocessor tasks on dedicated processors, Performance evaluation, 20, 361-371, (1994) · Zbl 0941.68519
[8] Bianco, L.; Błażewicz, J.; Dell’Olmo, P.; Drozdowski, M., Scheduling UET multiprocessor tasks, Foundations of computing and decision sciences, 19, 4, 273-283, (1994) · Zbl 0836.68004
[9] Bianco, L., Błażewicz, J. Dell’Olmo, P., and Drozdowski, M., “Preemptive multiprocessor task scheduling with release times and time windows”, to appear in Annals of Operations Research.
[10] Bianco, L.; Błażewicz, J.; Dell’Olmo, P.; Drozdowski, M., Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors, Annals of operations research, 58, 493-517, (1995) · Zbl 0836.90092
[11] Bianco, L.; Dell’Olmo, P.; Speranza, M.G., Nonpreemptive scheduling of independent tasks with prespecified processor allocations, Naval research logistics quarterly, 41, 959-971, (1994) · Zbl 0833.90065
[12] Bianco, L.; Dell’Olmo, P.; Speranza, M.G., Scheduling independent tasks with multiple modes, Discrete applied mathematics, 62, 35-50, (1995) · Zbl 0837.90064
[13] Błażewicz, J.; Dell’Olmo, P.; Drozdowski, M.; Speranza, M.G.; Błażewicz, J.; Dell’Olmo, P.; Drozdowski, M.; Speranza, M.G., Scheduling multiprocessor tasks on three dedicated processors, Information processing letters, Corrigendum, 49, 269-270, (1994) · Zbl 0788.68011
[14] Błażewicz, J.; Drabowski, M.; Wȩglarz, J., Scheduling multiprocessor tasks to minimize schedule length, IEEE transactions on computers, 35, 5, 389-393, (1986) · Zbl 0604.68040
[15] Błażewicz, J.; Drozdowski, M., Scheduling divisible jobs on hypercubes, Parallel computing, 21, 1945-1956, (1995)
[16] Błażewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, D., Scheduling independent two processor tasks on a uniform duo-processor system, Discrete applied mathematics, 28, 11-20, (1990) · Zbl 0715.90069
[17] Błażewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, D., Scheduling independent multiprocessor tasks on a uniform k-processor system, Parallel computing, 20, 15-28, (1994) · Zbl 0799.68032
[18] Błażewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, D., Scheduling independent multiprocessor tasks on a uniform k-processor system, () · Zbl 0799.68032
[19] Błażewicz, J.; Drozdowski, M.; de Werra, D.; Wȩglarz, J., Deadline scheduling of multiprocessor tasks, Discrete applied mathematics, 65, 81-96, (1996) · Zbl 0854.68005
[20] Błażewicz, J.; Ecker, K., Scheduling multiprocessor tasks under unit resource constraints, (), 161-169
[21] Błażewicz, J.; Ecker, K.; Schmidt, G.; Wȩglarz, J., Scheduling in computer and manufacturing systems, (1993), Springer-Verlag Berlin · Zbl 0767.90033
[22] Błażewicz, J.; Lenstra, J.K.; Rinntooy Kan, A.H.G., Scheduling subject to resource constraints: classification and complexity, Discrete applied mathematics, 5, 11-24, (1983) · Zbl 0516.68037
[23] Błażewicz, J.; Liu, Z., Scheduling multiprocessor tasks with chain constraints, (1995), private communication
[24] Błażewicz, J.; Wȩglarz, J.; Drabowski, M., Scheduling independent 2-processor tasks to minimize schedule length, Information processing letters, 18, 267-273, (1984) · Zbl 0544.68032
[25] Bozoki, G.; Richard, J.-P., A branch-and-bound algorithm for the continuous-process job-shop scheduling problem, AIIE transactions, 2, 3, 246-252, (1970)
[26] Bönniger, T.; Esser, R.; Krekel, D., CM-5, KSR2, paragon XP/S: A comparative description of massively parallel computers, Parallel computing, 21, 199-232, (1995)
[27] Brucker, P., Scheduling algorithms, (1995), Springer-Verlag Berlin · Zbl 0839.90059
[28] Brucker, P.; Krämer, A., Polynomial algorithms for resource constrained and multiprocessor task scheduling problems with a fixed number of task types, (), Reihe P Preprints, Heft 165 · Zbl 0916.90144
[29] Brucker, P.; Krämer, A., Shop scheduling problems with multiprocessor tasks and dedicated processors, Annals of operations research. mathematics of industrial systems I, 57, 13-27, (1995) · Zbl 0831.90071
[30] Chang, R.S.; Lee, R.C.T., On a scheduling problem where a job can be executed only by a limited number of processors, Computers & operations research, 15, 5, 471-478, (1988) · Zbl 0646.90045
[31] Chen, G.-I.; Lai, T.-H., Preemptive scheduling of independent jobs on a hypercube, Information processing letters, 28, 201-206, (1988) · Zbl 0658.68041
[32] Chen, G.-I.; Lai, T.-H., Scheduling independent jobs on partitionable hypercubes, Journal of parallel and distributed computing, 12, 74-78, (1991) · Zbl 0753.68013
[33] Chen, Y.L.; Chin, Y.H., Scheduling unit-time jobs on processors with different capabilities, Computers & operations research, 16, 5, 409-417, (1989) · Zbl 0674.90051
[34] Cheng, Y.C.; Robertazzi, T.G., Distributed computation with communication delay, IEEE transactions on aerospace and electronic systems, 24, 6, 700-712, (1988)
[35] Choundhary, A.N.; Narahari, B.; Nicol, D.M.; Simha, R., Optimal processor assignment for a class of pipelined computations, IEEE transactions on parallel and distributed systems, 5, 4, 439-445, (1994)
[36] Chrétienne, P., Tree scheduling with communication delays, Discrete applied mathematics, 49, 129-141, (1994) · Zbl 0799.90062
[37] ()
[38] Coffman, E.G.; Garey, M.R.; Johnson, D.S.; Lapaugh, A.S., Scheduling file transfers, SIAM journal on computing, 14, 3, 744-780, (1985) · Zbl 0604.68039
[39] Colin, J.Y.; Chrétienne, P., C.P.M. scheduling with small communication delays and task duplication, Operations research, 39, 4, 680-684, (1991) · Zbl 0793.68012
[40] Craig, G.L.; Kime, C.R.; Saluja, K.K., Test scheduling and control for VLSI built-in self-test, IEEE transactions on computers, 37, 9, 1099-1109, (1988)
[41] Dell’Olmo, P.; Speranza, M.G.; Tuza, Z., Easy and hard cases of a scheduling problem on three dedicated processors, (1993), private communication
[42] Dobson, G.; Karmarkar, U.S., Simultaneous resource scheduling to minimize weighted flow times, Operations research, 37, 4, 592-600, (1989) · Zbl 0675.90043
[43] Drozdowski, M., Scheduling multiprocessor tasks on hypercubes, Bulletin of the Polish Academy of sciences. technical sciences, 42, 3, 437-445, (1994) · Zbl 0826.68013
[44] Drozdowski, M., On complexity of multiprocessor tasks scheduling, Bulletin of the Polish Academy of sciences. technical sciences, 43, 3, 381-392, (1995) · Zbl 0844.68019
[45] Drozdowski, M., Real-time scheduling of linear speedup parallel tasks, Information processing letters, 57, 35-40, (1996) · Zbl 0900.68040
[46] Drozdowski, M.; Kubiak, W., Scheduling parallel tasks with sequential heads and tails, (1995), Faculty of Business Administration, Memorial University of Newfoundland, Working Paper · Zbl 0947.68017
[47] Du, J.; Leung, J.Y-T., Complexity of scheduling parallel task systems, SIAM journal on discrete mathematics, 2, 4, 473-487, (1989) · Zbl 0676.90029
[48] Efe, K.; Krishnamoorthy, V., Optimal scheduling of compute-intensive tasks on a network of workstations, IEEE transactions on parallel and distributed systems, 6, 6, 668-673, (1995)
[49] Feitelson, D.G.; Rudolph, L., Gang scheduling performance benefits for fine-grain synchronization, Journal of parallel and distributed computing, 16, 306-318, (1992) · Zbl 0786.68012
[50] Gehringer, E.F.; Siewiorek, D.P.; Segall, Z., Parallel processing: the cm^{∗} experience, (1987), Digital Press Bedford
[51] Goemans, M.X., An approximation algorithm for scheduling on three dedicated processors, Discrete applied mathematics, 61, 49-60, (1995) · Zbl 0831.68006
[52] Graham, R.I.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[53] Hakimi, S.L.; Amin, A.T., Characterization of the connection assignment of diagnosable systems, IEEE transactions on computers, 23, 1, 86-88, (1974) · Zbl 0278.94018
[54] van Hoesel, C.P.M., Preemptive scheduling on a hypercube, () · Zbl 0889.90084
[55] Hoogeveen, J.A.; van de Velde, S.L.; Veltman, B., Complexity of scheduling multiprocessor tasks with prespecified processors allocations, Discrete applied mathematics, 55, 259-272, (1994) · Zbl 0938.68671
[56] Hopkins, A.L.; Lala, J.M.; Smith, T.B., FTMP — A highly reliable fault-tolerant multiprocessor for aircraft, (), 10
[57] Jain, R.; Somalwar, K.; Werth, J.; Browne, J.C., Scheduling parallel I/O operations in multiple bus systems, Journal of parallel and distributed computing, 16, 352-362, (1992) · Zbl 0786.68013
[58] Jansen, K., Scheduling with constrained processor allocation for interval orders, Computers & operations research, 20, 6, 587-595, (1993) · Zbl 0779.90042
[59] Kellerer, H.; Woeginger, G., UET-scheduling with constrained processor allocations, Computers & operations research, 19, 1, 1-8, (1992) · Zbl 0751.90038
[60] Krawczyk, H.; Kubale, M., An approximation algorithm for diagnostic test scheduling in multicomputer systems, IEEE transactions on computers, 34, 9, 869-872, (1985)
[61] Krishnamurti, R.; Ma, E., An approximation algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems, IEEE transactions on computers, 41, 12, 1572-1579, (1992)
[62] Krueger, P.; Lai, T.-H.; Dixit-Radiya, V.A., Job scheduling is more important than processor allocation for hypercube computers, IEEE transactions on parallel and distributed systems, 5, 5, 488-497, (1994)
[63] Kubale, M., The complexity of scheduling independent two-processor tasks on dedicated processors, Information processing letters, 24, 141-147, (1987) · Zbl 0653.68015
[64] Kubale, M., Preemptive scheduling of two-processor tasks on dedicated processors, Zeszyty naukowe politechniki śla̧skiej. seria automatyka, 100, 1082, 145-153, (1990), (in Polish)
[65] Kubale, M., File transfer scheduling within time windows, Zeszyty naukowe politechniki śla̧skiej. seria automatyka, 110, 1176, 69-76, (1992), (in Polish)
[66] Kubale, M., Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors, (1995), private communication · Zbl 0949.68507
[67] Lin, J.F.; Chen, S.J., Scheduling algorithm for nonpreemptive multiprocessor tasks, Computers and mathematics with applications, 28, 4, 85-92, (1994)
[68] Lloyd, E.L., Concurrent task systems, Operations research, 29, 1, 189-201, (1981) · Zbl 0463.68053
[69] Markatos, E.P.; LeBlanc, T.J., Using processor affinity in loop scheduling on shared-memory multiprocessors, IEEE transactions on parallel and distributed systems, 5, 4, 379-400, (1994)
[70] Plehn, J., Preemptive scheduling of independent jobs with release times and deadlines on a hypercube, Information processing letters, 34, 161-166, (1990) · Zbl 0695.68030
[71] Preparata, F.P.; Metze, G.; Chien, R., On the connection assignment problem of diagnosable systems, IEEE transactions on electronic computers, 16, 6, 848-854, (1967) · Zbl 0189.16904
[72] Rayward-Smith, V.J., UET scheduling with interprocessor communication delays, Discrete applied mathematics, 18, 55-71, (1987) · Zbl 0634.90031
[73] Sevcik, K.C., Application scheduling and processor allocation in multiprogrammed parallel processing systems, Performance evaluation, 19, 107-140, (1994) · Zbl 0942.68513
[74] Shen, X.; Reingold, E.M., Scheduling on a hypercube, Information processing letters, 40, 323-328, (1991) · Zbl 0741.68061
[75] Srinivasa Prasanna, G.N.; Musicus, B.R., Generalized multiprocessor scheduling for directed acyclic graphs, (), 237-246
[76] Veltman, B.; Lageweg, B.J.; Lenstra, J.K., Multiprocessor scheduling with communication delays, Parallel computing, 16, 173-182, (1990) · Zbl 0711.68017
[77] Vizing, V.G., About schedules observing deadlines, Kibernetika, 1, 128-135, (1981), (in Russian)
[78] Vizing, V.G., Optimal choice of task execution intensities with a convex penalty function for intensity, Kibernetika, 3, 125-127, (1982), (in Russian)
[79] Vizing, V.G., Minimization of the maximum delay in servicing systems with interruption, U.S.S.R. computational mathematics and mathematical physics, 22, 3, 227-233, (1982) · Zbl 0509.90038
[80] Vizing, V.G.; Komzakowa, L.N.; Tarchenko, A.V., An algorithm for selecting the processing intensity, Kibernetika, 5, 71-74, (1981), (in Russian)
[81] Wang, Q.; Cheng, K.H., List scheduling of parallel tasks, Information processing letters, 37, 291-297, (1991) · Zbl 0724.68013
[82] Wang, Q.; Cheng, K.H., A heuristic of scheduling parallel tasks and its analysis, SIAM journal on computing, 21, 2, 281-294, (1992) · Zbl 0756.90053
[83] Wȩglarz, J., Scheduling under continuous performing speed vs. resource amunt activity models, (), 273-295
[84] Zahorjan, J.; Lazowska, E.D.; Eager, D.L., The effect of scheduling discipline on spin overhead in shared memory parallel systems, IEEE transactions on parallel and distributed systems, 2, 2, 180-198, (1991)
[85] Zhu, Y.; Ahuja, M., On job scheduling on a hypercube, IEEE transactions on parallel and distributed systems, 4, 1, 62-69, (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.