A combined compiler and architecture technique to control multithreaded execution of branches and loop iterations

Abstract

Simultaneous Speculation Scheduling (S³) is a combined compiler and architecture technique to control multiple path execution. It can be used for dual path branch speculation in case of unpredictable branches and for multiple path speculative execution of loop iterations in case of loop-carried dependences that make parallel execution otherwise impossible. We apply S³ In situations where purely static techniques cannot prove data independence. S³ can be seen as a cost-effective alternative to purely dynamic speculation techniques. We explain the S³ technique and discuss the requirements on possible target architectures. We further compare S³ to other speculation techniques.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Very long instruction word

    • Serial architectures

      • Complex instruction set computing

      • Reduced instruction set computing

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

• Hardware

  • Emerging technologies

    • Analysis and design of emerging devices and systems

      • Emerging languages and compilers

• Software and its engineering

  • Software notations and tools

    • Compilers

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Multithreading

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making