Optimización del Código Postpass de las Restricciones de Pipeline

Los interbloqueos de pipeline se usan en una arquitectura con pipelining para prevenir la ejecución de una instrucción de máquina antes de que sus operandos estén disponibles. Una alternativa a esta compleja pieza de hardware es reorganizar las instrucciones en tiempo de compilación para evitar interbloqueos de pipeline. Este problema se llama reorganización de código y se estudia aquí. Se demuestra que el problema básico de reorganización de instrucciones a nivel de máquina en tiempo de compilación es NP-completo. Se propone un algoritmo heurístico y se exploran sus propiedades y efectividad. Se presentan datos empíricos de MIPS, un diseño de procesador VLSI. Se discute el impacto de las técnicas de reorganización de código en el resto de un sistema de compilador.