Software Pipelining in a C-Compiler

Abstract

Very long instruction word (VLIW) Prozessoren nutzen instruction level paralellism (ILP) um die Ausführungszeit von Programmen zu verkürzen, indem sie mehrere Operationen zeitgleich verarbeiten. Da das Scheduling, insbesondere die Parallelisierung, ausschließlich vom Compiler durchgeführt wird, sind durchdachte Algorithmen notwendig um die zur Verfügung stehenden Ressourcen effizient zu nutzen.<br />Software pipelining ist eine Technik um ILP in Basic-Block-Schleifen zu erhöhen, indem die Ausführung von aufeinanderfolgenden Iterationen überlappt wird.<br />Die Software-Pipelining-Heuristik, die wir für die LLVM Compiler-Infrastruktur implementiert haben, heißt swing modulo scheduling (SMS).<br />SMS erzeugt dichte Schedules und schafft es die Anzahl der nötigen Register und die Compile-Zeit niedrig zu halten.<br />

Very long instruction word (VLIW) processors exploit instruction level parallelism (ILP) to reduce the execution time of programs by issuing multiple operations in parallel.<br />Since scheduling---especially parallelization---has to be done entirely by the compiler sophisticated algorithms are necessary to utilize the available resources efficiently.<br />Software pipelining is a scheduling technique to increase the ILP in basic block loops by overlapping the execution of consecutive iterations. The software pipelining heuristic we implemented for the LLVM compiler infrastructure is called swing modulo scheduling (SMS).<br />SMS creates dense schedules while keeping register pressure and compile time low.<br />