Removal of memory access bottlenecks for scheduling control-flow intensive behavioral descriptions

Application domains like signal and image processing, multimedia and networking protocols involve processing of huge amounts of data stored in memory modules. The behavioral descriptions of these applications may contain a large number of array references for data accesses. Dependencies between array accesses cause bottlenecks in the derivation of high-performance schedules. In this paper, we introduce a scheduling-integrated technique to identify and remove these bottlenecks. We first demonstrate that there is a significant loss in the quality of a schedule if these bottlenecks are not taken into account by the scheduler. We then propose a technique to overcome these bottlenecks by introducing new operations in the schedule called verification operations. Experimental results on several benchmarks show that a scheduler powered by our technique demonstrates a two-fold improvement in performance (measured in terms of the average number of clock cycles) over a recently-introduced scheduler for control-flow intensive behavioral descriptions, called Wavesched. Wavesched itself has a two-fold performance advantage over traditional methods such as path-based scheduling and loop-directed scheduling. Also, the best- and worst-case execution times for the enhanced schedules obtained by our method are usually equal to or much less than the corresponding values for the execution times obtained by previous schedulers.