2019/08/15 by Matthew Gray, Gray, Matthew
Computer Science · #Advanced Data Storage Technologies #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1908.05415
Algorithms, data structures, coding techniques, and other methods that reduce\nbit-flips are being sought to best utilize hardware where flipping bits is the\ndominating cost. Write efficient memories were introduced by Ahlswede and Zhang\nas a model for storage systems with these kinds of arbitrary read, write, and\nupdate costs. The introduction of non-volatile Random Access Memories like\nphase-change RAM, which have asymmetric read-write costs has re-motivated the\nfield. Our work focuses on potential bit-flip efficiencies to be gained at the\ndata structure layer. We examine Local Order Agnostic Data Structures (LOADS),\ndata structures in which local order does not convey information and in which\ncells are modified individually. We found that because these data structures\nhave a limited set of valid values and transitions, that bit flipping wins\nshould be possible without the use of additional hardware.\n