research-article

Job Scheduling is More Important than Processor Allocation for Hypercube Computers

Authors:

V. A. Dixit-RadiyaAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 5, Issue 5

Pages 488 - 497

https://doi.org/10.1109/71.282559

Published: 01 May 1994 Publication History

Abstract

Managing computing resources in a hypercube entails two steps. First, a job must bechosen to execute from among those waiting (job scheduling). Next a particular subcubewithin the hypercube must be allocated to that job (processor allocation). Whereasprocessor allocation has been well studied, job scheduling has been largely neglected.The goal of this paper is to compare the roles of processor allocation and job schedulingin achieving good performance on hypercube computers. We show that job schedulinghas far more impact on performance than does processor allocation. We propose a newfamily of scheduling disciplines, called Scan, that have particular performanceadvantages. We show that performance problems that cannot be resolved throughcareful processor allocation can be solved by using Scan job-scheduling disciplines.Although the Scan disciplines carry far less overhead than is incurred by even thesimplest processor allocation strategies, they are far more able to improve performancethan even the most sophisticated strategies. Furthermore, when Scan disciplines areused, the abilities of sophisticated processor allocation strategies to further improveperformance are limited to negligible levels. Consequently, a simple O(n) allocationstrategy can be used in place of these complex strategies.

References

[1]

{1} G. I. Chen and T. H. Lai, "Preemptive scheduling of independent jobs on a hypercube," Inform. Processing Lett., vol. 28, pp. 201-206, 1988.

Digital Library

[2]

{2} G. I. Chen and T. H. Lai, "Scheduling independent jobs on partitionable hypercubes," J. Parallel Distrib. Computing, vol. 12, pp. 74-78, 1991.

Digital Library

[3]

{3} M. S. Chen and K. G. Shin, "Embedment of interacting task modules into a hypercube multiprocessor," Proc. 2nd Hypercube Conf., 1986, pp. 121-129.

[4]

{4} M. S. Chen and K. G. Shin, "Processor allocation in an N-cube multiprocessor using Gray codes," IEEE Trans. Comput., vol. C-36, no. 12, pp. 1396-1407, Dec. 1987.

[5]

{5} F. Douglis and J. Ousterhout, "Transparent process migration: Design alternatives the sprite implementation," Software--Practice Experience, vol. 21, pp. 757-785, Aug. 1991.

Digital Library

[6]

{6} S. Dutt and J. P. Hayes, "Subcube allocation in hypercube computers," IEEE Trans. Comput., vol 40, pp. 341-352, Mar. 1991.

Digital Library

[7]

{7} J. L. Gustafson, "Reevaluating Amdahl's Law," CACM, vol. 31, pp. 532-533, May 1988.

Digital Library

[8]

{8} J. Kim, C. R. Das, and W. Lin, "A top-down processor allocation scheme for hypercube computers," IEEE Trans. Parallel Distrib. Syst., vol. 2, pp. 20-30, Jan. 1991.

Digital Library

[9]

{9} L. Kleinrock, Queueing Systems: Theory, Vol. 1. New York: Wiley, 1975.

[10]

{10} L. Kleinrock, Queueing Systems: Computer Applications, Vol. 2. New York: Wiley, 1976.

[11]

{11} K. C. Knowlton, "A fast storage allocator," Commun. ACM 8, vol. 8, no. 10, pp. 623-625, Oct. 1965.

[12]

{12} D. E. Knuth, The Art of Computer Programming: Fundamental Algorithms , Vol. 1, 2nd ed. Reading, MA: Addison-Wesley, 1973.

[13]

{13} P. Krueger, "Distributed scheduling for a changing environment," Tech. Rep. 780, Ph.D. dissertation, Univ. of Wis.-Madison, 1988.

[14]

{14} S. S. Lavenberg, Computer Performance Modeling Handbook. New York: Academic, 1983.

[15]

{15} S. T. Leutenegger and M. K. Vernon, "The performance of multiprogrammed multiprocessor scheduling policies," Proc. 1990 ACM SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., 1990, pp. 226-236.

[16]

{16} S. Majumdar, D. L. Eager, and R. B. Bunt, "Scheduling in multiprogrammed parallel systems," Proc. ACM SIGMETRICS 1988 1988, pp. 104-113.

[17]

{17} Y. Saad and M. H. Schultz, "Topological properties of hypercube," IEEE Trans. Comput., vol. 37, pp. 867-872, July 1988.

Digital Library

[18]

{18} A. Silberschatz, J. L. Peterson, and P. Galvin, Operating System Concepts , 3rd ed. Reading, MA: Addison-Wesley, 1991.

[19]

{19} T. J. Teorey and T. B. Pinkerton, "A comparative analysis of disk scheduling policies," CACM, vol. 15, no. 3, pp. 177-184, Mar. 1972.

Digital Library

[20]

{20} M. Theimer, K. Lantz, and D. Cheriton, "Preemptable remote execution facilities for the V-system," Proc. 10th ACM Symp. Operating Syst. Principles, 1985, pp. 2-12.

[21]

