TUNE: System Support for Memory-Friendly Programming

			Siddhartha Chatterjee
	   The University of North Carolina at Chapel Hill

The pervasive use of multi-level memory hierarchies in
microprocessor-based machines makes the performance of an application
primarily determined by, and extremely sensitive to, its memory
hierarchy mapping.  Good performance therefore requires
"memory-friendly programming": careful layout of data structures, and
restructuring of code and/or data use patterns to improve locality.
The lack of automatic tools for enhancing locality currently forces
many application programmers to manually restructure their codes.
Unfortunately, the sophisticated algorithms seen in modern scientific
computing require equally sophisticated restructuring techniques,
beyond the loop tiling transformations that some research compilers
can perform automatically for dense iterative affine loop codes.  Such
restructuring techniques require expertise in computer architecture,
burden the application programmer with tedious machine-specific
details unrelated to program correctness, and reduce the readability,
maintainability, and portability of the restructured code.  The goal
of the TUNE project is to improve our understanding of locality for a
wide class of "hierarchical" problems and to develop a toolkit to aid
the programmer in developing memory-friendly programs for such
problems.  Our ultimate goal is to demonstrate that the TUNE toolkit
can be used to improve the performance of a naive implementation of an
application to a level comparable to that of an implementation with
extensive manual restructuring, but at a small fraction of effort on
the part of the programmer.

A comprehensive solution to the problem of improving locality in
hierarchical codes requires interactions among several sub-disciplines
of computer science: scientific computing, numerical analysis,
programming languages, compilers, performance modeling, and computer
architecture.  This project therefore targets all aspects of the
locality problem: developing the relevant mathematical techniques for
representing and manipulating locality; characterizations of the
relationship between program transformations and numerical accuracy;
implementing interactive and automatic locality management tools; and
proposing and evaluating innovative memory architectures for
future-generation systems.

The talk will discuss these various aspects of the TUNE project.



Siddhartha Chatterjee is an assistant professor of computer science at
the University of North Carolina at Chapel Hill.  He received his
B.Tech. (Honors) in electronics and electrical communications
engineering in 1985 from the Indian Institute of Technology,
Kharagpur, and his Ph.D. in computer science in 1991 from Carnegie
Mellon University.  He was a visiting scientist at the Research
Institute for Advanced Computer Science (RIACS) in Mountain View,
California, from 1991 through 1994, and worked at AT&T Bell
Laboratories, Murray Hill, in the summer of 1988.  He has written
several papers in the areas of compilers for parallel languages,
computer architecture, and parallel algorithms.  His research
interests include the design and implementation of programming
languages and systems for high-performance scientific computations,
locality management in hierarchical computations, and parallel
algorithms and applications.



Dr. Siddhartha Chatterjee, Asst. Professor  http://www.cs.unc.edu/~sc/
Department of Computer Science              sc@cs.unc.edu,schatterjee@acm.org
The University of North Carolina            s.chatterjee@computer.org
Chapel Hill, NC 27599-3175                  (919) 962-1766