Language support for dynamic, hierarchical data partitioning

Applications written for distributed-memory parallel archi-tectures must partition their data to enable parallel execu-tion. As memory hierarchies become deeper, it is increas-ingly necessary that the data partitioning also be hierarchical to match. Current language proposals perform this hierarchi-cal partitioning statically, which excludes many important applications where the appropriate partitioning is itself data dependent and so must be computed dynamically. We de-scribe Legion, a region-based programming system, where each region may be partitioned into subregions. Partitions are computed dynamically and are fully programmable. The division of data need not be disjoint and subregions of a re-gion may overlap, or alias one another. Computations use regions with certain privileges (e.g., expressing that a com-putation uses a region read-only) and data coherence (e.g., expressing that the computation need only be atomic with respect to other operations on the region), which can be con-trolled on a per-region (or subregion) basis. We present the novel aspects of the Legion design, in par-ticular the combination of static and dynamic checks used to enforce soundness. We give an extended example illustrating how Legion can express computations with dynamically de-termined relationships between computations and data parti-tions. We prove the soundness of Legion’s type system, and show Legion type checking improves performance by up to 71 % by eliding provably safe memory checks. In particu-lar, we show that the dynamic checks to detect aliasing at runtime at the region granularity have negligible overhead. We report results for three real-world applications running on distributed memory machines, achieving up to 62.5X speedup on 96 GPUs on the Keeneland supercomputer. 1