research-article

Free access

Distributed task force scheduling in multi-microcomputer networks

Authors:

André M. Van Tilborg,

Larry D. WittieAuthors Info & Claims

AFIPS '81: Proceedings of the May 4-7, 1981, national computer conference

Pages 283 - 289

https://doi.org/10.1145/1500412.1500452

Published: 04 May 1981 Publication History

Abstract

Efficient task scheduling techniques are needed for microcomputer networks to be used as general purpose computers. The Wave Scheduling technique, developed for the MICRO-NET network computer, co-schedules groups of related tasks onto available network nodes. Scheduling managers are distributed over a logical control hierarchy. They subdivide requests for groups of free worker nodes and send waves of requests towards the leaves of the control hierarchy, where all workers are located. Because requests from different managers compete for workers, a manager may have to try a few times to schedule a task force. Each task force manager actually requests slightly more workers than it really needs. It computes a request size which minimizes expected scheduling overhead, as measured by total idle time in worker nodes. Using a Markov queueing model, it is shown that Wave Scheduling in a network of microcomputers is almost as efficient as centralized scheduling.

References

[1]

Flynn, M. J. 'Some Computer Organizations and Their Effectiveness', IEEE Trans. on Computers, C-21 (1972), 9, pp. 948--960.

[2]

Wittie, L. D. 'MICRONET: A Reconfigurable Network for Distributed Systems Research', Simulation, Nov. 1978, pp. 145--153.

[3]

Swan, R. J. et al, 'Cm*---A modular, multimicroprocessor', AFIPS Proceedings of the National Computer Conference, (Vol. 46), 1977, pp. 637--644.

Digital Library

[4]

Despain, A. M., and D. A. Patterson. 'X-Tree: A Tree Structured Multiprocessor Computer Architecture', Proc. Fifth Ann. Symp. on Computer Arch., 1978, pp. 144--151.

Digital Library

[5]

Halstead, R. H., and S. A. Ward. 'The MuNet: A Scalable Decentralized Architecture for Parallel Computation', Proc. Seventh Ann. Symp. on Comp. Arch., 1980, pp. 139--145.

Digital Library

[6]

Solomon, M. H., and R. A. Finkel. 'The ROSCOE Distributed Operating System', Proc. Seventh Symp. on Op. Sys. Prin., 1979, pp. 108--114.

Digital Library

[7]

Siewiorek, D. P. 'Process Coordination in Multimicroprocessor Systems', In R. W. Hartenstein and R. Zaks (Eds.), Microarchitecture of Computer Systems., Amsterdam: North-Holland, 1975, pp. 1--8.

[8]

Ousterhout, J. K. et al. 'Medusa: An Experiment in Distributed Operating System Structure', Communications of the Association for Computing Machinery 23, (1980), 2, pp. 92--104.

Digital Library

[9]

Swan, R. J. The Switching Structure and Addressing Architecture of an Extensible Multiprocessor: Cm*, Ph.D. Th., Carnegie-Mellon University, Aug. 1978.

Digital Library

[10]

Jones, A. K. et al. 'StarOS, a Multiprocessor Operating System for the Support of Task Forces', Proc. Seventh Symp. on Op. Sys. Prin., 1979, pp. 117--127.

Digital Library

[11]

Smith, R. G. A Framework for Problem Solving in a Distributed Processing Environment, Ph.D. Th., Stanford University, 1979.

Digital Library

[12]

van Tilborg, A. M. and L. D. Wittie. 'Wave Scheduling: Distributed Allocation of Task Forces in Network Computers', Proceedings of 2nd Int. Conf. on Dist. Comp. Sys., Paris (1981).

[13]

Wittie, L. D. and A. M. van Tilborg. 'MICROS, A Distributed Operating System for MICRONET, A Re-configurable Network Computer', IEEE Trans. on Comp., C-29 (1980), 12, pp. 1153--44.

Digital Library

[14]

