A Lightweight Run-time Scheduler for Multitasking Multicore Stream Applications

Abstract — Stream programming models promise dra-matic improvements in developers ’ ability to express par-allelism in their applications while enabling extremely efficient implementations on modern many-core processors. Unfortunately, the wide variation in the architectural fea-tures of available multi-core processors implies that a single compiler may be incapable of generating general solutions which can run on many target systems, or even on different configurations of the same system. In particular, off-line approaches for finding optimal mappings and schedules for a stream program on a specific processor are limited by their lack of portability across different processors, and by a lack of flexibility for run time variations in resource availability in typical multi-tasking environments. The paper presents a scheme that includes a lightweight compile-time sequencer, and a dynamic scheduler capable of mapping stream programs onto available cores in a multi-core processor at run-time. Unlike previous imple-mentations, our scheme requires limited knowledge of the target architecture’s resources at compile time. The off-line portion of the scheme generates canonical scheduling information about the stream program. This information is utilized by the lightweight run-time scheduling algorithm to generate application mappings in linear time based on available resources giving near optimal throughput. Evaluations of schedules generated for twelve streaming benchmarks gives an average of 96 % and 93 % of the theoretical optimum throughput for schedules with up to 4 and 128 cores, respectively. I