Opie Research Group
Department of Computer Science
|Introduction | Compiling | Papers | People | Distribution|
Welcome to the Opie Research Group's webpage!
You can find us in Lindley Hall 328 on the Bloomington campus.
Thanks to the National Science Foundation for supporting this research under a grant entitled "Compiler Support for Morton-Order Matrices," numbered CCR-0073491.
The goal of the Opie Project is to compile conventional programs in imperative languages like C, C++, Fortran, or Java operating on matrices into equivalent programs. So an Opie compiler merely transforms one program into another.
The difference is how matrices (arrays) are represented.
Traditional internal representation of matrices is in row-major (or, in Fortran, column-major) order. That is, a row (or column) occupies locations that are sequential in memory. Such locality is critical to cache performance. An important alternative is to represent matrices internally in Morton order, illustrated here for a 16x16 matrix, which stores blocks---nested recursively---in sequential memory. An Opie compiler, first, transforms archival code from row-major (analogously, column-major) onto Morton order.
Knowledge of the internal representation affects the programmer's choice of algorithm. An author who seeks fast code has a natural tendancy to honor the hardware in making that choice. Today a big contraint is hierarchical memory of more and more levels: L1, L2, and L3 cache, TLBs, RAM, and paging to disk. Opie does not change the programmer's algorithm! As a corollary, it might even slow a row-traversing program.
But Morton order admits other algorithms, via a different paradigm of programming being developed under the sister Arcee Project. Supported by Morton order internally, that family of algorithms is very fast. But as the new kid on the block, it lacks the infrastructure (libraries) from forty years of row/column-major algorithms. The goal of the Opie compilers is to transform that infrastructure (essentially) intact.
The second goal of an Opie compiler is to provide convenient syntactic support for indexing schemes that support the quadtree decomposition of matrices on which the Arcee project depends. Classes like Ahnentafel indices and dilated integers augment the usual ints used as cartesian, Morton, and level-order indices into binary-tree representations of vectors, quadtree representations of matrices,
and---generally--- 2d-ary trees representing d-dimensional arrays.
This support will be especially useful to carry the Arcee paradigm into languages like ML, Scheme, and Haskell.
The most accessible characterization of the philosophy is a picture:
Morton-ordered matrices instrinsically provide excellent locality of reference. In addition, we advocate divide-and-conquer algorithms on these matrices. Thus it is possible to formulate elegant recursive algorithms that, by default, account for performance in the memory hierarchy, and are easy to parallelize.
So you're probably asking yourself, "What's an opie?" Recall that we perceive the compiler performing a transformation from certain styles of code onto another.
That makes it a Transformer ... and of course, we all know that the best Transformer® is Optimus Prime. So Optimus Prime---O.P.---is shortened to Opie, and the name stuck. And, just because, we have the above picture of everyone's favorite Autobot in all his glory. (This is from the movie ... right now, he's about to charge into the Decepticon-controlled Autobot City to save the Autobots trapped inside. He's saying "Megatron must be stopped ... no matter the cost.")
The link between Megatron and Fortran is left to the reader.
Contributors to the Opie Project:
|Michael A Rainey Last modified: 2003Aug12 Tues|