Swing Module Scheduling in GCC

Software pipelining [2] is a scheduling technique intended for loops, and exploits inter-iteration ILP. It produces a new loop kernel in which instructions from different iterations of the loop are scheduled in parallel.

Swing Modulo scheduling (SMS) [1] is a software pipelining implementation. It is implemented in GCC [3] since version 4.0 and can be triggered by using -fmodulo-sched and -fmodulo-sched-allow-regmoves flags.

Our work for the upcoming Linaro release includes supporting SMS for Thumb-2 technology and enhancement for SMS to have it applied on more loops. With this support there is performance improvements of ~20% when running the MP3 decode benchmark in a popular suite on Cortex-A9 with the following flags:

  • -O3 -fmodulo-sched-allow-regmoves -fmodulo-sched -mcpu=cortex-a9 -mtune=cortex-a9 -mthumb

On the autocur benchmark of another popular suite, a known speed-up with SMS was retrieved; showing up to 27% on Cortex A9 with the following flags:

  • -funsafe-loop-optimizations -fmodulo-sched -fno-auto-inc-dec(*) -O3 -mcpu=cortex-a9 -mtune=cortex-a9 -mthumb

(*) I'm preparing a patch to avoid using -fno-auto-inc-dec

References:

  1. J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero. Swing modulo scheduling: A lifetime sensitive approach. In Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques (PACT ’96), pages 80–87, Boston, Massachusetts, USA, October 1996.
  2. M. Lam. Software pipelining: An effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language Design and Implementation.
  3. M. Hagog and A. Zaks. Swing modulo scheduling for GCC. In Proceedings of the GCC Developer Summit 2004, pages 55–64, June 2004. 17

Where to find it

SMS is in trunk and is due to land in the 2011.04 releases of Linaro GCC 4.5 and 4.6

The blueprint is here:

The work was done by:

Work was completed in April 2011.

WorkingGroups/ToolChain/Outputs/GCCSMS (last modified 2011-03-31 01:16:37)