Efficient Algorithms for Cyclic Scheduling

Abstract

This work addresses the problem of non-preemptively scheduling a cyclic set of interdependent operations, representing for instance a program loop, when p identical processors are available. For p = 1 we give a simple, efficient, polynomial time algorithm producing optimum results. When p ! 1 the problem becomes NP-hard and a slight modification of our algorithm generates provably close to optimum results. 1 Introduction With advances in hardware technology most of todays high performance computers offer some degree of parallelism. To take advantage of this concurrency, parallel extensions to sequential programming languages have been designed. Such extensions have mostly proved inadequate as they are usually tailored to some underlying parallel architecture and are consequently not portable. On the other hand there is a large amount of sequential applications that the users would like to run on these high performance computers. The high cost of machine specific software developm...