Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 2015
The fast development of parallel computer systems poses a challenge to programming
language design and implementation. On the one hand, simple semantics
are desirable; on the other hand, language implementations are expected to help
programmers fully utilize complex parallel systems. Scripting languages are becoming
popular because of their simplicity, but parallel performance has never
been irrelevant for their design and implementation.
In this thesis, we propose the design and implementation of a deterministic
parallel scripting language. Determinism is an appealing property for parallel programs,
as it simplifies understanding, reasoning and debugging. It is particularly
appealing in scripting languages, where ease of programming is a dominant design
goal. We start by proposing a formal semantic framework for deterministic parallel
programming. We suggest several history-based definitions of determinism,
discuss some of their comparative advantages, prove containment relationships
among them, and identify programming idioms that ensure them.
On top of the proposed formal semantic framework, we discuss the design of
Deterministic Parallel Ruby (DPR), a parallel dialect of the Ruby programming
language. DPR extends Ruby by adding simple deterministic parallel constructs
while giving up on full generality (of conventional parallel programming models).
We introduce the constructs of DPR, and a dynamic determinism checking mechanism
(Tardis) that verifies properties required for determinism. With our DPR
implementation, RB-DPR (RB stand for Rochester-Beijing Institute of Technology),
experimental results confirm that DPR can provide scalable performance
on multicore machines and that the overhead of Tardis is low enough for practical
testing. In particular, Tardis significantly outperforms alternative data-race
detectors with comparable functionality.
We conclude with a discussion of future directions in parallel scripting languages
that are simple to use.
