Unrolling shape for out-of-order processors

Loop unrolling is today one of the most effective optimizations for modern architectures. To give an analytical model for loop unrolling performance, unrolling shape was proposed. It was applied to in-order processors, and was proved to give an accurate performance model for loop unrolling in term of software pipelining and cache miss alleviation. In this paper, we apply unrolling shape to out-of-order processors. A scheme for calculating PL_OOO, pipelining terms of an unrolled loop by factor l are presented as PL_OOO(l) = {(Nins(l)/F + NOccpy(l))}/l, where Nins(l) is the number of instructions in an unrolled loop by factor l, F the fetch rate of the architecture, NOccpy(l) the number of store instructions scheduled after Nins(l)/F-th cycle. A pipelining term for in-order processors is essential for calculating NOccpy(l). It is to be noted that the scheme for out-of-order processors uses unrolling shape for in-order processors. Experiments show that our scheme is precise in calculating the behaviour of loop unrolling on out-of-order processors. We show that our scheme quantitatively shows the effect of loop unrolling as the one of infinitely unrolled loops on in-order processors. Furthermore, we reveal that the old folklore that the loop unrolling reduces the loop overhead has revived on out-of-order processors as a performance improvement factor as d/dlPL_OOO (Aho et al., 1986).