Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism

Publication image

Most systems that support speculative parallelization, like hardware transactional memory (HTM), do not support nested parallelism. This sacrifices substantial parallelism and precludes composing parallel algorithms. And the few HTMs that do support nested parallelism focus on parallelizing at the coarsest (shallowest) levels, incurring large overheads that squander most of their potential.

We present FRACTAL, a new execution model that supports un- ordered and timestamp-ordered nested parallelism. FRACTAL lets programmers seamlessly compose speculative parallel algorithms, and lets the architecture exploit parallelism at all levels. FRACTAL can parallelize a broader range of applications than prior speculative execution models. We design a FRACTAL implementation that extends the Swarm architecture and focuses on parallelizing at the finest (deepest) levels. Our approach sidesteps the issues of nested parallel HTMs and uncovers abundant fine-grain parallelism. As a result, FRACTAL outperforms prior speculative architectures by up to 88× at 256 cores.


Suvinay Subramanian (Massachusetts Institute of Technology)
Mark C. Jeffrey (Massachusetts Institute of Technology)
Maleen Abeydeera (Massachusetts Institute of Technology)
Hyun Ryong Lee (Massachusetts Institute of Technology)
Victor A. Ying (Massachusetts Institute of Technology)
Daniel Sanchez (Massachusetts Institute of Technology)

Publication Date

Research Area

Uploaded Files