FCFS: a novel scheduling policy for tightly-coupled parallel computer systems

ABSTRACT

Tightly-coupled parallel computer systems are available from several vendors. The mechanism for process scheduling employed by virtually all of these systems is preemptive by job priority. This scheme for process scheduling consumes significant processor resources and can result in significant processor contention for the scheduling data structure. In this paper we show that it is possible to reduce the number of job priorities, and at the same time reduce the administrative overhead on the system, without significantly increasing job wait time. Also we show, by four simulation studies, that non-preemptive scheduling mechanisms are just as effective as preemptive techniques when coupled with time slice control and multiprogramming limits. Thus simplified scheduling techniques that require little overhead to prevent processor contention may be employed in a tightly coupled parallel environment without sacrificing either mean response time or the &sgr; of response time.

REFERENCES

• BISW87: J. Biswas ~ J. Browne, Simultanenus update of priority sructures, Proc 1987 Int Conf on Parallel Processing, IBEE Press, New York, (Aug. 1987)
• GOTT83a: A. Gcttlleb, R. C-rishman, C. Kruskal, K. MeAuliff, L. Rudolph and M. Snir, The NYU Ultrscomputer - Designing an MIMD shared memory parallel computer, IEEE Trans on Computers, C-32, 2, (Feb.1983), pp. 175-189
• GOTT83a: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• IBM: OS/VS2 MVS Syatemm Programming Library: Initialization and Tuning Guide, GC28-I029, IBM Corp., Poughkeepsie, NY
• JONES6: Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
• KENA84: Lawrence J. Kenah , Simon F. Bate, VAX/VMS internals and data structures, Digital Press, Newton, MA, 1984
• NI85: L. Ni and C. Wu, Design trade-offs for process synchronization in tightly coupled multiprocessor systems, Proc 1985 l n t Conf on Parallel Processing, IEEE Press, New York, (Aug, 1985), pp. 63-7O
• PLAC86: J. Place, System data structure contention overhead in shared-memory floating control parallel systems. UMKC Tech Report 86-8-1, (1986)
• PLAC87: J. Place ~ A. Goemer, The System Data Structure Contention Problem and A Novel Software Solution - for Shared Memory, Floating Contxol Parallel Systems, Proc NCC '87, 56, Chicago, IL , (June 1987), pp. 109-117

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Measurement, Performance