Name
Abstract | ||
|---|---|---|
Irregular or pointer-based structures such as graphs and trees are commonly used in algorithms dealing with sparse data. Given their reliance on pointers, these algorithms are difficult to analyze and the structure of their memory accesses is obfuscated which makes the extraction of parallelism difficult. In this work, we present a framework that is capable of reasoning about the semantics of the dynamic data footprints of operations to determine their potential overlap. We leverage the knowledge the programmer has about access patterns for the algorithm but is currently unable to express. This knowledge allows our runtime to make either a parallelization decision or throttle concurrency to improve performance in Software Transactional Memories (STMs) [6]. Our framework relies on programmer-supplied predicates that are appropriately evaluated at runtime and utilized to probabilistically assert certain properties about data footprints. We present simple abstractions and a low-overhead runtime to support our framework. We demonstrate our work by parallelizing a graph-coloring benchmark and by improving the transactional performance of benchmarks from the STAMP suite. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2016604.2016638 | Conf. Computing Frontiers |
Keywords | Field | DocType |
software transactional memories,sparse data,transactional performance,certain property,data footprint,access pattern,low-overhead runtime,dynamic data footprint,efficient algorithmic parallelism,graph-coloring benchmark,stamp suite,data-structure semantics,dynamic data,data structure,software transactional memory,graph coloring | Pointer (computer programming),Data structure,Programming language,Programmer,Computer science,Concurrency,Parallel computing,Transactional memory,Theoretical computer science,Dynamic data,Software,Obfuscation | Conference |
Citations | PageRank | References |
1 | 0.35 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Romain Cledat | 1 | 67 | 4.61 |
| Kaushik Ravichandran | 2 | 24 | 2.26 |
| Santosh Pande | 3 | 567 | 59.76 |