20 research outputs found
Determinacy Race Detector for Promises (Artifact)
No full textMuch of the past work on dynamic data-race and determinacy-race detection algorithms for task parallelism has focused on structured parallelism with fork-join constructs and, more recently, with future constructs. This paper addresses the problem of dynamic detection of data-races and determinacy-races in task-parallel programs with promises, which are more general than fork-join constructs and futures.
We have introduced a dynamic data race detector, DRDP, to help examine task-parallelism programs with promises. DRDP is designed for the HCLIB parallel programming model and capable of pinpointing data races in a HCLIB program. In this artifact, we provide the race detector implementation and all benchmarks to help reproduce the reported results in the paper
Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises
No full textMuch of the past work on dynamic data-race and determinacy-race detection algorithms for task parallelism has focused on structured parallelism with fork-join constructs and, more recently, with future constructs. This paper addresses the problem of dynamic detection of data-races and determinacy-races in task-parallel programs with promises, which are more general than fork-join constructs and futures. The motivation for our work is twofold. First, promises have now become a mainstream synchronization construct, with their inclusion in multiple languages, including C++, JavaScript, and Java. Second, past work on dynamic data-race and determinacy-race detection for task-parallel programs does not apply to programs with promises, thereby identifying a vital need for this work.
This paper makes multiple contributions. First, we introduce a featherweight programming language that captures the semantics of task-parallel programs with promises and provides a basis for formally defining determinacy using our semantics. This definition subsumes functional determinacy (same output for same input) and structural determinacy (same computation graph for same input). The main theoretical result shows that the absence of data races is sufficient to guarantee determinacy with both properties. We are unaware of any prior work that established this result for task-parallel programs with promises. Next, we introduce a new Dynamic Race Detector for Promises that we call DRDP. DRDP is the first known race detection algorithm that executes a task-parallel program sequentially without requiring the serial-projection property; this is a critical requirement since programs with promises do not satisfy the serial-projection property in general. Finally, the paper includes experimental results obtained from an implementation of DRDP. The results show that, with some important optimizations introduced in our work, the space and time overheads of DRDP are comparable to those of more restrictive race detection algorithms from past work. To the best of our knowledge, DRDP is the first determinacy race detector for task-parallel programs with promises
Data Race Detection for Event-Driven Parallel Runtime Systems
No full textEvent-Driven Parallel (EDP) runtime systems (or more simply, EDP runtimes) are growing in popularity in the high-performance computing area because they provide a promising foundation for new programming systems that can support heterogeneous architectures and ever-increasing hardware complexity. EDP runtimes allow the programmer to focus on program logic, such as control and data dependences, thereby enabling portability across a wide range of platforms and system configurations. However, the applications written on top of EDP runtimes remain vulnerable
to data races. Existing data race detection tools either do not support the primitives in EDP runtimes, or incur intractable large overheads by failing to utilize the structural information available in event-driven programs. In this dissertation, we propose a graph-traversal based data race detection method for EDP runtimes. It
introduces a reachability graph (encodes the dependences in a program), to check the happens-before relation between memory accesses. In order to reduce the time complexity for race detection, we propose a few optimizations, such as reachability cache and reversed reachability graph to avoid unnecessary graph traversals and path compression to reduce the number of steps performed for graph traversal. Based on our race detection technique, we have developed a prototype implementation for the Open Community Runtime (OCR). Our evaluation on a set of open source OCR benchmarks shows that our tool handles all OCR constructs, and that the time overhead for race detection is comparable to that of past work on race detection for more constrained (e.g., fork-join) runimes
Prediction of estimated time of arrival for multi-airport systems via “Bubble” mechanism
No full textPredicting Estimated Time of Arrival (ETA) for a Multi-Airport System (MAS) is much more challenging than for a single airport system because of complex air route structure, dense air traffic volume and vagaries of traffic conditions in an MAS. In this work, we propose a novel “Bubble” mechanism to accurately predict medium-term ETA for a Multi-Airport System (MAS), in which the prediction of travel time of an origin–destination (OD) pair is decomposed into two stages, termed as out-MAS and in-MAS stages. For the out-MAS stage, Auto-Regressive Integrated Moving Average (ARIMA) is used to predict the travel time of a flight to reach the MAS boundary. For the in-MAS stage, we construct new spatio-temporal features based on clustering analysis of trajectory patterns facilitated by a novel data-driven hybrid polar sampling method. A sequence-to-sequence prediction model, Multi-variate Stacked Fully connected Bidirectional Long–Short Term Memory, is further developed to achieve multi-step-ahead predictions of in-MAS travel time for each trajectory pattern using the spatio-temporal features as input. Finally, the medium-term ETA prediction for an MAS is achieved by integrating the out-MAS and in-MAS prediction with the help of trajectory pattern prediction via random forest. A case study of predicting medium-term ETA for a typical MAS in China, Guangdong–Hong Kong–Macao Greater Bay Area, is conducted to demonstrate the usage and promising performance of the proposed method in comparison to several commonly used end-to-end learning methods.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Air Transport & Operation
GT-Race: Graph Traversal Based Data Race Detection for Asynchronous Many-Task Parallelism
No full textARBALEST : Dynamic Detection of Data Mapping Issues in Heterogeneous OpenMP Applications
No full text
A marshalled data format for pointers in relocatable data blocks
No full textAs future computing hardware progresses towards extreme-scale technology, new challenges arise for addressing heterogeneous compute and memory resources, for providing application resilience in the presence of more frequent failures, and for working within strict energy constraints. While C++ has gained popularity in recent years within the HPC community, some concepts of object-oriented program design may be at odds with the techniques we use to address the challenges of extreme-scale computing. In this work, we focus on the challenges related to using aggregate data structures that include pointer values within a programming model where the runtime may frequently relocate data, and traditional serialization techniques are not practical. We propose and evaluate a marshalled encoding for relocatable data blocks, and present a C++ library and other tools to simplify the work of the application programmer developing new applications or porting existing applications to such emerging programming models.</jats:p
