Applications of key-value (KV-)storage often exhibit high spatial locality, such as when many data items have identical composite key prefixes. This prevalent access pattern is underused by the ubiquitous LSM design underlying high-throughput KV-stores today.

In this big data era, data structures indexed by strings are the backbone of many systems - key-value stores, computing systems and relational database indexes. Traversing such data structures requires multiple string comparisons. This poster introduces keydomet, a string wrapper that optimizes key comparisons by storing string prefixes as integers and extending the comparison procedure accordingly.

Data versioning and renaming is a technique to enforce true dependencies and eliminate false dependencies in concurrent out-of-order execution. By extending the addressing to memory to support both a location and a version number, the memory system can match loads with the appropriate stores. With multiple versions of data for a single memory location, Write-after-Read and Write-after-Write dependencies are avoided. In this paper, we present architectural support for O-structures, which provide memory versioning and renaming. We describe a microarchitectural implementation of an O-structure in the cache hierarchy of a multicore processor and demonstrate the need of each feature provided by O-structures. Our evaluation shows that O-structures can be effective in supporting a range of parallel workloads, including irregular, pointer-heavy code.

Task-based programming models aim to simplify parallel programming. A runtime system schedules tasks to execute on cores. An essential component of this runtime is to track and manage dependencies between tasks. A typical approach is to rely on programmers to annotate tasks and data structures, essentially manually specifying the input and output of each task. As such, dependencies are associated with named program objects, making this approach problematic for pointer-based data structures. Furthermore, because the runtime system must track these dependencies, for efficient runtime performance the read and write sets should be kept small. We presume a memory system with architecturally visible support for multiple versions of data stored at the same program address. This paper proposes and evaluates a task-based execution model that uses this versioned memory system to deterministically parallelize sequential code. We have built a task-based runtime layer that uses this type of memory system for dependence tracking. We demonstrate the advantages of the proposed model by parallelizing pointer-heavy code, obtaining speedup of up to 19x on a 32-core system.