Parallel processor scheduling with delay constraints

ABSTRACT

We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on the jobs, and both communication and precedence delays impose relative timing constraints on dependent jobs. The combination of these two types of timing constraints naturally models the instruction scheduling problem that occurs during software compilation for state-of-the-art VLIW (Very Long Instruction Word) processors and multiprocessor parallel machines.

We present the first known polynomial-time algorithm for the case where the precedence constraint graph is a forest of in-trees (or a forest of out-trees), the number of machines m is fixed, and the delays (which are a function of both the job pair and the machines on which they run) are bounded by a constant D.

Our algorithm relies on a new structural theorem for scheduling jobs with arbitrary precedence constraints. Given an instance with many independent dags, the theorem shows how to convert, in linear time, a schedule S for only the largest dags into a complete schedule that is either optimal or has the same makespan as S.

REFERENCES

• 1: David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989 [doi>10.1145/59287.59291]
• 2: P. Chretienne and C. Picouleau. Scheduling with communication delays: A survey. In P. Chretienne, Jr. E. G. Coffman, J. K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, pages 65-90. John Wiley & Sons Ltd, 1995.
• 3: E.G. Coffman, Jr. and R.L. Graham. Optimal sequencing for two-processor systems. Acta Informatica, 1:200-213, 1972.
• 4: Daniel Wayne Engels , Srinivas Devadas, Scheduling for hardware-software partitioning in embedded system design, 2000
• 5: Lucian Finta , Zhen Liu, Single machine scheduling subject to precedence delays, Discrete Applied Mathematics, v.70 n.3, p.247-266, Oct. 8, 1996 [doi>10.1016/0166-218X(96)00110-2]
• 6: Lucian Finta , Zhen Liu , Ioannis Milis , Evripidis Bampis, Scheduling UET-UCT series-parallel graphs on two processors, Theoretical Computer Science, v.162 n.2, p.323-340, Aug. 20, 1996 [doi>10.1016/0304-3975(96)00035-7]
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A Survey. Annals of Discrete Mathematics, 5:287-326, 1979.
• 9: Intel Corporation. The IA-64 Architecture Software Developer's Manual, January 2000.
• 10: H. Jung , L. Kirousis , P. Spirakis, Lower bounds and efficient algorithms for multiprocessor scheduling of dags with communication delays, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.254-264, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72962]
• 11: Jan Karel Lenstra , Marinus Veldhorst , Bart Veltman, The complexity of scheduling trees with communication delays, Journal of Algorithms, v.20 n.1, p.157-173, Jan. 1996 [doi>10.1006/jagm.1996.0007]
• 12: Rolf H. M6hring and Markus W. Schoffter. A simple approximation algorithm for scheduling forests with unit processing times and zero-one communication delays. Technical Report 506, Technische Universitat Berlin, Germany, 1995,
• 13: Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
• 14: C. Picouleau. Etude de problemes les systdmes distrubes. PhD thesis, Univ. Pierre et Madame Curie, Paris, France, 1992.
• 15: Texas Instruments. TMS320C6000 Programmer's Guide, March 2000.
• 16: J.D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384-393, June 1975.
• 17: Theodora A. Varvarigou , Vwani P. Roychowdhury , Thomas Kailath , Eugene Lawler, Scheduling In and Out Forests in the Presence of Communication Delays, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1065-1074, October 1996 [doi>10.1109/71.539738]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sequencing and scheduling

General Terms:
Algorithms, Reliability, Theory, Verification