Designing languages for parallel portability of physical simulations, using relational algebraic abstractions
Abstract/Contents
- Abstract
- The desire to ever more efficiently simulate physical phenomena using computers produces a demand for increased specialization of physical models, geometric & numeric algorithms, and computing hardware/systems. This demand limits itself by trending towards unmanagable complexity; manifesting as an inability to separate disciplinary specialties via distinct parts of the simulation code. For parallelism in particular, the interface along which this separation happens must necessarily take the form of a language, separating compiler-programmers from simulation-programmers. Furthermore, such languages must exploit a more abstract and restricted data model than random-access-memory in order to enable performant portability across different parallel systems. I propose using a relational (algebraic) abstraction of simulation data in order to give compiler programmers both sufficient freedom and information to successfully port applications onto parallel hardware, while maintaining high performance (time and memory). I investigate three aspects of this problem, organized by the metric-topology distinction from geometry, and explored by constructing language prototypes: (1) Ebb, a language for local stencil computations on metric data; (2) Seam, a language for local modification of topological data (i.e. remeshing); and (3) Gong, a language for generation of topology from metric locality (i.e. collision detection). These languages use a common relational abstraction of data, including coupling of structured and unstructured mesh domains in a single program. Seam additionally leverages the concepts of transactions and views from databases, while Gong leverages the concepts of joins and indices. Database queries are extended by treating actions on queries using parallelizable lock-free effects beyond simple reading and writing. Experimental evaluation of prototype language implementations (with support for GPUs) shows that the performance of highly-tuned implementations can be matched to within a 1.25x overhead at worst (for an Ebb implementation of a super-computing benchmark; 1.15x for a Gong implementation of an industrial collision detection system). However, the ability to systematically port code to different platforms easily allows 2-9x accelerations of many simulation programs over the next best cpu/multi-core implementations available. Ebb programs are usually less than half as long, while automatic view maintenance in Seam yields 10x reductions in complex pointer manipulation code size.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Bernstein, Gilbert Louis |
|---|---|
| Degree supervisor | Hanrahan, P. M. (Patrick Matthew) |
| Thesis advisor | Hanrahan, P. M. (Patrick Matthew) |
| Thesis advisor | Aiken, Alexander |
| Thesis advisor | James, Doug L |
| Degree committee member | Aiken, Alexander |
| Degree committee member | James, Doug L |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Gilbert Louis Bernstein. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Gilbert Louis Bernstein
- License
- This work is licensed under a Creative Commons Attribution Non Commercial Share Alike 3.0 Unported license (CC BY-NC-SA).
Also listed in
Loading usage metrics...