Parallel Processing Letters · 1994 · 35 citations · 0 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel ComputingSchedulingComputational ComplexityInstruction SchedulingParallel Algorithm DesignPipeline ParallelismResource-constrained SchedulingSchedule OptimizationInstruction Scheduling AlgorithmsNp-hardnessOptimality CriteriaParallel Loop SchedulingParallel SchedulingParallel Scheduling AlgorithmsPipeline SchedulingScheduling In Multiprocessor Systems
This paper addresses the NP-hard problem of scheduling a cyclic set of interdependent operations, representing a program loop, when a finite number of identical pipelined or unpipelined processors are available. We give a simple and efficient algorithm which provably produces close to optimum results. When sufficient processors are available our algorithm guarantees optimality.