Optimal scheduling algorithms for software-defined radio pipelined and replicated task chains on multicore architectures

Software-Defined Radio (SDR) represents a move from dedicated hardware to software implementations of digital communication standards. This approach offers flexibility, shorter time to market, maintainability, and lower costs, but it requires an optimized distribution tasks in order to meet performance requirements. Thus, we study the problem of scheduling SDR linear task chains of stateless and stateful tasks for streaming processing. We model this problem as a pipelined workflow scheduling problem based on pipelined and replicated parallelism on homogeneous resources. We propose an optimal dynamic programming solution and an optimal greedy algorithm named OTAC for maximizing throughput while also minimizing resource utilization. Moreover, the optimality of the proposed scheduling algorithm is proved. We evaluate our solutions and compare their execution times and schedules to other algorithms using synthetic task chains and an implementation of the DVB-S2 communication standard on the AFF3CT SDR Domain Specific Language. Our results demonstrate how OTAC quickly finds optimal schedules, leading consistently to better results than other algorithms, or equivalent results with fewer resources. • A formulation of a throughput optimization problem for linear streaming task chains in Software-Defined Radio (SDR). • An optimal dynamic programming solution with its proof of optimality, and possible optimizations. • A faster and optimal algorithm named OTAC with its proof of optimality. • An evaluation of the schedule obtained with OTAC for synthetic chains. • An evaluation of the performance of the DVB-S2 standard, scheduled with OTAC, on the AFF3CT SDR Domain Specific Language running on the StreamPU runtime system.