More Web Proxy on the site http://driver.im/

research-article

Exploiting Fine-Grained Idle Periods in Networks of Workstations

Authors:

Kyung Dong Ryu,

Jeffrey K. HollingsworthAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 11, Issue 7

Pages 683 - 698

https://doi.org/10.1109/71.877793

Published: 01 July 2000 Publication History

Abstract

Studies have shown that for a significant fraction of the time, workstations are idle. In this paper, we present a new scheduling policy called Linger-Longer that exploits the fine-grained availability of workstations to run sequential and parallel jobs. We present a two-level workload characterization study and use it to simulate a cluster of workstations running our new policy. We compare two variations of our policy to two previous policies: Immediate-Eviction and Pause-and-Migrate. Our study shows that the Linger-Longer policy can improve the throughput of foreign jobs on a cluster by 60 percent with only a 0.5 percent slowdown of local jobs. For parallel computing, we show that the Linger-Longer policy outperforms reconfiguration strategies when the processor utilization by the local process is 20 percent or less in both synthetic bulk synchronous and real data-parallel applications.

References

[1]

A. Acharya G. Edjlali and J. Saltz, “The Utility of Exploiting Idle Workstations for Parallel Computation,” Proc. SIGMETRICS '97, pp. 225–236, May 1997.

Digital Library

[2]

A. Acharya and S. Setia, “Availability and Utility of Idle Memory in Workstation Clusters,” Proc. ACM SIGMETRICS, vol. 27, pp. 35–46, June 1999.

Digital Library

[3]

T.E. Anderson D.E. Culler and D.A. Patterson, “A Case for NOW (Networks of Workstations),” IEEE Micro, vol. 15, no. 1, pp. 54–64, 1995.

Digital Library

[4]

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,” Proc. SIGMETRICS, pp. 267–278, May 1995.

Digital Library

[5]

A. Barak O. Laden and Y. Yarom, “The NOW Mosix and Its Preemptive Process Migration Scheme,” Bull. IEEE Technical Committee on Operating Systems and Application Environments, vol. 7, no. 2, pp. 5–11, 1995.

[6]

S.N. Bhatt F.R.K. Chung F.T. Leighton and A.L. Rosenberg, “On Optimal Strategies for Cycle-Stealing in Networks of Workstations,” IEEE Trans. Computers, vol. 46, no. 5, pp. 545–557, 1997.

Digital Library

[7]

J. Casas D.L. Clark P.S. Galbiati R. Konuru S.W. Otto R.M. Prouty and J. Walpole, “MIST: PVM with Transparent Migration and Checkpointing,” Proc. Ann. PVM Users' Group Meeting, May 1995.

[8]

A. Chowdhury L.D. Nicklas S.K. Setia and E.L. White, “Workload Characteristics for Process Migration and Load Balancing,” Proc. ICDCS, pp. 1–7, June 1997.

[9]

R.B. Dannenberg and P.G. Hibbard, “A Butler Process for Resource Sharing on Spice Machines,” ACM Trans. Office Information Systems, vol. 3, no. 3, pp. 234–252.

Digital Library

[10]

A.C. Dusseau R.H. Arpaci and D.E. Culler, “Effective Distributed Scheduling of Parallel Workloads,” Proc. SIGMETIRCS, pp. 25–36, May 1996.

Digital Library

[11]

M. Forum, “MPI: A Message Passing Interface Standard,” Int'l J. Supercomputing Applications, vol. 8, no. 3/4, 1994.

[12]

A. Geist A. Beguelin J. Dongarra W. Jiang R. Manchek and V. Sunderam, PVM: Parallel Virtual Machine. Cambridge, Massachusetts: The MIT Press, 1994.

Digital Library

[13]

A.S. Grimshaw A. Nguyen-Tuong and W.A. Wulf, “Campus-Wide Computing: Early Results Using Legion at the University of Virginia,” J. Supercomputing Applications and High Performance Computing, vol. 11, no. 2, pp. 129–43, 1997.

Digital Library

[14]

M. Harchol-Balter and A.B. Downey, “Exploiting Process Lifetime Distributions for Dynamic Load Balancing,” Proc. SIGMETRICS, pp. 13–24, May 1996.

Digital Library

[15]

P. Keleher, “The Relative Importance of Concurrent Writers and Weak Consistency Models,” Proc. ICDCS, pp. 91–98, May 1996.

Digital Library

[16]

P. Krueger and R. Chawla, “The Stealth Distributed Scheduler,” Proc. Int'l Conf. Distributed Computing Systems (ICDCS), pp. 336–343, May 1991.

[17]

W.E. Leland and T.J. Ott, “Loadbalancing Heuristics and Process Behavior,” Proc. SIGMETRICS, pp. 54–69, May 1986.

Digital Library

[18]

S. Leutenegger and X.H. Sun, “Distributed Computing Feasibility in a Non-dedicated Homogenous Distributed System,” Supercomputing, pp. 143–152, Nov. 1993.

Digital Library

[19]

M. Litzkow M. Livny and M. Mutka, “Condor—A Hunter of Idle Workstations,” Int'l Conf. Distributed Computing Systems, pp. 104–111, June 1988.

[20]

J.C. Mogul and A. Borg, “The Effect of Context Switches on Cache Performance,” Proc. ASPLOS, pp. 75–84, Apr. 1991.

Digital Library

[21]

M.W. Mutka and M. Livny, “The Available Capacity of a Privately Owned Workstation Environment,” Performance Evaluation, vol. 12, pp. 269–284, 1991.

Digital Library

[22]

M.L. Powell and B.P. Miller, “Process Migration in DEMOS/MP,” Proc. SOSP, pp. 110–119, 1983.

