Opie Research GroupDepartment of Computer Science Indiana Univeristy Home 

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 MortonOrder Matrices," numbered CCR0073491. 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 rowmajor (or, in Fortran, columnmajor) 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 blocksnested recursivelyin sequential memory. An Opie compiler, first, transforms archival code from rowmajor (analogously, columnmajor) 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 rowtraversing 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/columnmajor 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 levelorder indices into binarytree representations of vectors, quadtree representations of matrices, andgenerally 2^{d}ary trees representing ddimensional 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: Mortonordered matrices instrinsically provide excellent locality of reference. In addition, we advocate divideandconquer 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 PrimeO.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 Decepticoncontrolled 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:
Related Work:


Michael A Rainey Last modified: 2003Aug12 Tues 