Interface levels

I like to think of the interface in terms of "levels." The lower the level (i.e. the smaller the number), the closer it is to the raw computational routines. In some sense the organization into levels can be thought of as a compiler design: Level 3 compiles into Level 2, Level 2 into Level 1, and so on. Furthermore, as illustrated by libraries such as GASNet, a multi-layer architecture can lend itself to faster implementations, by exploiting specific hardware features as they lend themselves to implementing higher-level functions. Below, I describe some ideas for the levels in our design.

Level 0

• Numerical libraries in C / Fortran, such as the BLAS or LAPACK
• Alternately: for small fixed-size vectors and matrices, a native Lisp implementation with calls to compiler intrinsics (e.g. for SSE2 instructions).

Level 1: low-level wrappers

• Use CFFI (for portability)
• Can and should be autogenerated (and have been) from headers or Fortran source
• LAPACK developers have their own scripts and templates that might be useful

Level 2: medium-level "linear algebra library"

• Vectors and vector windows, matrices and matrix windows
• I/O
• Intelligent wrappers of the low-level wrappers
• Know when to copy data for more efficient operation in LAPACK vs. when to leave it in place
• Expose and make explicit expensive tuning operations (like determining matrix structure)
• Exploit LAPACK semantics: e.g. implicit representation of outputs such as Q factors from a QR factorization
• Take advantage of automatic code generation, e.g. for different datatypes (single-float, double-float, complex)
• Take advantage of series functions, etc. to simplify and make more efficient common iteration patterns over a whole matrix
• Matlisp and others do some of our ideas of Level 2

Level 3: Matlab clone?

• "Looks like math"
• Operators like +, *, /, \
• Can take many different forms
  • Matlab clone
  • Lisp syntax (embedded language approach)
  • Some other syntax
• Parser / macro system / compiler transforms high-level code into medium-level code, optimizing it along the way (e.g. avoiding copies and using in-place operations whenever possible)
• Intelligent compiler may do its own auto-tuning, taking advantage of the tuning facilities provided by Level 2
• This is ground covered somewhat by Matlab, R, Octave, Scilab, etc., though few of them provide a full optimizing compiler that can support a variety of syntaxes.

Level 2 interface in detail

Level 2 is a kind of "assembly language for linear algebra."

• Matrices (objects) and matrix views (references to objects)
• Matrix (view) indexing
• MREF (indexing overhead paid per access)
• SCAN-MATVIEW, etc. (indexing overhead amortized over whole matrix)
• BLAS and LAPACK functionality, with similar semantics as the original functions
• Functions produce "tagged" matrices to indicate storage method, e.g. "collection of Householder reflectors", "packed symmetric storage", etc.
• Any tuning operations (e.g. runtime checks for structure) are exposed and explicit only

Notes

1. CFFI home page.
2. GASNet home page. Check out the "system diagram showing GASNet layers" on the front page.