Cache-oblivious algorithm

Formal sciences
Theoretical computer science
Algorithms and data structures
Analysis of algorithms

About
Privacy
Disclaimer

Graph Chatbot

Related publications (31)

Successive Refinement to Caching for Dynamic Content

Michael Christoph Gastpar, Pinar Sen

To reduce the network load during peak hours, servers deliver partial data to users during the off-peak time of the network before the actual requests are known, which is known as caching. This paper studies a single user caching problem in which the file ...

IEEE2019

Relaxed Wyner's Common Information

Michael Christoph Gastpar, Erixhen Sula

In the problem of coded caching for media delivery, two separate coding opportunities have been identified. The first opportunity is a multi-user advantage and crucially hinges on a public broadcast link in the delivery phase. This has been explored in a p ...

IEEE2019

Stop Crying Over Your Cache Miss Rate: Handling Efficiently Thousands of Outstanding Misses in FPGAs

Paolo Ienne, Mikhail Asiatici

FPGAs rely on massive datapath parallelism to accelerate applications even with a low clock frequency. However, applications such as sparse linear algebra and graph analytics have their throughput limited by irregular accesses to external memory for which ...

ASSOC COMPUTING MACHINERY2019

Gem5-X: A Gem5-Based System Level Simulation Framework to Optimize Many-Core Platforms

David Atienza Alonso, Marina Zapater Sancho, William Andrew Simon, Yasir Mahmood Qureshi

The rapid expansion of online-based services requires novel energy and performance efficient architectures to meet power and latency constraints. Fast architectural exploration has become a key enabler in the proposal of architectural innovation. In this p ...

IEEE2019

Bridging the Latency Gap between NVM and DRAM for Latency-bound Operations

Anastasia Ailamaki, Georgios Psaropoulos

Non-Volatile Memory (NVM) technologies exhibit 4× the read access latency of conventional DRAM. When the working set does not fit in the processor cache, this latency gap between DRAM and NVM leads to more than 2× runtime increase for queries dominated by ...

ACM2019

Improving Main-memory Database System Performance through Cooperative Multitasking

Georgios Psaropoulos

Database systems access memory either sequentially or randomly. Contrary to sequential access and despite the extensive efforts of computer architects, compiler writers, and system builders, random access to data larger than the processor cache has been s ...

EPFL2019

Interleaving with coroutines: a systematic and practical approach to hide memory latency in index joins

Anastasia Ailamaki, Georgios Psaropoulos

Index joins present a case of pointer-chasing code that causes data cache misses. In principle, we can hide these cache misses by overlapping them with computation: The lookups involved in an index join are parallel tasks whose execution can be interleaved ...

2019

Adaptive Cache Mode Selection for Queries over Raw Data

Anastasia Ailamaki, Tahir Azim, Azqa Nadeem

Caching the results of intermediate query results for future re-use is a common technique for improving the performance of analytics over raw data sources. An important design choice in this regard is whether to lazily cache only the offsets of satisfying ...

2018

Closing the Performance Gap Between Volatile and Persistent Key-Value Stores Using Cross-Referencing Logs

Matej Pavlovic

Key-Value (K-V) stores are an integral building block in modern datacenter applications. With byteaddressable persistent memory (PM) technologies, such as Intel/Micron's 3D XPoint, on the horizon, there has been an influx of new high performance K-V stores ...

USENIX ASSOC2018

Exploiting Compute Caches for Memory Bound Vector Operations

Paolo Ienne, Gabriel Falcao Paiva Fernandes, João Miguel Morgado Pereira Vieira

To reduce the average memory access time, most current processors make use of a multilevel cache subsystem. However, despite the proven benefits of such cache structures in the resulting throughput, conventional operations such as copy, simple maps and red ...

IEEE2018

ESTIMA: Extrapolating ScalabiliTy of In-Memory Applications

Rachid Guerraoui, Aleksandar Dragojevic, Georgios Chatzopoulos

This article presents ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. ESTIMA is designed to perform a simple yet important task: Given the performance of an application on a small machine with a handful of cores, ES ...

2017

Page 2 of 2