An abstract machine for partial differential equations
Luigi Semenzato · 1994
This dissertation is about high-level programming abstractions for modern partial differential equation solvers, primarily those based on finite difference methods and particle methods. The main abstractions are an algebra of index sets, also called domains, and an extension of the array type, the map type. Like arrays, maps are functions from index tuples to elements, but without the traditional restriction that the domain be rectangular. Expressing PDE algorithms in terms of these abstractions is more natural than with conventional arrays and control structures, and results in programs that are easier to write, verify, and optimize. The programming language Infidel offers these abstractions. The main focus of this work is on the design of Infidel, and its translator and run-time system for vector processors. The run-time system deals with most of the complexity of maps and domains. It uses several kinds of descriptors to represent them, with each kind optimized for a specific situation. The choice of kind, and the adaptive conversion between kinds, is mostly transparent. Because the Infidel programming style results in the frequent recomputation of descriptors, they are all memorized to improve performance. The work also reports on the experience of programming some PDE algorithms in Infidel, particularly an adaptive mesh refinement method, and proposes additional useful abstractions. It finally observes that the measured performance of Infidel programs is comparable to that of programs written in conventional languages, and it can even be better.