×

Idle regulation in non-clairvoyant scheduling of parallel jobs. (English) Zbl 1155.90394

Summary: The optimization of parallel applications is difficult to achieve by classical optimization techniques because of their diversity and the variety of actual parallel and distributed platforms and/or environments. Adaptive algorithmic schemes, capable of dynamically changing the allocation of jobs during the execution to optimize global system behavior, are the best alternatives for solving this problem. In this paper, we focus on non-clairvoyant scheduling of parallel jobs with known resource requirements but unknown running times, with emphasis on the regulation of idle periods in the context of general list policies. We consider a new family of scheduling strategies based on two phases which successively combine sequential and parallel execution of jobs. We generalize known worst-case performance bounds by considering two extra parameters, in addition to the number of processors and maximum processor requirements considered in the literature, namely, job parallelization penalty and idle regulation factor. Furthermore, we prove that under certain conditions of idle regulation, the performance guarantee of parallel job scheduling in space-sharing mode can be improved.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Błażewicz, J.; Drozdowski, M.; Ecker, K., Management of resources in parallel systems, (Bazewicz, J.; Trystram, D.; Plateau, B., Handbook on Parallel and Distributed Processing (2000), Springer Verlag), 263-341
[2] Blayo, E.; Debreu, L.; Mounie, G.; Trystram, D., Dynamic load balancing for adaptive mesh ocean circulation model, Engineering Simulation, 22, 2, 8-23 (2000)
[3] Blazewicz, J.; Ecker, K.; Pesch, E.; Schmidt, G.; Weglarz, J., Scheduling Computer and Manufacturing Processes (2001), Springer Verlag: Springer Verlag Berlin, New York · Zbl 0985.90033
[4] Bharadwaj, V.; Ghose, D.; Mani, V.; Robertazzi, T., Scheduling Divisible Loads in Parallel and Distributed Systems (1996), IEEE Computer Society Press: IEEE Computer Society Press Los Alamos, USA
[5] Brent, R., (Traub., J. F., The Parallel Evaluation of Arithmetic Expressions in Logarithmic Time Complexity of Sequential and Parallel Numerical Algorithms (1973), Academic Press: Academic Press New York), 83-102
[6] Chapin, S.; Cirne, W.; Feitelson, D.; Patton Jones, J.; Leutenegger, S. T.; Schwiegelshohn, U.; Smith, W.; Talby, D., Benchmarks and standards for the evaluation of parallel job Schedulers, (Feitelson, D. G.; Rudolph, L., Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, LNCS, vol. 1659 (1999), Springer-Verlag), 66-89
[7] Decker, T.; Krandick, W., Parallel real root isolation using the Descartes method, (Proceedings of the 6th High Performance Conference (HiPC99). Proceedings of the 6th High Performance Conference (HiPC99), LNCS, vol. 1745 (1999), Springer-Verlag), 261-268
[8] A Downey, A parallel workload model and its implications for processor allocation, in: Proc. the 6th International Symposium of High Performance Distributed Computing, 1997, pp. 112-123; A Downey, A parallel workload model and its implications for processor allocation, in: Proc. the 6th International Symposium of High Performance Distributed Computing, 1997, pp. 112-123
[9] Feitelson, D.; Jette, M., Improved utilisation and responsiveness with gang scheduling, (Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, vol. 1291 (1997), Springer-Verlag: Springer-Verlag Berlin, Germany), 238-261
[10] Feitelson, D.; Rudolph, L., Parallel job scheduling: Issues and approaches, (Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, vol. 949 (1995), Springer-Verlag: Springer-Verlag Berlin, Germany), 1-18
[11] Feitelson, D.; Rudolph, L., Toward convergence in job schedulers for parallel supercomputers, (Feitelson, D.; Rudolph, L., Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, LNCS, vol. 1162 (1996), Springer-Verlag), 1-26
[12] Feitelson, D.; Rudolph, L., Evaluation of design choices for gang scheduling using distributed hierarchical control, Journal of Parallel and Distributed Computing, 35, 18-34 (1996) · Zbl 0855.68006
[13] Feitelson, D.; Rudolph, L., Metrics and benchmarking for parallel job scheduling, (Feitelson, D. G.; Rudolph, L., JSSPP, IPPS/SPDP’98 Workshop. JSSPP, IPPS/SPDP’98 Workshop, Proceedings, LNCS, vol. 1459 (1998), Orlando: Orlando Florida, USA), 1-24
[14] Feitelson, D.; Rudolph, L.; Schweigelshohn, U.; Sevcik, K.; Wong, P., Theory and practice in parallel job scheduling, (Feitelson, D. G.; Rudolph, L., Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, LNCS, vol. 1291 (1997), Springer-Verlag), 1-34
[15] Ghosal, D.; Serazii, G.; Tripathi, S., The processor working set and its use in scheduling multiprocessor system, IEEE Transactions on Software Engineering, 17, 5, 443-453 (1991)
[16] E. Heymann, M Senar, E. Luque, M. Livny, Self-adjusting scheduling of master-worker applications on distributed clusters, in: R. Sakellariou et al. (Eds.), Euro-Par 2001, in: LNCS, vol. 2150, Manchester, UK, 2001, pp. 742-751; E. Heymann, M Senar, E. Luque, M. Livny, Self-adjusting scheduling of master-worker applications on distributed clusters, in: R. Sakellariou et al. (Eds.), Euro-Par 2001, in: LNCS, vol. 2150, Manchester, UK, 2001, pp. 742-751 · Zbl 1005.68678
[17] S. Iyer, P. Druschel, Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O, in: Symposium on Operating Systems Principles, 2001, pp. 117-130; S. Iyer, P. Druschel, Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O, in: Symposium on Operating Systems Principles, 2001, pp. 117-130
[18] Karatza, H., A simulation-based performance analysis of gang scheduling in a distributed system’, (Proc. of the 32nd Annual Simulation Symp. (San Diego, CA, USA, April) (1999), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 26-33
[19] Lloyd, E., Concurrent task systems, Operational Research, 29-1, 189-201 (1981) · Zbl 0463.68053
[20] McCann, C.; Vaswani, R.; Zahorjan, J., A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors, ACM Transactions on Computer System, 11, 2, 146-178 (1993)
[21] Nguyen, T.; Vaswani, R.; Zahorjan, J., Parallel application characterization for multiprocessor scheduling policy design, (Feitelson, D. G.; Rudolph, L., JSSPP. JSSPP, LNCS, vol. 1162 (1996), Springer-Verlag)
[22] Nguyen, T.; Vaswani, R.; Zahorjan, J., Using runtime measured workload characteristics in parallel processor scheduling, (Feitelson, D. G.; Rudolph, L., JSSPP. JSSPP, LNCS, vol. 1162 (1996), Springer-Verlag)
[23] Rosti, E.; Smirni, E.; Serazzi, G.; Dowdy, L., Analysis of non-work-conserving processor partitioning policies, (Feitelson, D.; Rudolph, L., Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, LNCS, vol. 949 (1995), Springer-Verlag), 165-181
[24] Rapine, C.; Scherson, I.; Trystram, D., On-line scheduling of parallelizable jobs, (Proceedings of EUROPAR’98 Conference. Proceedings of EUROPAR’98 Conference, LNCS, vol. 1470 (1998), Springer-Verlag), 322-327
[25] Sgall; Feldmann, A.; Kao, M.; Teng, S., Optimal online scheduling of parallel jobs with dependencies, Journal of Combinatorial Optimization, 1, 4, 393-411 (1998) · Zbl 0897.90126
[26] Sgall, On-line scheduling-A survey, (Fiat, A.; Woeginger, G. J., Online Algorithms: The State of the Art. Online Algorithms: The State of the Art, LNCS, vol. 1442 (1998), Springer-Verlag), 196-231
[27] Silva, F.; Scherson, I., Improving parallel job scheduling using runtime measurements, (Feitelson, D.; Rudolph, L., JSSPP. JSSPP, LNCS, vol. 1911 (2000), Springer-Verlag), 18-39
[28] Sinnen, O.; Sousa, L., Exploiting unused time slots in list scheduling, considering communication contention, (Sakellariou, R., Euro-Par. Euro-Par, LNCS, vol. 2150 (2001), Springer-Verlag), 166-170 · Zbl 1007.68962
[29] Sobalvarro, P.; Weihl, W., Demand based coscheduling of parallel jobs on multiprogrammed multiprocessors, (Job Scheduling Strategies for Parallel Processing. Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, vol. 949 (1995), Springer-Verlag: Springer-Verlag Berlin, Germany), 106-126
[30] Shmoys, D.; Wein, J.; Williamson, D., Scheduling parallel machines on-line, SIAM Journal on Computing, 24, 1313-1331 (1995) · Zbl 0845.68042
[31] A. Tchernykh, D. Trystram, Adaptive strategy for on-line scheduling of real world parallel applications, in: SOCAL’02 Southern California Workshop on Parallel and Distributed Processing and Architecture, Santa Barbara, USA, 2002, pp. 7-8; A. Tchernykh, D. Trystram, Adaptive strategy for on-line scheduling of real world parallel applications, in: SOCAL’02 Southern California Workshop on Parallel and Distributed Processing and Architecture, Santa Barbara, USA, 2002, pp. 7-8
[32] Tchernykh, A.; Trystram, D., On-line scheduling of multiprocessor jobs with idle regulation, (Wyrzykowski, Parallel Processing and Applied Mathematics. Parallel Processing and Applied Mathematics, LNCS, vol. 3019 (2004), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 131-144 · Zbl 1128.68343
[33] Wang, F.; Papaefthymiou, M.; Squillante, M., Performance evaluation of gang scheduling for parallel and distributed systems, (Job Scheduling for Parallel Processing. Job Scheduling for Parallel Processing, LNCS, vol. 1291 (1997), Springer-Verlag: Springer-Verlag Berlin, Germany), 184-195
[34] Tchernykh, A.; Trystram, D.; Rapine, C., Adaptive (a,b,c)-scheme strategy for on-line scheduling, (New Trends in Scheduling in Parallel and Distributed Systems (2001), CIRM: CIRM Luminy, Marseille, France)
[35] Lepere, R.; Mounie, G.; Trystram, D., An approximation algorithm for scheduling trees of malleable tasks, EJOR, 142, 242-249 (2002) · Zbl 1082.90527
[36] Lepere, R.; Mounie, G.; Trystram, D., Malleable tasks: An efficient model for solving actual parallel applications, (PARCO99 (1999), World Scientific)
[37] Graham, R., Bounds on multiprocessor timing anomalies, SIAM Journal on Applied Mathematics, 17, 263-269 (1969)
[38] (Leung, J., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL), 1120
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.