Digital Library

[23]

J. Pruyne and M. Livny, “Providing Resource Management Services to Parallel Applications,” Proc. Second Workshop Environments and Tools for Parallel Scientic Computing, SIAM Proc. Series, J. Dongarra and B. Tourancheau, eds., pp. 152–161, 1994.

[24]

S.H. Russ J. Robinson B.K. Flachs and B. Heckel, “The Hector Distributed Run-Time Environment,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 11, pp. 1,102–1,114, 1999.

Digital Library

[25]

K.D. Ryu J.K. Hollingsworth and P. Keleher, “Mechanisms and Policies for Supporting Fine-Grained Cycle Stealing,” Int'l Conf. Supercomputing, pp. 93–100, June 1999.

Digital Library

[26]

G. Stellner, “CoCheck: Checkpointing and Process Migration for MPI,” Proc. Int'l Parallel Processing Symp., pp. 526–531, Apr. 1996.

Digital Library

[27]

M.M. Theimer K.A. Lantz and D.R. Cheriton, “Premptable Remote Execution Facilities for the V-System,” Proc. SOSP, pp. 2–12, Dec. 1985.

Digital Library

[28]

G. Thiel, “Locus Operating System, A Transparent System,” Computer Comm., vol. 14, no. 6, pp. 336–346, 1991.

Digital Library

[29]

K.S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications. Prentice-Hall, 1982.

Digital Library

[30]

S.C. Woo M. Ohara E. Torrie J.P. Singh and A. Gupta, “The SPLASH-2 Programs: Characterization and Methodological Considerations,” Proc. 22nd Ann. Int'l Symp. Computer Architecture, pp. 24–37, 1995.

Digital Library

[31]

E.R. Zayas, “Attacking the Process Migration Bottleneck,” Proc. SOSP, pp. 13–24, 1987.

Digital Library

[32]

S. Zhou X. Zheng J. Wang and P. Delisle, “Utopia: A Load Sharing Facility for Large, Heterogeneous Distributed Computer Systems,” Proc. SPE, vol. 23, no. 12, pp. 1,305–1,336, 1993.

Digital Library

Cited By

Min AWang RTsai JErgin MTai TFeo JFaraboschi PVilla O(2012)Improving energy efficiency for mobile platforms by exploiting low-power sleep statesProceedings of the 9th conference on Computing Frontiers10.1145/2212908.2212928(133-142)Online publication date: 15-May-2012
https://dl.acm.org/doi/10.1145/2212908.2212928
Abawajy J(2009)Adaptive hierarchical scheduling policy for enterprise grid computing systemsJournal of Network and Computer Applications10.1016/j.jnca.2008.04.00932:3(770-779)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.jnca.2008.04.009
Stiehr GChamberlain R(2006)Improving cluster utilization through intelligent processor sharingProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898923(364-364)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898923
Show More Cited By

Index Terms

Recommendations

Resource Policing to Support Fine-Grain Cycle Stealing in Networks of Workstations

This paper presents the design, implementation, and performance evaluation of a suite of resource policing mechanisms that allow guest processes to efficiently and unobtrusively exploit otherwise idle workstation resources. Unlike traditional policies ...
Mechanisms and policies for supporting fine-grained cycle stealing
ICS '99: Proceedings of the 13th international conference on Supercomputing
Guidelines for Data-Parallel Cycle-Stealing in Networks of Workstations

We derive computationally efficient guidelines for nearly optimal scheduling of data-parallel computations within a draconian mode of cycle-stealing in networks of workstations (nows). In this computing regimen, workstation A takes control of ...

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 11, Issue 7

July 2000

144 pages

ISSN:1045-9219

Editor:
John A. Stankovic
Univ. of Virginia, Charlottesville, VA

Issue’s Table of Contents

Copyright © Copyright © 2000 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 July 2000

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Min AWang RTsai JErgin MTai TFeo JFaraboschi PVilla O(2012)Improving energy efficiency for mobile platforms by exploiting low-power sleep statesProceedings of the 9th conference on Computing Frontiers10.1145/2212908.2212928(133-142)Online publication date: 15-May-2012
https://dl.acm.org/doi/10.1145/2212908.2212928
Abawajy J(2009)Adaptive hierarchical scheduling policy for enterprise grid computing systemsJournal of Network and Computer Applications10.1016/j.jnca.2008.04.00932:3(770-779)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.jnca.2008.04.009
Stiehr GChamberlain R(2006)Improving cluster utilization through intelligent processor sharingProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898923(364-364)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898923
Weatherly DLowenthal DNakazawa MLowenthal F(2006)Dyn-MPIJournal of Parallel and Distributed Computing10.1016/j.jpdc.2006.02.00266:6(822-838)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1016/j.jpdc.2006.02.002
Mason RKelly W(2005)G2-P2PProceedings of the 2005 Australasian workshop on Grid computing and e-research - Volume 4410.5555/1082290.1082296(33-39)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/1082290.1082296
Ryu KHollingsworth J(2004)Resource Policing to Support Fine-Grain Cycle Stealing in Networks of WorkstationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2004.5815:10(878-892)Online publication date: 1-Oct-2004
https://dl.acm.org/doi/10.1109/TPDS.2004.58
Ryu KHollingsworth JKeleher PSlocomb C(2001)Efficient network and I/O throttling for fine-grain cycle stealingProceedings of the 2001 ACM/IEEE conference on Supercomputing10.1145/582034.582037(3-3)Online publication date: 10-Nov-2001
https://dl.acm.org/doi/10.1145/582034.582037

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents