On optimal loop unrolling in two-processor scheduling

In this paper, we study the problem of scheduling loop task graphs onto two processor systems to minimize the exceution time. We use the idea of loop unrolling to uncover dependence among different loop iterations in loop task graphs. The scheduling is divided into two stages: determining an optimal unrolling factor, and constructing an optimal schedule for this unrolling factor. We propose a criterion for optimal loop unrolling for unit-delay task graphs, where the tasks are enclosed in a single loop. Our main theorem presents a useful test for detecting optimal unrolling factors. A scheduling algorithm that employs the concept of optimal loop unrolling is introduced. We also present serial and parallel algorithms to find the best unrolling factor.