2018/09/25 by Guy E. Blleloch, Yan Gu, Blleloch, Guy E. +1 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1809.09330
openalex publication_date 2018/09/25 · openalex created_date 2022/08/03 · openalex updated_date 2026/07/28
Emerging non-volatile main memory (NVRAM) technologies provide\nbyte-addressability, low idle power, and improved memory-density, and are\nlikely to be a key component in the future memory hierarchy. However, a\ncritical challenge in achieving high performance is in accounting for the\nasymmetry that NVRAM writes can be significantly more expensive than NVRAM\nreads.\n In this paper, we consider a large class of cache-oblivious algorithms for\ndynamic programming (DP) and linear algebra, and try to reduce the writes in\nthe asymmetric setting while maintaining high parallelism. To achieve that, our\nkey approach is to show the correspondence between these problems and an\nabstraction for their computation, which is referred to as the k-d grids.\nThen by showing lower bound and new algorithms for computing k-d grids, we\nshow a list of improved cache-oblivious algorithms of many DP recurrences and\nin linear algebra in the asymmetric setting, both sequentially and in parallel.\n Surprisingly, even without considering the read-write asymmetry (i.e.,\nsetting the write cost to be the same as the read cost in the algorithms), the\nnew algorithms improve the existing cache complexity of many problems. We\nbelieve the reason is that the extra level of abstraction of k-d grids helps\nus to better understand the complexity and difficulties of these problems. We\nbelieve that the novelty of our framework is of interests and leads to many new\nquestions for future work.\n