Opie Research Group


Department of Computer Science
Indiana Univeristy

Home

 Opie - Optimus Prime
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.

Introduction
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.

Compiling
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.

"Opie"
 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:
Papers:
  1. Steven T. Gabriel. and David S. Wise. The Opie Compiler: from Row-major Source to Morton-ordered Matrices. Proc. 3rd Workshop on Memory Performance Issues (WMPI-2004), 38, (2004 June), accepted. Authors' version .
  2. Jeremy D. Frens and David S. Wise. QR factorization with Morton-ordered quadtree matrices for memory re-use and parallelism. Proc. 2003 ACM Symp. on Principles and Practice of Parallel Programming, SIGPLAN Not. 38, 10 (2003 Odtober), 144--154. Authors' version.
  3. David S. Wise, Jeremy D. Frens, Yuhong Gu, and Gregory A. Alexander. Language support for Morton-order matrices. Proc. 2001 ACM Symp. on Principles and Practice of Parallel Programming, SIGPLAN Not. 36, 7 (2001 July), 24--33. Authors' version.
  4. David S. Wise. Ahnentafel indexing into Morton-ordered arrays, or matrix locality for free. In A. Bode, T. Ludwig, R. Wismu"ller (eds.), Euro-Par 2000 -- Parallel Processing, Lecture Notes in Computer Science 1900, Berlin: Springer (2000 August), 774-784.
  5. David S. Wise and Jeremy D. Frens. Morton-order matrices deserve compilers' support. Technical Report 533. Computer Science Department, Indiana University (1999 November).
  6. David S. Wise. Undulant block elimination and integer-preserving matrix inversion. Sci. Comput. Program 33, 1 (1999 January), 29--85. Math Review 1 653 749. Abstract only: SIGSAM Bull. 29 (1995 June), 28. Author's version.
  7. Jeremy D. Frens and David S. Wise. Auto-blocking matrix-multiplication, or Tracking BLAS3 performance from source code. Proc. 1997 ACM Symp. on Principles and Practice of Parallel Programming, SIGPLAN Not. 32, 7 (1997 July), 206--216. Authors' version.
Distribution:under construction

Related Work:
  1. E. Elmroth and F. Gustavson. Applying recursion to serial and parallel QR factorization leads to better performance. IBM J. Res. Develop., 44(4):605-624, July 2000.
  2. S. Chaterjee, A. R. Lebeck, P. K. Patnala, and M. Thottenthodi. Recursive array layouts and fast parallel matrix multiplication. IEEE Trans. Parallel Distrib. Syst., 13(11):1105-1123, Nov. 2002.
Michael A Rainey
Last modified:    2003Aug12 Tues