Global Scheduling Algorithms

Global Scheduling Algorithms are used to improve performance by reducing the execution time or maximizing resource utilization.

1. Trace Scheduling:

In trace scheduling algorithm, we rearrange the instructions along traces (frequently executed paths). This helps in improving the performance of the code.

Goals of Trace Scheduling Algorithm:

• Minimize branch misprediction
• Maximize instruction-level parallelism

2. List Scheduling:

In list scheduling algorithm, the overall execution time of a program can be reduced by rescheduling instructions. They can be rescheduled based on their availability or resource constraints.

Advantage of List Scheduling Algorithm:

• It is a flexible algorithm
• Can handle multiple constraints like resource constraints and instructions latencies
• Used in modern compilers

3. Modulo Scheduling:

In Modulo Scheduling Algorithm, iteration counts must be known in advance. It works by dividing the iterations of loop into groups and schedules instructions from different iterations parallelly. It aims at exploiting parallelism within loops.

4. Software Pipelining:

In this algorithms, loop iterations are overlapped to improve performance and reduce time complexity. It executes multiple loops simultaneously. The main aim of this algorithm is to reduce loop-level parallelism and increase instruction-level parallelism

In the fifth phase of compiler design, code optimization is performed. There are various code optimization techniques. But the order of execution of code in a computer program also matters in code optimization. Global Code Scheduling in compiler design is the process that is performed to rearrange the order of execution of code which improves performance. It comprises the analysis of different code segments and finding out the dependency among them.

The goals of Global Code Scheduling are:

• Optimize the execution order
• Improving the performance
• Reducing the idle time
• Maximize the utilization of resources

There are various techniques to perform Global Code Scheduling:

• Primitive Code Motion
• Upward Code Motion
• Downward Code Motion