Software Pipelining via Stochastic Search Algorithms

The scheduling of loops for architectures which support instruction level parallelism is an important area of research. Many polynomial time, heuristic algorithms for software pipelining have been proposed for this NPcomplete problem. In this research, genetic algorithms and simulated annealing are used to test the feasibility of applying artificial intelligence techniques to the problem of software pipelining. Both algorithms are iterative search algorithms which adjust their response based on feedback from the fitness function. Results indicate these techniques are superior to deterministic polynomial time algorithms. Key Words: software pipelining, instruction-level parallelism, Petri nets, cyclic scheduling, artificial intelligence, genetic algorithm, simulated annealing. 1 Introduction Frequently code optimization concentrates on loops as loop execution dominates the total execution time of most programs. Software pipelining is a loop optimization technique in which the body of t..