{21} E. Zayas, "Attacking the process migration bottleneck," Proc. 11th ACM Symp. Operating Syst. Principles, ACM Operating Syst. Rev., vol. 21, no. 5, pp. 13-24, Nov. 1987).

Digital Library

[22]

{22} Y. Zhu and M. Ahuja, "Preemptive job scheduling on a hypercube," Proc. 1990 Int. Conf. Parallel Processing, 1990, pp. 301-304.

[23]

{23} P. Krueger, T.-H. Lai, and V. A. Radiya, "Processor allocation vs. job scheduling on hypercube computers," Proc. 11th Int. Conf. Distrib. Computing Syst., 1991, pp. 394-401.

Cited By

Duque RArbelaez ADíaz J(2018)Online over time processing of combinatorial problemsConstraints10.1007/s10601-018-9287-423:3(310-334)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s10601-018-9287-4
Alsarhan AAbdallah EAljammal A(2017)Competitive Processors Allocation in 2D Mesh Connected Multicomputer NetworksInternational Journal of Grid and High Performance Computing10.4018/IJGHPC.20170401049:2(53-69)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.4018/IJGHPC.2017040104
Deng KSong JRen KIosup AGropp WMatsuoka S(2013)Exploring portfolio scheduling for long-term execution of scientific workloads in IaaS cloudsProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.1145/2503210.2503244(1-12)Online publication date: 17-Nov-2013
https://dl.acm.org/doi/10.1145/2503210.2503244
Show More Cited By

Index Terms

Job Scheduling is More Important than Processor Allocation for Hypercube Computers
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

On Job Scheduling on a Hypercube

The problem of scheduling n independent jobs on an m-dimensional hypercube system to minimize the finish time is studied. Each job J/sub i/, where 1>or=i>or=n, is associated with a dimension d/sub i/ and a processing time t/sub i/, meaning that J/sub i/ ...
Efficient job scheduling in a mesh multicomputer without discrimination against large jobs
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing

Many innovative schemes for allocating jobs to parallel computing systems have been proposed in order to achieve highly utilized parallel computing systems. The schemes have tried to achieve good job response times with little system fragmentation of ...
Job scheduling and processor allocation for grid computing on metacomputers
Special issue: Design and performance of networks for super-, cluster-, and grid-computing: Part II

Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 5, Issue 5

May 1994

114 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1994 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 May 1994

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Duque RArbelaez ADíaz J(2018)Online over time processing of combinatorial problemsConstraints10.1007/s10601-018-9287-423:3(310-334)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s10601-018-9287-4
Alsarhan AAbdallah EAljammal A(2017)Competitive Processors Allocation in 2D Mesh Connected Multicomputer NetworksInternational Journal of Grid and High Performance Computing10.4018/IJGHPC.20170401049:2(53-69)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.4018/IJGHPC.2017040104
Deng KSong JRen KIosup AGropp WMatsuoka S(2013)Exploring portfolio scheduling for long-term execution of scientific workloads in IaaS cloudsProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.1145/2503210.2503244(1-12)Online publication date: 17-Nov-2013
https://dl.acm.org/doi/10.1145/2503210.2503244
Zydek DSelvaraj HBorowik GŁuba T(2011)Energy characteristic of a processor allocator and a network-on-chipInternational Journal of Applied Mathematics and Computer Science10.5555/3063041.306304821:2(385-399)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.5555/3063041.3063048
Bani-Ahmad SJena SKumar RTuruk ADash M(2011)On improved processor allocation in 2D mesh-based multicomputersProceedings of the 2011 International Conference on Communication, Computing & Security10.1145/1947940.1947984(204-209)Online publication date: 12-Feb-2011
https://dl.acm.org/doi/10.1145/1947940.1947984
Bender MBunde DDemaine EFekete SLeung VMeijer HPhillips C(2008)Communication-Aware Processor Allocation for SupercomputersAlgorithmica10.5555/3118763.311908050:2(279-298)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.5555/3118763.3119080
Aridor YDomany TGoldshmidt OKliteynik YShmueli EMoreira J(2008)Multitoroidal Interconnects For Tightly Coupled SupercomputersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2007.111819:1(52-65)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1109/TPDS.2007.1118
Bender MBunde DDemaine EFekete SLeung VMeijer HPhillips C(2005)Communication-aware processor allocation for supercomputersProceedings of the 9th international conference on Algorithms and Data Structures10.1007/11534273_16(169-181)Online publication date: 15-Aug-2005
https://dl.acm.org/doi/10.1007/11534273_16
Seo KKim S(2003)Improving system performance in contiguous processor allocation for mesh-connected parallel systemsJournal of Systems and Software10.1016/S0164-1212(02)00086-967:1(45-54)Online publication date: 15-Jul-2003
https://dl.acm.org/doi/10.1016/S0164-1212%2802%2900086-9
Feitelson D(2002)Workload Modeling for Performance EvaluationPerformance Evaluation of Complex Systems: Techniques and Tools, Performance 2002, Tutorial Lectures10.5555/647414.725164(114-141)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.5555/647414.725164
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents