Compiler Optimization of Value Communication for Thread-Level Speculation

Antonia Zhai

Friday, January 14, 2005
2:00pm - SENSQ 5317

Abstract

As technology advances, processors that support chip-level multithreading are becoming commonplace. Computer architecture and compiler designers are thus challenged to exploit their performance potential. Creating parallel programs is an attractive approach, however, automatic parallelization of general-purpose applications has always been difficult. Thread-level speculation (TLS) facilitates automatic parallelization by allowing the hardware to ensure correct execution at runtime. With TLS support, the compiler is able to optimistically create parallel threads that are potentially dependent. Our studies have shown that inter-thread value communication is the key to efficient parallel execution.

In this talk, I will describe several compiler optimizations that were designed, implemented and evaluated as part of my thesis to enhance the efficiency of value communication. Value communication can manifest as speculation and synchronization. To improve the accuracy of speculation, I designed compiler techniques that first identify frequently occurring inter-thread data dependences and then synchronize the dependent pairs. To reduce the cost of synchronization, I developed instruction scheduling algorithms to compute the synchronized values early. With these optimization techniques, I was able to improve the performance of parallel regions. My techniques can be applied to applications with arbitrary control-flow and data dependence patterns.

Biography of Speaker

Antonia Zhai is a Ph.D. candidate in the Department of Computer Science at Carnegie Mellon University. She received her B.A.Sc. and M.A.Sc. in Computer Engineering from the University of Toronto in 1996 and 1998 respectively. Currently, she is a member of the STAMPede project led by Todd Mowry. Her thesis research focuses on developing advanced compiler technology to exploit the potential of thread-level speculation for general-purpose applications. Her areas of interests include programming language, compiler optimization, computer architecture and pervasive computation/communication systems. She has now accepted a position as an assistant professor at the University of Minnesota.