ACM Transactions on Programming Languages and Systems · 2001 · 22 citations · 34 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureSchedulingCpu SchedulingInstruction SchedulingInstruction-level ParallelismPipeline ParallelismResource-constrained SchedulingScheduling TheoryInstruction Scheduling AlgorithmsInverse Ackermann FunctionPipeline SchedulingPipelinesPrecedence DiagramsScheduling Under Precedence ConstraintsScheduling With Precedence ConstraintsTime-constrained Scheduling
In this work we investigate the problem of scheduling instructions on idealized microprocessors with multiple pipelines, in the presence of precedence constraints, release-times, deadlines, and latency constraints. A latency of l ij specifies that there must be at least l ij time-steps between the completion time of instruction i and the start time of instruction j . A latency of l ij =−1 can be used to specify that j may be scheduled concurrently with i but not earlier. We present a generic algorithm that runs in O ( n 2 log n α( n )+ ne ) time, given n instructions and e edges in the precedence DAG, where α( n ) is the functional inverse of the Ackermann function. Our algorithm can be used to construct feasible schedules for various classes of instances, including instances with the following configurations: (1) one pipeline, with individual release-times and deadlines and where the latencies between instructions are restricted to 0 and 1; (2) m pipelines, with individual release-times and deadlines, and monotone-interval order precedences; (3) two pipelines with latencies of −1 or 0, and release-times and deadlines; (4) one pipeline, latencies of 0 or 1 and individual processing times that are at least one; (5) m pipelines, intree precedences, constant latencies, and deadlines; (6) m pipelines, outtree precedences, constant latencies, and release-times. For instances with deadlines, optimal schedules that minimize the maximal tardiness can be constructed using binary search, in O (log n ) iterations of our algorithm. We obtain our results using backward scheduling, a very general relaxation method, which extends, unifies, and clarifies many previous results on instruction scheduling for pipelined and parallel machines.
34
NP-complete scheduling problems
Jeffrey D. Ullman · Journal of Computer and System Sciences · 1975 · 1.4K citations
Parallel Sequencing and Assembly Line Problems
T. C. Hu · Operations Research · 1961 · 895 citations
Management, Industrial Engineering, Operations Management +10
Monica S. Lam · ACM SIGPLAN Notices · 2004 · 890 citations
B. Ramakrishna Rau · 1994 · 708 citations · Full text