Mohammad Ali Ghodrat, Tony Givargis, and Alex Nicolau win Best Paper Award for CASES 2008

Mohammad Ali Ghodrat, Tony Givargis, and Alex Nicolau recently received the Best Paper Award for CASES 2008 for their “Control Flow Optimization in Loops Using Interval Analysis.” Congratulations!
Abstract of Paper: 
The work presents a novel loop transformation technique, particularly well suited for optimizing embedded compilers, where an increase in compilation time is acceptable in exchange for significant performance increase. The transformation technique optimizes loops containing nested conditional blocks. Specifically, the transformation takes advantage of the fact that the Boolean value of the conditional expression, determining the true/false paths, can be statically analyzed using a novel interval analysis technique that can evaluate conditional expressions in the general polynomial form. Results from interval analysis combined with loop dependency information is used to partition the iteration space of the nested loop. In such cases, the loop nest is decomposed such as to eliminate the conditional test, thus substantially reducing the execution time. Our technique completely eliminates the conditional from the loops (unlike previous techniques) thus further facilitating the application of other optimizations and improving the overall speedup. Applying the proposed transformation technique on loop kernels taken from Mediabench, SPEC- 2000, mpeg4, qsdpcm and gimp, on average we measured a 175% (1.75X) improvement of execution time when running on a SPARC processor, a 336% (4.36X) improvement of execution time when running on an Intel Core Duo processor and a 198.9% (2.98X) improvement of execution time when running on a PowerPC G5 processor. The CASES conference provides a forum for emerging technology in embedded computing systems, with an emphasis on compilers and architectures for embedded systems. CASES is a common forum for researchers with an interest in embedded systems to reach across vertically integrated communities and to promote synergies. As evident from the past CASES meetings, several emerging applications are critically dependent on these interactions for their sustained growth and evolution (from http:// thedude.cc.gt.atl.ga.us/conferences/cases/).