Scalable Dynamic Task Scheduling on Adaptive Many-Core

Abstract

Workloads from autonomous systems project an unprecedented processing demand onto their underlying embedded processors. Workload comprises of an ever-changing mix of multitudes of sequential and parallel tasks. Adaptive many-core processors with their immense yet flexible processing potential are up to the challenge. Adaptive many-core house together tens of base cores capable of forming more complex cores at run-time. Adaptive many-cores, therefore, can accelerate both sequential and parallel tasks whereas non-adaptive many-cores can only accelerate the latter. Adaptive many-cores can also reconfigure themselves to conform to the needs of any workload whereas non-adaptive many-cores - homogeneous or heterogeneous - are inherently limited given their immutable design. The accompanying qualitative schedule is the key to achieving the real potential of an adaptive many-core. The scheduler must move base cores between tasks on the fly to meet the goals of the overlying autonomous system. The scheduler also needs to scale up with the increase in the number of cores in adaptive many-cores without making compromises on the schedule quality. We present a nearoptimal distributed scheduler for maximizing performance on adaptive many-cores. We also introduce an online performance prediction technique for adaptive many-cores that enable the proposed scheduler to operate without any task profiling.