Elamur Research⌕
☰
home / papers / 2013 / Data-Driven Equivalence Checking

Data-Driven Equivalence Checking

Paper · 2013 · Rahul Sharma, Eric Schkufza, Berkeley Churchill et al.

Summary

Mismatch: the title given is Sharma et al.'s "Data-Driven Equivalence Checking", but the supplied text is a different OOPSLA 2013 paper on Legion by Treichler, Bauer and Aiken. This summary covers the supplied text.

Distributed-memory and GPU machines require data to be split to fit deep memory hierarchies. Earlier systems such as Sequoia and DPJ fix one alias-free partitioning at compile time, which fails when the right split depends on the data. Legion makes logical regions first-class values that can be divided at runtime into subregions, in several ways and possibly overlapping. Tasks declare per-region privileges and coherence modes. The authors formalize Core Legion with a type system and a compositional, asynchronous parallel semantics, and they prove it sound. They also show that if two tasks do not interfere, their subtasks do not either, which justifies a hierarchical, distributed scheduler. Experiments on three real applications confirm that checking pointers statically pays off, while region-level alias checks at runtime are cheap. Dynamic, aliased partitioning is therefore compatible with safety and scalability.

Key points

  • Privileges are read-only, read-write and reduce. Coherence modes are exclusive (the default), atomic and simultaneous.
  • Static type checking removes provably safe memory checks, improving performance by up to 71%. Dynamic aliasing checks at region granularity add negligible overhead.
  • The Circuit simulation reaches a 62.5X speedup on 96 GPUs of the Keeneland supercomputer, compared with a hand-coded single-GPU version.
  • Replacing atomic with exclusive coherence in the Circuit charge-distribution task slows execution by 34% on 48 GPUs and 67% on 96 GPUs, and the penalty grows with node count.
  • Compared with Sequoia, DPJ, Chapel, X10, Jade and HPT, Legion uniquely allows multiple dynamic partitions of the same data and per-region coherence.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States567 works · 335,189 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputational Theory and Mathematics · 496 worksSoftware · 150 works

Cite

Cite as Rahul Sharma, Eric Schkufza, Berkeley Churchill and Alex Aiken. 2013. Data-Driven Equivalence Checking. OOPSLA 2013.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{sharma2013data,
  title = {{Data-Driven Equivalence Checking}},
  author = {Rahul Sharma, Eric Schkufza, Berkeley Churchill and Alex Aiken},
  booktitle = {OOPSLA 2013},
  year = {2013},
  doi = {10.1145/2509136.2509509},
  url = {https://doi.org/10.1145/2509136.2509509}
}

References

22 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. M. Bauer, J. Clark, E. Schkufza, and A. Aiken. Programming the memory hierarchy revisited: Supporting irregular parallelism in Sequoia. In Proceedings of the Symposium on Principles and Practice of Parallel Programming, 2011. find
  2. M. Bauer, S. Treichler, E. Slaughter, and A. Aiken. Legion: Expressing locality and independence with logical regions. In Supercomputing (SC), 2012. find
  3. C. Bienia. Benchmarking Modern Multiprocessors. PhD thesis, Princeton University, January 2011. find
  4. R. Bocchino et al. A type and effect system for deterministic parallel Java. In OOPSLA, 2009. find
  5. R. Bocchino et al. Safe nondeterminism in a deterministic-by-default parallel language. In POPL, 2011. find
  6. C. Boyapati, B. Liskov, and L. Shrira. Ownership types for object encapsulation. In POPL, 2003. find
  7. B.L. Chamberlain et al. Parallel programmability and the chapel language. Int’l Journal of HPC Applications, 2007. find
  8. P. Charles et al. X10: An object-oriented approach to non-uniform cluster computing. In OOPSLA, 2005. find
  9. D. Clarke and S. Drossopoulou. Ownership, encapsulation and the disjointness of type and effect. In OOPSLA, 2002. find
  10. K. Fatahalian et al. Sequoia: Programming the Memory Hierarchy. In Supercomputing, November 2006. find
  11. D. Gay and A. Aiken. Language support for regions. In PLDI, 2001. find
  12. D. Grossman et al. Region-based memory management in cyclone. In PLDI, 2002. find
  13. T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPOPP, 2005. find
  14. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 1998. find
  15. M. Lijewski, A. Nonaka, and J. Bell. Boxlib. https://ccse.lbl.gov/BoxLib/index.html, 2011. ↗
  16. J. C. Reynolds. Separation logic: A logic for shared mutable data structures. In IEEE Symposium on Logic in CS, 2002. find
  17. M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. ACM Trans. Program. Lang. Syst., 1998. find
  18. M. Tofte and J.P. Talpin. Region-based memory management. In POPL, 1994. find
  19. S. Treichler, M. Bauer, and A. Aiken. Language support for dynamic, hierarchical data partitioning: Extended version. http://theory.stanford.edu/~aiken/publications/papers/oopsla13a-extended.pdf, 2013. Technical Report. ↗
  20. J.S. Vetter et al. Keeneland: Bringing heterogeneous gpu computing to the computational science community. Computing in Science Engineering, pages 90 –95, 2011. find
  21. Y. Yan, J. Zhao, Y. Guo, and V. Sarkar. Hierarchical place trees: A portable abstraction for task parallelism and data movement. In Workshop on Languages and Compilers for Parallel Computing, 2009. find
  22. K. Yelick et al. Titanium: A high-performance Java dialect. In Workshop on Java for High-Performance Network Computing, 1998. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sharma-2013-data-driven-equivalence-checking/