van Tilborg, A. M. and L. D. Wittie. 'High-Level Operating System Formation in Network Computers', Proc. 1980 Int. Conf. on Parallel Proc., Aug. 1980, pp. 131--132.

[15]

van Tilborg, A. M. and L. D. Wittie. 'A Concurrent Pascal Operating System for a Network Computer', Proc. IEEE CompSAC '80, 1980, pp. 757--763.

[16]

Kleinrock, L. Queueing Systems Volume I: Theory, New York: Wiley-Interscience, 1975, pp. 94--99.

Digital Library

[17]

Ibid., p. 17.

[18]

Schwartz, M. Computer-Communication Network Design and Analysis, Englewood Cliffs: Prentice-Hall, 1977.

Digital Library

[19]

Sullivan, H. et al. 'A Large Scale, Homogeneous Fully Distributed Parallel Machine, II', Proc. Fourth Ann. Symp. on Comp. Arch., 1977, pp. 118--124.

Digital Library

Cited By

Grunwald DNazief BReed D(1990)Empirical Comparison of Heuristic Load Distribution in Point-to-Point Multicomputer NetworksProceedings of the Fifth Distributed Memory Computing Conference, 1990.10.1109/DMCC.1990.556309(984-993)Online publication date: 1990
https://doi.org/10.1109/DMCC.1990.556309
Wittie LFrank A(1984)A portable modula-2 operating systemProceedings of the July 9-12, 1984, national computer conference and exposition10.1145/1499310.1499347(283-292)Online publication date: 9-Jul-1984
https://dl.acm.org/doi/10.1145/1499310.1499347
Van Tilborg AWittie L(1984)Wave Scheduling Decentralized Scheduling of Task Forces in MulticomputersIEEE Transactions on Computers10.1109/TC.1984.167650033:9(835-844)Online publication date: 1-Sep-1984
https://dl.acm.org/doi/10.1109/TC.1984.1676500
Show More Cited By

Distributed task force scheduling in multi-microcomputer networks
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Scheduling task with state-dependent deadlines
Task Scheduling in Networks

Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research. Most of the research on this problem incorporates the potentially unrealistic assumption that ...
Efficient Compile-Time Task scheduling for Heterogeneous Distributed Computing Systems
ICPADS '06: Proceedings of the 12th International Conference on Parallel and Distributed Systems - Volume 1

Efficient task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems (or HeDCSs). Because of its key importance, several scheduling algorithms have been proposed in the literature, which are mainly for ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

AFIPS '81: Proceedings of the May 4-7, 1981, national computer conference

May 1981

736 pages

ISBN:9781450379212

DOI:10.1145/1500412

Copyright © 1981 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

AFIPS: American Federation of Information Processing Societies

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1981

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)2

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Grunwald DNazief BReed D(1990)Empirical Comparison of Heuristic Load Distribution in Point-to-Point Multicomputer NetworksProceedings of the Fifth Distributed Memory Computing Conference, 1990.10.1109/DMCC.1990.556309(984-993)Online publication date: 1990
https://doi.org/10.1109/DMCC.1990.556309
Wittie LFrank A(1984)A portable modula-2 operating systemProceedings of the July 9-12, 1984, national computer conference and exposition10.1145/1499310.1499347(283-292)Online publication date: 9-Jul-1984
https://dl.acm.org/doi/10.1145/1499310.1499347
Van Tilborg AWittie L(1984)Wave Scheduling Decentralized Scheduling of Task Forces in MulticomputersIEEE Transactions on Computers10.1109/TC.1984.167650033:9(835-844)Online publication date: 1-Sep-1984
https://dl.acm.org/doi/10.1109/TC.1984.1676500
Chuan-Lin Wu Tse-Yun Feng Min-Chang Lin (1982)StarIEEE Transactions on Computers10.1109/TC.1982.167590131:10(923-933)Online publication date: 1-Oct-1982
https://dl.acm.org/doi/10.1109/TC.1982.1675901

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents