2025/04/07 by Christos P. Lamprakos, Christos Lamprakos, Lamprakos, Christos +10 · 2 voices
Computer Science · #Advanced Data Storage Technologies #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Operating Systems (cs.OS) #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #Real-Time Systems Scheduling #cs.AI #cs.OS #cs.PL
paper · pdf · doi:10.48550/arxiv.2504.04874
openalex publication_date 2025/04/07 · arxiv published 2025/04/07 · arxiv updated 2025/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The NP-complete combinatorial optimization task of assigning offsets to a set of buffers with known sizes and lifetimes so as to minimize total memory usage is called dynamic storage allocation (DSA). Existing DSA implementations bypass the theoretical state-of-the-art algorithms in favor of either fast but wasteful heuristics, or memory-efficient approaches that do not scale beyond one thousand buffers. The "AI memory wall", combined with deep neural networks' static architecture, has reignited interest in DSA. We present idealloc, a low-fragmentation, high-performance DSA implementation designed for million-buffer instances. Evaluated on a novel suite of particularly hard benchmarks from several domains, idealloc ranks first against four production implementations in terms of a joint effectiveness/robustness criterion.