Loop-Carried Dependencies (LCDs) are ubiquitous in behaviors that describe recurrences. Effective parallelization and scheduling of behaviors involving recurrences is a difficult task but is crucial for several real-time high-performance applications such as DSP. We present a novel approach, Harmonic Scheduling, that exploits the parallelism in these recurrences beyond LCDs and which generates optimal schedules for parallel evaluation of linear difference equations with resource constraints. Based on this approach, we then formulate the problem of and give an algorithm for finding optimal schedules for linear difference equations under more realistic constraints: using a fixed number of adders and multipliers that have different execution times.
['Haigeng Wang', 'Nikil Dutt', 'Alexandru Nicolau']
Harmonic Scheduling: A Technique for Scheduling beyond Loop-Carried Dependencies