Scheduling Of Data-Independent Recursive Algorithms

A new scheduling formulation for data independent recursive algorithms is proposed. This formulation is intuitive and finds a static rate optimal schedules. Processing elements may be non-preemptive and non-homogenous. Comparisons with some other common scheduling methods to increase throughput is made. I. INTRODUCTION Today's telecommunication requires a lot of digital signal processing. Many of these algorithms are recursive and data independent, i.e. digital filters, FFT, etc. Common requirements are high throughput, low power, and high integration. Systems using these algorithms are often mobile, forcing the implementation to focus on low power consumption. Efficient scheduling and mapping of operations to hardware is then critical to meet the requirements. The proposed scheduling formulation utilizes dependencies between sample periods, allowing for high throughput and resource utilization. The formulation is suitable both to find rate-optimal schedules as well as high resource ..