News Archives

[Colloquium] Tools for the Construction of Optimized Matrix Algebra Software

February 28, 2012

Watch Colloquium: 

M4V file (797 MB)

  • Date: Tuesday, February 28, 2012 
  • Time: 11:00 am — 12:15 pm 
  • Place: Mechanical Engineering 218

elizabeth-jessup

Elizabeth Jessup
University of Colorado Department of Computer Science

Linear algebra constitutes the most time-consuming part of simulations in many fields of science and engineering. Reducing the costs of those calculations can have a significant impact on overall routine performance, but such optimization is difficult. At each step of the process, the code developer is confronted with many possibilities. Choosing between them generally requires expertise in numerical computation, mathematical software, compilers, and computer architecture, yet few scientists have such broad expertise. This talk will cover two interrelated collaborative projects focused on easing the production of high-performance matrix algebra software.

I will first present work in progress on a taxonomy of software that can be used to build highly-optimized matrix algebra software. The taxonomy will provide an organized anthology of software components and programming tools needed for that task. It will serve as a guide to practitioners seeking to learn what is available for their programming tasks, how to use it, and how the various parts fit together. It will build upon and improve existing collections of numerical software, adding tools for the tuning of matrix algebra computations. Our objective is to build a taxonomy that will provide all of the software needed to take a matrix algebra problem from algorithm description to a high-performance implementation.

I will then introduce one of the tuning tools to be included in the taxonomy, the Build to Order (BTO) compiler which automates loop fusion in matrix algebra kernels. This optimization serves to reduce the amount of data moved between memory and the processor. In particular, I will describe BTO’s analytic memory model which accelerates the compiler by substantially reducing the number of loop fusion options processed by it. The initial draft of the model took into account traffic through the caches and TLB. I will discuss an example that motivated us to improve the accuracy of the model by adding register allocation.

 

Bio: Elizabeth Jessup’s research concerns the development of efficient algorithms and software for matrix algebra problems. This work began with the development of innovative memory-efficient algorithms and, more recently, has moved toward tools to aid in programming of matrix algebra software. Dr. Jessup has recently been collaborating with experts in compiler technology, focusing on compilers that create fast numerical software. Their initial focus has been on making efficient use of the memory hierarchy on a single processor but they are moving into multicore and GPU implementations. She is also interested in usability of scientific software. To that end, Dr. Jessup is working with collaborators on a tool to automate the construction of numerical software. Given a problem specification, the tool will find and tune appropriate routines for its solution.

Dr. Jessup was co-developer of an award-winning, NSF-funded undergraduate curriculum in high-performance scientific computing and have continued to work on innovative approaches to education in her field. She has also conducted research on factors that influence women’s interest in computer science.