In this paper we investigate the benefit of scheduling non-critical loads for a higher latency during software pipelining. "Non-critical" denotes those loads that have sufficient slack in the cyclic data dependence graph so that increasing the scheduling distance to their first use can only increase the number of stages of the software pipeline, but should not increase the lengths of the individual stages, the initiation interval (II). The associated cost is in many cases negligible, but the memory stall reduction due to improved latency coverage and load clustering in the schedule can be considerable.

We present a global instruction scheduler based on integer linear programming (ILP) that was implemented experimentally in the Intel Itaniumreg product compiler. It features virtually the full scale of known EPIC scheduling optimizations, more than its heuristic counterpart in the compiler, GCS, and in contrast to the latter it computes optimal solutions in the form of schedules with minimal length. Due to our highly efficient ILP model it can solve problem instances with 500-750 instructions, and in combination with region scheduling we are able to schedule routines of arbitrary size. In experiments on five SPECreg CPU2006 integer benchmarks, ILP-scheduled code exhibits a 32% schedule length advantage and a 10% runtime speedup over GCS-scheduled code, at the highest compiler optimization levels typically used for SPEC submissions. We further study the impact of different code motion classes, region sizes, and target microarchitectures, gaining insights into the nature of the global instruction scheduling problem.

We consider the problem of scheduling a number of periodic tasks T on a real-time architecture composed of a set of identical processors P connected by a common bus. Each processor p \in P has a certain amount of memory \mu (p). In our setting, a task \tau \in¸ T is specified by the period t(\tau), the memory requirement \mu (\tau), the execution time c(\tau), and the deadline d(\tau). We always assume d (\tau) \leqslant t(\tau). Tasks may communicate with each other by sending messages. We denote the set of messages by M, and for each m \in M, src(m) is the source task of m, dst(m) is the target task of m, l(m) is the length of m, and d(m) is the deadline for m. The problem is to find a mapping \prod\limits_{}{} : T \in P representing an assignment of the tasks to the processors that satisfies timing and resource requirements for both tasks and messages. The problem is known to be NP-hard even if tasks do not communicate with each other [9].

HP and Intel's Itanium processor family (IPF) is considered as one of the most challenging processor architectures to generate code for. During global instruction scheduling, the compiler must balance the use of strongly interdependent techniques like code motion, speculation and predication. A too conservative application of these features can lead to empty execution slots, contrary to the EPIC philosophy. But overuse can cause resource shortage which spoils the benefit. We tackle this problem using integer linear programming (ILP), a proven standard optimization method. Our ILP model comprises global, partial-ready code motion with automated generation of compensation code as well as vital IPF features like control/data speculation and predication. The ILP approach can-with some restrictions-resolve the interdependences between these decisions and deliver the global optimum. This promises a speedup for compute-intensive applications as well as some theoretically funded insights into the potential of the architecture. Experiments with several hot functions from the SPEC benchmarks show substantial improvements: our postpass optimizer reduces the schedule lengths produced by Intel's compiler by about 20-40%. The resulting speedup of these routines is 16% on average.