Abstract
Networks of Workstations (NOW) have become important and cost-effective parallel platforms for scientific computations. In practice, a NOW system is heterogeneous and non-dedicated. These two unique factors make scheduling policies on multiprocessor/multicomputer systems unsuitable for NOWs. However, the coscheduling principle is still an important basis for parallel process scheduling in these environments. We propose a new coscheduling algorithm for reducing the number of page faults across a non-dedicated cluster by increasing the execution priority of parallel tasks with lower page fault rate. Our method is based on knowledge of events obtained during execution, as communication activity and memory size of every task. The performance of our proposal has been analyzed and compared with other coscheduling implementations by means of simulation.
This workw as supported by the CICYT under contract TIC98-0433
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
D.G. Feitelson, L. Rudolph, U. Schwiegelshohn, K.C. Sevcik and P. Wong. “Theory and Practice in Parallel Job Scheduling”. In Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph (eds), Lecture Notes in Computer Science, Vol. 1291, 1997.
S. Setia, M.S. Squillante and V.K. Naik. “The Impact of Job Memory Requirements on Gang-Scheduling Performance”. In Performance Evaluation Review, March 1999.
D. Burger, R. Hyder, B. Miller and D. Wood. “Paging Tradeo.s in Distributed Shared-Memory Multiprocessors”. Journal of Supercomputing, vol. 10, pp.87–104, 1996.
M. Bach. “The Design of the UNIX Operating System’. Prentice-Hall International Editions, 1986.
T. Anderson, D. Culler, D. Patterson and the Now team.“ A case for NOW (Networks of Workstations)”. IEEE Micro, 1995.
M. Litzkow, M. Livny and M. Mutka.“ Condor-A Hunter of Idle Workstations”. 8th Int’l Conference of Distributed Computing Systems, 1988.
S. Russ, J. Robinson, B. Flachs and B. Heckel. “The Hector Distributed Run-Time Environment”. IEEE trans. on Parallel and Distributed Systems, Vol.9 (11). 1988.
A.C. Dusseau, R.H. Arpaci and D.E. Culler. “Effective Distributed Scheduling of Parallel Workloads”. ACM SIGMETRICS’96, 1996.
M. Crovella et al. “Multiprogramming on Multiprocessors”. 3rd IEEE Symposium on Parallel and Distributed Processing, 1994.
R.H. Arpaci, A.C. Dusseau, A.M. Vahdat, L.T. Liu, T.E. Anderson and D.A. Patterson. “The Interaction of Parallel and Sequential Workloads on a Network of Workstations”.ACM SIGMETRICS’95, 1995.
D.G. Feitelson. “Memory Usage in the LANL CM-5 Workload”. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, vol. 1291, pp. 78–84, 1997.
J.K. Ousterhout. “Scheduling Techniques for Concurrent Systems.” In 3rd. Intl. Conf. Distributed Computing Systems, pp.22–30, 1982.
F. Petrini and W. Feng. “Buffered Coscheduling: A New Methodology for Multitasking Parallel Jobs on Distributed Systems”. International Parallel & Distributed Processing Symposium, Cancun, 2000.
P.G. Sobalvarro and W.E. Weihl. “Demand-based Coscheduling of Parallel Jobs on Multiprogrammed Multiprocessors”. IPPS’95 Workshop on Job Scheduling Strategies for Parallel Processing, 1995.
P.G. Sobalvarro, S. Pakin, W.E. Weihl and A.A. Chien. “Dynamic Coscheduling on Workstation Clusters”. IPPS’98 Workshop on Job Scheduling Strategies for Parallel Processing, 1998.
F. Solsona, F. Giné, P. Hernández and E. Luque. “Implementing Explicit and Implicit Coscheduling in a PVM Environment”. 6th International Euro-Par Conference (Europar’2000), Lecture Notes in Computer Science, vol. 1900, 2000.
F. Solsona, F. Giné, P. Hernández and E. Luque. “Predictive Coscheduling Implementation in a non-dedicated Linux Cluster”. To appear in 7th International Euro-Par Conference (Europar’2001), August 2001.
S. Setia. “The Interaction between Memory Allocation and Adaptive Partitioning in Message Passing Multicomputers”. In IPPS Job Scheduling Workshop, Apr. 1995.
E. Parsons and K. Sevcik. “Coordinated Allocation of Memory and Processors in Multiprocessors”. In Proc. ACM Sigmetrics/Performance’96, pp. 57–67, May 1996.
W. Leinberger, G. Karypis and V. Kumar. “Gang Scheduling for Distributed Memory Systems”. 6th International Euro-Par Conference (Europar’2000), Lecture Notes in Computer Science, vol. 1900, 2000.
A. Batat and D. G. Feitelson. “Gang Scheduling with Memory Considerations”. Intl. Parallel and Distributed Processing Symposium, pp. 109–114, May 2000.
A.C. Arpaci-Dusseau, D.E. Culler and A.M. Mainwaring. “Scheduling with Implicit Information in Distributed Systems”. ACM SIGMETRICS’98, 1998.
F. Solsona, F. Giné, P. Hernández and E. Luque. “CMC: A Coscheduling Model for non-Dedicated Cluster Computing”. IPDPS’2001, April 2001.
P.J. Denning. “Working Sets Past and Present”. IEEE Transactions on Software Engineering, vol. SE-6, No 1, January 1980.
M. Becket al. “LINUX Kernel Internals”. Addison-Wesley, 1996.
L. Kleinrock. “Queuing Systems”. John Wiley and Sons, 1976.
D. Feitelson and B. Nitzberg. “Job Characteristics of a Production Parallel Scientific Workload on the NASA Ames IPSC/860”. In Proceedings of the IPPS’95 Workshop on Job Scheduling Strategies for Parallel Processing, pp. 215–227, April 1997.
K.Y. Wang and D.C. Marinescu. “Correlation of the Paging Activity of Individual Node Programs in the SPMD Execution Model”. In 28th Hawaii Intl. Conf. System Sciences, vol. I, pp. 61–71, Jan 1995.
V.G.J. Peris, M.S. Squillante and V.K. Naik. “Analysis of the Impact of Memory in Distributed Parallel Processing Systems”. In Proceedings of ACM SIGMETRICS Conference, pp. 158–170, May 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giné, F., Solsona, F., Hernández, P., Luque, E. (2001). Coscheduling under Memory Constraints in a NOW Environment. In: Feitelson, D.G., Rudolph, L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2001. Lecture Notes in Computer Science, vol 2221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45540-X_4
Download citation
DOI: https://doi.org/10.1007/3-540-45540-X_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42817-6
Online ISBN: 978-3-540-45540-0
eBook Packages: Springer Book Archive