Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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: R. J. Swan , S. H. Fuller , D. P. Siewiorek, Cm*: a modular, multi-microprocessor, Proceedings of the June 13-16, 1977, national computer conference, June 13-16, 1977, Dallas, Texas [doi>10.1145/1499402.1499515]
• 4: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 5: Robert H. Halstead, Jr. , Stephen A. Ward, The MuNet: A scalable decentralized architecture for parallel computation, Proceedings of the 7th annual symposium on Computer Architecture, p.139-145, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801919]
• 6: Marvin H. Solomon , Raphael A. Finkel, The Roscoe distributed operating system, Proceedings of the seventh ACM symposium on Operating systems principles, p.108-114, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806577]
• 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: John K. Ousterhout , Donald A. Scelza , Pradeep S. Sindhu, Medusa: an experiment in distributed operating system structure, Communications of the ACM, v.23 n.2, p.92-105, Feb. 1980 [doi>10.1145/358818.358823]
• 9: Richard James Swan, The switching structure and addressing architecture of an extensible multiprocessor: cm*., Carnegie Mellon University, Pittsburgh, PA, 1978
• 10: Anita K. Jones , Robert J. Chansler, Jr. , Ivor Durham , Karsten Schwans , Steven R. Vegdahl, StarOS, a multiprocessor operating system for the support of task forces, Proceedings of the seventh ACM symposium on Operating systems principles, p.117-127, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806579]
• 11: Reid Garfield Smith, A framework for problem-solving in a distributed processing environment., Stanford University, Stanford, CA, 1979
• 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: L. D. Wittle , A. M. Van Tilborg, Micros, A Distributed Operating System for Micronet, A Reconfigurable Network Computer, IEEE Transactions on Computers, v.29 n.12, p.1133-1144, December 1980 [doi>10.1109/TC.1980.1675518]
• 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: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 17: Ibid., p. 17.
• 18: Mischa K. Schwartz, Computer Communications Network Design and Analysis, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 19: Herbert Sullivan , Theodore R. Bashkow , David Klappholz, A Large Scale, Homogenous, Fully Distributed Parallel Machine, II, Proceedings of the 4th annual symposium on Computer architecture, p.118-124, March 23-25, 1977 [doi>10.1145/800255.810660]