2019/10/27 by Tim Kaler, William Kuszmaul, Kaler, Tim +5
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1910.12340
openalex publication_date 2019/10/27 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Software engineers designing recursive fork-join programs destined to run on\nmassively parallel computing systems must be cognizant of how their program's\nmemory requirements scale in a many-processor execution. Although tools exist\nfor measuring memory usage during one particular execution of a parallel\nprogram, such tools cannot bound the worst-case memory usage over all possible\nparallel executions.\n This paper introduces Cilkmem, a tool that analyzes the execution of a\ndeterministic Cilk program to determine its p-processor memory high-water\nmark (MHWM), which is the worst-case memory usage of the program over \all\npossible p-processor executions. Cilkmem employs two new algorithms for\ncomputing the p-processor MHWM. The first algorithm calculates the exact\np-processor MHWM in O(T1 \⋅ p) time, where T1 is the total work of\nthe program. The second algorithm solves, in O(T1) time, the approximate\nthreshold problem, which asks, for a given memory threshold M, whether the\np-processor MHWM exceeds M/2 or whether it is guaranteed to be less than\nM. Both algorithms are memory efficient, requiring O(p \⋅ D) and O(D)\nspace, respectively, where D is the maximum call-stack depth of the program's\nexecution on a single thread.\n Our empirical studies show that Cilkmem generally exhibits low overheads.\nAcross ten application benchmarks from the Cilkbench suite, the exact algorithm\nincurs a geometric-mean multiplicative overhead of 1.54 for p=128, whereas\nthe approximation-threshold algorithm incurs an overhead of 1.36 independent\nof p. In addition, we use Cilkmem to reveal and diagnose a previously unknown\nissue in a large image-alignment program contributing to unexpectedly high\nmemory usage under parallel executions.\n