Candidate talk: On the Evaluation and Extraction of Thread-Level Parallelism in Ordinary Programs

November 19, 2007
Arun Kejariwal | University of California, Irvine

Multi-core systems such as IBM’s Cell, Intel’s Core 2 Duo and AMD’s Barcelona are becoming ubiquitous. Efficient exploitation of the hardware parallelism available on such systems is tightly coupled to the degree of program parallelization (or multithreading). Although there has been a large amount of work done in the context of multithreading, the lack of a rigorous performance evaluation methodology and detailed application characterization make it difficult to assess the performance gain achievable using the existing techniques.

As a first step, we present a rigorous performance evaluation methodology to establish a solid baseline of the performance gain achievable via program parallelization at the loop-level. Specifically, we determine the coverage, defined as the percentage of the total execution time, of loops in ordinary programs as represented by the industry-standard SPEC CPU
2000/6 (both integer and floating point) and EEMBC benchmarks.
Subsequently, we dissect the loop coverage into two categories: inherently parallel (DOALL) and potentially parallel (non-DOALL) loops. The coverage of each category establishes an upper bound on the performance gain achievable for each category by any technique. Next, we proposed novel techniques for thread synchronization and load balancing for non-DOALL and DOALL loops respectively. We evaluated the techniques using the applications from the SPEC CPU and OMPM benchmark suites and achieved better performance, on real machines, than the state-of-the-art.

Speaker Details

Arun Kejariwal is a doctoral student at the Center for Embedded Computer Systems, University of California, Irvine (UCI). He received a B. Tech. (EE) from Indian Institute of Technology (IIT), New Delhi, India in 2002, a M.S. (CS) from UCI in 2003 and is expecting to graduate in Dec’07. His interests are parallelizing and optimizing compilers, multi-core systems, performance evaluation and program analysis.