Network Flow Modeling of Some Data-Locality
Enhancement Techniques
Abstract
The speed gap between microprocessors and the main memory continues to widen.
One of the most important methods to address this problem is to improve data locality of the programs such that the small and fast memory devices (such as registers and caches) can be efficiently utilized.For some numerical programs, data locality may be improved by rearranging the program execution order and the memory layout without changing computation results. We discuss two techniques to make such rearrangement, namely loop tiling for iterative relaxation codes and array contraction to reduce data size. We describe how we model these techniques as integer linear programs and then reduce them to network flow problems. We have implemented these techniques in a research prototyping compiler and show good results for a number of testing programs.
Bio of the Speaker
Zhiyuan Li is Associate Professor at the Department of Computer Science in Purdue University. He received an M.S. and a Ph.D., both in Computer Science, from University of Illinois, Urbana-Champaign, in 1985 and 1989 respectively.
Before he joined Purdue University in 1997, he worked as a senior software engineer at Center for Supercomputing Research and Development in University of Illinois, Urbana-Champaign, and as Assistant Professor at the Department of Computer Science, University of Minnesota, Minneapolis-St. Paul.
Li received a Research Initiation Award and an Early-Faculty Career Award from National Science Foundation (NSF) in 1992 and 1995 respectively. He has served on program committees of several computer conferences, including IEEE/ACM International Parallel and Distributed Processing symposium (IPDPS), ACM International Conference on Supercomputing (ICS), International Conference on Parallel Processing (ICPP) and SIGPLAN Symposium on Languages, Compilers, and Tools for Embedded Systems (LCTES). He has also co-edited special issues for journals such as IEEE Transactions on Parallel and Distributed Systems and International Journal on Parallel Programming.