Abstract:

Parallelism is critical to achieve high performance in modern computer systems. Unfortunately, most programs scale poorly beyond a few cores, and those that scale well often require heroic implementation efforts. This is because current architectures squander most of the parallelism available in applications and are too hard to program.

I will present Swarm, a new architecture that exploits far more parallelism than conventional multicores and is almost as easy to program as a sequential thread. Swarm programs consist of tiny tasks, as small as tens of instructions each. Synchronization is implicit: the programmer specifies a total or partial order on tasks. This eliminates the correctness pitfalls of explicit synchronization (e.g. deadlock and data races). Swarm hardware uncovers parallelism by speculatively running tasks out of order, even thousands of tasks ahead of the earliest active task. Its speculation mechanisms build on decades of prior work, but Swarm is the first to scale to hundreds of cores due to its new programming model, distributed structures, and distributed protocols. Swarm also incorporates new techniques to reduce data movement, harness nested parallelism, and combine speculative and non-speculative parallelism.

Swarm achieves efficient near-linear scaling to hundreds of cores on challenging irregular applications. These span a broad set of domains, including graph analytics, machine learning, databases, simulation, and more. Swarm even accelerates applications that are often deemed sequential. It outperforms state-of-the-art software-only parallel algorithms by one to two orders of magnitude, and sequential implementations by up to 600x at 256 cores.