Serialization Sets: A Dynamic Dependence-Based Parallel Execution Model

Abstract

This paper proposes a new parallel execution model where programmers augment a sequential program with pieces of code called serializers that dynamically map computational operations into serialization sets of dependent operations. The runtime system executes operations in the same serialization set in program order, and may parallelize the execution of operations in different sets. For many types of applications, writing and debugging such programs is significantly easier than using existing parallel programming techniques, and results in deterministic parallel execution.

We describe the API and design of Prometheus, a C++ library that implements the serialization set abstraction through compile-time template instantiation and a runtime support library. We evaluate a set of parallel programs running on the x86_64 and SPARC-V9 ISAs and study their performance on multi-core, symmetric multiprocessor, and ccNUMA parallel machines. We find that parallel execution of programs written with serialization sets achieves performance comparable to traditional parallel execution models.