Dwarf Mine

From View

Revision as of 22:17, 1 December 2006; view current revision
←Older revision | Newer revision→
Jump to: navigation, search


A dwarf is an algorithmic method that captures a pattern of computation and communication.

We were inspired by the work of Phil Colella, who identified seven numerical methods that he believed will be important for science and engineering for at least the next decade (Colella 2004:Media:DARPAHPCS.ppt). The Seven Dwarfs, constitute equivalence classes where membership in a class is defined by similarity in computation and data movement. The dwarfs are specified at a high level of abstraction to allow reasoning about their behavior across a broad range of applications. Programs that are members of a particular class can be implemented differently and the underlying numerical methods may change over time, but the claim is that the underlying patterns have persisted through generations of changes and will remain important into the future.

As we have examined more applications in search of basic patterns, we have expanded the list of dwarfs.

List of Dwarfs

  1. Dense Linear Algebra
  2. Sparse Linear Algebra
  3. Spectral Methods
  4. N-Body Methods
  5. Structured Grids
  6. Unstructured Grids
  7. MapReduce
  8. Combinational Logic
  9. Graph Traversal
  10. Dynamic Programming
  11. Backtrack and Branch-and-Bound
  12. Graphical Models
  13. Finite State Machines
Personal tools