Memory Bank Aware Dynamic Loop Scheduling∗

In a parallel system with multiple CPUs, one of the key prob-lems is to assign loop iterations to processors. This problem, known as the loop scheduling problem, has been studied in the past, and several schemes, both static and dynamic, have been pro-posed. One of the attractive features of dynamic schemes, as com-pared to their static counterparts, is their ability of exploiting the latency variations across the execution times of the different loop iterations. In all the dynamic loop scheduling techniques proposed in literature so far, performance has been the primary metric of interest. In a battery-operated embedded execution environment, however, power consumption is another metric to consider dur-ing iteration-to-processor assignment. In particular, in a banked memory system, this assignment can have an important impact on memory power consumption, which can be a significant portion of the overall energy consumption, especially for data-intensive embedded applications such as those from the domain of image data processing. This paper presents a bank aware dynamic loop scheduling scheme for array-intensive embedded media applica-tions. The goal behind this new scheduling scheme is to minimize the number of memory banks that need to be used for executing the current working set (group of loop iterations) when all proces-sors are considered together. That is, during the loop iteration-to-processor assignment, our approach considers the bank access patterns of loop iterations and carefully selects the set of itera-tions to assign to an idle processor so that, if possible, the num-ber of memory banks that are used at the current state is not in-creased. Our experimental results show that the proposed schedul-ing scheme leads to much better energy results when compared to prior loop scheduling techniques and it is also competitive with the scheduler that generates the best performance. To our knowledge, this is the first dynamic loop scheduling scheme that is memory bank aware. 1