Search Results

Documents authored by Imam, Shams

Document
DOI: 10.4230/DARTS.1.1.6
The Eureka Programming Model for Speculative Task Parallelism (Artifact)

Authors: Shams Imam and Vivek Sarkar

Published in: DARTS, Volume 1, Issue 1, Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
This artifact includes a Java-based library implementation of the Eureka programming model (EuPM) that simplifies the expression of speculative parallel tasks. Eureka-style computations are especially well-suited for parallel search and optimization applications. The artifact includes implementations of the eureka patterns that are supported by our Eureka API. These patterns include search, optimization, convergence, N-version programming, and soft real-time deadlines. These different patterns of computations can also be safely combined or nested in the EuPM, along with regular task-parallel constructs, thereby enabling high degrees of composability and reusability. We also include source code of the different benchmarks presented in the paper. The interested reader can use the artifact to experiment with various eureka-style applications and custom Eureka variants in the EuPM.
Cite as

Shams Imam and Vivek Sarkar. The Eureka Programming Model for Speculative Task Parallelism (Artifact). In Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015). Dagstuhl Artifacts Series (DARTS), Volume 1, Issue 1, pp. 6:1-6:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{imam_et_al:DARTS.1.1.6,
  author =	{Imam, Shams and Sarkar, Vivek},
  title =	{{The Eureka Programming Model for Speculative Task Parallelism (Artifact)}},
  pages =	{6:1--6:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2015},
  volume =	{1},
  number =	{1},
  editor =	{Imam, Shams and Sarkar, Vivek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.1.1.6},
  URN =		{urn:nbn:de:0030-drops-55157},
  doi =		{10.4230/DARTS.1.1.6},
  annote =	{Keywords: Async-Finish Model, Delimited Continuations, Eureka Model, Parallel Programming, Speculative Parallelism, Task Cancellation, Task Termination}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2015.421
The Eureka Programming Model for Speculative Task Parallelism

Authors: Shams Imam and Vivek Sarkar

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
In this paper, we describe the Eureka Programming Model (EuPM) that simplifies the expression of speculative parallel tasks, and is especially well suited for parallel search and optimization applications. The focus of this work is to provide a clean semantics for, and efficiently support, such "eureka-style" computations (EuSCs) in general structured task parallel programming models. In EuSCs, a eureka event is a point in a program that announces that a result has been found. A eureka triggered by a speculative task can cause a group of related speculative tasks to become redundant, and enable them to be terminated at well-defined program points. Our approach provides a bound on the additional work done in redundant speculative tasks after such a eureka event occurs. We identify various patterns that are supported by our eureka construct, which include search, optimization, convergence, and soft real-time deadlines. These different patterns of computations can also be safely combined or nested in the EuPM, along with regular task-parallel constructs, thereby enabling high degrees of composability and reusability. As demonstrated by our implementation, the EuPM can also be implemented efficiently. We use a cooperative runtime that uses delimited continuations to manage the termination of redundant tasks and their synchronization at join points. In contrast to current approaches, EuPM obviates the need for cumbersome manual refactoring by the programmer that may (for example) require the insertion of if checks and early return statements in every method in the call chain. Experimental results show that solutions using the EuPM simplify programmability, achieve performance comparable to hand-coded speculative task-based solutions and out-perform non-speculative task-based solutions.
Cite as

Shams Imam and Vivek Sarkar. The Eureka Programming Model for Speculative Task Parallelism. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 421-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{imam_et_al:LIPIcs.ECOOP.2015.421,
  author =	{Imam, Shams and Sarkar, Vivek},
  title =	{{The Eureka Programming Model for Speculative Task Parallelism}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{421--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.421},
  URN =		{urn:nbn:de:0030-drops-52327},
  doi =		{10.4230/LIPIcs.ECOOP.2015.421},
  annote =	{Keywords: Async-Finish Model, Delimited Continuations, Eureka Model, Parallel Programming, Speculative Parallelism, Task Cancellation, Task Termination}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact