Home
Home
  Research
    Datatypes
    Immutator
  Old Projects
  Calendar
  CV

 Publications
Fredrik Kjolstad, Shoaib Kamil, Jonathan Ragan-Kelley, David I.W. Levin, Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar, Wojciech Matusik, and Saman Amarasinghe
 
Simit: A Language for Physical Simulation

ACM, Transactions on Graphics 2016 (to be presented at SIGGRAPH 2016)

Abstract

With existing programming tools, writing high-performance simulation code is labor intensive and requires sacrificing readability and portability. The alternative is to prototype simulations in a high-level language like Matlab, thereby sacrificing performance. The Matlab programming model naturally describes the behavior of an entire physical system using the language of linear algebra. However, simulations also manipulate individual geometric elements, which are best represented using linked data structures like meshes. Translating between the linked data structures and linear algebra comes at significant cost, both to the programmer and to the machine. High-performance implementations avoid the cost by rephrasing the computation in terms of linked or index data structures, leaving the code complicated and monolithic, often increasing its size by an order of magnitude.

In this article, we present Simit, a new language for physical simulations that lets the programmer view the system both as a linked data structure in the form of a hypergraph and as a set of global vectors, matrices, and tensors depending on what is convenient at any given time. Simit provides a novel assembly construct that makes it conceptually easy and computationally efficient to move between the two abstractions. Using the information provided by the assembly construct, the compiler generates efficient in-place computation on the graph. We demonstrate that Simit is easy to use: a Simit program is typically shorter than a Matlab program; that it is high performance: a Simit program running sequentially on a CPU performs comparably to hand-optimized simulations; and that it is portable: Simit programs can be compiled for GPUs with no change to the program, delivering 4 to 20x speedups over our optimized CPU code.



Documents

download article:

BibTeX

@article{Kjolstad:2016,
  author = {Kjolstad, Fredrik and Kamil, Shoaib and Ragan-Kelley, Jonathan and Levin, David I. W. and Sueda, Shinjiro and Chen, Desai and Vouga, Etienne and Kaufman, Danny M. and Kanwar, Gurtej and Matusik, Wojciech and Amarasinghe, Saman},
  title = {Simit: A Language for Physical Simulation},
  journal = {ACM Trans. Graph. Presented at SIGGRAPH 2016},
  issue_date = {March 2016},
  volume = {35},
  number = {2},
  month = mar,
  year = {2016},
  issn = {0730-0301},
  pages = {20:1--20:21},
  articleno = {20},
  numpages = {21},
  url = {http://doi.acm.org/10.1145/2866569},
  doi = {10.1145/2866569},
  acmid = {2866569},
  publisher = {ACM},
  address = {New York, NY, USA},
  keywords = {Graph, matrix, simulation, tensor},
}