NC State University

Department of Computer Science Colloquia 1999-2000

Date: Wednesday, May 31, 2000
Time: 3: 30 PM (talk)
Place: Withers 402A, NCSU Historical Campus (click for courtesy parking request)

Speaker: Ruth E. Anderson, Computer Science, University of Washington

Cascaded Execution: Speeding Up Unparallelized Execution on Shared-Memory Multiprocessors

Abstract: Parallelizing compilers are one approach to harnessing the power of parallel processors. These compilers are adept at finding legal parallel executions for many loop nests commonly found in numerically intensive applications. However, rarely are all portions of an application parallelized.

Both inherently sequential code and limitations of analysis techniques commonly leave unparallelized loop nests that must be executed sequentially. Amdahl's Law tells us that as parallelization becomes increasingly effective, any unparallelized loop becomes an increasingly dominant performance bottleneck.

She will present a technique for speeding up the execution of unparallelized loops by cascading their sequential execution across multiple processors: only a single processor executes the loop body at any one time, and each processor executes only a portion of the loop body before passing control to another. Cascaded execution allows otherwise idle processors to optimize their memory state for the eventual execution of their next portion of the loop, resulting in significantly reduced overall loop body execution times.

Short Bio: Ruth Anderson has a BS from UNC Chapel Hill in mathematics with a computer science concentration. She has an MS from the University of Washington, and has completed the course work for a PhD at Washington.

Host: Alan Tharp, Computer Science, NCSU

Colloquia Home Page.