  Task-based programming models have become very popular, as they offer an
attractive solution to parallelize serial application code with task and data
annotations. They usually depend on a runtime system that schedules the tasks
to multiple cores in parallel while resolving any data hazards. However,
existing runtime system implementations are not ready to scale well on emerging
manycore processors, as they often rely on centralized structures and/or locks
on shared structures in a cache-coherent memory. We propose design choices,
policies and mechanisms to enhance runtime system scalability for single-chip
processors with hundreds of cores. Based on these concepts, we create and
evaluate Myrmics, a runtime system for a dependency-aware, task-based
programming model on a heterogeneous hardware prototype platform that emulates
a single-chip processor of 8 latency-optimized and 512 throughput-optimized
CPUs. We find that Myrmics scales successfully to hundreds of cores. Compared
to MPI versions of the same benchmarks with hand-tuned message passing, Myrmics
achieves similar scalability with a 10-30% performance overhead, but with less
programming effort. We analyze the scalability of the runtime system in detail
and identify the key factors that contribute to it.
